Пример 15

Анализ методом рекурсивного спуска

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

Вопросы

1. Какие функции выполняет синтаксический анализатор?

2. Какая грамматика является однозначной?

3. Какой цели служат преобразования правил КС-грамматик?

4. Почему из правил грамматики необходимо устранять именно левую рекурсию?

5. Почему при преобразовании КС-грамматик к приведенному виду сначала необходимо удалить бесполезные, а потом недостижимые символы?

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

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

Рассмотрим пример, в котором откат необходим.

Рассмотрим грамматику

S → cAd

A → ab|a

и входную строку w = cad.

При нисходящем построении дерева разбора для этой строки вначале создаем дерево, состоящее из одного узла, помеченного как S. Указатель входа указывает на с, первый символ строки w. Теперь воспользуемся первой продукцией для S, чтобы получить дерево, показанное на рис. 27а.

Рис. 27. Шаги нисходящего разбора

Крайний слева лист, с,соответствует первому символу строки w, так что переместим указатель входа к а, второму символу строки w, и рассмотрим следующий лист дерева, помеченный А. Теперь можно воспользоваться для А первой альтернативой и получить дерево, изображенное на рис. 27 б. Здесь обнаружено соответствие считанного символа листу дерева, и осуществляется переход к следующему символу — d. Однако d не соответствуют листу дерева b, значит, надо вернуться к А с тем, чтобы выбрать новую альтернативу для работы.

Возвращаясь к А, необходимо вернуть указатель входа в позицию 2, в которой он был когда впервые выбирали продукцию для разложения А. Это означает, что процедура для А должна хранить указатель входа в локальной переменной. При рассмотрении второй альтернативы для А получаем дерево, показанное на рис. 21 в. Лист а соответствует второму символу w, а лист d - третьему. Поскольку в этот момент построено дерево разбора для w, прекращаем работу и сообщаем об успешном завершении разбора.

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

Дата добавления: 2014-12-27