Построение таблиц анализа

7.4.1 Понятие ситуации

Как уже отмечалось, LR-анализатор представляет собой конечный автомат. Состояниями недетерминированного конечного автомата являются ситуации. Ситуация – это продукция из заданной грамматики, в которую помещена точка, отделяющая распознанную часть от нераспознанной части. Например, если в грамматике есть продукция Аà xyz, то для нее возможна ситуация [Аà xy× z], которая соответствует состоянию автомата в котором анализатор получил на входе x и y и теперь ожидает z. Вообще для продукции Аà xyz возможны следующие ситуации: [Аà × xyz], [Аà x× yz], [Аà xy× z], [Аà xyz× ]. Для продукции вида Аà e возможна только одна ситуация [Aà × ].

Теперь необходимо сгруппировать ситуации, чтобы получить детерминированный конечный автомат.

7.4.2 Каноническая совокупность множеств ситуаций

Вначале введем понятие замыкание множества ситуаций I (closure(I)). Замыкание I строится по двум правилам.

1 В замыкание I заносится множество ситуаций I.

2 Если ситуация [Aà a× Bb] уже принадлежит closure(I) и есть продукция Bà g, то добавляем в closure(I) ситуацию [Bà × g].

Теперь рассмотрим переходы (goto (I, x)). Переход представляет собой множество ситуаций, в которые можно перейти из множества ситуаций I по грамматическому символу х, то есть по терминалу или нетерминалу. При выполнении функции (goto (I, x)) строят замыкание множества состояний вида [Aà ax× b], если в I есть ситуация [Aà a× xb], то есть точка переходит за символ х в ситуациях. После этого строиться замыкание этого множества.

Используя функции closure(I) и goto(I, x) можно построить каноническую совокупность всех возможных множеств ситуаций дополненной грамматики. Для этого строят замыкание для ситуации [S¢ à × S]. После этого в цикле находят все множества ситуаций, в которые можно перейти из уже найденного множества по любому грамматическому символу. Цикл завершается, когда нельзя ничего нового добавить в каноническую совокупность.

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

Замыкание ситуации [EXPR¢ à × EXPR] = {[EXPR¢ à × EXPR], [EXPR à × EXPR+TERM], [EXPR à × TERM], [TERM à × TERM*FACTOR], [TERM à × FACTOR], [FACTORà × id]}. Обозначим это множество как I₀.

Рассмотрим, в какие множества ситуаций можно перейти из I₀ по различным грамматическим символам. По символу EXPR можно перейти в множество {[EXPR¢ à EXPR× ], [EXPR à EXPR× +TERM]}. Замыкание этого множества будет равно самому этому множеству. Обозначим полученное множество как I₁. По грамматическому символу TERM из I₀ можно перейти во множество I₂={[EXPR à TERM× ], [TERM à TERM× *FACTOR]}. По символу FACTOR осуществляется переход в множество I₃={[TERM à FACTOR× ]}. Аналогично по символу id переходим в множество ситуаций I₄={[FACTORà id× ]}. Все переходы из множества I₀ рассмотрены.

Теперь рассмотрим множество I₁. Из него возможен переход только по символу + в множество {[EXPR à EXPR+× TERM]}. В каноническую совокупность добавляем множество I₅, представляющее собой замыкание множества {[EXPR à EXPR+× TERM]}, то есть I₅={[EXPR à EXPR+× TERM], [TERM à × TERM*FACTOR], [TERM à × FACTOR], [FACTOR à × id]}.

Из множества I₂ существует переход только по символу *. Построение замыкания полученного множества приведет к занесению в каноническую совокупность множества I₆={[TERM à TERM*× FACTOR], [FACTOR à × id]}

Из множеств I₃ и I₄ нельзя выполнить ни один переход.

Рассматривая символ TERM и множество I₅, добавим в каноническую совокупность I₇={[EXPR à EXPR+TERM× ], [TERM à TERM× *FACTOR]}. По символу FACTOR из множества I₅ можно перейти в множество {[ TERM à FACTOR× ]}, то есть во множество I₃. Таким образом, на данном шаге ничего нового в каноническую совокупность не добавляем. Рассмотрение символа id для множества I₅ так же не приведет к появлению нового множества, так как переход будет осуществлен во множество I₄.

Для множества I₆ характерны переходы по символам FACTOR и id. В первом случае к канонической совокупности добавляется множество I₈={[TERM à TERM*FACTOR× ]}. По символу id выполняется переход в уже существующее множество I₄.

Из множества I₇ по символу * осуществляется переход в состояние I₆. Из множества I₈ переходов нет.

Результирующая каноническая совокупность изображена на рисунке 22.

I₀={[EXPR¢ à × EXPR], [EXPR à × EXPR+TERM], [EXPR à × TERM], [TERM à × TERM*FACTOR], [TERM à × FACTOR], [FACTORà × id]};

I1={[EXPR¢ à EXPR× ], [EXPR à EXPR× +TERM]};

I2={[EXPR à TERM× ], [TERM à TERM× *FACTOR]};

