Пусть в грамматике есть правила

K -> L

K -> M № L

и других правил, содержащих K в левой части, нет. Мы хотим узнать, выводится ли данное слово A из нетерминала K. Это будет так в одном из случаев: (1) если A выводится из L; (2) если A можно разбить на непустые слова B, C, D, для которых B выводится из M, C выводится из N, а D выводится из L. Вся эта информация уже есть (слова B, C, D короче A, а L рассмотрен до K).

Легко видеть, что число действий этого алгоритма полиномиально. Степень полинома зависит от числа нетерминалов в правых частях правил и может быть понижена, если грамматику преобразовать к форме, в которой правая часть каждого правила содержит 1 или 2 нетерминала (это легко сделать, вводя новые нетерминалы: например, правило K -> LMK можно заменить на K -> LN и № -> MK, где № —новый нетерминал).

Рассмотрим грамматику с единственным нетерминалом K, нетерминалами 1, 2, 3 и правилами

K -> 0

K -> 1 K

K -> 2 K K

K -> 3 K K K

Как проверить выводимость слова в этой грамматике, читая слово слева направо? (Число действий при прочтении одной буквы должно быть ограничено.)

Решение. Хранится целая переменная n, инвариант: слово выводимо <‑> непрочитанная часть представляет собой конкатенацию (соединение) n выводимых слов.

Тот же вопрос для грамматики

K -> 0

K -> K 1

K -> K K 2

K -> K K K 3

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

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

Идея метода рекурсивного спуска такова. Для каждого нетерминала K мы строим процедуру ReadK, которая —в применении к любому входному слову x —делает две вещи:

(1) находит наибольшее начало z слова x, которое может быть началом выводимого из K слова;

(2) сообщает, является ли найденное слово z выводимым из K. Прежде чем описывать этот метод более подробно, договоримся о том, как процедуры получают сведения о входном слове и как сообщают о результатах своей работы. Мы предполагаем, что буквы входного слова поступают к ним по одной, т.е. имеется граница, отделяющая «прочитанную»часть от «непрочитанной». Будем считать, что есть функция (без параметров)

Next: Symbol

дающая первый непрочитанный символ. Ее значениями могут быть терминальные символы, а также специальный символ EOI (End Of Input —конец входа), означающий, что все слово уже прочитано. Вызов этой функции, естественно, не сдвигает границы между прочитанной и непрочитанной частью —для этого есть процедура Move, которая сдвигает границу на один символ. (Она применима, если Next <> EOI.) Пусть, наконец, имеется булевская переменная b.

Теперь мы можем сформулировать наши требования к процедуре ReadK. Они состоят в следующем:

(1) ReadK прочитывает из оставшейся части слова максимальное начало A, являющееся началом некоторого слова, выводимого из K;

(2) значение b становится истинным или ложным в зависимости от того, является ли A выводимым из K или лишь невыводимым началом выводимого (из K) слова.

Для удобства введем такую терминологию: выводимое из K слово будем называть K‑словом, а любое начало любого выводимого из K слова —K‑началом. Требования (1) и (2) вместе будем выражать словами корректна для K».