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, то

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


 

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

37101. Национальная политика первых лет Советской власти. Образование СССР 17.32 KB
  Большевистская идея мировой революции и создания в будущем Всемирной Федеративной Республики Советов форсировала новый объединительный процесс. В связи с победой советской власти на основной территории бывшей Российской империи возникли и другие предпосылки для объединительного процесса единый характер политического строя диктатура пролетариата в форме республики Советов сходные черты организации государственной власти и управления. В большинстве республик власть принадлежала национальным коммунистическим партиям входившими в состав...
37102. Индустриализация 36.5 KB
  Необходимость индустриализации: экономическая: крупная промть определяет экономическое развитие страны в целом. Военнополитическая без индустриализации невозможно обеспечить техникоэкономическую независимость страны и ее оборонную мощь. Проблемы создания индустриализации стали первоочередными в конце 1925г. Источники индустриализации: внутренние накопления: внутренние займы выкачивание средств из деревни доходы от внешней торговли дешевая рабочая сила энтузиазм трудящихся труд заключенных.
37103. Коллективизация сельского хозяйства и ее последствия 19.56 KB
  Коллективиза́ция это процесс объединения единоличных крестьянских хозяйств в коллективные хозяйства колхозы в СССР. объединению подлежало 25 процентов крестьянских хозяйств. Основу аграрного сектора экономики страны составляли мелкие крестьянские хозяйства которые имели полунатуральный характер.
37104. Начальный период Великой Отечественной войны. Причины поражения Красной Армии на первом этапе войны 15.43 KB
  Причины поражения Красной Армии на первом этапе войны. 22 июня 1941 года нацистская Германия вероломно нарушив договор о ненападении внезапно без объявления войны нанесла по Советскому Союзу мощный удар. Этот день вошел в историю нашей страны трагической датой стал днем начала неимоверно тяжелой войны советского народа против фашизма справедливо названной Великой Отечественной войной.
37105. Причины, цена и историческое значение победы советского народа в Великой Отечественной войне 17.16 KB
  Решения партии лежали в основе постановлений Государственного Комитета Обороны Президиума Верховного Совета СССР и Совета Народных Комиссаров СССР приказов Народного комиссара обороны и Верховного Главнокомандующего а также призывов и лозунгов обращенных к советскому народу и воинам Вооруженных Сил. В руках Государственного Комитета Обороны сосредоточилась вся полнота власти в государстве. Все граждане и все партийные советские комсомольские и военные органы обязаны были беспрекословно выполнять решения и распоряжения Государственного...
37106. Послевоенное устройство мира. Формирование двух мировых систем и их противостояние 18.75 KB
  Особенностью послевоенного периода стали народнодемократические социалистические революции в странах Восточной Европы и ряде стран Азии которые при поддержке СССР приступили к строительству социализма. Образовалась мировая система социализма во главе с СССР. В годы мировой войны сложилась единая антифашистская коалиция – союз великих держав – СССР США Великобритания и Франция. Основой конфронтации стали отношения между двумя сверхдержавами – СССР и США.
37107. СССР в период восстановления разрушенного войной хозяйства 23.22 KB
  В 1943 году для организации восстановительных работ в Совете Народных Комиссаров СССР был образован специальный комитет а в Госплане СССР управление обеспечивающее планирование деятельности всех ведомств причастных к этой работе. Постановление ЦК ВКП б и СНК СССР от 21 августа 1943 г. В Госплане СССР и научных учреждениях были разработаны краткосрочные и долгосрочные планы восстановления народного хозяйства как в целом так и по отдельным отраслям. На сессии Верховного Совета СССР был утвержден пятилетний план восстановления и развития...
37108. Разоблачение культа личности Сталина. XX съезд КПСС 15.81 KB
  Именно Хрущеву было поручено прочитать доклад и лично встретить непредсказуемую реакцию участников съезда. Созванный за восемь месяцев до уставного срока в связи с насущной необходимостью подвести итоги произошедших после смерти Сталина изменений и дискуссии о выборе курса съезд завершился знаменитым секретным докладом Хрущева. в последний день работы XX съезда на закрытом заседании с докладом О культе личности и его последствиях выступил первый секретарь ЦК КПСС Н. В докладе были обнародованы и осуждены факты массовых репрессий...
37109. Политика либерализации советского общества. «Оттепель». Н.С. Хрущев – политик и человек 18.45 KB
  Хрущев – политик и человек. Хрущев. После недолгой борьбы к власти пришел Никита Сергеевич Хрущев. Резкий решительный неосторожный в словах и поступках Хрущев прошел все ступени партийной работы возглавлял крупные парторганизации.