I3={[TERM à FACTOR× ]};

I4={[FACTORà id× ]};

I5={[EXPR à EXPR+× TERM], [TERM à × TERM*FACTOR],
[TERM à × FACTOR], [FACTOR à × id]}

I6={[TERM à TERM*× FACTOR], [FACTOR à × id]}

I7={[EXPR à EXPR+TERM× ], [TERM à TERM× *FACTOR]}

I8={[TERM à TERM*FACTOR× ]}

Рисунок 26

7.4.3 Заполнение таблиц action и goto

Таблица action в зависимости от пары < входной сигнал, состояние> определяет, достигнут ли конец основы. Если конец основы достигнут, то выполняется приведение, в противном случае выполняется сдвиг.

Таблица goto в зависимости от пары < нетерминал в вершине стека, состояние> определяет состояние конечного автомата после выполнения приведения.

Алгоритм заполнения таблиц анализа заключается в следующем.

1 Построить каноническую совокупность множества ситуаций.

2 Каждое множество I канонической совокупности определяет состояние конечного автомата с соответствующим номером, а следовательно строку в таблицах анализа. Ячейки в таблице заполняются по следующим вариантам.

а) Если ситуация [Aà a× ab] принадлежит множеству I_i и существует переход по терминалу a в некоторое множество I_j, то в ячейку action(i, a) значение shift j. В приведенной ситуации основа не может быть найдена, так как для ее завершения как минимум необходимо распознать терминал a, то есть выполнить сдвиг.

б) Если ситуация [Aà a× ] принадлежит множеству I_i, то для всех терминалов а, принадлежащих follow(A), в ячейку action[i, a] заносим значение reduce Aà a. Это происходит потому что основа найдена полностью и распознавание любого символа, следующего за А, должно привести к приведению основы.

в) Если ситуация [S¢ à S× ], принадлежит множеству I_i, то есть можно осуществить редукцию для стартовой продукции, то в ячейку action[I, eof] записываем значение accept. То есть разбор успешно закончен, если достигнут конец входной последовательности.

3 Если существует переход из множества I_i в множество I_j по некоторому нетерминалу А, то в ячейку goto[i, А] заносим значение j.

4 Все незаполненные ячейки в таблицах action и goto заполняем значением “ошибка”.

5 Начальным состояние автомата является состояние, содержащее ситуацию [S¢ à S]

Построим таблицы разбора для грамматики с рисунка 21. Каноническая совокупность для этой грамматики приведена на рисунке 22. Для построения таблицы action необходимо построить множество follow для нетерминалов грамматики. Это множество приведено в таблице 6.

Таблица 7. – Множество follow для упрощенной грамматики арифметических выражений

В канонической совокупности девять множеств, то есть в конечном автомате будет девять состояний с S0 по S8, столько же строк будет в таблицах анализа.

Рассмотрим переходы по терминалам в канонической совокупности. Из множества I₀ по терминалу id есть переход во множество I₄, а ситуация [FACTORà × id] принадлежит I₀. Поэтому action[S0, id]: =shift S4. Множеству I₁ принадлежит ситуация [EXPRà EXPR× +TERM], и есть переход из I₁ в I₅ по входному символу +, поэтому заносим значение shift S5 в ячейку action[S1, +]. Из I₂ существует переход в I₆ по символу *, ситуация [TERMà TERM× *FACTOR] принадлежит множеству I₂, следовательно, action[S2, *]: =shift S6. Из множеств I₅ и I₆ в канонической совокупности существуют переходы во множество I₄ по символу id. Ситуация [FACTORà × id] принадлежит обоим этим множествам. Поэтому значение shift S4 заносим в ячейки action[S5, id] и action[S6, id]. Множеству I₇ принадлежит ситуация [TERMà TERM× *FACTOR], и существует переход из множества I₇ во множество I₆, поэтому записываем значение shift S6 в ячейку action[S7, *].

Ситуация [EXPR¢ à EXPR× ] принадлежит множеству I₁, follow(EXPR¢)={eof}, поэтому должно было быть выполнено присвоение action[S1, eof]: =reduce 1, то есть приведение по первой продукции грамматики. Однако эта ситуация соответствует стартовой продукции, следовательно, action[S1, eof]: =accept. Множеству I₂ канонической совокупности принадлежит ситуация [EXPRà TERM× ], follow(EXPR)={+, eof}, следовательно, action[S2, +] и action[S2, eof] принимают значение reduce 3. Множество I₃ содержит ситуацию [TERMà FACTOR× ], follow(TERM)={*, +, eof}, поэтому значение reduce 5 заносим в ячейки action[S3, *], action[S3, +] и action[S3, eof]. I₄ содержит ситуацию [FACTORà id× ], follow(FACTOR)={*, +, eof}, поэтому ячейки action[S4, *], action[S4, +] и action[S4, eof] будут содержать значение reduce 6. Наличие ситуации [EXPRà EXPR+TERM× ] во множестве I₇ приводит к записи значения reduce 2 в ячейки action[S7, +] и action[S7, eof]. Аналогично, ситуация [TERMà TERM*FACTOR× ] во множестве I₈ обосновывает наличие значения reduce 4 в ячейках action[S8, *], action[S8, +] и action[S8, eof].

