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

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

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

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

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

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

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

2) .

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