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

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

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

находит наибольшее начало z слова x , которое может быть началом выводимого из K слова;
сообщает, является ли найденное слово z выводимым из K.

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

Next: Symbol

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

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

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

Для удобства введем такую терминологию: выводимое из K слово будем называть K-словом, а любое начало любого выводимого из K слова -- K-началом. Два сформулированных требования вместе будем выражать словами <<ReadK корректна для