Теперь рассмотрим переходы по нетерминальным символам между множествами канонической совокупности. Из множества I₀ есть такие переходы в состояние I₁ по нетерминалу EXPR, I₂ по нетерминалу TERM и I₃ по символу FACTOR, поэтому в ячейку goto[S0, EXPR] записываем значение S1, goto[S0, TERM]: =S2 и goto[S0, FACTOR]: =S3. Также переходы по нетерминальным символам существуют из множества I₅ в множества I₃ и I₇. Поэтому goto[S5, FACTOR]: =S3, а goto[S5, TERM]: =S7. В таблице переходов будет еще одно значение, goto[S6, FACTOR]: =S8, так как в канонической совокупности есть переход из I₆ в I₈ по символу FACTOR.

В незаполненные до сих пор ячейки заносим информацию об ошибке. Построенные таблицы приведены ниже.

Таблица 8. – Таблица action для упрощенной грамматики арифметических выражений

Таблица 9. – Таблица goto для упрощенной грамматики арифметических операций

7.5 Алгоритм LR-разбора

Алгоритм LR-разбора состоит в следующем.

Занести в стек символ конца входной последовательности (eof)

Занести в стек начальное состояние конечного автомата

Распознать лексему

repeat

Если action[состояние в вершине стека, лексема]=shift S

то

занести в стек лексему и состояние S, после чего распознать следующую лексему

Если action[состояние в вершине стека, лексема]=reduce P

то

извлечь из стека столько пар < состояние, грамматический символ>, сколько грамматических символов составляют правую часть правила P. В стек занести нетерминал левой части продукции P и goto[состояние в вершине стека, нетерминал левой части продукции P]

Если action[состояние в вершине стека, лексема]=accept

то

вывести пользователю сообщение об успешном разборе и выйти из цикла

Если action[состояние в вершине стека, лексема]=ошибка

то

обработать ошибочную ситуацию

until false

Рассмотрим, как работает алгоритм для входной последовательности x*y+z. Грамматика представлена на рисунке 21, таблицы action и goto приведены выше под номерами 7 и 8. Рассмотрим этапы разбора.

1 В начале работы алгоритма в стек заносим символ конца входной последовательности и стартовое состояние. Таким образом, стек= “eof S0”. Распознанная лексема = id.

2 action[S0, id]= “Shift S4”, то есть необходимо выполнить сдвиг и занести в стек символ id и состояние 4. Распознаем следующую лексему. Это символ *. В вершине стека находится состояние S4.

3 action[S4, *]=reduce 6. Шестое правило грамматики имеет вид FACTORà id. При приведении по нему из стека извлекается верхняя пара < состояние, символ>, так как правая часть продукции состоит из одного символа. Теперь в вершине стека находится состояние S0. В стек заносим левую часть шестой продукции и состояние найденное как goto[S0, FACTOR]. В результате стек имеет вид “eof S0 FACTOR S3”.

4 action[S3, *]=reduce 5. Пятая продукция имеет вид TERMà FACTOR. После извлечения стек имеет вид “eof S0”. goto[S0, TERM]=S2. Таким образом, стек= “eof S0 TERM S2”.

5 action[S2, *]=shift S6. Стек= “eof S0 TERM S2 * S6”. Следующей распознанной лексемой является id.

6 action[S6, id]=shift S4. Стек= “eof S0 TERM S2 * S6 id S4”. Лексема=+.

7 action[S4, +]=reduce 6. Стек= “eof S0 TERM S2 * S6 FACTOR S8”.

8 action[S8, +]=reduce 4. Четвертая продукция имеет вид TERMà TERM*FACTOR. Длина правой части равна 3, поэтому из стека извлекаем три пары < состояние, символ>. После выполнения приведения стек имеет вид “eof S0 TERM S2”.

8 action[S2, +]=reduce 3. Третья продукция имеет вид EXPRà TERM. Стек после выполнения приведения равен “eof S0 EXPR S1”.

9 action[S1, +]=shift S5. Стек= “eof S0 EXPR S1 + S5”. Распознанная лексема=id.

10 action[S5, id]=Shift S4. Стек=“eof S0 EXPR S1 + S5 id S4”. Лексема=eof.

11 action[S4, eof]=reduce 6. Стек = “eof S0 EXPR S1 + S5 FACTOR S3”.

12 action[S3, eof]=reduce 5. Стек= “eof S0 EXPR S1 + S5 TERM S7”.

13 action[S7, eof]=reduce 2. Стек= “eof S0 EXPR S1”.

14 action[S1, eof]=accept.

Таким образом, разбор завершен успешно, входная последовательность соответствует распознаваемому языку

