ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Моделирование восходящего распознавателя.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 = SN È ST следующим образом: 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 ÎST, если (A ® aBYb)Î P & [ B Þ+ gX ~ X Î R (B)] & [ Y Þ* ad ~ a Î L (Y) ]. Грамматика называется грамматикой простого предшествования, если она приведенная, не содержит e – правил, обратимая (нет правил с одинаковыми правыми частями) и любые два символа связаны не более чем одним отношением предшествования. Пример: Является ли G0 грамматикой простого предшествования? Имеем + ≐ T и + ⋖ T, т.к. (E®E +T)ÎP и TÎL(T): TÞ+Tg, если взять g=*F и правило T®T*F. Т.е. G0Ï классу ГПП. Кстати, отношения предшествования несимметричны. Легко видеть, что T ≐ + неверно. Техника «перенос-свертка». (АУ-452…6) Если между верхним символом стека и первым необработанным символом входной цепочки есть отношение ≐ или ⋖, то переносим правый символ цепочки в стек, если ⋗, то в стеке выделяем правую часть правила – основу b, определяем левую часть правила – нетерминал Y, и выполняем свертку – замену b на Y. Кстати, если b - основа правовыводимой цепочки abw, w ÎST*, то смежные символы цепочки a связаны отношением ≐ или ⋖, правый символ a и левый символ b - отношением ⋖, символы основы - отношением ≐, правый символ b и левый символ w - отношением ⋗. Можно ли грамматику G0 привести к виду простого предшествования? – ДА. Пример: Матрица предшествования для грамматики G 0’, полученной из G0. $ - дно стека.
E ® D D ® D+T | T T ® K K ® K*F | F F ® (E) | a
Во всех клетках матрицы не более одного символа Þ G 0’ - грамматика простого предшествования.
Алгоритм восходящего анализа цепочки w для ГПП. (АУ-461) Инициализация: Вход = w $ Стек = $ Перенос: первый символ входа записывается в стек, goto Сравнение. Сравнение: if a =$ then свертка (здесь а – начало остатка) Else a сравниваем с вершиной стека Н if (H ≐ a) || (H ⋖ a) then перенос else if H. ⋗a then свертка else неудача (нет отношений). Свертка: Пусть Стек= HH 1 H 2 …Hk Выбираем i = arg min (Hi +1⋖ Hi) и ищем правило Y ® H…Hi. Если правило есть, то заменяем в стеке H…Hi на Y, иначе (нет правила) – неудача. Цикл до тех пор, пока не встретится начальный символ грамматики. Если Н=Е & a =$, то успех. Иначе- неудача. Продолжение примера G 0. Вход: a + a * a. При свертке выделяемая в стеке основа подчеркнута.
Правый разбор цепочки берем в столбце 4, выписывая его в обратном порядке: 12458683468. Строим дерево. Не нашли, что искали? Воспользуйтесь поиском:
|