Лексический анализ

Лексический анализ
План
1. Основная задача
2. Классы лексем
3. Построение анализатора
4. Требования к таблице имен
5. Структуры данных
6. Реализация сканера
7. Блок-схема
Основная задача лексического анализа – разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, т.е. выделить эти слова из непрерывной последовательности символов.
Все символы входной последовательности с этой точки зрения разделяются на символы, принадлежащие каким-либо лексемам, и символы, разделяющие лексемы (разделители). В некоторых случаях между лексемами может и не быть разделителей. С другой стороны, в некоторых языках лексемы могут содержать незначащие символы (пробелы и комментарии). 

Классы лексем

Обычно все лексемы делятся на классы. Примерами таких классов являются:
• Служебные слова (одним типом или каждое служебное слово отдельным типом лексем, в который будет входить только одна лексема)
• Числа (целые, восьмеричные, шестнадцатиричные, действительные и т.д.),
• Идентификаторы,
• Строки.
• Другие литералы

Построение анализатора

Отдельно выделяются ключевые слова и символы пунктуации (иногда их называют символы-ограничители). Как правило, ключевые слова – это некоторое конечное подмножество идентификаторов. С точки зрения дальнейших фаз анализа лексический анализатор выдает информацию двух сортов:
На вход лексическому анализатору подается
• Текст исходной программы;
• Список зарезервированных слов языка;
• Список служебных символов и символов разделителей.

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

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

Требования к таблице имен

Таблица имен должна удовлетворять следующим требованиям
• Выполнять быстрый поиск;
• Быть динамически расширяемой;
• При обнаружении искомого имени возвращать адрес элемента таблицы;
• Добавлять новый элемент, если такого еще нет в таблице (когда разрешено);
• Хранить дополнительные атрибуты для контекстного анализа (например тип переменной, принадлежность ее области видимости);
• Иметь возможность хранить переменные достаточно большой длинны и при этом экономно использовать память. Иногда ограничения на длину переменной не вводят, но в идентификации участвуют только N первых символов.
• Возможно, иметь иерархическую структуру по областям видимости;
• Может быть, иметь несколько таблиц: для переменных, типов, имен подпрограмм, литералов и зарезервированных слов языка. Причем в последнюю добавлять конечно нельзя.

Структуры данных

Можно предложить следующую структуру данных для хранения лексемы

struct TTableMember{char *Name;
TType Type;
int FormalParams[10];
int VisibleRegion;
void *Value;
};

enum TTableType{tVarName, tProcName, tLiteral};

enum TLextType{ltName, ltLiteral, ltIF, ltTHEN,
ltELSE, ltWHILE, ltFOR, …};

struct TLexema{TLexType LexType;
TTableType NameTable;
int NinTable;
};