/*Редукции по правилу EXPR¢ à EXPR не производилось. В вершине стека не стартовый символ, или стартовый, но без дополненной грамматики. В примере из лекций то же самое. Зачем нужна стартовая продукция? И как тогда работает Yacc, который выполняет приведение по продукции goal: expr? */

Для реализации этого алгоритма выполним следующее.

Объявляем тип для отражения состояний автомата. Дополнительно элементом этого типа будет s_er, необходимый для заполнения ошибочных ячеек таблицы action. Еще один тип объявим для отражения грамматических символов.

type

state=(s0, s1, s2, s3, s4, s5, s6, s7, s8, s_er);

symb = (expr1, expr, term, factor, t_id, t_plus, t_mult, eof);

Для работы программы нужно будет написать функцию, переводящую значение типа integer, в значение типа symb. Это связано с тем, что лексический анализатор возвращает значение типа integer, а синтаксический анализатор будет работать с собственным типом для грамматических символов.

Грамматики будем хранить в виде массива записей. Каждая запись будет содержать нетерминал левой части и количество символов в правой. Сам текст продукций для работы алгоритма не важен, он уже был использован для построения таблиц анализа. Таким образом, для хранения грамматики выполним следующие объявления.

type

gramm_type=record

noterm: symb;

basic_length: integer;

end;

const

gramm: array[1..6] of gramm_type=

((noterm: expr1; basic_length: 1),

(noterm: expr; basic_length: 3),

(noterm: expr; basic_length: 1),

(noterm: term; basic_length: 3),

(noterm: term; basic_length: 1),

(noterm: factor; basic_length: 1)

);

Стек должен содержать пары < состояние, символ>. Для его реализации можно написать следующий код.

Декларируем тип элементов массива

type

stack_type=record

stack_state: state;

stack_symb: symb;

end;

Объявляем переменные стек и указатель на вершину стека

var stack: array[1..100] of stack_type; p_s: integer;

Реализуем процедуры извлечения из стека и занесения в стек

procedure pop;

begin

dec(p_s);

end;

procedure push(value_state: state; value_symb: symb);

begin

inc(p_s);

stack[p_s].stack_state: =value_state;

stack[p_s].stack_symb: =value_symb;

end;

7.6 Контрольные вопросы

1 В чем состоит основная идея синтаксического разбора сверху вниз?

2 Чему соответствует обратный порядок построения дерева разбора метода “сдвиг-приведение”?

3 Что такое основа?

4 Какова структура LR(k)-анализатора?

5 Какие действия выполняет LR-анализатор?

6 Что такое ситуация?

7 Чему в терминах конечного автомата соответствует ситуация и каноническая совокупность ситуаций?

7.7 Задание

1 Построить грамматику для распознавания запроса по одной таблице в стандарте SQL. Запрос начинается ключевым словом select, за которым через запятую следуют имена поле. После этого списка следует служебное слово from и имя таблицы. В запросе может присутствовать раздел условий, начинающийся со служебного слова where. За ним следует список условий. Каждое условие имеет вид “имя поля < |> |= значение”. Условия соединяются операциями or или and.

2 Построить таблицы анализа для LR(1)-разбора.

3 Реализовать алгоритм LR-разбора для построенной грамматики.

Части 1 и 2 задания выполняются студентом при подготовке к лабораторной работе.

7.8 Содержание отчета

Отчет должен содержать грамматику распознаваемого в ходе лабораторной работы языка, а также таблицы action и goto для синтаксического анализатора.

7.9 Защита лабораторной работы

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

8 Лабораторная работа № 6 “Генерация кода и реализация машины”

8.1 Цель работы

Целью данной лабораторной работы является:

- получение навыков построения генератора кода на основе синтаксического разбора методом рекурсивного спуска;

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

8.2 Построение транслятора на основе синтаксического анализа методом рекурсивного спуска

Задача генератора кода – построение эквивалентной машиной программы по программе на входном языке.

Таким образом, для реализации транслятора необходимо определить язык машины и построить генератор, который преобразует входной язык к машинному языку.

8.2.1 Входной язык

Будем рассматривать в качестве входного для генератора кода язык арифметических выражений. Рассмотрим грамматику этого языка. Входной язык представляет собой раздел переменных и раздел кода

1 LANGUAGE à VARIABLE PROGRAM

Раздел переменных – это служебное слово var, описание переменной и список описания переменных.

2 VARIABLEà var VAR_DESCRIBE LIST_VAR

Описание переменной это ее имя (идентификатор), двоеточие и начальное значение. Описание переменной заканчивается символом “; ”.

3 VAR_DESCRIBE à id: num;

Список переменных это запятая и описание переменной. Список может быть пустым

4 LIST_VARà VAR_DISCRIBE LIST_VAR

5 LIST_VARà e

Раздел кода это список команд, заключенный между ключевыми словами begin и end.

6 PROGRAMà begin LIST_ INSTRUCTION end

Список команд - это команды приведенные через разделитель (;) или пустой список.

7 LIST_ INSTRUCTIONà INSTRUCTION; LIST_ INSTRUCTION

8 LIST_ INSTRUCTIONà e

