5 Нисходящий анализ методом рекурсивного спуска.

Для СА (синтаксический анализатор) используется автомат с магазинной (стековой) памятью (сокращенно МП-автомат) – это кортеж из семи элементов P=(Q,T,Г,d,q0,Z0,F) , где

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

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

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

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

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

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

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

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

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

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

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

Начальной конфигурацией МП-автомата P называется конфигурация вида (q0,w,Z0), где w T* , т.е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно распознать, а в стеке есть только начальный символ Z0 (в лекциях мы как

Процедуры рекурсивного спуска могут быть записаны, как это изображено на рисунке. В процедуре N для случая, когда имеется альтернатива N -> ui -> *e (не может быть более одной альтернативы, из которой выводится e), приведены два варианта 1.1 и 1.2. В варианте 1.1 делается проверка, принадлежит ли следующий входной символ FOLLOW(N). Если нет - выдается ошибка. Во втором варианте этого не делается, так что анализ ошибки откладывается на процедуру, вызвавшую N.

6 Транслирующие грамматики. Построение нисходящих МП-трансляторов.

Для СА (синтаксический анализатор) используется автомат с магазинной (стековой) памятью (сокращенно МП-автомат) – это кортеж из семи элементов P=(Q,T,Г,d,q0,Z0,F) , где

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

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

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

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

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

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

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

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

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

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

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

Начальной конфигурацией МП-автомата P называется конфигурация вида (q0,w,Z0), где w T* , т.е. управляющее устройство находится в начальном состоянии, входная лента содержит

цепочку, которую нужно распознать, а в стеке есть только начальный символ Z0 (в лекциях мы как правило использовали символ S). Заключительная конфигурация - это конфигурация вида (q,e,u), где q F, u Г* .

В таком автомате определены операции:

1) Над входной цепочкой:

-сдвиг

-держать

2) Над магазином:

-втолкнуть

-вытолкнуть

-не изменять

3) Над состоянием:

-перейти в новое состояние

-не изменять

Рассмотрим работу нисходящего распознавателя: входную цепочку можно представить в виде 2 частей: a b -|, где

a - обработанная часть цепочки (изначально пустая)

b – необработанная часть

Магазин содержит цепочку j, которая представляет собой символы языка и считается что j => *b (если так то считается что цепочка допускается). В начальный момент в магазине находится начальный нетерминал (S), и символ дна $.

Цепочку b можно представить в виде: t1 b‘ -|

Магазин можно представить в виде: t2 j‘ $

Если t1=t2, то t1 и t2 считаются обработанными и отбрасываются. Если t2 – нетерминал то его надо заменить на правую часть правила грамматики, которое определяет этот нетерминал.

Можно предложить вариант предсказывающего анализатра, когда каждому нетерминалу сопоставляется, вообще говоря, рекурсивная процедура и стек образуется неявно при вызовах этих процедур.

Процедуры рекурсивного спуска могут быть записаны, как это изображено на рисунке. В процедуре N для случая, когда имеется альтернатива N -> ui -> *e (не может быть более одной альтернативы, из которой выводится e), приведены два варианта 1.1 и 1.2. В варианте 1.1 делается проверка, принадлежит ли следующий входной символ FOLLOW(N). Если нет - выдается ошибка. Во втором варианте этого не делается, так что анализ ошибки откладывается на процедуру, вызвавшую N.

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

Один из способов задания транслятора – транслирующая грамматика. Транс. Грамматика содержит 2 типа терминалов:

1)из которых формируется цепочка входного языка

2)из которых формируется цепочка выходного языка (так называемые символы действия)

Пример:

E -> E+T {+}

E -> T

T -> T*P {*}

… {+} и {*} и есть символы действия. Если убрать все символы действия, то получится грамматика входного языка.

Т.о. если входная грамматика принадлежит классу LL(1) грамматик, то по ней можно построить нисходящий МП-транслятор. Магазинными символами будут являться нетерминалы, терминалы и символы действия. Входными символами: терминалы и концевой маркер.

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

i. A→α

Если α * ε, то ВЫБОР(i) = ПЕРВ(α)

Если α * ε, то ВЫБОР(i) = ПЕРВ(α) СЛЕД(α)

Если множества выбора для любых двух правил с одинаковой левой частью не пересекаются, то грамматики относятся к классу LL(1).

Для грамматик такого вида можно построить нисходящий МП-распознаватель.

Как находить множество первых:

ПЕРВ(t) = {t}

ПЕРВ(А):

Если есть A→ε, то ε включить в множество первых.

Если есть правило A→X1X2…Xn, то в множество первых для А надо добавить множество первых для X1. Если множество первых для X1 содержит ε, то добавить к нему множество первых для X2 и т.д.

A→α

ПЕРВ(α)

Если α=X1X2…Xn, то в первые α включается множество первых для X1. Если множество первых для X1 содержит ε, то добавить к нему множество первых для X2 и т.д.

Определение множества следующих:

СЛЕД(А)

B→αAβ – в множество следующих для А надо добавить множество первых для β. Если множество первых для β содержит ε, то к множеству следующих за А надо добавить множество следующих за В.

Пример:

S->AbB

S->d

A->CAb

A->Bl

B->CSD

B->e

C->a

C->ld