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

В алгориме, описанном ранее, есть один серьезный недостаток,

который проявляется, когда цель определена с использованием левосто-

ронней рекурсии. Если X - наша цель, а первое же правило имеет вид

X ::= X ..., то мы незамедлительно усыновляем того, кто будет искать

X. Он в свою очередь немедленно заведет себе сына, чтобы тот искал

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

на, и для решения задачи не хватит населения Китая.

По этой причине правила грамматики написаны с применением право-

сторонней рекурсии вместо более привычной левосторонней. Лучший способ

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

пользуя итеративные и факультативные обозначения. Запишем правила

(3.1) E ::= E+T | T как E ::= T { +T }

и

T ::= T*F | T/F | F как T ::= F { *F | /F }

Сейчас будут сформулированы два основных принципа, на основании

которых правила языка, включающие прямую левостороннюю рекурсию, пре-

оьразуются в эквивалентные правила, использующие итерацию.

(3.2 ) Факторизация. Если существуют правила вида

U ::= xy | xw | ... |xz, то их надо заменить на

U ::= x(y|w|...|z), где скобки являются метасимволами

Допустима факторизация в более общей форме, такая как в арифметиче-

ских выражениях. Например, если в (3.2) y=y y и w=y w , мы могли бы за-

1 2 1 2

менить U ::= x (y|w|...|z) на

U ::= x(y (y |w )|...|z).

1 2 2

Заметим, что исходные правила U ::= x|xy мы преобразуем к виду

U ::= x(y|Л), где Л - пустая цепочка. Когда бы ни использовалось по-

добное преобразование, Л всегда помещается как последняя альтернати-