Факультет вычислительной математики и кибернетики (стр. 13 из 15)

1 ) Позиция переноса Sn обеспечивает выполнение операции переноса

и переход в состояние n .

2 ) Позиция свертки Rk обеспечивает выполнение операции свертки ,

используя продукцию k .

Пустые позиции таблицы соответствуют синтаксическим ошибкам и для каждой такой позиции можно предусмотреть выдачу своего

индивидуального сообщения об ошибке.

На каждом этапе синтаксического анализа анализатор находится в одном из конечного числа состояний , и это состояние плюс входной символ ( либо символ предосмотра , либо символ только что свернутого нетерминала ) определяют элемент в таблице синтаксического анализа.

Если предположить отсутствие ошибок , этот элемент определяет операцию переноса или свертки. В начале синтаксического анализа

анализатор находится в состоянии 1 , а входной символ - это первый символ анализируемого предложения .

Пусть позиция таблицы определяет операцию переноса , тогда :

- символ , соответствующий столбцу , в котором находится данная

позиция таблицы , заносится в стек символов ;

- анализатор переходит в состояние , определяемое позицией

переноса , и это состояние заносится в стек состояний ;

- если входной символ является терминалом , он принимается ,

и входным символом становится следующий терминал

предложения .

Пусть позиция таблицы определяет операцию свертки , тогда :

- из стека символов удаляются m -символов , а из стека состояний

удаляются m состояний , где m - число символов в правой части

продукции , фигурирующей в свертке ;

- анализатор переходит в состояние , определяемое вершиной стека

состояний ;

- входной символ становится символом в левой части продукции ,

определенной в позиции свертки .

Ниже приводится пример анализа предложения x+x+x*x на основе использования таблицы 3.4.3 -3 .

На начальном этапе имеем :

входная строка стек состояний стек символов сентенциальная

форма

x+x+x*x 1 x+x+x*x

Состояние -1 , входной символ -x , значение соответствующего элемента таблицы - S12 ; выполняется переход в состояние 12 , в стек состояний заносится 12 , в стек символов заносится x :

входная строка стек состояний стек символов сентенциальная

форма

x+x+x*x 1,12 x x+x+x*x

Состояние -12 , входной символ - + , значение соответствующего элемента таблицы - R6 ; выполняется свертка согласно продукции 6 ,

удаляется одно состояние из стека состояний и один символ из стека символов ( так как в правой части продукции 6 имеется только один символ) ; входным символом становится F :

входная строка стек состояний стек символов сентенциальная

форма

x+x+x*x 1 x+x+x*x

Состояние -1 , входной символ - F , значение соответствующего элемента таблицы - S8 ; выполняется переход в состояние 8 , в стек состояний заносится 8 , в стек символов заносится F :

входная строка стек состояний стек символов сентенциальная

форма

x+x+x*x 1,8 F F+x+x*x

Состояние -8 , входной символ - + , значение соответствующего элемента таблицы - R4 ; выполняется свертка согласно продукции 4 ,

удаляется одно состояние из стека состояний и один символ из стека символов; входным символом становится T :

входная строка стек состояний стек символов сентенциальная

форма

x+x+x*x 1 F+x+x*x

Состояние -1 , входной символ - T , значение соответствующего элемента таблицы - S5 ; выполняется переход в состояние 5 , в стек состояний заносится 5 , в стек символов заносится T :

входная строка стек состояний стек символов сентенциальная

форма

x+x+x*x 1,5 T T+x+x*x

Далее выполняются аналогичные действия , основанные на приведенной таблице синтаксического анализа , которые завершаются

следующим состоянием.

Состояние -1 , входной символ - E , значение соответствующего элемента таблицы - S2 ; выполняется переход в состояние 2 , в стек состояний заносится 2 , в стек символов заносится E :

входная строка стек состояний стек символов сентенциальная

форма

x+x+x*x 1,2 E E

Как только в стеке символов оказывается символ E и считано все предложение , анализ успешно завершается .

В данном пособии этот не рассматриваются способы создания таблицы синтаксического анализа , которые можно найти в книге [ 6 ] .

3.4.4. Префиксная и постфиксная записи выражений.

Классическим способом представления выражений для анализа

