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

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


 

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

7021. Стадии производства по делам об административных правонарушениях 147.5 KB
  Стадии производства по делам об административных правонарушениях Учебные вопросы: Общая характеристика стадий производства по делам об административных правонарушениях. Виды стадий производства по делам об административных правонар...
7022. Система управления 142.5 KB
  Система управления Понятие и содержание системы управления. Элементы системы управления. Процесс управления. Технология управления. Все сферы управления между собой объективно взаимосвязаны, поскольку управление представляет собой системное образ...
7023. Управление конфликтами и стрессами 838.5 KB
  Управление конфликтами и стрессами В этой теме осваивающие менеджмент и стремящиеся стать профессиональными специалистами в области управления производством найдут нужные им ответы на следующие вопросы: понятие конфликта организационный конфлик...
7024. Организационная культура в управлении и ее развитие 146 KB
  Организационная культура в управлении и ее развитие Понятие и элементы организационной культуры. Функции и типы организационной культуры. Виды организационной и управленческой культуры. I. Повышением эффективности управления, наряду с другими важным...
7025. Меры обеспечения производства по делам об административных правонарушениях 113.5 KB
  Меры обеспечения производства по делам об административных правонарушениях Учебные вопросы: Понятие мер обеспечения производства по делам об административных правонарушениях. Виды мер обеспечения производства по делам об а...
7026. Управленческое решение 726 KB
  Управленческое решение Эта тема позволит изучающим менеджмент пополнить свои знания по следующим вопросам: понятие управленческого решения решения в многоярусной экономике содержательные аспекты решения свойства управленческого решения логическа...
7027. Доказательства и доказывание в производстве по делам об административных правонарушениях 91 KB
  Тема 11. Доказательства и доказывание в производстве по делам об административных правонарушениях. Учебные вопросы: 1. Понятие доказательств в производстве по делам об административных правонарушениях. 2. Требования предъявляемые...
7028. Лидерство; теория, подходы, стиль 146.5 KB
  Тема 11 Лидерство теория, подходы, стиль Теоретические основы лидерства. Подходы к лидерству. Стиль управления руководителя. I . Лидерство относится к числу вопросов, имеющих важное значение для любой цивилизации (западной или восточной). Нет ничег...
7029. Информация в системе управления 224.5 KB
  Информация в системе управления Эта тема раскрывает осваивающим менеджмент следующие вопросы: понятие информации построение информационной модели информация как предмет и продукт управленческого труда носители информации ...