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

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

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

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

Пример:

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

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

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

	c		A		d

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

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

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

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

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