Алгоритм нисходящего разбора. Нисходящие распознаватели
| + | 8 T 18 7 12 0
F T 9 F 28 8 10 0
| | 10 i 0 9 0 0
i *---*---* 11 * 0 8 0 9
| | | 12 T 20 8 13 11
F * T 13 F 28 12 14 0
| | 14 i 0 13 0 0
i F 15 # 0 1 0 2
|
i
Рис 3. Стек после нисходящего разбора i+i*i
а) - синтаксическое дерево б) - стек после разбора
Поле SON используется для хранения ссылки на последнего (младше-
го) сына. Тогда поле BRO элемента, соответствующего этому сыну, укажет
на старшего брата. В качестве иллюстрации расмотрим изображенное на
рис .3 а) синтаксическое дерево для предложения i+i*i вышеописанной
грамматики. Состояние стека после окончания работы показано на рис.3 б).
Теперь у человека 2(S (2)) есть цель E; предполагается, что он в соотве-
тствии с синтаксическим деревом использует правило E ::= T+E. Таким
образом, ему для того, чтобы найти символы T,+,E потребуется три сына.
Значение поля S(2).SON=7, так что младшим сыном является человек, c
номером 7, цель которого E. Имя среднего сына - число 6, определяется
значением поля 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| | | | *-----* | | /
*-* | | | Нет | | *
| *--|-------------* |