Реферат: Алгоритм нисходящего разбора. Нисходящие распознаватели

Рис 5. Деревья, использующие рекурсию и итерацию

Применив правило (3.2) получим A ::= BC(D|Л)|Ax(z|y); Применив

(3.3), получим A ::= BC(D|Л){x(z|y)}. Можно избавиться от одной па-

ры скобок, после чего получим A ::= BC(D|Л){x(z|y)}.

После таких изменений мы, конечно, должны изменить и наш алгоритм

нисходящего разбора. Теперь алгоритм должен уметь обрабатывать альтер-

нативы не только в одной правой части, но и в ее подцепочках, должен

учитывать в своей работе существование пустой цепочки Л, должен уметь

обрабатывать итерацию.

Использование итерации вместо рекурсии отчасти меняет и структуру

деревьев. Таким образом, рис 3.а должен был бы походить на рис. 3.б. Но

эти два дерева следует рассматривать как эквивалентные; операторы "плюс"

должны заменяться слева направо.

Общая левосторонняя рекурсия

Мы не решили всей проблемы левосторонней рекурсии: с прямой лево-

сторонней рекурсией покончено, но общая левосторонняя рекурсия еще ос-

талась. Таким образом, правила

U ::= Vx и V ::= Uy|v

дают вывод U => +Uyx. Избавиться от этого не так просто, но обнаружить

ситуацию можно. Исключим из исходной грамматики все правила с прямой

левосторонней рекурсией. Символ U, получившейся в результате этих пре-

образований грамматики, может быть леворекурсивным тогда и только тогда

когда U FIRST+ U. Как проверить это отношение, нам уже известно.

Представление грамматики в оперативной памяти

Одной из проблем, возникающих при реализации нисходящих методов,

является представление грамматики в вычислительной машине. Одно из

возможных представлений уже использовалось ранее. Очевидно, что оно

неудачно из-за обьема работы необходимой для поиска правил, соответст-

вующих каждому нетерминалу. Речь пойдет о другом представлении. Прежде