Команда это оператор чтения или оператор присвоения

9 INSTRUCTIONà READ_INSTR

10 INSTRUCTIONà ASSIGN_INSTR

Оператор чтения описывается продукцией 11, а продукции 12-22 описывают оператор присвоения

11 READ_INSTR à read (id)

12 ASSIGN_INSTRà id: = EXPR

13 EXPRà TERM EXPR1

14 EXPR1à + TERM EXPR1

15 EXPR1à - TERM EXPR1

16 EXPR1à e

17 TERMà FACTOR TERM1

18 TERM1à * FACTOR TERM1

19 TERM1à / FACTOR TERM1

20 TERM1à e

21 FACTORà id

22 FACTORà num

Будем считать, что синтаксический анализатор для этой грамматики построен с использованием метода рекурсивного спуска.

8.2.2 Структура машины

Машина состоит из области данных (таблицы переменных), кода и стека.

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

Таблицу переменных для наглядности будем хранить в объекте sgData класса TStringGrid с двумя столбцами: имя и значение.

Стек будет использован в данном трансляторе только для хранения чисел, поэтому зададим его в качестве массива. Кроме того, необходимо определить способы работы со стеком.

var

stack: array [1..100] of real;

p_s: integer;

function pop: real;

begin

result: =stack[p_s];

dec(p_s);

end;

procedure push(value: real);

begin

inc(p_s);

stack[p_s]: =value;

end;

Машина, работающая с языком арифметических выражений, будет иметь следующие команды.

ldc (value) – поместить в стек константу (число), передаваемую в качестве параметра.

procedure ldc(value: real);

begin

push(value);

end;

ldv (value) – поместить в стек значение переменной, передаваемой в качестве параметра. Эта команда производит поиск по таблице переменных, если переменная присутствует в таблице, то в стек помещается ее значение. Если переменная не найдена, то порождается ошибочная ситуация.

procedure ldv(value: string);

var i: integer; f: boolean;

begin

i: =0; f: =true;

while (i< sgData.RowCount) and f do

begin

if sgData.cells[0, i]=value

then

begin

push(strtofloat(sgData.cells[1, i]));

f: =false;

end

else inc(i);

end;

if f

then raise exception.Create('Неизвестный идентификатор');

end;

add – сложение.

sub – вычитание.

mult – умножение.

div – деление.

Операции арифметических действий выполняются одинаково. Они заключаются в чтении из стека двух значений, выполнения операции и записи результата в стек. Приведем в качестве примере процедуру для выполнения вычитания.

procedure TForm1.sub;

var a1, a2: real;

begin

a1: =pop; a2: =pop;

push(a2-a1)

end;

assignment(value) – присвоение значения переменной, полученной в качестве параметра. Эта команда читает значение из стека и записывает прочитанную величину в качестве значения переменной в таблицу переменных.

procedure assignment(value: string);

var i: integer; f: boolean;

begin

i: =0; f: =true;

while (i< sgData.RowCount) and f do

begin

if sgData.cells[0, i]=value

then

begin

sgData.cells[1, i]: =floattostr(pop);

f: =false;

end

else inc(i);

end;

if f

then raise exception.Create('Неизвестный идентификатор')

end;

read(value) – чтение значения переменной, передаваемой в качестве параметра. Для реализации такого диалога с пользователем будем использовать объект класса Tform, создаваемый при необходимости ввода и разрушаемый после ввода. На такой форме будут помещаться объекты класса TLabel для вывода имени переменной и класса TEdit для ввода пользователем значения переменной. Если переменной, значение которой необходимо вести нет в таблице переменных, то порождается ошибочная ситуация.

procedure read;

var form: Tform; edit: Tedit; label1: Tlabel;

i: integer; f: boolean;

begin

i: =0; f: =true;

while (i< sgData.RowCount) and f do

begin

if sgData.cells[0, i]=value

then

begin

push(strtofloat(sgData.cells[1, i]));

f: =false;

end

else inc(i);

end;

if f

then raise exception.Create('Неизвестный идентификатор')

else

begin

form: =tform.Create(application);

edit: =tedit.Create(form);

edit.Parent: =form;

edit.top: =20;

label1: =tlabel.Create(form);

label1.Parent: =form;

label1.caption: =sgData.Cells[0, i];

form.ShowModal;

sgData.Cells[1, i]: =edit.text;

form.Destroy;

end;

end;

8.2.3 Генерация кода из синтаксического анализатора

Таблицу переменных необходимо сформировать при декларации переменных во входной последовательности (продукции 2-5). Поэтому заполнение таблицы будем производить в соответствующей функции синтаксического анализатора. Ниже приведен код функции синтаксического анализатора, которая производит заполнение таблицы переменных. В коде подчеркнуты строки, которые дописаны к синтаксическому анализатору для генерации кода.

function var_describe;

var help: string;

begin

help: =yytext;

if (lex=id) and (yylex=ord(': ')) and (yylex=num)

then

begin

sgData.cells[0, sgData.RowCount-1]: =help;

