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

Министерство образования Российской Федерации

Новосибирский государственный технический университет

Кафедра прикладной математики

Лабораторная работа №3,4

по курсу «Языки программирования и трансляторы»

Факультет: ПМИ

Группа: ПМ-12

Студент: Дуркин Д.С., Марков В. В., Хиценко Е.В.

Преподаватель: Полетаева И.А., Еланцева И.Л.

Новосибирск

2004 г.

1.  Задание:

В ЛР2 необходимо реализовать синтаксический анализатор с использованием одного из табличных методов (LL-, LR-метод ,  метод предшествования). Результатом работы синтаксического анализатора является дерево разбора или постфиксная запись.

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

2.  Вариант:

C2) Подмножество языка включает:

                                                       ► оператор цикла   while  ;

                                                       ►логические выражения;

                                                       ►арифметические выражения;

                                                       ►инструкции присваивания.

3.  Реализация

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

Уточним состав языка:

Арифметические выражения имеют вид: op1 | op1+op2 | op1-op2

Логические выражения имеют вид: op1>op2 | op1<op2

В случае op1 | op1+op2 | op1-op2 в условии while выражение считается ложным, если оно нулевое, и истинным в остальных случаях.

Телом цикла для while является один оператор: либо еще один вложенный цикл, либо инструкция присваивания. Допускается 9 уровней вложенности цикла.

Исходная грамматика языка:

, где P – язык логических выражений,

A – язык арифметических выражений,

Id – язык идентификаторов.

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

Проверим, принадлежит ли эта грамматика к классу LL1:

Массив пустых строк:

Матрица предшествования:

Матрица следования: