КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Нисходящий разбор.Если нам известен левый разбор π цепочки , где G – КС - грамматика, то дерево её разбора строится так: пометим корень дерева начальным символом грамматики S; пусть – определяет номер правила, который надо применить к S; положим, что это правило ; присоединим k прямых потоков к вершине S и пометим их символами ; если - первый слева нетерминал в цепочке , то символами должны быть символы ; следующее примененное при выводе правило грамматики с номером должно иметь в левой части нетерминал ; допустим это правило ; продолжаем построение.
Т. е. строем дерево разбора, соответствующее левому разбору. Двигаемся слева направо от корня к листьям:
Известно, что для любой грамматике G можно построить недетерминированный МП – преобразователь, который является основой синтаксического анализатора. Для левого анализатора строем преобразователь: δ определяется следующим образом: 1) Если – это правило из P с номером i, то ; 2) . Этот анализатор может развёртывать нетерминал, расположенный вверху магазина, в соответствии с правилом P и одновременно выдавать номер этого правила, используя функцию , построенную по правилу 1) определения. Кроме того он может сравнивать текущий входной символ с верхним символом магазина, применяя функцию , построенную по правилу 2) определения.
|