sgData.cells[1, sgData.RowCount-1]: =yytext;

if yylex=ord('; ')

then

begin

sgData.RowCount: =sgData.RowCount+1;

lex: =yylex;

result: =true;

end

else result: =false;

end

else result: =false;

end;

Теперь перейдем непосредственно к формированию кода. Программа должна будет выполняться в снизу вверх и слева направо налево по дереву разбора, которое строиться при синтаксическом разборе. С каждым узлом дерева может быть связана какая-либо операция. Операция некоторого узла дерева может быть выполнена тогда, когда выполнены все необходимые операции других узлов.

Если построить дерево разбора для входной последовательности, соответствующей приведенной выше грамматике, то в самом низу этого дерева окажутся терминалы id и num, выведенные из нетерминала FACTOR. Поэтому в функцию factor синтаксического анализатора встраиваем генератор. Если распознано число, то оно помещается в стек, если распознан идентификатор, то в стеке необходимо сохранить значение этой переменной.

Ниже приведена функция factor синтаксического анализатора со встроенным генератором кода. При этом код храниться в объекте sgCode: TStringGrid. Первый столбец этого объекта хранит имя команды машины, а остальные два предназначены для хранения параметров команды, если они предусмотрены машиной.

function factor;

begin

case lex of

id:

begin

sgCode.Cells[0, sgCode.RowCount-1]: ='ldv';

sgCode.Cells[1, sgCode.RowCount-1]: =yytext;

sgCode.RowCount: =sgCode.RowCount+1;

result: =true;

lex: =yylex;

end;

num:

begin

sgCode.Cells[0, sgCode.RowCount-1]: ='ldc';

sgCode.Cells[1, sgCode.RowCount-1]: =yytext;

sgCode.RowCount: =sgCode.RowCount+1;

result: =true;

lex: =yylex;

end;

else result: =false;

end;

end;

Код, соответствующий операциям сложения, вычитания, умножения и деления встраивается одинаковым образом. Рассмотрим это на примере вычитания. Вычитание заключается в извлечении из стека двух значений, вычитании из первого значения второго и сохранения результата в стеке.

Приведем фрагмент дерева разбора для входной строки 5-2-3.

Рисунок 27

Операцию вычитания имеет смысл встроить в функцию, соответствующую узлу EXPR1. Если эту операцию встроить после выполнения всех поддеревьев узла EXPR1, то получится следующая ситуация. При выполнении кода сначала выполняться действия, соответствующие левому поддереву узла EXPR. В результате в стеке окажется идентификатор 5 (операция ldc, встроенная в функцию factor). Далее выполняться операции, связанные с центральным поддеревом EXPR1. После этого в стеке окажется идентификатор 5 и идентификатор 2. Операция вычитания, которая должна быть выполнена на этом этапе согласно математическим правилам, выполнена не будет, так как вначале должны выполняться операции правого поддерева узла EXPR1. При выполнении правого поддерева в стеке окажутся идентификаторы 5, 2 и 3. После этого выполниться операция вычитания, соответствующая нижнему узлу EXPR1, что приведет к наличию в стеке значений 5 и –1. Теперь все поддеревья верхнего узла выполнены и выполняется последняя операция вычитания. При этом результат вычислений равен 6, а должен быть равен 0.

Поэтому операцию вычитания встроим в узел EXPR1, после доказательства центрального поддерева, но до доказательства правого. Ниже приведен код функции, соответствующей узлу EXPR1. Заметим, что сложение можно выполнять после выполнения всех поддеревьев узла EXPR1, так как порядок слагаемых на результат не влияет.

function expr1;

begin

case lex of

ord('+'):

begin

lex: =yylex;

result: =term and expr1;

sgCode.Cells[0, sgCode.rowcount-1]: ='add';

sgCode.RowCount: =sgCode.RowCount+1;

end;

ord('-'):

begin

lex: =yylex;

if term

then

begin

sgCode.Cells[0, sgCode.rowcount-1]: ='sub';

sgCode.RowCount: =sgCode.RowCount+1;

result: =expr1;

end

else result: =false

end;

else result: =true

end;

end;

8.2.4 Работа машины

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

procedure execute;

var i: integer;

begin

for i: =0 to sgCode.RowCount-2 do

begin

if sgCode.Cells[0, i]='ldc'

then ldc(strtofloat(sgCode.Cells[1, i]));

if sgCode.Cells[0, i]='ldv'

then ldv(sgCode.Cells[1, i]);

if sgCode.Cells[0, i]='add'

then add;

…

end;

end;

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

8.3 Контрольные вопросы

1 В чем состоит задача генератора кода?

2 Из каких составных частей состоит машина?

3 В каком направлении по дереву разбора выполняется программа?

4 Каким образом влияет положение генератора кода в функции узла дерева? Пояснить на примере операции вычитания.

8.4 Задание

Реализовать транслятор, встроив генератор кода в синтаксический анализатор, построенный в лабораторной работе № 3.

