29377

Нисходящий грамматический разбор с возвратами

Доклад

Информатика, кибернетика и программирование

Суть данного метода можно представить в виде следующей последовательности шагов выполнение которых повторяется в процессе чтения входной цепи символов. Если активная вершина помечена а T то сравнить его с очередным символом входной цепочки. Сравниваемые символы совпали тогда сделать активной вершиной дерева лист правее а и перейти к следующим символам входной цепочки. Символы не совпали то выполним возврат к предыдущему уровню дерева разбора и соответствующему символу входной цепочки.

Английский

2013-08-21

83 KB

0 чел.

15) Нисходящий грамматический разбор с возвратами.

Данный метод является наиболее простым, но трудоемким. Для любой продукции используемой грамматики с одинаковыми левыми частями перенумеруем правые части. 
A→α1 | … | αk и будем называть их альтернативами соответствующим нетерминалам. Т.к. для КС(контекстно-свободные) грамматик правая часть продукции может быть любой цепочкой терминальных и нетерминальных символов, до обозначений некоторых альтернатив α, так 

α=x1, x2, x3 … xp; x1, x2, x3 … xp NUT
Замечание. Для упрощения метода предположим, что правая часть любой продукции не может быть пустой строкой. 
Суть данного метода можно представить в виде следующей последовательности шагов, выполнение которых повторяется в процессе чтения входной цепи символов.
1. Определить корень дерева разбора и пометить его S N. Считать его активной вершиной.
2. Если активная вершина помечена некоторым нетерминированным символом A, то выбрать первую альтернативу этого нетерминированного α=x1, x2, x3 … xp и определить р новых вершин дерева разбора, являющихся непосредственно последовательностью вершины А, пометить их x1, x2, x3 … xp, соответственно (→) и сделать вершину х1 активной.
3. Если активная вершина помечена а T, то сравнить его с очередным символом входной цепочки. 
Сравниваемые символы совпали, тогда сделать активной вершиной дерева (лист) правее а и перейти к следующим символам входной цепочки. 
Символы не совпали, то выполним возврат к предыдущему уровню дерева разбора и соответствующему символу входной цепочки. Повторяя шаг 2 для следующего альтернативного нетерминала, если все альтернативы данного нетерминала исследованы, то возврат на более высокий уровень дерева и соответствующего символа и т.д.
4. Повтор пункта 2 и 3 до тех пор, пока не будет найден разбор входной цепочки или исследованы все возможные альтернативы. 
Разбор завершён успешно если листья построенного дерева помечены терминальными символами и самый правый лист соответствует последнему символу входной цепочки.
Замечание. Порядок нумерации альтернатив влияет на скорость работы метода.
Пример.

SE;
ET+E | T;
Ti*T | i
Порождая арифметические выражения +, i, –, всегда завершаются « ; ».

Перенумеруем символы входной цепочки.

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

Замечание. Метод требует чтобы используемая КС грамматика не содержала продукции с левой рекурсией, т.е.:

т.к. это ведёт к зацикливанию метода.
Если бы в рассматриваемом случае грамматика содержала правила E→E+T, то

Замечание. Существующий 
формальный алгоритм позволяет преобразовывать грамматику с левой рекурсией в эквивалентную ей грамматику без левой рекурсии.
Замечание. Метод – учебный показывает идею, из-за его трудоёмкости на его базе разрабатывают практический метод разбора – метод рекурсивного спуска.


 

А также другие работы, которые могут Вас заинтересовать

47812. ЭКОНОМИЧЕСКАЯ ТЕОРИЯ 2.03 MB
  Потребности как предпосылка производства. Ресурсы и факторы производства Продукт как результат производства фирмы.3 Издержки производства: явные и неявные внешние и внутренние постоянные и переменные
47813. Сборник клинических задач. Лечебное дело 740 KB
  При осмотре влагалищными зеркалами: слизистая оболочка влагалища и шейки матки синюшная. Устанавливается на основании сомнительных и вероятных признаков беременности: отвращение к запахам тошнота отсутствие менструации синюшность слизистой оболочки влагалища и шейки матки увеличение тела матки. Дополнительные методы диагностики беременности: определение ХГЧ гормона хорионического гонодотропина в сыворотке крови и моче; ультразвуковое исследование матки. по величине тела матки 8 недель небеременная матка имеет размер с крупную...
47816. Физика. Учебно-методический комплекс 1.67 MB
  Общие свойства и характеристики волновых процессов. Заряды одного знака отталкиваются друг от друга заряды разных знаков притягиваются рис. Шелк Стекло = Мех Янтарь = Рис. Величина элементарного заряда по абсолютной величине в СИ: Электрические заряды присущи многим элементарным частицам в частности электронам и протонам входящим в состав различных атомов из которых построены все тела в природе.
47817. ОБЛІК У БЮДЖЕТНИХ УСТАНОВАХ. КОНСПЕКТ ЛЕКЦІЙ 1.48 MB
  Метою вивчення дисципліни є засвоєння теорії і практики бухгалтерського обліку в бюджетних установах оволодіння студентами базовими знаннями з організації і функціонування бюджетних установ формування вміння орієнтуватись у законодавчонормативних документах та інструктивнометодичних матеріалах з організації та методики бухгалтерського обліку в...
47818. ОСНОВЫ ПРАВА 891 KB
  Теория права. Признаки государства: Наличие особой публичной власти не совпадающей с основным населением особый аппарат управления и принуждения Территориальная организация населения государство защищает интересы каждого субъекта находящегося на его территории в отличие от власти в догосударственный период когда интересы субъекта защищались либо по признаку принадлежности к данному сообществу либо по признаку родства Наличие права Налоги обязательные платежи с субъектов идущие в т. на содержание “публичной властиâ€...
47819. Інвестування. Навчально-методичний посібник 789 KB
  Рецензенти: РВВ ЖДТУ Житомир 2005 ВСТУП Мета і завдання дисципліни її місце у навчальному процесі Актуальним завданням на сьогодні є розвиток інвестиційної діяльності спрямованого на створення привабливого інвестиційного середовища та суттєвого нарощування обсягів інвестицій. Разом з тим річні обсяги інвестицій в Україні поки ще залишаються на низькому рівні через велику низку причин: несприятливий інвестиційний клімат нерозвинутість фондового ринку та фінансовокредитної системи високий податковий тиск неефективне використання...