Построение лексических анализаторов

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

Алфавит автомата лексического анализатора – все множество однобайтовых (ASCII) или двухбайтовых (Unicode) символов. При записи правил обычно используются обобщающие нетерминалы вида «Буквы», «Цифры». В процессе распознавания может формироваться описываемый объект, например, литерал или идентификатор.

Пример. Распознаватель целых чисел. Синтаксическая диаграмма синтаксиса языка описывается синтаксической диаграммой (см. рисунок 6).

1 – начало разбора; 2 – распознан знак; 3 – целое; К – завершение разбора

Рисунок 6 – Синтаксическая диаграмма

По диаграмме строим таблицу переходов (см. таблицу 6), обозначая состояние ошибки символом «E». В таблице переходов указываем подпрограммы обработки, которые должны быть выполнены при осуществлении указанного перехода. При выполнении этих подпрограмм формируются указанные значения.

Таблица 6 – Таблица переходов

а) Подпрограммы обработки:

A0: Инициализация: Целое:= 0; Знак_числа:= «+».

А1: Знак_числа:= Знак

А2: Целое:= Целое*10 + Цифра

А3: Если Знак_числа = «-» то Целое:= -Целое Все-если

б) Диагностические сообщения:

Д1: «Строка не является десятичным числом»;

Д2: «Два знака рядом»;

Д3: «В строке отсутствуют цифры»,

Д4: «В строке встречаются недопустимые символы»

Обозначим: S – строка на входе автомата; Ind – номер очередного символа; q – текущее состояние автомата; Table – таблица, учитывающая символы завершения и другие символы.

Тогда алгоритм сканера-распознавателя можно представить следующим образом.

Ind:= 1

q:= 1

Выполнить А0