Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Нисходящий разбор.




Если нам известен левый разбор π цепочки , где G – КС - грамматика, то дерево её разбора строится так: пометим корень дерева начальным символом грамматики S; пусть – определяет номер правила, который надо применить к S; положим, что это правило ; присоединим k прямых потоков к вершине S и пометим их символами ; если - первый слева нетерминал в цепочке , то символами должны быть символы ; следующее примененное при выводе правило грамматики с номером должно иметь в левой части нетерминал ; допустим это правило ; продолжаем построение.

           
   
 
 
 
 

 


Т. е. строем дерево разбора, соответствующее левому разбору. Двигаемся слева направо от корня к листьям:

 

Известно, что для любой грамматике G можно построить недетерминированный МП – преобразователь, который является основой синтаксического анализатора.

Для левого анализатора строем преобразователь:

δ определяется следующим образом:

1) Если – это правило из P с номером i, то ;

2) .

Этот анализатор может развёртывать нетерминал, расположенный вверху магазина, в соответствии с правилом P и одновременно выдавать номер этого правила, используя функцию , построенную по правилу 1) определения. Кроме того он может сравнивать текущий входной символ с верхним символом магазина, применяя функцию , построенную по правилу 2) определения.


Поделиться:

Дата добавления: 2015-01-29; просмотров: 148; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты