Разработка лексического анализатора

Введение

По классификации программного обеспечения ЭВМ компиляторы относятся к системным обрабатывающим программам. Их функцией является перевод программы с языка высокого уровня в машинный код. В процессе перевода в программе выделяются и изменяются такие уровни или слои как алфавит, лексика, синтаксис при сохранении семантики.

Алфавит - набор допустимых символов и знаков, из которых строятся элементарные конструкции языка. Отдельные знаки объединяются в лексемы.

Лексема - отдельная неделимая конструкция, имеющая смысл.

Слова (лексемы) объединяются в предложения (операторы) согласно правилам синтаксиса.

Синтаксис - описание правильных конструкций языка или правил получения правильных конструкций языка.

Компиляция состоит из этапов анализа и синтеза. В анализ входит лексический, синтаксический и семантический анализ.

Лексический анализ состоит из распознавания лексем, их классификации и определения правильности.

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

Анализ задания

Задание можно разделить на 3 части: лексический анализ, синтаксический анализ, разработка компилятора в целом

Лексический анализ включает этапы:

преобразование исходного текста в длинную строку;

выделение лексических единиц (лексем);

распознавание типов лексем;

добавление лексем в соответствующие таблицы;

сохранение таблиц в виде файлов.

В данном задании используются следующие типы лексем:

идентификаторы;

ключевые слова;

16-ричные и римкие константы;

знаки операций;

разделители.

Идентификаторы (имена)

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

В данном задании встречаются следующие идентификаторы:

‘var15’, ‘n’. Их следует записать в таблицу идентификаторов.

Ключевые слова

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

Лексический анализатор должен различить следующие ключевые слова:

‘program’, ‘var’, ‘integer’, ‘begin’, ‘repeat’, ‘until’, ‘end’, и записать их в таблицу терминальных символов.

Константы.

В данном задании встречаются как 16-ричные, так и римские константы. Необходимо, чтобы лексический анализатор правильно различал константы и различал их тип (16-ричная константа, римская константа) и записывал тип в таблицу констант.

Константа считается римской, если она состоит из знака и символов ‘X’,’V’ и ‘I’ и образована по правилам составления римских констант. Она считается 16-ричной, если начинается с символа ‘$’ и знака и состоит из цифр и букв ‘A’. ’F’. Константы могут быть как положительными, так и отрицательными, это зависит от знака после символа ‘$’.

Лексический анализатор должен различить константы:

‘$+00’, ‘$-0A’ - как 16-ричные;

‘-XII’ - как римскую.

Эти лексемы он должен записать в таблицу констант с указанием их типа (’16-рич. ’ - для 16-ричной константы, ’римск. ’ - для римской константы) и указанием десятичной формы.

Знаки операций.

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

В данном задании встречаются следующие операции:

Односимовольные: ‘-’, ‘<’;

Двухсимвольные: ‘: =’.

Разделители.

К ним относятся специальные символы, разделяющие конструкции языка, например:; |, |. | (|) | пробелы | символы табуляции и перехода на новую строку. Они могут либо возвращаться в синтаксический анализатор в качестве лексем, либо только указывать на окончание предыдущей лексемы и пропускаться при вводе следующей. Некоторые из этих символов одновременно могут играть роль терминальных символов в грамматическом описании отдельных конструкций языка.

В данном задании встречаются следующие разделители:

‘; ’, ‘: ’, ‘. ’,’ (‘,’) ’.

Границами лексем являются разделители, знаки операций, пробелы.

В процессе синтаксического анализа решаются две задачи:

распознавание предложений языка;

определение правильности конструкций.

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

В процессе синтаксического анализа всего исходного текста в целом и каждого предложения в отдельности возможно два направления движения по цепочке правил: сверху вниз и снизу вверх.

В процессе синтаксического анализа строится дерево грамматического разбора для каждого предложения. Это дерево строится от начального к конечному символу или наоборот.

Дерево вывода состоит из начального (корневого) узла. В него включают еще промежуточные узлы и внешние узлы.

Каждой ветви соответствует одно из правил грамматики.

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

Выходные данные - сообщение об успешном завершении анализа или сообщение об имеющихся ошибках.

Разработка лексического анализатора