Алексей Молчанов - Системное программное обеспечение. Лабораторный практикум

1. Лексический анализ исходного текста и построение таблицы лексем.

2. Синтаксический анализ по таблице лексем и построение дерева синтаксического разбора.

3. Построение списка триад по дереву синтаксического разбора.

4. Оптимизация списка триад методом свертки объектного кода.

5. Оптимизация списка триад методом исключения лишних операций.

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

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

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

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

Для программной реализации компилятора рекомендуется использовать язык программирования Object Pascal и систему программирования Borland Delphi. Возможно использовать другие языки и системы программирования по согласованию с преподавателем.

Компилятор рекомендуется построить из следующих составных частей:

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

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

3. Оптимизатор.

4. Генератор результирующего кода.

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

Рекомендуемый порядок выполнения работы представлен в табл. 5.1.

Пояснительная записка к курсовой работе должна содержать следующие разделы:

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

2. Задание по лабораторной работе (номер варианта и полное описание своего варианта).

3. Грамматика входного языка в одном из трех возможных видов:

• форма Бэкуса—Наура;

• форма с метасимволами;

• графическая форма.

4. Описание выбранного способа организации таблицы идентификаторов с обоснованием сделанного выбора.

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

6. Граф переходов или иное описание конечного автомата лексического анализатора.

7. Обоснование выбора класса КС-грамматик для построения синтаксического анализатора.

8. Описание синтаксического анализатора в зависимости от выбранного класса КС-грамматик (включая все необходимые управляющие таблицы и множества).

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

10. Описание используемого метода порождения результирующего кода.

11. Описание используемого метода оптимизации.

12. Информация об организации построенного компилятора, его разбиении на проходы, количество проходов в компиляторе.

13. Выводы по проделанной работе.

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

15. Текст программы компилятора.

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

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

Допускается для построения лексического и (или) синтаксического анализаторов использовать автоматизированные методы построения распознавателей (например на основе программ LEX и YACC) [2, 3, 7, 27, 35]. В этом случае не требуется приводить граф переходов конечного автомата (для лексического анализатора) и описание синтаксического анализатора.

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

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

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

Входной язык компилятора должен удовлетворять следующим требованиям:

• входная программа начинается ключевым словом prog (program) и заканчивается ключевым словом end.;

• входная программа может быть разбита на строки произвольным образом, все пробелы и переводы строки должны игнорироваться компилятором;

• текст входной программы может содержать комментарии любой длины, которые должны игнорироваться компилятором (вид комментария задан в варианте задания);

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

• должны быть предусмотрены следующие варианты операторов входной программы:

– оператор присваивания вида <���переменная>:=<���выражение>;