Моделирование восходящего распознавателя.

0.Упорядочить редукции.

1. Инициализация: объявляем входную цепочку текущей вершиной дерева редукций;

2. Основной цикл.

Если текущая вершина равна Е, то УСПЕХ,

иначе если в текущей вершине есть нерассмотренный сын,

то он обьявляется текущей вершиной и goto2,

иначе ВОЗВРАТ

3 .ВОЗВРАТ: Если у текущей вершины есть отец

то он обьявляется текущим и goto2

иначе НЕУДАЧА

4. НЕУДАЧА:Входная цепочка Ï L(G) STOP.

5 .УСПЕХ: Пройти из вершины Е в обратном порядке и выписать все исполненные правила.

Этот алгоритм трудоемок и на практике не используется. Он плохо приспособлен для диагностики ошибок. Попытаемся сделать его безвозвратным. Для этого достаточно, чтобы по префиксу цепочки однозначно выделялась основа, и грамматика была обратимой (т.е. нет двух правил A ® b, B ® b с одинаковой правой чпастью). Если КС-грамматика G является LR (k)- грамматикой или грамматикой простого предшествования, то основу можно определить однозначно Þ однозначно определяется терминал Þ безвозвратный алгоритм.

4.6. Грамматики простого предшествования (ГПП). (АУ-455,462)

Отношения предшествования Вирта-Вебера для КС–грамматики G определены на парах X, Y Î S = S_N È S_T следующим образом: 0. $⋖ X " X Î L (E), X ⋗$ " X Î R (E).

1. X ⋖ Y, если (A ® a XBb)Î P и B Þ⁺ Yg ~ Y Î L (B) (сначала Y м.б. свернуто до В, потом Х до А).

2. X ≐ Y, если (A ® aXYb)Î P, т.е. Х и Y обрабатываются при свертке одновременно.

3. X ⋗ a ÎS_T, если (A ® aBYb)Î P & [ B Þ⁺ gX ~ X Î R (B)] & [ Y Þ^* ad ~ a Î L (Y) ].

Грамматика называется грамматикой простого предшествования, если она приведенная, не содержит e – правил, обратимая (нет правил с одинаковыми правыми частями) и любые два символа связаны не более чем одним отношением предшествования.

Пример: Является ли G₀ грамматикой простого предшествования? Имеем + ≐ T и + ⋖ T,

т.к. (E®E +T)ÎP и TÎL(T): TÞ⁺Tg, если взять g=*F и правило T®T*F. Т.е. G₀Ï классу ГПП.

Кстати, отношения предшествования несимметричны. Легко видеть, что T ≐ + неверно.

Техника «перенос-свертка». (АУ-452…6)

Если между верхним символом стека и первым необработанным символом входной цепочки есть отношение ≐ или ⋖, то переносим правый символ цепочки в стек, если ⋗, то в стеке выделяем правую часть правила – основу b, определяем левую часть правила – нетерминал Y, и выполняем свертку – замену b на Y. Кстати, если b - основа правовыводимой цепочки abw, w ÎS_T^*, то смежные символы цепочки a связаны отношением ≐ или ⋖, правый символ a и левый символ b - отношением ⋖, символы основы - отношением ≐, правый символ b и левый символ w - отношением ⋗.

Можно ли грамматику G₀ привести к виду простого предшествования? – ДА.

Пример: Матрица предшествования для грамматики G ₀’, полученной из G₀. $ - дно стека.

E ® D D ® D+T | T

T ® K K ® K*F | F

F ® (E) | a

Во всех клетках матрицы не более одного символа Þ G ₀’ - грамматика простого предшествования.

Алгоритм восходящего анализа цепочки w для ГПП. (АУ-461)

Инициализация: Вход = w $ Стек = $

Перенос: первый символ входа записывается в стек, goto Сравнение.

Сравнение: if a =$ then свертка (здесь а – начало остатка)

Else a сравниваем с вершиной стека Н

if (H ≐ a) || (H ⋖ a) then перенос

else if H. ⋗a then свертка else неудача (нет отношений).

Свертка: Пусть Стек= HH ₁ H ₂ …H_k

Выбираем i = arg min (H_{i +1}⋖ H_i) и ищем правило Y ® H…H_i.

Если правило есть, то заменяем в стеке H…H_i на Y, иначе (нет правила) – неудача.

Цикл до тех пор, пока не встретится начальный символ грамматики.

Если Н=Е & a =$, то успех. Иначе- неудача.

Правый разбор цепочки берем в столбце 4, выпи­сывая его в обратном порядке: 12458683468.

Строим дерево.

Не нашли, что искали? Воспользуйтесь поиском: