Порядок выполнения работы

1. Получить вариант задания у преподавателя.

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

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

4. Подготовить и защитить отчет.

5. Написать и отладить программу на ЭВМ.

6. Сдать работающую программу преподавателю.

Требования к оформлению отчета

Отчет должен содержать следующие разделы:

• Задание по лабораторной работе.

• Краткое изложение цели работы.

• Запись заданной грамматики входного языка в форме Бэкуса-Наура.

• Множества крайних правых и крайних левых символов с указанием шагов построения.

• Множества крайних правых и крайних левых терминальных символов.

• Заполненную матрицу предшествования для грамматики.

• Пример выполнения разбора простейшего предложения (по выбору).

• Текст программы (оформляется после выполнения программы на ЭВМ).

Основные контрольные вопросы

1. Какую роль выполняет синтаксический анализ в процессе компиляции ?

2. Какие типы грамматик существуют ? Как связаны типы грамматик и языков ?

3. Дайте определение приведенной грамматики, грамматики в нормальной форме Хомского.

4. Поясните правила построения дерева вывода грамматики.

5. Что такое грамматики простого предшествования ?

6. Как вычисляются отношения предшествования для грамматик простого предшествования ?

7. Что такое грамматика операторного предшествования ?

8. Как вычисляются отношения для грамматик операторного предшествования ?

9. Расскажите о задаче разбора. Что такое распознаватель языка ?

10. Расскажите об общих принципах работы распознавателя языка.

11. Что такое перенос, свертка. Для чего необходим алгоритм «перенос-свертка» ?

12. Как работает алгоритм «перенос-свертка» (объясните на своем примере) ?

Лабораторная работа № 4 Генерация и оптимизация объектного кода

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

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

Возможны два варианта: 1 – программа генерирует объектный код; 2 – программа реализует работу интерпретатора.

1. Программу рекомендуется построить из трех основных частей: первая часть - порождение дерева синтаксического разбора (по результатам лабораторной работы №3), вторая часть - реализация алгоритма порождения объектного кода по дереву разбора, и третья часть - оптимизация порожденного объектного кода. Результатам работы должна быть построенная на основании заданного предложения грамматики программа на объектном языке. В качестве объектного языка предлагается взять язык ассемблера для процессоров типа Intel 80x86 в реальном режиме (возможен выбор другого объектного языка по согласованию с преподавателем). Все встречающиеся в исходной программе идентификаторы считать простыми скалярными переменными, не требующими выполнения преобразования типов. Ограничения на длину идентификаторов и констант соответствуют требованиям предыдущей лабораторной работы.

2. Порождение дерева синтаксического разбора (по результатам лабораторной работы №3) и зпись этого дерева в виде ПОЛИЗ, далее вычисление результата по обратной польской записи.