Способы построения лексических анализаторов

Лексические ошибки

На уровне лексического анализатора определяются только некоторые ошибки, поскольку лексический анализатор рассматривает исходный текст программы в ограниченном контексте. Если в программе на языке С строка fi впервые встретится в контексте

fi (a == f(x))...

лексический анализатор не сможет определить, что именно представляет собой fi – неверно записанное слово if или необъявленный идентификатор функции. Поскольку fi является корректным идентификатором, лексический анализатор должен вернуть лексему для идентификатора и предоставить обработку ошибки другой части компилятора.

Лексический анализатор может не продолжать работу, поскольку ни один из шаблонов не соответствует оставшейся части входного потока. Простейшим выходом в этой ситуации будет восстановление в “режиме паники”. То есть просто пропускаются входные символы до тех пор, пока лексический анализатор не встретит распознаваемую лексему. Иногда это запутывает синтаксический анализатор, но для интерактивной среды данная технология может оказаться вполне подходящей.

Существуют и другие возможные действия по восстановлению после ошибки:

1. Удаление лишних символов.

2. Вставка пропущенных символов.

3. Замена не верного символа верным.

4. Перестановка двух соседних символов.

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

Имеется три основных способа реализации лексического анализатора.

1. Использование генератора лексических анализаторов, такого как LЕХ, для создания лексического анализатора по спецификациям, основанным на регулярных выражениях. В этом случае генератор предоставляет функции для чтения и буферизации ввода.

2. Написание лексического анализатора на подходящем языке программирования с использованием возможностей ввода – вывода этого языка для чтения входной информации.

3. Написание лексического анализатора на языке ассемблера и явное управление процессом чтения входной информации.

Эти методы перечислены в порядке усложнения их реализации. К сожалению, более трудные для реализации подходы часто дают более быстрые лексические анализаторы [3].

LEX — программа для генерации лексических анализаторов. Входной язык содержит описания лексем в терминах регулярных выражений. Результа­том работы LEX является программа на некотором языке программирования, которая читает входной файл (обычно это стандартный ввод) и выделяет из него последовательности символов (лексемы), соответствующие заданным регуляр­ным выражениям.

Принцип работы LEX достаточно прост: на вход ей подается текстовый файл, содержащий описания нужных лексем в терминах регулярных выражений, а на выходе получается файл с текстом исходной программы сканера, на заданном языке программирования (обычно — на С). Текст исходной программы сканера может быть дополнен вызовами любых функций из любых библиотек, поддер­живаемых данным языком и системой программирования. Таким образом, LEX позволяет значительно упростить разработку лексических анализаторов, практически сводя эту работу к описанию требуемых лексем в терминах регулярных выражений.

Дата добавления: 2014-12-27