Программная реализация лексических анализаторов

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

Глава 3. Синтаксический анализ

3.1. Автомат с магазинной памятью

Автомат с магазинной (стековой) памятью (сокращенно МП-автомат) - это семерка P=(Q,T,Г,d,q₀,Z₀,F) , где

Q- конечное множество символов состояний, представляющих всевозможные состояния управляющего устройства;

T- конечный входной алфавит;

Г - конечный алфавит магазинных символов;

d- функция переходов - отображение множества Q x (T {e}) x Г в множество конечных подмножеств Q x Г* , т.е.d:Q x (T {e}) x Г -> {Q x Г*} ;

q₀ Q - начальное состояние управляющего устройства;

Z₀ Г- символ, находящийся в стеке в начальный момент (начальный символ);

F Q- множество заключительных состояний

Конфигурацией МП-автомата называется тройка (q,w,u) Q x T* x Г* , где

q- текущее состояние управляющего устройства;

w- неиспользованная часть входной цепочки; первый символ цепочки w находится под входной головкой; если we, то считается, что вся вхоная лента прочитана;

u- содержимое стека; самый левый символ цепочки u считается верним символом стека; если u=e, то стек считается пустым.

Такт работы МП-автомата P будем представлять в виде бинарного отношения |-, определенного на конфигурациях. Будем писать (q,aw,zu)|-(q`,w,vu) если множество d(q,a,Z) содержит (d`,v) , где q, q` Q, a T {e}, w T*, Z Г, u, v Г*.

Начальной конфигурацией МП-автомата P называется конфигурация вида (q₀,w,Z₀), где w T* , т.е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно распознать, а в стеке есть только начальный символ Z₀ . Заключительная конфигурация - это конфигурация вида (q,e,u), где q F, u Г* .

Говорят, что цепочка w допускается МП-автоматом P, если (q₀,w,Z₀)|-*(q,e,u) для некоторых q F и u Г* . Языком, определяемым (или допускаемым) автоматом P (обозначается L(P) ), называют множество цепочек, допускаемых автоматом P. Иногда допустимость определяют несколько иначе: цепочка допускается МП-автоматом P, если (q₀,w,Z₀)|-*(q,e,e). Эти определения эквивалентны.

3.2. Таблично-управляемый предсказывающий разбор

3.2.1. Алгоритм разбора сверху-вниз

Основная проблема предсказывающего разбора - определение правила вывода, которое нужно применить к нетерминалу. Процесс предсказывающего разбора (сверху-вниз) с точки зрения построения дерева разбора можно проиллюстрировать рис. 3.1. Фрагменты недостроенного дерева соответствуют сентенциальным формам вывода. Вначале дерево состоит только из одной вершины, соответствующей аксиоме S. В этот момент по первому символу входного потока предсказывающий анализатор должен определить правило S -> X₁X₂..., которое должно быть применено к S. Затем необходимо определить правило, которое должно быть применено к X₁, и т.д., до тех пор, пока в процессе такого построения сентенциальной формы, соответствующей левому выводу, не будет применено правило Y -> a... . Этот процесс затем применяется для следующего самого левого нетерминального символа сентенциальной формы.

На рис.3.2 приведена структура предсказывающего анализатора, который определяет очередное правило из таблицы. Такую таблицу множно построить непосредственно из грамматики.

Таблично-управляемый предсказывающий анализатор имеет входной буфер, таблицу анализа и выход. Входной буфер содержит распознаваемую строку, за которой следует $ - правый концевой маркер, признак конца строки. Магазин содержит последовательность символов грамматики с $ на дне. Вначале стек содержит начальный символ грамматики на верхушке и $ на дне. Таблица анализа - это двумерный массив M[A,a] , где A - нетерминал, и a - терминал или символ $.

Анализатор управляется программой, которая работает следующим образом. Она рассматривает X - символ на верхушке стека и a - текущий входной символ. Эти два символа определяют действие анализатора. Имеются три возможности.

Если X=a=$ , анализатор останавливается и сообщает об успешном окончании разбора.

Если X=a#$ , анализатор удаляет X из стека и продвигает указатель входа на следующий входной символ.

Если X - нетерминал, программа заглядывает в таблицу M[X,a] . По этому входу хранится либо правило для X, либо ошибка. Если, например, M[X,a]=(X -> UVW) , анализатор заменяет X на верхушке стека на WVU {на верхушке U }. Будем считать, что анализатор в качестве выхода просто печатает использованные правила вывода. Если M[X,a]=error , анализатор обращается к подпрограмме анализа ошибок.

Поведение анализатора может быть описано в терминах конфигураций автомата разбора.

Алгоритм 3.1. Нерекурсивный предсказывающий анализ.

Repeat X := верхний символ стека;

if X - терминал или $

then if X = InSym

then удалить X из стека;

InSym := очередной символ;

else error()

end

else /*X = нетерминал*/

if M[X,InSym]=X -> Y₁Y₂...Y_k

then удалить X из стека;

поместить Y_k, Y_k-1,...,Y₁ в стек (Y₁ на верхушку);

вывести правило X -> Y₁Y₂...Y_k

else error() /*вход таблицы M пуст*/

end

end

Until X = $ /*стек пуст*/

Рис. 3.3

Вначале анализатор находится в конфигурации, в которой стек содержит S$ , (S - начальный символ грамматики), во входном буфере w$ (w - входная цепочка), переменная InSym содержит первый символ входной строки. Программа, использующая таблицу анализатора M для осуществления разбора, изображена на рис.3.3.

Пример 3.1. Рассмотрим грамматику арифметических выражений:

Таблица предсказывающего анализатора для нее изображена на рис.3.4. Здесь пустые клетки - входы ошибок. Непустые дают правила, по которым делается развертка нетерминала.

На входе id+id*id предсказывающий анализатор совершает последовательность шагов, изображенную на рис.3.5. Указатель входа указывает на самый левый символ в колонке Вход. Если внимательно проанализировать действия анализатора, то видно, что он осуществляет левый вывод, т.е. правила применяются в соответствии с левым выводом. За уже просмотренными входными символами следуют символы грамматики в стеке (сверху вниз), что соответствует левым сентенциальным формам вывода. Дерево разбора приведено на рис. 3.6.