Функции компилятора как системной обрабатывающей программы. Этапы компиляции: анализ и синтез. Разработка лексического анализатора. Алгоритм и программа лексического анализа. Реализация двухфазного компилятора. Описание логической структуры программы.
Аннотация к работе
По классификации программного обеспечения ЭВМ компиляторы относятся к системным обрабатывающим программам. В процессе перевода в программе выделяются и изменяются такие уровни или слои как алфавит, лексика, синтаксис при сохранении семантики. Алфавит - набор допустимых символов и знаков, из которых строятся элементарные конструкции языка. Слова (лексемы) объединяются в предложения (операторы) согласно правилам синтаксиса.Задание можно разделить на 3 части: лексический анализ, синтаксический анализ, разработка компилятора в целом Следует отметить, что идентификатор может начинаться только с буквы, следующие символы могут быть как буквы, так и цифры и знак подчеркивания (‘_’). Лексический анализатор должен различить следующие ключевые слова: ‘program’, ‘var’, ‘integer’, ‘begin’, ‘repeat’, ‘until’, ‘end’, и записать их в таблицу терминальных символов. Необходимо, чтобы лексический анализатор правильно различал константы и различал их тип (16-ричная константа, римская константа) и записывал тип в таблицу констант. Константа считается римской, если она состоит из знака и символов ‘X’,’V’ и ‘I’ и образована по правилам составления римских констант.Для хранения таблицы имен используется массив из записей Const_tab, содержащих следующие элементы: Номер лексемы. Путь к элементу по дереву (последовательность левых и правых ветвей, которые необходимо пройти, чтобы достичь данного элемента). Для хранения таблицы имен используется массив из записей Term_tab, содержащих следующие элементы: Номер лексемы. Путь к элементу по дереву (последовательность левых и правых ветвей, которые необходимо пройти, чтобы достичь данного элемента). Для хранения таблицы констант используется массив из записей Id_tab, содержащих следующие элементы: Ссылка на элемент цепочки.Автоматными или регулярными грамматиками называются грамматики, продукции которых имеют одну из двух форм: Праволинейная Леволинейная Грамматику лексических единиц обычно явно не описывают, а строят эквивалентный ей граф распознавания лексических единиц.1 - промежуточное состояние, соответствующее продолжению формирования имени; 2 - конечное состояние, соответствующее выделению правильного идентификатора;1 - промежуточное состояние, обозначающее, что распознан символ начала константы ‘$’; 2 - промежуточное состояние, обозначающее, что распознан знак константы, и продолжение формирования константы;В соответствии с приведенными правилами, сформируем ряд ограничений для автомата-распознавателя: Символ X может встречаться в начале строки от 1 до 3 раз подряд (см. правило 3). Символ V может встречаться не более 1 раза в начале строки и после 1 или более символов X (см. правило 3). Символ I может встречаться от 1 до 3 раз подряд в начале строки, а также в конце правильной строки, образованной символами X и V (см. ограничения 1 и 2, правило 3). Символ X может встречаться в конце строки 1 раз после символа I, если перед последним находятся только символы X или ничего (иначе будет нарушено правило 2 - неизвестно, к какому символу будет относиться символ I). Символ V может встречаться в конце строки 1 раз после символа I, если перед последним находятся только символы X (аналогично ограничению 4). рис.4.Объединенный автомат является соединением приведенных выше автоматов при общем начальном состоянии S.Непосредственно лексический анализ представляет собой 2 этапа: выделение лексем и их распознавание.Процесс выделения лексем состоит в просмотре входной строки по одному символу и в случае обнаружения символа-разделителя формирование лексемы. При чтении очередного символа сначала проверяется, является ли он разделителем. Если это не так, то разделитель считается частью текущей лексемы и продолжается процесс ее формирования.Последовательно определяется тип каждой лексемы с помощью соответствующих распознавателей. Каждая лексема добавляется в таблицу кодов лексем и в соответствующую типу таблицу (констант, имен, терминальных символов). Если лексема ошибочна (т.е. не принадлежит ни одному из вышеназванных типов), то в таблице кодов лексем ей присваивается тип Е, обозначающий ошибку. множество состояний, свидетельствующих об ошибке в лексеме; Если лексема ошибочна, то она заносится в таблицу кодов лексем с типом E и выдается сообщение об ошибке (процедура Err_Lex).
План
Содержание
Введение
1. Анализ задания
2. Разработка лексического анализатора
2.1 Выбор и обоснование структур данных
2.2 Разработка автоматных грамматик для распознавания лексем
2.3 Разработка автоматов, работающих по правилам грамматики
2.3.1 Автомат для распознавания имен
2.3.2 Автомат для распознавания 16-ричных констант
2.3.3 Автомат для распознавания римских констант
2.3.4 Объединенный автомат
2.4 Разработка алгоритма и программы лексического анализа
2.4.1 Выделение лексем
2.4.2 Распознавание лексем
2.4.3 Реализация лексического анализатора
2.4.4 Тестирование лексического анализатора
3. Разработка синтаксического анализатора
3.1 Уточнение грамматики языка применительно к варианту задания
3.2 Разработка алгоритма синтаксического анализа
3.3 Алгоритмы распознающих функций
3.3.1 Функция Lex_Progr
3.3.2 Функция Lex_Descr_List
3.3.3 Функция Lex_Descr
3.3.4 Функция Lex_Name_List
3.3.5 Функция Lex_Oper_List
3.3.6 Функция Lex_Assign
3.3.7 Функция Lex_Exp
3.3.8 Функция Lex_Simple_Exp
3.3.9 Функция Lex_Term
3.3.10 Функция Lex_mnozh
3.3.12 Функция Lex_Body
3.4 Тексты распознающих процедур
3.5 Результаты тестирования синтаксического анализатора
4. Реализация двухфазного компилятора
4.1 Результаты тестирования двухфазного компилятора
5. Описание программы
5.1 Общие сведения и функциональное назначение
5.2 Вызов и загрузка
5.3 Входные данные
5.4 Выходные данные
5.5 Описание логической структуры программы
5.5.1 Файлы программы
5.5.2 Общее описание работы программы
Список использованной литературы
Введение
По классификации программного обеспечения ЭВМ компиляторы относятся к системным обрабатывающим программам. Их функцией является перевод программы с языка высокого уровня в машинный код. В процессе перевода в программе выделяются и изменяются такие уровни или слои как алфавит, лексика, синтаксис при сохранении семантики.
Алфавит - набор допустимых символов и знаков, из которых строятся элементарные конструкции языка. Отдельные знаки объединяются в лексемы.