перед генерацией кода являются префиксная и постфиксная записи .

Для пояснения рассмотрим выражение вида a+b*c+d/e-f . Такая запись выражения называется инфиксной , что означает расположение знака

бинарной операции между операндами . Интерпретация и

соответственно анализ такого выражения в общем случае носит

неодназначный характер . Для устранения неодназначности

используется приоритет операций . Анализ основывается на

представлении выражения в древовидной форме следующего вида :

-

+ f

+ /

a * d e

b c

Рис. 3.4.4-1. Пример древовидного представления выражения .

Каждая промежуточная вершина этого дерева помечена знаком

соответствующей операции , а дуги , исходящие из данной вершины ,

ведут к операндам .

Теперь , начиная с вершины (сверху вниз) и придерживаясь

левоориентированного пути , обойдем это дерево , попутно выписывая

в строку все встречающиеся символы . В результате получим выражение

вида - + + a * b c / d e f , представляющее префиксную запись.

Отличительная собенность префиксной записи заключается в том , что

каждый знак операции предшествует своим операндам .

Постфиксная запись получается "зеркальным отображением "

соответствующей префиксной записи . Таким образом для указанного

выше выражения постфиксная запись имеет вид f e d / c b * a + + - .

Отличительной собенностью постфиксной записи является то , что

каждый знак операции записывается после операндов . Постфиксная

запись является очень удобной для вычисления выражений , поскольку

в ней все знаки выполняемых операций располагаются в порядке

убывания приоритетов.

Последнее означает , что первая встретившаяся операция при

просмотре выражения слева направо выполняется первой , вторая встретившаяся - второй и т.п. . Для вычисления постфиксной записи используется классический алгоритм с использованием стека . Алгоритм

основывается на просмотре символов выражения слева направо и вы-

полнении соответствующих действий в зависимости от назначения

символа (знак операции , символ операнда или символ конца строки) .

Таким образом алгоритм в процессе просмотра выражения может

находиться в одном из следующих состояний .

1. Считываемый символ является операндом. В этом случае

значение операнда заносится в стек .

2. Считываемый символ является знаком операции . Выполняется

соответствующая операция с операндами , которые извлекаются

из стека. Извлеченные из стека операнды соответственно удаляю-

тся из стека и в стек заносится результат выполнения операции .

3. Считываемый символ определяет конец строки . Алгоритм завер-

шает свою работу . В стеке остается единственный элемент ,

определяющий результат вычисления выражения .

Таблица 3.4.4-1 иллюстрирует работу алгоритма на примере

постфиксной записи f e d / c b * a + + - ^ , где символ ^ определяет

конец строки .

____________________________________________________________

Считываемый символ Состояние Содержимое стека

____________________________________________________________

f 1 V_f

e 1 V_f ,V_e

d 1 V_f ,V_e,V_d

/ 2 V_f,V_d/e

c 1 V_f,V_d/e ,V_c

b 1 V_f,V_d/e ,V_c,V_b

* 2 V_f,V_d/e ,V_b*c

a 1 V_f,V_d/e ,V_b*c,V_a

+ 1 V_f,V_d/e ,V_a+b*c

+ 1 V_f,V_a+b*c+d/e

- 1 V_a+b*c+d/e-f

^ 3 V_a+b*c+d/e-f

____________________________________________________________

Таблица 3.4.4 -1 . Пример вычисления постфиксной записи .

Здесь V_E определяет значение выражения E , а верх стека

предполагается находящимся справа .

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

снять указанное ограничение , то потребуется разделять элементы постфиксной записи (например запятой).

Пример. Инфиксная запись : x1+y*x2 . Постфиксная запись : x2,y,*,x1,+ .

В результате трансляции перед генерацией машинного кода

выполняется ,как правило, формирование так называемого

промежуточного кода, с помощью которого генерируется машинный код,

либо промежуточный код выполняется интерпретатором ( в случае

языков интерпретируемого типа ). Получение промежуточного кода традиционно выполняется на основе постфиксной записи , которая

может применяться не только к выражениям , но и к различным

программным конструкциям с соответствующей модификацией.

3.5. Семантический анализ.

Основная часть языков программирования основывается на контекстно-

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

контекстно-свободных грамматик .В основном это связано с