Сложность при реализации может вызвать команда If. Для того, чтобы эта команда работала корректно необходимо ввести еще одну команду машины goto(номер строки). Эта команда должна перенести выполнение кода с текущей строки на строку, указанную в качестве параметра. Команда if должна иметь в качестве аргумента строку, на которую должно передаваться управление, в случае, если условие ложно. Часть кода, соответствующая истинному условию, должна заканчиваться командой goto, передающей управление на строку, следующую за кодом, обрабатывающим ложное условие.

8.5 Защита лабораторной работы

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

9 Лабораторная работа № 7 “Автоматизированное построение трансляторов с использованием генератора YACC”

9.1 Цель работы

Целью выполнения лабораторной работы является:

- закрепление теоретических знаний в области атрибутных грамматик;

- получение опыта работы со средствами автоматизированного построения трансляторов на примере генератора компиляторов Yacc.

9.2 Общие сведения

Одним из средств автоматизированного построения трансляторов является генератор компиляторов Yacc.

Yacc строит синтаксический анализатор, работающий на основе метода “сдвиг - приведение”.

Этот генератор работает с атрибутными грамматиками. Атрибутные грамматики характеризуются тем, что с каждым грамматическим символом связывается множество атрибутов.

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

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

Исходный текст для Yacc, основой которого являются продукции и семантические правила, пишется в текстовом редакторе, например в блокноте, и сохраняется в файле с расширением y. Работа программы yacc.exe, в качестве параметра которой выступает исходный файл с расширением y, строит транслятор. Yacc строит транслятор на основе кода, содержащегося в файле Yyparse.cod. Если исходный текст содержит ошибки, то при генерации транслятора будет создан файл ошибок с расширением lst.

Полученный в результате работы yacc модуль присоединяется к проекту Delphi, который содержит текст основной программы. Для корректной работы с этим проектом, он должен использовать библиотеку Yacclib.pas.

Транслятор строится Yacc в виде функции yyparse, которая вызывается из основной программы.

При генерации транслятора Yacc включает код лексического анализатора, построенного Lex. На рисунке 28 приведена схема взаимодействия модулей компилятора.

Рисунок 28 - Схема взаимодействия модулей компилятора.

9.3 Структура Yacc-программы

Исходный текст для yacc состоит из трех частей: определения, продукции и вспомогательные процедуры. Части разделяются символами %%.

В части определений можно указать код, который должен быть перенесен в текст результирующего транслятора без изменения. Для этого он помещается между символами %{ и %}. В качестве такого кода могут выступать заголовок модуля или объявления типов, используемые затем для описания атрибутов терминалов и нетерминалов.

В результирующем коде будет объявлена переменная yyLval. Эта переменная всегда автоматически определяется YACC в тексте синтаксического анализатора. Она предназначена для хранения атрибутов терминалов, которые должны быть переданы из лексического анализатора в синтаксический. Тип этой переменной YYSType. Этот тип также автоматически определяется YACC в синтаксическом анализаторе. Он представляет собой запись с переменными полями. Количество и имена полей записи определяются количеством и типами объявленных терминалов. Например, если объявлены терминалы стандартного типа real и пользовательского типа mytype, то у типа YYSType будет два поля YYReal и YYMytype.

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

1 Задание стартового символа.

%start символ

Если такое определение отсутствует, то в качестве стартового символа используется нетерминал левой части первой продукции.

2 Определение атрибутов терминалов грамматики.

%token < тип атрибута> терминал

При наличии такого определения в исходном тексте, в модуле, содержащем транслятор, декларируется константа указанного типа с именем, соответствующим терминалу. Эти константы используются в исходном файле Lex без дополнительных объявлений. В качестве типа может быть использован любой стандартный тип Pascal или декларированный ранее.

3 Задание ассоциативности операций.

%left символ – лево ассоциативная операция

%right символ – право ассоциативная операция

%noassoc символ – неассоциативная операция

Приоритет операции определяется ее положением при определении. Чем ниже задана операция при определении, тем выше ее приоритет.

4 Задание типов атрибутов нетерминалов

%type < тип атрибута> нетерминал.

Вторая часть Yacc-программы содержит продукции и связанные с ними семантические правила. Левая часть продукции отделяется от правой символом “: ”.

Семантические правила записываются на языке Pascal и следуют за продукцией, заключенные между символами “{” и “}”. Для обращения в семантических правилах к атрибуту нетерминала левой части продукции используют символы $$. Для обращения к атрибутам грамматических символов правой части продукций используются символы $i, где i – номер грамматического символа в продукции.

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

нетерминал: продукция 1 {семантическое правило 1}

| продукция 2 {семантическое правило 2}

…

| продукция n {семантическое правило n}

Третья часть Yacc-программы содержит вспомогательные процедуры. Эта часть переносится в результирующий код без изменения.

9.4 Примеры трансляторов, построенных в Yacc

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

Решение.

1 Лексический анализатор (lex.l).

Определяем класс “цифра”

dig [0-9]

%%

Если распознана лексема “Цифра”, то соответствующему полю переменной, хранящей значение атрибута, присваивается значение распознанной лексемы. Кроме этого, возвращается значение константы num.

