Лексический анализатор
Техническое задание
на выполнение лабораторной работы №1
по курсу «Методы трансляции»
на тему: «Лексический анализатор»
Постановка задачи
Первый шаг в конструировании Вашего компилятора - это разработка лексического анализатора (ЛА) для подмножества языка ПАСКАЛЬ.
Разработать лексический анализатор (ЛА) для подмножества языка Паскаль. ЛА должен распознавать правильные слова (лексемы), формируя при этом диагностику неправильных слов и таблицу лексем. Результаты должны быть в наглядном виде предоставлены проверяющему.
Ограничения на входные данные
Классы лексем Паскаля:
1. Классы ключевых слов:
AND ARRAY BEGIN FORWARD DIV DO ELSE END FOR FUNCTION IF MOD NOT OF OR PROCEDURE PROGRAM RECORD THEN TO TYPE VAR WHILE
2. Классы предопределенных слов:
CHAR INTEGER
3. Классы специальных символов, имеющих фиксированную семантику:
+ - * = < <= > >= <>.,:;
:=.. () [ ]
4. Класс остальных символов, не имеющих фиксированной семантики.
5. Класс идентификаторов, определяемый следующим регулярным выражением:
letter (letter | digit | _)*
где
letter - латинская буква
digit - цифра.
6. Классы констант:
а) Целые константы задаются регулярным выражением:
digit+
б) Строковые константы, определяемые рег. выражением:
' char* '
где char - любой символ.
Таблица лексем
Каждая лексема заносится в таблицу лексем. При этом для повышения эффективности используем HASH-функцию. В таком случае таблица лексем распадается на 3 части:
1) HASH-таблица, содержащая различные значения HASH-функции и ссылки на таблицу имен.
2) Таблица имен лексем.
3) Таблица атрибутов лексем.
Общие Требования к ЛА
1. Игнорировать "пустые" символы (знаки пробела, табуляции и признаки конца строки или файла) и комментарии.
2. Не различать большие и маленькие латинские буквы в ключевых словах и идентификаторах.
3. Выделять слово из текста путем обнаружения его первого и последнего символов. Первый символ слова - это первый символ, отличный от "пустого". Последний символ слова - это символ, расположенный перед символом-ограничителем. Множество символов-ограничителей ПАСКАЛЯ должно быть Вами определено.
4. Определять класс лексемы по ее префиксу.
Синтаксический анализатор
Второй шаг в конструировании Вашего компилятора - это разработка синтаксического анализатора (СА) для подмножества языка ПАСКАЛЬ. СА должен определять правильность порядка правильных слов (лексем) в предложении, формируя при этом диагностику синтаксических ошибок и дерево разбора. Результаты должны быть в наглядном виде предоставлены проверяющему.
Грамматический (синтаксический) разбор предложения (в нашем случае - программы на ПАСКАЛЕ) проводить методом Рекурсивного Спуска.
Грамматика подмножества языка ПАСКАЛЬ задана в виде Расширенных Бэкусо-Науровских Форм (РБНФ) с использованием следующих обозначений:
| Обозначение | Смысл |
| ::= | "по определению есть" |
| | | "или" (задание альтернативы) |
| [X] | 0 или 1 раз появление X |
| {X} | 0 или более раз появление X |
| (X|Y) | выбор: или X или Y |
| xyz | терминальный символ xyz (подчеркнуто жирный) |
| Определение_типов | нетерминальный символ "Определение_типов" (курсивом) |
программа::= Program ID; Блок.
Блок::= [ Определение_типов ]
[ Определение_констант ]
[ Объявление_переменных ]
[ Объявление_процедур_и_функций ]
Составное_действие
| Определение_типов | ::= | Type Определение_типа; { Определение_типа; } |
| Определение_констант | ::= | Const Определение_константы; { Определение_константы; } |
| Объявление_переменных | ::= | Var Объявление_переменной; { Объявление_переменной;} |
| Объявление_процедур_и_функций | ::= | {(Объявление_процедуры | Объявление_функции);} |
| Определение_типа | ::= | ID = Тип |
| Определение_константы | ::= | ID = Константа |
| Объявление_переменной | ::= | Список_идентификаторов: Тип |
| Объявление_процедуры | ::= | Procedure ID (Список_формальных_параметров); (Блок | Forward) |
| Объявление_функции | ::= | Function ID (Список_формальных_параметров): Тип_результата; (Блок | Forward) |
| Список_формальных_параметров | ::= | [ Список_идентификаторов: ID {; Список_идентификаторов: ID } ] |
| Составное_действие | ::= | begin Последовательность_действий end |
| Последовательность_действий | ::= | Действие {; Действие } |
| Действие | ::= | Простое_действие | Сложное_действие |
| Простое_действие | ::= | [ (Действие_присваивания | Действие_вызова_процедуры) ] |
| Действие_присваивания | ::= | Переменная:= Выражение |
| Действие_вызова_процедуры | ::= | ID (Список_фактических_параметров) |
| Сложное_действие | ::= | Составное_действие | IF Выражение THEN Действие [ ELSE Действие ]1 | WHILE Выражение DO Действие | FOR ID:= Выражение TO Выражение DO Действие |
| Тип | ::= | ID | ARRAY [ Диапазон_индекса ] OF Тип | RECORD Список_полей END | Константа.. Константа |
| Диапазон_индекса | ::= | ID | Константа.. Константа |
| Тип_результата | ::= | ID |
| Список_полей | ::= | [ Список_идентификаторов: Тип {; Список_идентификаторов: Тип } ] |
| Константа | ::= | [ Знак ] INT | STRCONST |
| Выражение | ::= | Простое_выражение [ Знак_отношения Простое_выражение ] |
| Знак_отношения | ::= | < | <= | > | >= | <> | = |
| Простое_выражение | ::= | [ Знак ] Слагаемое { Аддитивная_операция Слагаемое } |
| Аддитивная_операция | ::= | + | - | or |
| Слагаемое | ::= | Множитель { Мультипликативная_операция Множитель } |
| Мультипликативная_операция | ::= | * | div | mod | and |
| Множитель | ::= | INT | STRCONST | Переменная | Вызов_функции | not Множитель | (Выражение) |
| Вызов_функции | ::= | ID (Список_фактических_параметров) |
| Переменная | ::= | ID Выбор_компоненты |
| Выбор_компоненты | ::= | [ (. ID Выбор_компоненты | [ Выражение ] Выбор_компоненты) ] |
| Список_фактических_параметров | ::= | [ Выражение {, Выражение } ] |
| Список_идентификаторов | ::= | ID {, ID } |
| Знак | ::= | + | - |
В приведенной РБНФ почти все терминалы соответствуют реальным словам и знакам исходной программы на ПАСКАЛЕ. Исключение составляют лишь следующие терминалы:
ID - произвольный идентификатор программы
INT - произвольная целая константа программы
STRCONST - произвольная строковая константа программы
Семантический анализатор
Очередной(третий) шаг в конструировании Вашего компилятора - это разработка семантического анализатора (СемА) для подмножества языка ПАСКАЛЬ. СемА должен:
1. Завершить проверку корректности программы, начатую на этапах ЛА и СА:
а) осуществить контроль типов в выражениях и операторе присваивания;
б) реализовать контроль использования имен в рамках одного блока: отсутствие дубликатов имен (т.е., отсутствие повторного объявления имени); обязательное объявление имени перед его использованием; использование имени в соответствии с его объявлением.
2. Собрать информацию, необходимую для генерации кода:
а) сформировать таблицу атрибутов
- для выражений конструкторов типа
- для имен переменных
- для значений и имен констант;
б) построить Абстрактное Дерево Разбора.
Результатами СемА являются:
- диагностика семантических ошибок
- обновленная таблица лексем (таблица атрибутов)
- абстрактное дерево разбора.
Результаты должны быть в наглядном виде предоставлены проверяющему.
СемА представляет собой набор семантических действий, вызываемых по мере прохождения СА. Сем. действия вызываются после чтения не каждой лексемы, а лишь после "важной", значимой с точки зрения СемА лексемы. Решает какая лексема "важна", какая нет - разработчик СемА. Обычно "важные" лексемы - это ID, константы, знаки операций (имена действий) и некоторые, но не все ключевые слова.
Как правило, встретив "важную" лексему, находящуюся в начале или середине правой части правила, семантическое действие накапливает необходимую информацию в одном или нескорльких Семантических Стеках. По достижении конца правой части правила накопленная информация обрабатывается семантическим действием.
Т.о. для того, чтобы разработать СемА, вначале нужно расставить метки-обозначения сем. действий по "важным" символам правых частей правил грамматики, а затем проставить в соответствующих местах СА вызовы семантических процедур и функций.