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

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

S

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

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

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

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

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

2. .

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

Нисходящий анализ.

Метод рекурсивного спуска.

Предиктивный разбор.

Рассмотрим на примере нисходящий анализ в общем виде, а именно анализ методом рекурсивного спуска, который может использовать откаты (возвраты), т. е. производить повторное сканирование входного потока.

Пример:

Рассмотрим грамматику с правилами

и входной строкой: ω = cad.

Сначала создаём дерево, состоящее из одного узла, помеченного как S. Теперь воспользуемся первой продукцией для S, получим дерево 1)

S

S

S

c

A

d

c

A

d

c

A

d

a

b

a

1)

2)

3)

Крайний слева лист, c, соответствует первому символу строки ω. В противном случае мы должны перейти ко второй продукции для S. Если её нет, то строка не соответствует правилам грамматики. Переместим указатель входа на второй символ в строке ω и рассмотрим следующий лист в строке – это нетерменал A. Применим к A первую продукцию и получим 2). ca соответствует ω, передвигаем и видим, что d не соответствует листу дерева b, а значит мы должны вернуться к A и попробовать следующую продукцию.

Возвращаясь к A, мы должны вернуть указатель входа на вторую позицию, т. е. на ту позицию, в которой он был, когда мы впервые пришли к разложению A. При рассмотрении второй альтернативы для A мы получаем дерево 3).

Таким образом, получаем, что и разбор прекращен. Причем для каждого из нетерменалов в некоторой локальной переменной должен храниться указатель входа.

Леворекурсивную грамматику можно вызвать зацикливанием СА, работающего методом спуска с откатом. Поэтому при нисходящем анализе сначала необходимо избавиться от левой рекурсии, а затем провести левую факторизацию.

Для построения предиктивного СА правильная альтернатива должна точно определяться по первому ее символу. В противном случае может получиться неоднозначность.