{dig}+ begin

yylval.yyreal: =strtofloat(yytext);

returni(num);

end;

Если распознана лексема “символ +”, то возвращаем код этого символа, используя функцию returnc(< символ>). Для остальных символов производим аналогичные действия.

\+ returnc('+');

\- returnc('-');

\* returnc('*');

\/ returnc('/');

\(returnc('(');

\) returnc(')');

Заметим, что приведенный текст не имеет фрагментов, необходимых для формирования модуля. Это связано с тем, что файл lex.pas будет включен в другой модуль.

2 Синтаксический анализатор (yacc.y).

Оформляем заголовок модуля

%{ unit yacc;

interface

uses lexlib, yacclib, dialogs;

%}

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

%left '+' '-'

%left '*' '/'

Определяем тип атрибутов используемых терминалов.

%token < real> num

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

%type < real> expr

%%

Часть определений на этом завершена. Теперь опишем продукции и семантические правила. После редукции по правилу 1 пользователь должен получить сообщение с вычисленным значением выражения.

goal: expr {showmessage(floattostr($1)); }

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

expr: expr '+' expr {$$: =$1+$3; }

| expr '-' expr {$$: =$1-$3; }

| expr '*' expr {$$: =$1*$3; }

| expr '/' expr {$$: =$1/$3; }

| '(' expr ')' {$$: =$2; }

| num

%%

Включаем в модуль yacc.pas файл lex.pas. При этом файлы должны находиться в одном каталоге.

(*$I lex.pas*)

В третьей части yacc-программы завершаем формирование модуля.

end.

После выполнения “yacc.exe yacc.y” YACC построит файл yacc.pas, содержащий функцию yyparse, представляющую собой синтаксический анализатор. Рассмотрим фрагменты кода анализатора.

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

const num = 257;

type YYSType = record case Integer of

1: (yyreal: real);

end;

var yylval: YYSType;

3 Текст основной программы.

Выполняем установки для работы лексического анализатора.

yymemoinit(memo1, memo2, memo2, memo2);

yyclear;

yylineno: =0;

Запускаем синтаксический анализатор.

yyparse;

Пример 2. Синтаксический анализатор должен распознавать идентификаторы. Результат его работы заключается в выдаче пользователю списка идентификаторов исходной строки без дубликатов и количество повторений идентификатора в исходной строке. Например, если исходная строка имеет вид “first second first fifth”, то результат имеет вид “first – 2 second – 1 fifth - 1”. Так как при работе со строковыми типами в YACC необходимо четко задавать их длину введем предположение, что длина имени идентификатора не более 5. Список идентификаторов будем хранить в массиве, поэтому предположим, что идентификаторов в строке не более 10.

Решение

1 Лексический анализатор. Предполагается, что в синтаксическом анализаторе будет объявлен тип myString и константа id этого типа.

L [A-Za-z]

%%

{L}+ begin

yylval.yymyString: =yytext;

returni(id);

end;

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

%{ unit yacc;

interface

uses lexlib, yacclib, dialogs;

type

Определяем строковый тип фиксированной длинны

myString=string[5];

Определяем тип, соответствующий элементу списка, то есть идентификатору и количеству его повторений во входной последовательности.

el=record

ident: myString;

amount: integer;

end;

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

arType=array[1..10] of el;

Описываем все переменные, которые будут необходимы в правилах, терминалы и нетерминалы.

var

point_ar: integer;

i: integer;

s: string;

f: boolean;

%}

%token < myString> id

%type < arType> list

%%

При редукции по первому правилу пользователю выводится вся информация из массива.

goal: list {s: ='';

for i: =1 to point_ar do

s: =s+'; '+$1[i].ident+' - '+inttostr($1[i].amount);

showmessage(s); }

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

При редукции по третьему правилу, имеющему вид listà e, никаких действий не выполняем (отсутствует семантическое правило).

list: list id {i: =1; f: =true;

while (i< =point_ar) and f do

begin

if $1[i].ident=$2

then

begin

$1[i].amount: =$1[i].amount+1;

f: =false;

end

else i: =i+1;

end;

if f

then

begin

inc(point_ar);

$1[point_ar].ident: =$2;

$1[point_ar].amount: =1;

end;

$$: =$1; }

|;

%%

(*$I lex.pas*)

initialization

point_ar: =0;

end.

9.5 Контрольные вопросы

1 Какой метод разбора используется в Yacc?

2 Что такое атрибутные грамматики?

3 Какие виды атрибутов могут быть в атрибутных грамматиках?

4 Что такое семантическое правило?

5 Для чего служит переменная yyLval? От чего зависит ее тип?

9.6 Задание

Реализовать грамматику, описанную в задании к лабораторной работе№ 5 с использование Yacc.

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

9.7 Защита лабораторной работы

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

На основе записей в объекте yyDbgMemo, произведенных в ходе работы транслятора, студент должен проиллюстрировать процесс сдвига и приведения при распознавании входной последовательности.