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

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


 

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

34387. Реальные доходы населения. Методы их прогнозирования 55 KB
  Методы их прогнозирования Важнейшим обобщающим показателем социального развития и уровня жизни населения являются реальные доходы. Основным источником формирования реальных денежных доходов и стимулирования трудовой деятельности являются зарплата повышение производительности труда и эффективности хозяйствования во всех звеньях экономики рост инвестиционного потенциала населения снижение налоговой нагрузки на фонд зарплаты субъектов хозяйствования всех форм собственности что будет способствовать созданию новых рабочих мест...
34388. Потребительский рынок (ПР). Прогнозирование спроса на товары народного потребления 33.5 KB
  Рынок – сфера товарноденежного обращения охватывает совокупность конкретных отношений и связей между производителями и потребителями товаров. Структура ПР: международный рынок рынок государств содружества рынок РБ рынок региональных областей рынок конкретных товарных групппродовольственных. Рынок: 1.
34389. Прогнозирование и планирование покупательных фондов и товарных ресурсов 37.5 KB
  Рассчитанный таким образом покупательный фонд определяет необходимый объем продажи товаров населению в денежном выражении. К этой величине прибавляется оборот по продаже товаров организациям и учреждениям в порядке мелкооптовой торговли и в результате определяется необходимый объем товарооборота. Дело в том что потребительские ожидания относительно таких факторов как будущие цены на товары наличие товаров и будущий доход способны изменить спрос. Для увязки совокупного спроса на товары народного потребления с товарными ресурсами наряду с...
34390. Формирование структуры товарооборота. Баланс спроса и предложения, его содержание и назначение 41.5 KB
  Чтобы сформировать структуру товарооборота необходимо определить спрос на отдельные группы товаров и сопоставить с ресурсами этих товаров. Структура характеризует соотношение товарных групп и отдельных товаров в общем объеме розничного товарооборота. Соотношение отдельных товарных групп и товаров связано вопервых с их значимостью и вовторых со степенью дополняемости и заменяемости товаров в процессе реализации и потребления. В процессе разработки прогнозов должен осуществляться анализ тенденций изменения структуры товарооборота за...
34391. Внешнеэкономическая политика. Прогнозирование экспорта и импорта 37.5 KB
  Среди моделей получивших широкое применение в мировой практике для прогнозирования экспорта и импорта следует выделить: трендовые модели; функции экспорта и импорта многофакторные модели; комплексные эконометрические модели; модели межотраслевого баланса; матричные модели международной торговли; оптимизационные модели. Трендовые модели у = t b и др. Эти модели используются на стадии составления инерционного прогноза. При конструировании целевого прогноза применяются функции экспорта и импорта многофакторные модели.
34392. Квотирование, лицензирование, валютное регулирование экспорта и импорта 25 KB
  Квотирование К – установление количественных ограничений квот на ввоз и вывоз товаров. Лицензирование Л: для ввоза вывоза определенных товаров требуется получить установленный документ лицензию. Число квотированных товаров по мере приближения цен к мировым снижается. Кроме того лицензированию подлежат экспорт и импорт специфических товаров: товаров и технологий военного и двойного назначения ядерных материалов драгоценных металлов и камней наркотических и психотронных средств ядов.
34393. Определение эффективности ВЭС 29 KB
  Эффективность экспорта продукции Ээ определяется соотношением валютной выручки Вэ к затратам на экспорт Зэ. Если Ээ 1 то экспорт продукции экономически выгоден Ээ = Вэ Зэ. Эффективность импорта продукции Эи определяется соотношением затрат на производство импортозамещающих товаров Зи к валютным расходам на приобретение импортных товаров Ви Эи = Зи Ви. На основе расчетов эффективности экспорта и импорта делается вывод о целесообразности поставок продукции в ту или иную страну и импорта товаров.
34394. Промышленные комплексы. Проблемы их функционирования в современных условиях. Реструктуризация промышленности 34 KB
  Строительство основа строительного комплекса особенностями которого являются длительный период производства продукции и большие затраты трудовых материальных и финансовых ресурсов. Особое внимание при этом предусматривается уделять модернизации наукоемкого сектора промти экспортно ориентированным отраслям и импортозамещающим производствам созданию и развитию производств основанных на прогрессивных технологиях. Предусматриваются следующие важнейшие меропр: реформирование системы гос п п завершение приватизации малых п п и...
34395. Прогнозирование и планирование объема и структуры промышленного производства 33 KB
  На заключительном этапе формируются плановый объем и структура выпуска промышленной продукции с учетом спроса возможностей производства и обеспечения производственными ресурсами. Обосновывается и устанавливается заказ на поставку важнейших видов продукции для государственных нужд. Для прогнозирования спроса и объема производства конкретных видов продукции хорошие результаты дает метод Дельфи . Путем анкетного опроса группы ученых и специалистов по данной проблеме формируется информация по выпуску каждого вида продукции по годам которая...