Xreferat.com » Рефераты по информатике и программированию » Алгоритм нисходящего разбора. Нисходящие распознаватели

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

7 E 12 2 8 6

| + | 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| | | | *-----* | | /

*-* | | | Нет | | *

| *--|-------------* |

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: