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

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


 

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

84583. Теплоутворення в організмі, його регуляція 42.13 KB
  В дорослих цей механізм посилення теплоутворення мобілізується рідко лише за умови тривалої дії холодових факторів коли виникає загроза зниження температури ядра тіла. Цей механізм теплоутворення часто використовується регуляторними механізмами за необхідності збільшити теплоутворення. Виділяють наступні види скоротливого термогенеза: терморегуляторний тонус збільшення тонусу мязів яке починається з мязів шиї та плечового поясу; виникає безумовнорефлекторно може збільшити теплоутворення на 50100; мязове тремтіння виникає...
84584. Тепловіддача в організмі та її регуляція 43.34 KB
  Виділення тепла з організму відбувається наступними шляхами: 1. Тепловипромінювання виділення тепла за допомогою довгохвильового інфрачервоного випромінювання. Тому механізми регуляції змінюють віддачу тепла шляхом радіації змінюючи температуру тіла. Віддача тепла шляхом випаровування змінюється регуляторними механізмами за рахунок зміни потовиділення.
84585. Регуляція ізотермії при різній температурі навколишнього середовища 50.47 KB
  При кімнатній температурі організм оголеної людини 30 тепла віддає шляхом радіації 1215 шляхом конвекції 20 шляхом випаровування та 35 шляхом проведення поки що не встановлено чому але при наявності двох оголених людей в кімнаті теплепродукція збільшується на 500 досліджувати цей цікавий факт Вам майбутнім фізіологам світочам української науки. Варто зауважити що для віддачі тепла шляхом радіації конвекції та проведення має буте градієнт температури шкіри та оточуючого середовища. Тому під час високої зовнішньої...
84586. Механізми сечоутворення. Клубочкова фільтрація і фактори, від яких вона залежить 44.81 KB
  В результаті цього процесу плазма крові фільтрується в просвіт капсули ШумлянськогоБоумена і утворюється первинна сеча ультрафільтрат плазми крові який за складом відрізняється від неї тільки відсутністю білків. гідростатичний тиск крові в капілярах ниркового тільця близько 70 мм. онкотичний тиск плазми крові близько 30 мм. Плазма крові фільтрується в просвіт капсули через нирковий фільтр який складається з трьох шарів: шар ендотеліоцитів капілярів 1; базальна мембрана 2; шар подоцитів епітелій капсули 3; Ендотелій...
84587. Канальцева реабсорбція і секреція, їх фізіологічні механізми 46.32 KB
  Реабсорбція окремих речовин в проксимальному сегменті нефрона: Реабсорбція іонів натрію N в основному проходить активно. В базолатеральних мембранах клітин епітелію канальців локалізується нптрійкалієва помпа яка з затратами АТФ транспортує іони натрію із клітини в інтерстиційну рідину. За рахунок роботи помпи в клітині підтримується низька концентрація іонів натрію. Через канали апікальної мембрани клітин іони натрію входять в неї пасивно за механізмом дифузії.
84588. Реабсорбція речовин в наступних відділах нефрона 50.77 KB
  Кількість речовин в первинній сечі можна розрахувати за формулою: Кількість речовини = Кпл ШКФ де: Кпл концентрація речовини в плазмі крові; ШКФ швидкість клубочкової фільтрації ШКаФ; Кпл ШКФ = Кс Д звідси: ; Синтетичний полісахарид інулін вільно фільтрується але не реабсорбується і не секретується. Тому визначивши коефіцієнт очищення за інуліном оцінюють ШКФ. ШКФ можна оцінити визначивши кліренс за ендогенним креатиніном який реабсорбується і секретується але обєми цих процесів однакові. Показники ШКФ розраховують на стандартну...
84589. Поворотно-протипоточна система нирок її фізіологічні механізми і роль 52 KB
  Поворотнопротипоточна система нирки ППСН забезепчує при необхідності: розведення сечі тобто виводить у великому обємі води малу кількість солей та метаболітів. Так нирки працюють при надлишку води в організмі наприклад при надлишковому її прийомі. концентровання сечі тобто виводять у малому обємі води велику кількість солей та метаболітів. Регуляція реабсорбції йонів натрію і води в канальцях нирки.
84590. Роль нирок в забезпеченні кислотно-основного стану крові 38.28 KB
  Роль нирок у підтримці кислотноосновного стану крові повязана із здатністю епітеліоцитів ниркових канальців секретувати протони які надалі виводяться з організму. Протони секретуються в просвіт канальців а бікарбонатні йони реабсорбуються у кров. Протони котрі секретуються нирковим епітелієм взаємодіють з різними компонентами сечі.
84591. Фізіологія як наука. Поняття про функцію. Методи фізіологічних досліджень 44.59 KB
  Нормальна фізіологія наука про обєктивні закономірності протікання функцій організму в їх взаємозвязку і у взаємодії організму із зовнішнім середовищем. Функція це діяльність і властивість клітин органів систем організму які проявляються як фізіологічний процес чи сукупність процесів. Неспецифічні притаманні багатьом чи всім тканинам та клітинам організму. Обєктом фізіологічного дослідження є функція організму його систем органів і клітин.