Для лексического анализа был построен детерминированный конечный автомат. Для этого сначала были построены регулярные выражения:
1. Идентификатор: (буква)(буква|цифра)*
2. Число: (цифра)+(( , | .)(цифра)+)?
3. Точка: .
4. Запятая: ,
5. Знак сложения: +
6. Знак вычитания: -
7. Знак умножения: *
8. Знак деления: /
9. Открывающая скобка: (
10. Закрывающая скобка: )
11. Знаки сравнения: >|<|=
12. Точка с запятой: ;
13. Знак двоеточие: :
14. Знак присваивания: :=
Лексический анализатор проверят каждый идентификатор на совпадение с ключевым словом. Если совпадение найдено, то идентификатор распознается как ключевое слово, в противном случае, он распознается как идентификатором. В данном подмножестве языка Паскаль ключевыми словами являются:
1. var
2. begin
3. end
4. read
5. write
6. while
7. do
8. if
9. then
10. else
11. or
12. and
Все регулярные выражения были преобразованы в недетерминированные конечные автоматы. Основные из них представлены на рисунках 2.1–2.7.
Рисунок 2.1 – НКА для точки
Рисунок 2.2 – НКА для запятой
Рисунок 2.3 – НКА для точки с запятой
Рисунок 2.4 – НКА для знаков сравнения
Рисунок 2.5 – НКА для знака присваивания
Рисунок 2.6 – НКА для числа
Рисунок 2.7 – НКА для идентификатора
Далее недетерминированные конечные автоматы были детерминированы. Основные из полученных детерминированных конечных автоматов представлены на рисунках 2.8–2.9. Шаги преобразования представлены в таблицах 1–2.
Таблица 1– Преобразование идентификатора
Буква
Цифра
{0}
{1,2,4,6,7}
–
{1,2,4,6,7}
{3,6,7,1,2,4}
{5,6,7,1,2,4}
{3,6,7,1,2,4}
{3,6,7,1,2,4}
{5,6,7,1,2,4}
{5,6,7,1,2,4}
{3,6,7,1,2,4}
{5,6,7,1,2,4}
Рисунок 2.8 – ДКА для идентификатора
Таблица 2 – Преобразование числа
Цифра
.
,
{1}
{2,3,5,1,9}
–
–
{2,3,5,1,9}
{2,3,5,1,9}
{4,7}
{6,7}
{4,7}
{8,9,7}
–
–
{6,7}
{8,9,7}
–
–
{8,9,7}
{8,9,7}
–
–
Рисунок 2.9 – ДКА для числа
Следующим шагом построения конечного автомата является минимизация. При минимизации конечного автомата все состояния делятся на две группы: финальные и нефинальные. Затем выполняется следующая процедура. Рассматриваем группу {S1, S2, …, Sk} и некоторый входной символ а. Если по этому входному символу есть переходы в разные группы, то исходную группу разбивают на части. Принадлежность Si к той или иной части зависит от того, в какую группу существует переход из состояния Si по входному символу а. Эта процедура продолжается до тех пор, пока не останется ни одной группы, которую можно было бы разбить по какому-либо входному сигналу. Результаты минимизации представлены на рисунках 2.10-2.11
Рисунок 2.10 – МКА для идентификатора
Рисунок 2.11 – МКА для числа
Все минимизированные ДКА были объединены в один автомат. Результат объединения представлен на рисунке 2.12. Это автомат далее используется в лексическом анализе.
Рисунок 2.12 – ДКА для подмножества языка Паскаль
Код лексического анализатора представлен в приложении А.
3 Синтаксический анализатор
Одним из средств автоматизированного построения трансляторов является генератор компиляторов Yacc.
Yacc строит синтаксический анализатор, работающий на основе метода “сдвиг - приведение”.
Этот генератор работает с атрибутными грамматиками. Атрибутные грамматики характеризуются тем, что с каждым грамматическим символом связывается множество атрибутов.
Атрибуты в атрибутных грамматиках могут быть двух видов: синтезируемые и наследуемые. Синтезируемые атрибуты вычисляют свои значения, используя только значения атрибутов потомков. Наследуемые атрибуты при вычислении значений используют значения атрибутов соседей и родителей.
С каждой продукцией атрибутной грамматики связывается семантическое правило. Такие правила выполняются в тот момент, когда происходит приведение по соответствующей продукции.
Исходный текст для yacc состоит из трех частей: определения, продукции и вспомогательные процедуры. Части разделяются символами %%.
В части определений можно указать код, который должен быть перенесен в текст результирующего транслятора без изменения. Для этого он помещается между символами %{ и %}.
Часть определений включает следующие разделы.
1 Задание стартового символа.
%start символ
Если такое определение отсутствует, то в качестве стартового символа используется нетерминал левой части первой продукции.
2 Определение атрибутов терминалов грамматики.
%token <тип атрибута> терминал
При наличии такого определения в исходном тексте, в модуле, содержащем транслятор, декларируется константа указанного типа с именем, соответствующим терминалу. Эти константы используются в исходном файле Lex без дополнительных объявлений..
3 Задание ассоциативности операций.
%left символ – лево ассоциативная операция
%right символ – право ассоциативная операция
%noassoc символ – неассоциативная операция
Приоритет операции определяется ее положением при определении. Чем ниже задана операция при определении, тем выше ее приоритет.
4 Задание типов атрибутов нетерминалов
%type <тип атрибута> нетерминал.
Вторая часть Yacc-программы содержит продукции и связанные с ними семантические правила. Левая часть продукции отделяется от правой символом “:”.
Семантические правила записываются на языке Pascal и следуют за продукцией, заключенные между символами “{” и “}”. Для обращения в семантических правилах к атрибуту нетерминала левой части продукции используют символы $$. Для обращения к атрибутам грамматических символов правой части продукций используются символы $i, где i – номер грамматического символа в продукции.
Если для одного и того же нетерминала левой части существует несколько продукций, то это записывается следующим образом.
нетерминал : продукция 1 {семантическое правило 1}
…
| продукция n {семантическое правило n}
Третья часть Yacc-программы содержит вспомогательные процедуры. Эта часть переносится в результирующий код без изменения.
Код синтаксического анализатора представлен в приложении Б.
Семантические правила строились на основе следующей грамматики:
1. GOAL → VARZONE PROGZONE
2. VARZONE → key_var id LIST_ID dp typ tz VARZONE1
3. |ε
4. VARZONE1→ id LIST_ID dp typ tz VARZONE1
5. |ε
6. LIST_ID → zpt id LIST_ID
7. |ε
8. PROGZONE → key_begin COMMANDS key_end tchk
9. COMMANDS →COMMAND tz COMMANDS
10. |ε
11. COMMAND → BLOCK
12. |PRISVCOM
13. |READCOM
14. |WRITECOM
15. |WHILECOM
16. |IFCOM
17. PRISVCOM → id prisv EXPR
18. READCOM → key_read os id zs
19. WRITECOM → key_write os id zs
20. WHILECOM → key_while BOOL key_do BLOCK
21. IFCOM → key_if BOOL key_ then IF_INSTR ELSECOM
