Теория и реализация языков программирования



Конструктор лексических анализаторов LEX


Для автоматизации разработки ЛА было создано довольно много средств. Как правило, входным языком для них служат или праволинейные грамматики, или язык регулярных выражений. Одной из наиболее распространенных систем является LEX, работающий с расширенными регулярными выражениями. LEX-программа состоит из трех частей:

Объявления %% Правила трансляции %%

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

[abc]- либо a, либо b, либо c,
[a-z]- диапазон символов,
R*- 0 или более повторений регулярного выражения R,
R+- 1 или более повторений регулярного выражения R,
R1/R2- R1, если за ним следует R2,
R1|R2 - либо R1, либо R2,
R?- если есть R, выбрать его,
R$- выбрать R, если оно последнее в строке,
^R- выбрать R, если оно первое в строке,
[^R]- дополнение к R,
R{n,m}- повторение R от n до m раз,
{имя} - именованное регулярное выражение,
(R)- группировка.

Правила трансляции LEX-программ имеют вид

p_1 { действие_1 } p_2 { действие_2 } ................ p_n { действие_n }

где p_i - регулярное выражение, а действие_i - фрагмент программы, описывающий, какое действие должен сделать ЛА, когда образец p_i сопоставляется лексеме. В LEX действия записываются на Си.

Третья секция содержит вспомогательные процедуры, необходимые для действий. Эти процедуры могут транслироваться раздельно и загружаться с ЛА.

ЛА, сгенерированный LEX, взаимодействует с синтаксическим анализатором следующим образом. При вызове его синтаксическим анализатором ЛА посимвольно читает остаток входа, пока не находит самый длинный префикс, который может быть сопоставлен одному из регулярных выражений p_i. Затем он выполняет действие_i. Как правило, действие_i возвращает управление синтаксическому анализатору. Если это не так, то есть в соответствующем действии нет возврата, то ЛА продолжает поиск лексем до тех пор, пока действие не вернет управление синтаксическому анализатору.


Содержание  Назад  Вперед