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

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


 

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

65114. ТАТАРЫ (ПОПУЛЯРНЫЙ ОЧЕРК ЭТНИЧЕСКОЙ ИСТОРИИ И ДЕМОГРАФИИ) 92.5 KB
  Татары являются одним из крупных тюркоязычных этносов. Татарский народ прошел длительный путь исторического развития и имел в прошлом свою государственность древнетюркские каганаты Причерноморская Булгария Хазарский каганат Волжская Булгария Золотая Орда Казанское Крымское...
65115. Образование Золотой Орды и формирование средневекового татарского этноса (XIII – первая четверть XV века) 299.5 KB
  Золотая Орда как великая евразийская империя вторая после Тюркского каганата существовал сравнительно недолгий период а на фоне истории мировой цивилизации и достаточно незначительный. Это государство современники называли поразному...
65116. ЮГО-ВОСТОК ТАТАРСТАНА: ПРОБЛЕМА ИЗУЧЕНИЯ ЭТНИЧЕСКОЙ ИСТОРИИ РЕГИОНА XIV-XVII ВЕКОВ 123.5 KB
  В связи с состоянием источников ранняя история татарского населения юго-восточных районов республики остается исследованной недостаточно. Дискуссионным остается вопрос о существовании в этой зоне татарского населения до начала XVIII века.
65117. Из истории изучения формирования тюркоязычного населения Пермского края 63.5 KB
  Тюркоязычное население Пермского края татары и башкиры длительное время поддерживали интенсивные этнические контакты. Именно поэтому история изучения формирования пермских татар и башкир рассматривается вместе.
65118. К вопросу о клановой принадлежности Тайбугидов (по русским и тюркским источникам) 45 KB
  Носители титула Сибирский князь Тайбугиды возводимые в сохранившихся в составе так называемых Сибирских летописей родословных к некоему князю Тайбуге см. Родословная их согласно Сибирским летописям выглядит так: I II III IV Царь Он князь Тайбуга князь Ходжа князь Мар Адер Одер...
65119. К вопросу об этносоциальной структуре татарских ханств (на примере Казанского и Касимовского ханств ХV-сер. ХVI вв.) 49.5 KB
  Более чем двухвековой спор сторонников булгарского и золотоордынского ("татарского") происхождения волго-уральских татар сегодня приобретает новый импульс. Объясняется это тем, что появился целый ряд новых исследований, раскрывающих роль золотоордынско-тюркского компонента в формировании татар Поволжья.
65120. Чингисхан. Формирование личности Темучжина 117.5 KB
  В давнем споре эпоха ли создает личности или личности формируют эпоху нет пока ни победителей ни побежденных. Эпоха несомненно сыграла огромную роль в формировании личности Темучжина будущего Чингисхана. В любом случае это было время когда первое еще дочингисовское государство монголов именовавшееся...
65121. ИСТОРИЯ ТИБЕТА С ДРЕВНЕЙШИХ ВРЕМЕН ДО НАШИХ ДНЕЙ 2.26 MB
  Далайлама XIV покинул Тибет что тоже осложнило и осложняет продвижение Тибета по пути преобразований. Б Дхармасале Индия размещается эмигрантское правительство Тибета возглавляемое Далайламой. В хронике Далайламы V говорится...
65122. Медные джучидские монеты XV века 70 KB
  Особенностью этих пулов является форма начертания слова чекан. Тем же резчиком очевидно делались и штемпеля для чеканки аверса пулов с изображением утки в картуше. Опираясь на фактурные признаки не характерные для пулов предыдущего периода.