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

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


 

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

2446. Основы получения пластмасс, эластомеров и полимерных композитов с заданными свойствами 326 KB
  Композиционные составляющие: связующая смола, наполнители, пластификаторы смазывающие вещества, отверждающие вещества. Схема установки для получения полиэтилена непрерывным методом при высоком давлении. Схема установки для непрерывной полимеризации стирола в массе. Схема установки для производства поливинилхлорида непрерывным эмульсионным способом. Поликонденсационные пластмассы. Схема реактора для получения поликонденционных смол.
2447. Особові займенники. Зворотний займенник. Відмінювання 122 KB
  Мета організації уроку: сформувати в учнів поняття про особові та зворотний займенники на основі відтворення і поглиблення знань про займенник отриманих ними на попередніх уроках; навчити їх об’єктивно використовувати особові та зворотний займенники в усному і писемному мовленні.
2448. Займенник: загальне значення, морфологічні ознаки, синтаксична роль 505.5 KB
  Мета: поглибити, удосконалити, систематизувати й узагальнити знання учнів про займенник, набуті в початкових класах. формувати відповідні уміння і навички. Займенник – це самостійна частина мови, яка вказує на особу, предмет або кількість, але не називає їх.
2449. Принципы линейного моделирования 435.24 KB
  Вывод нелинейной математической модели. Формулировка системы допущений. Модель статики. Исследование нелинейной модели в динамическом режиме. Линеаризация полученной нелинейной модели в динамке и сравнение линейной и нелинейной моделей. Вывод линеаризованной модели в динамике.
2450. Оборудование машиностроительных производств 290.7 KB
  Главный привод или привод главного движения – передаёт движение осуществления процесса резания с заданной скоростью. Несущие системы состоят из последовательного набора базовых деталей (основание, станина, стойка, колонна и т.д.), соединённых между собой неподвижными соединениями (стыками) или подвижными (направляющими).
2451. Електропостачання сільськогосподарського підприємства та населеного пункту с. Голубівка 77.91 KB
  Територіальна адреса, географічне положення та кліматичні умови. Розрахунок радіуса електропередачі схеми електропостачання підприємства. Аналіз роботи системи електропостачання в нормальному та післяаварійному режимах з урахуванням вимог надійності та використання поновлювальних джерел електричної енергії. Розрахунок струмів короткого замикання. Розрахунок капітальних вкладень, витрат на амортизацію,обслуговування та інше. Розрахунок показників ефективності та прибутковості проекту.
2452. Бандероли с объявленной ценностью с уведомлением о вручении 388.5 KB
  Цель данной работы изучить технологический процесс обработки и вручения бандероли с объявленной ценностью с уведомлением о вручении, от физических лиц бандероли с объявленной ценностью принимаются только в открытом виде с описью вложения всех отправляемых предметов.
2453. Докладний переказ тексту з елементами опису тварини. 102.5 KB
  Мета організації уроку. Засвоєння учнями методів аналізу тексту, розвиток умінь і навичок у написанні докладного переказу з елементами опису тварини.
2454. Групи слів за значенням: синоніми, антоніми, омоніми. Ознайомлення зі словниками антонімів, синонімів 92 KB
  Мета організації уроку: сформувати в учнів поняття про синоніми, антоніми, омоніми, на основі повторення матеріалу засвоєного в початковій школі, ознайомити учнів зі словниками синонімів, антонімів.