По теории языков программирования и методов трансляции Разработка компилятора модельного языка

program

var integer a,b;

begin

read(a,b);

if a>b then

write (a)

else write (b)

end.

Выходные данные ЛА: { (1,1) (1,2) (1,20),(4.1),(2,18),(4.2)  (2,12) (1,3) (1,12) (2,14) (4,1) (2,18) (4,2) (2,15) (2,12) (1,14) (4,1) (2,7) (4,2) (1,15) (1,13) (2,14) (4,1) (2,15) (1,16) (1,13) (2,14) (4,2) (2,15)(1,4),(2,19)  }

     Анализ  текста проводится путем разбора  по регулярным грамматикам и опирается  на способ разбора по диаграмме состояний, снабженной дополнительными пометками-действиями. Смысл этой конструкции: если текущим является состояние А и очередной входной символ совпадает с для какого либо i, то осуществляется переход в новое состояние В, при этом выполняются действия D₁, D₂, …, D_m.

     Для удобства разбора вводится дополнительное состояние диаграммы ER, попадание в которое соответствует появлению ошибки в алгоритме разбора.

     Переход по дуге, не помеченной ни одним символом, осуществляется по любому другому символу, кроме тех, которыми помечены все  другие дуги, выходящие из данного состояния.

     Алгоритм. Разбор цепочек символов по ДС с действиями

     Шаг 1. Объявляем текущим начальное  состояние  в диаграмме состояний H.

     Шаг 2. До тех пор, пока не будет достигнуто состояние ER или конечное состояние диаграммы состояний, считываем очередной символ анализируемой строки и переходим из текущего состояния диаграммы состояний в другое по дуге, помеченной этим символом, выполняя при этом соответствующие действия. Состояние, в которое попадаем, становится текущим.

     Составим  ЛА для модельного языка М. Предварительно введем следующие обозначения для переменных, процедур и функций.

     Переменные:

     1) СН – очередной входной символ;

2. CS – текущее состояние буфера накопления лексем с возможными значениями: Н – начало, I – идентификатор, N – число, С – комментарий, M – конец программы («}»), N2 – запись двоичного числа, N8 – запись восьмеричного числа, N16 – запись шестнадцатеричного числа, N10 – запись десятичного числа, ER –ошибка;
3. t - таблица лексем анализируемой программы с возможными значениями: TW – таблица служебных слов М-языка, TL – таблица ограничителей М-языка,

TI – таблица идентификаторов программы, TC – таблица чисел;

     4) z - номер лексемы в таблице t (если лексемы в таблице нет, то z=0).

     Процедуры и функции:

     1) gc – процедура считывания очередного символа текста в переменную СН;

     2) let – логическая функция, проверяющая, является ли переменная СН буквой;

     3) digit - логическая функция, проверяющая, является ли переменная СН цифрой;

     4) nill – процедура очистки буфера S;

     5) add – процедура добавления очередного символа в конец буфера S;

     6) look(n,k) – процедура поиска лексемы из буфера S в таблице с номером n с возвращением номера лексемы в таблице, k – количество элементов в таблице;

     7) put(t) – процедура записи лексемы из буфера S в таблицу t, если там не было этой лексемы, иначе возвращает номер данной лексемы в таблице;

      8) out(n, k) – процедура записи пары чисел (n, k) в файл лексем;

        Диаграмма состояний с действиями  для модельного языка

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Рисунок 1 – Диаграмма состояний с действиями для модельного языка М 

  
3.2 Синтаксический анализатор

      Задача  синтаксического анализатора (СиА) - провести разбор текста программы, сопоставив его с эталоном, данным в описании языка. Для синтаксического разбора используются контекстно-свободные грамматики.

   Один  из эффективных методов синтаксического  анализа – метод рекурсивного спуска. В основе метода рекурсивного спуска лежит левосторонний разбор строки языка. Исходной сентенциальной формой является начальный символ грамматики, а целевой – заданная строка языка. На каждом шаге разбора правило грамматики применяется к самому левому нетерминалу сентенции. Данный процесс соответствует построению дерева разбора цепочки сверху вниз, следующим образом. Для каждого нетерминального символа грамматики создается своя процедура, носящая его имя. Задача этой процедуры – начиная с указанного места исходной цепочки, найти подцепочку, которая выводится из этого нетерминала. Если такую подцепочку считать не удается, то процедура завершает свою работу вызовом процедуры обработки ошибок, которая выдает сообщение о том, что цепочка не принадлежит языку грамматики и останавливает разбор. Если подцепочку удалось найти, то работа процедуры считается нормально завершенной и осуществляется возврат в точку вызова. Тело каждой такой процедуры составляется непосредственно по правилам вывода соответствующего нетерминала, при этом терминалы распознаются самой процедурой, а нетерминалам соответствуют вызовы процедур, носящих их имена.

   Входные данные – файл лексем в числовом представлении.

   Выходные  данные – заключение о синтаксической правильности программы или сообщение об имеющихся ошибках. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Цепочка вывода и дерево разбора

