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

гда сопоставляется.

Помимо того что факторизация позволяет нам исключить прямую реку-

рсию, использование этого приема сокращает размеры грамматики и позво-

ляет проводить разбор более эффективно. В этом мы убедимся позже.

После факторизации (3.2) в грамматике останется не более одной пра-

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

Если такая правая часть есть, мы делаем следующее:

(3.3) Пусть U ::= x|y|...|z|Uv - правила, у которых осталась леворе-

курсивная правая часть. Эти правила означают, что членом син-

таксического класса U является x, y или z, за которыми либо ни-

чего не следует, либо следует только v. Тогда преобразуем эти

правила к виду U ::= (x|y| ... |z) {v}.

Мы использовали (3.3) чтобы сделать преобразование в (3.1),

позволяющее избавиться от ненужных скобок заключающихся в T. В качес-

тве другого примера преобразуем A ::= BC|BCD|Axz|Axy

а) Z б) Z

| |

*----*-* *-*-*-*-*-*-*

| | | | | | | | | |

E + T T + T + T + T

|

*--*-*

| | |

E + T

|

*-*-*

| | |

E + T

|