значением поля S(7).BRO; - цель этого сына - символ +. Имя старшего
сына находится в поле BRO человека 6 и равно 3.
Очевидно, что у нас имеется список сыновей каждого человека и
элементы этого списка связаны в стеке между собой. То есть стек в его
окончательном виде представляет собой внутреннюю форму синтаксического
дерева.
Рассмотрим теперь сам алгоритм нисходящего разбора. Для удобства
чтения разделим его на шесть поименованных частей.
1. НАЧАЛЬНАЯ УСТАНОВКА
S(1) := (Z,0,0,0,0); c:=1; v:=1; j:=1; переход на НОВЫЙ ЧЕЛОВЕК
(первое усыновление. Цель усыновления - начальный символ Z.)
2. НОВЫЙ ЧЕЛОВЕК
IF GOAL терминал THEN Новый человек изучает свою цель.
IF INPUT (j)=GOAL THEN Цель - терминал.
BEGIN j:=j+1; Если GOAL совпадает с символом из
GO TO УСПЕХ; предложения, человек закрывает этот
ELSE GO TO НЕУДАЧА символ и сообщает об успехе.
i:= индекс в GRAMMAR правой Не совпадает - сообщает об неудаче.
части для GOAL; Цель нового человека - нетерминал.
GO TO ЦИКЛ Подготовка к просмотру правых частей
в правилах для GOAL
3. ЦИКЛ
IF GRAMMAR(i)="|" Просмотр правой части
THEN IF FAT=/=0 Достигли конца правой части, поэтому
THEN GO TO УСПЕХ сообщаем об успехе. Если нет отца,
ELSE STOP - предложение; то останов - окончен разбор
предложения
IF GRAMMAR(i )="$" Нет больше правых частей, которые
THEN IF FAT=/=0 можно было бы попробовать, поэтому
THEN GO TO НЕУДАЧА сообщение о неудаче или, если нет отца
ELSE STOP - не остановка, не распознав предложения
предложение;
v:=v+1; GRAMMAR(i) - другая цель, которую
S(v):=(GRAMMAR (i),0,c,0, можно попытаться найти. Берем сына.
SON); Тогда старший брат - тот, кто был до
этого младшим сыном
Переключить внимание на младшего сына
SON:=v; c:=v; и ждать от него ответа
GO TO НОВЫЙ ЧЕЛОВЕК
4. УСПЕХ
c:=FAT; Сообщить об успехе своему отцу. Он
i:=i+1; GO TO ЦИКЛ предпримет следующий шаг.
5. НЕУДАЧА
c:=FAT; Сообщить о неудаче своему отцу. Он
v:=v-1; отречется от сына и попросит его
SON:=S(SON).BRO; старшего брата предпринять еще одну
GO TO ЕЩЕ РАЗ попытку.
6. ЕЩЕ РАЗ
IF SON=0 THEN Есть ли еще сын, который может пред-
BEGIN WHILE GRAMMAR(i) принять еще одну попытку? Нет.
=/="|" Тогда пропускается правая часть -
DO i:=i+1; Это не та, которая нужна - переход к
i:=i+1 GO TO ЦИКЛследующей.
END;
i:=i-1; c:=SON; Естьсын. Его просят повторить попытку
IF GOAL нетерминал Его цель - нетерминал, так что он по-
THEN GO TO ЕЩЕ РАЗ пытается еще раз добиться успеха.
j=j-1 Его цель терминал. Попытка не приведет
GO TO НЕУДАЧА к успеху. Поэтому он открывает свой
символ и сообщает о неудаче.
Блок схема данного алгоритма приведена ниже.
*---------*
| 1 |
*----*----*
*---------------------------->| *------*
| * *----->| |<------*
| Нет / \ | | | |
| *-----------< 2 > | | * |
| Нет / \ А \ / | | Д / \ |
| *----------< 4 > | * | *-------< 9 > |
| | \ / | | | | | \ / |
| | * | | | | | * |
| | | Да | | Да | | | | Нет |
| | * | | | | | *---*---* |
| | *---* Н / \ | | | | | | 10 | |
| | | 6 |--< 5 > | * | | | *---*---* |
| | *---* \ / | / \ | | | | |
| | * | *-< 3 > | | | * |
| | | Да | | \ / | | | / \ Да |
| *-* | | | * | | | <1 1>-----*
*-|7| | | | *-----* | | \ /
*-* | | | Нет | | *
| *--|-------------* | | Нет
| | А | *---*---*
|<--------* | *--| 1 2 |
*---*---* | *-------*
| 8 |-------*
*-------*
Рис 4. Блок-схема алоритма нисходящего разбора
1. S(1) := (Z,0,0,0,0); c:=1; v:=1;
2. GOAL - терминал ?
3. j:=j+1; INPUT(j)=GOAL ?
4. GRAMMAR(i)="Конец" ?
5. FAT =/= 0 ?
6. STOP - Конецработы;
7. v := v+1; S(v) := (GRAMMAR (i),0,c,0,SON);
SON := v; c := v;
8. c := FAT; i := i+1;
9. SON = 0 ?
10. Пока GRAMMAR (i) =/= "Конец":
i := i+1,
j:=j+1;
i :=i -1;
c := SON;
11. GOAL - нетерминал ?
12. C := FAT ; v := v-1; SON := S (SON) * BRO.
3. Проблемы нисходящего разбора
Прямая левосторонняя рекурсия
В алгориме, описанном ранее, есть один серьезный недостаток,
который проявляется, когда цель определена с использованием левосто-
ронней рекурсии. Если 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|Л), где Л - пустая цепочка. Когда бы ни использовалось по-
добное преобразование, Л всегда помещается как последняя альтернати-
ва, так как мы принимаем условие, что если цель - Л, то эта цель все-
гда сопоставляется.
Помимо того что факторизация позволяет нам исключить прямую реку-
рсию, использование этого приема сокращает размеры грамматики и позво-
ляет проводить разбор более эффективно. В этом мы убедимся позже.
После факторизации (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
|
T
Рис 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. Как проверить это отношение, нам уже известно.
Представление грамматики в оперативной памяти
Одной из проблем, возникающих при реализации нисходящих методов,
является представление грамматики в вычислительной машине. Одно из
возможных представлений уже использовалось ранее. Очевидно, что оно
неудачно из-за обьема работы необходимой для поиска правил, соответст-
вующих каждому нетерминалу. Речь пойдет о другом представлении. Прежде
чем начать изложение, стоит упомянуть о том что написать конструктор,
который воспринимает грамматику, проводит любые из преобразований, о
которых только что говорилось, проверяет не являются ли правила рекур-
сивными, и составляет таблицы для грамматики в одной из описываемых да-
лее форм довольно легко.
Для представления грамматики используется списочная структура, на-
зываемая синтаксическим графом. Каждый узел представляет символ S из
правой части и состоит из четырех компонент: ИМЯ, ОПРЕДЕЛЕНИЕ (ОПР),
АЛЬТЕРНАТИВА (АЛТ) и ПРЕЕМНИК (ПРЕМ), где
1. ИМЯ - это сам символ S в некоторой внутренней форме.
2. ОПРЕДЕЛЕНИЕ равно 0, если S - терминал; в противном случае эта
компонента указывает на узел соответствующий первому символу в
перво правой части для S.
3. АЛЬТЕРНАТИВА указывает на первый символ той альтернативы пра-
вой части которая следует за правой частью, содержащей данный
узел (0, если такой правой части нет). Это только для символов
в правых частях.
4. ПРЕЕМНИК указывает на следующий символ правой части (0, если
такого символа нет).
Кроме того, каждый нетерминальный символ представлен узлом, состо-
ящим из одной компоненты, которая указывает а первый символ в первой
правой части, относящейся к этому символу. Примером может служить
рис. 4, на котором изображено расположения компонент узла синтаксическо-
го графа грамматики:
*---------------------------*
| ИМЯ |
*--------*---------*--------*
| ОПР | АЛТ | ПРЕМ |
*--------*---------*--------*
Рис 6. Расположение компонент узла синтаксического
графа грамматики
Подробно о синтаксических графах см. в книге Д.Гриса "Конструи-
рование компиляторов для цифровых вычислительных машин"