Рассмотрим пример следующей программы:

program var int a,b; begin for a ass 1 to 3 do b ass b+1; end

Дерево  разбора

        

      

        
 
 

      

      

      

      

      

      

      

      

      

      

        

      

      

      

      

      

        

      

      

      

        

      

        

        
 
 
 

 

     3.3 Семантический анализатор  программы

      В ходе семантического анализа проверяются  отдельные правила записи исходных программ, которые не описываются КС-грамматикой. Эти правила носят контекстно-зависимый характер, их называют семантическими соглашениями или контекстными условиями.

      Рассмотрим  пример построения семантического анализатора (СеА) для программы на модельном языке М. Соблюдение контекстных условий для языка М предполагает три типа проверок:

1) обработка  описаний;  2) анализ выражений; 

3) проверка правильности операторов.

      В оптимизированном варианте СиА и  СеА совмещены и осуществляются параллельно. Поэтому процедуры СеА будем внедрять в ранее разработанные процедуры СиА.

      Обработка описаний. Задача обработки описаний – проверить, все ли переменные программы описаны правильно и только один раз. Решается расширением таблицы идентификаторов.

     Задача анализа выражений – проверить описаны ли переменные, встречающиеся в выражениях, и соответствуют ли типы операндов друг другу и типу операции. Эти задачи решаются следующим образом. Вводится таблица двуместных операций (таблица 2) и стек, в который в соответствии с разбором выражения B заносятся типы операндов и знак операции. После семантической проверки в стеке оставляется только тип результата операции. В результате разбора всего выражения в стеке остается тип этого выражения.

      Пример. Дано выражение b-4+8. Дерево разбора выражения:

        
 

 

real

-

integer

+

integer

    

real

+

integer

                                                                      

     

       

real

 
 

       

     Рисунок 2 – Анализ выражения b-4+8 

      Проверка  правильности операторов

     Задачи  проверки правильности операторов:

     1) выяснить, все ли переменные, встречающиеся  в операторах, описаны;

     2) установить соответствие типов в операторе присваивания слева и справа от символа «ass»;

     3) определить, является ли выражение  E в операторах условия и цикла булевым.

     Задача  решается проверкой типов в соответствующих  местах программы.

Пример таблицы  идентификаторов

      Таблица 1 – Таблица идентификаторов на этапе семантического анализа

Номер	Идентификатор	адрес	тип
1	a	0	integer
2	b	0	integer
3	c	0	real
4	d	0	boolean

 

    Пример  таблицы  двуместных операций

       Таблица 2 – Таблица  двуместных операций

Операция	Тип 1	Тип 2	Тип результата
+, -, *	integer	integer	integer
/	integer	integer	real
+, -, *,/	integer	real	real
+, -, *,/	real	integer	real
+, -, *,/	Real	real	real
<,>,<=,>=,=	integer	integer	boolean
<,>,<=,>=,=	integer	real	boolean
<,>,<=,>=,=	real	integer	boolean
<,>,<=,>=,=	real	real	boolean
and, or	boolean	boolean	boolean