Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364139
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21319)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8692)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Алгоритм нисходящего разбора. Нисходящие распознаватели
Раздел: Рефераты по информатике, программированию
Тип: реферат Добавлен 21:42:08 09 апреля 2007 Похожие работы
Просмотров: 428 Комментариев: 22 Оценило: 3 человек Средний балл: 5 Оценка: неизвестно     Скачать

1. Задача разбора

Разбор сентенциальной формы означает построение вывода и, возможно

синтаксического дерева для нее. Программу разбора называют также рас-

познавателем, так как она распознает только предложения рассматривае-

мой грамматики. Именно это и является нашей задачей в данный момент.

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

тмами слева направо ввиду того, что они обрабатывают сначала самые ле-

вые символы обрабатываемой цепочки и продвигаются по цепочке только

тогда, когда это необходимо. Можно подобным способом определить разбор

справа налево, но он менее естественен. Инструкции в программе выполня-

ются слева направо, да и мы читаем слева направо.

Различают две категории алгоритмов разбора: нисходящий (сверху вниз)

и восходящий (снизу вверх). Их называют также разверткой и сверткой.

( В данном реферате будет рассмотрен процесс только нисходящего раз-

бора. ) Соотетственно, эти термины соответствуют и способу построения

синтаксического дерева. При нисходящем разборе дерево строится от корня

( начального символа ) вниз к концевым узлам. Метод восходящего разбора

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

к начальному символу. В качестве примера нисходящего разбора рассмотрим

предложение (1) в следующей грамматике целых чисел ( последовательностей,

состоящих из одной и более цифр ):

N ::= D | ND

D ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (1)

На первом шаге непосредственный вывод N => ND будет строиться так,

как показано в первом дереве на рис. 1. На каждом последующем шаге

самый левый нетерминал V текущей сентенциальной формы xVy заменяется

на правую часть u правила V ::= u, в результате чего получается сле-

дующая сентенциальная форма. Этот процесс для предложения (1) предс-

тавлен на рис. 1. в виде пяти деревьев. Фокус в том, конечно, что

надо получить ту сентенциальную форму, которая сопадает с заданной

цепочкой.

N N N N N

| | | |

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

| | | | | | | |

N D N D N D N D

| | | |

D D D 5

| |

3 3

N => N D => D D => 3 D => 3 5

Рис. 1. Нисходящий разбор и построение

вывода

2. Нисходящие разбор с возвратами

Алгоритм нисходящего разбора строит синтаксическое дерево, как уже

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

жения, как было показано ранее. Описание усложняется главным образом

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

вным образом для того, чтобы выполнять возвраты с твердой уверенностью,

что все возможные попытки построения дерева были предприняты.

Чтобы свести осложнеия к минимуму, давайте опишем этот алгоритм раз-

бора образно. Вообразим, что на любом этапе разбора, в каждом узле уже

построенной части дерева находится по одному человеку. Люди, которые

находятся в терминальных узлах, занимают места соответственно символам

предложения.

Некоему человеку надлежит провести разбор предложения x. Прежде все-

го ему необходимо отыскать вывод Z => +x, где Z - начальный символ; сле-

довательно первым непосредственным выводом должен будет быть вывод

Z => y где Z ::= y - правило. Пусть для Z существуют правила

Z ::= X X .. X | Y Y .. Y | Z Z .. Z

1 2 n 1 2 m 1 2 1

Сначала человек пытается определить правило Z ::= X X .. X . Если

1 2 n

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

нить второе правило Z ::= Y Y ... Y . В случае неудачи он переходит к

1 2 m

следующему правилу и т.д.

Как ему определить, правильно он выбрал непосредственный вывод

Z => X X .. X ? Заметим, что если вывод правилен, то для некоторых

1 2 n

цепочек x будет иметь место x=x x .. x , где X => *x для i=1,...,n.

i 1 2 n i i

Прежде всего человек, выполняющий разбор, возьмет себе приемного сына

M , который должен будет найти вывод X =>*x для любого x , такого,

1 1 1 1

что x = x ... Если сыну M удастся найти такой вывод, он (и любой из

1 1

сыновей, внуков и т.д.) закрывает цепочку x в предложении x и сообща-

1

ет своему отцу об успехе. Тогда его отец усыновит M , чтобы тот нашел

2

вывод X => *x , где x = x x ... и ждет ответа от него и т.д. Как толь-

2 2 1 2

ко сообщил об успехе сын M ,он усыновит еще и M , чтобы тот нашел

i-1 i

вывод X => *x . Сообщение об успехе, пришедшее от сына M , означает

i i n

что разбор предложения закончен.

Как быть, если сыну M не удается найти вывод X =>*x ? В этом

i i i

случае M сообщает о неудаче своему отцу; тот от него отрекается и

i

дает старшему брату M ,M такое распоряжение: "Ты уже нашел вывод,

i i-1

но этот вывод неверен. Найди-ка мне другой". Если M сумеет найти

i-1

другой вывод, он вновь сообщит об успехе, и все продолжится по-пре-

жнему. Если же M сообщит о неудаче, отец отречется и от него, и

i-1

тогда уже старшего брата M , попросят предпринять еще одну попыт-

i-2

ку. Если придется отречься даже от M , значит, непосредственный вы-

1

вод Z => X X .. X был неверен, и человек, начинавший разбор, попы-

1 2 n

тается воспользоваться другим выводом Z => Y .. Y .

1 m

Как же действует каждый из M ? Положим, его целью является тер-

1

минал X . Входная цепочка имеет вид x=x x ..x T.. ,где символы в

1 2 i-1

x ,x ,...,x уже закрыты другими людьми. M проверяет, совпадает

1 2 i-1 i

ли очередной незакрытый символ T с его целью X . Если это так, он

i

закрывает этот символ и сообщает об успехе. Если нет, сообщает об

неудаче.

Если цель M - нетерминал X , то M поступает точно так же, как

1 1

и его отец. Он начинает проверять правые части правил, относящихся к

нетерминалу, и, если необходимо, тоже усыновляет или отрекается от

сыновей. Есливсе его сыновья сообщают об успехе то M в свою очередь

i

сообщает об успехе отцу. Если отец просит M найти другой вывод, а це-

i

лью является нетерминальный символ, то M сообщает о неудаче, так как

i

другого такого вывода не существует. В противном случае M просит своего

i

младшего сына найти другой вывод и реагирует на его ответ также, как и

раньше. Если все сыновья сообщат о неудаче, он сообщит о неудаче свое-

му отцу.

Теперь, наверное, понятно, почему этот метод называется прогнозиру-

ющим или целенаправленным. Используется и название "нисходящий" из-за

способа построения синтаксического дерева. При разборе отправляются от

начального символа и нисходят к предложению (см рис. 2)

Z

|

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

| | |

F | T

| | |

T |

| |

F |

| |

i + i * i

Рис. 2. Частичный нисходящий разбор предложения i+i*i.

Привлекательность этого метода (и его представления) в том и сос-

тоит, что каждый человек должен помнить лишь о своей цели, о своем от-

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

почке. И никому не нужны точные сведения о том, что происходит в других

местах. Это как раз и есть то, к чему мы вообще стремимся в программиро-

вании: в каждом сегменте программы или в подпрограмме необходимо забо-

титься о собственной входной и выходной информации и ни о чем более.

Для имитации усыновления и отречения сыновей в программах использу-

ют стек типа LIFO (последний вошел - первый вышел), или, как его иногда

называют, "магазин".

Опишем алгоритм в более явном виде:

Положим, во-первых, что грамматика задана списком в одномерном мас-

сиве GRAMMAR таким образом, что каждое множество правил

U ::= x|y|...|z

представлено, как Ux|y|...|z|$. То есть каждый символ занимает одну

ячейку, за каждой правой частью следует вертикальная черта "|", а за

последним символом следует "|$". Таким образом, грамматика

Z ::= E#

E ::= T+E|T

T ::= F*T|F

F ::= (E)|i

будет выглядеть как

ZE#|$ET+E|T|$TF*T|F|$F(E)|i|$

Каждый элемент стека соответствует человеку и состоит из пяти

компонент

(GOAL,i,FAT,SON,BRO)

которые означают следующее:

1. GOAL - цель, т.е. символ, который человек ищет. Таким обра-

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

найти такую голову, которая приводится к GOAL, и закрыть ее. GOAL

передается ему отцом.

2. i - индекс в массиве GRAMMAR, указывающий на тот символ в

правой части для GOAL, с которым человек работает в данный момент.

3. FAT - имя отца (номер элемента стека, соответствующего от-

цу).

4. SON - имя самого последнего (младшего) из сыновей.

5. BRO - имя его старшего брата.

Нуль в любом из полей означает, что данная величина отсутствует.

В программе значение переменной v равно количеству участвующих в

разборе людей (количеству элементов в стеке в текущий момент), c -

имя (номер элемента в стеке) человека, работающего в данный момент.

Остальные ожидают конца его работы. Индекс j относитстя к самому ле-

вому (незакрытому) символу входной цепочки INPUT(1),...,INPUT(n).

а) Z б) СТЕКЦЕЛЬ i FAT SON BRO

|

*---------*------* 1 Z 4 0 15 0

| | 2 E 10 1 7 0

E # 3 T 20 2 4 0

| 4 F 28 3 5 0

*--*------* 5 i 0 4 0 0

| | | 6 + 0 2 0 3

T | E 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| | | | *-----* | | \ /

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

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

| | А | *---*---*

|<--------* | *--| 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. Расположение компонент узла синтаксического

графа грамматики

Подробно о синтаксических графах см. в книге Д.Гриса "Конструи-

рование компиляторов для цифровых вычислительных машин"

Разбор без возвратов

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

гать к возвратам. Мы должны иметь уверенность в том, что каждая пред-

полагаемая цель верна. Это нреобходимо потому, чтонам предстоит связать

семантику с синтаксисом, и по мере того, как мы будем прогнозировать и

находить цели, эти символы будут обрабатываться семантически. Вот неко-

торые примеры "обработки": 1) при обработке описаний переменных иденти-

фикаторы помещаются в таблицу символов; 2) при обработке арифметических

выражений проверяют, совместимы ли типы операндов.

Если возврат произошел из-за того, что прогнозируемая цель неверна,

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

время поисков этой цели. Сделать это не так -то просто, поэтому постара-

емся провести грамматический разбор без возвратов.

Для того, чтобы избавиться от возвратов, в компиляторах в качестве

контекста обычно используется следующий "незакрытый" символ исходной про-

граммы. Тогда на грамматику налагается следующее требование: если есть

альтернативы x|y|...|z, то множества символов, которыми могут начинаться

выводимые из x,y,..,z слова, должны быть попарно различны. То есть если

x => *Au и y => *Bv то A =/= B. если это требование выполнено, можно

довольно просто определить, какая из альтернатив x,y или z - наша цель.

Заметим, что факторизация оказывает здесь большую помощь. Если есть пра-

вило U ::= xy|xz, ео преобразование этого правила к виду U ::= x(y|z)

помогает сделать множесва первых символов для разных альтернатив непе-

ресекающимися.

4. Заключение

В данном реферате рассматривались нисходящие распознаватели,

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

разбором. Одна из первых статей, рассматривающих фиксированный ал-

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

являлся нисходящим разбором в чистом виде, а являлся смешением нис-

ходящих и восходящих разборов. Алгоритм, приведенный в данном рефе-

рате, впервые был предложен в обзоре Флойда. Он же ввел и понятия

"отец - сын - брат". Способы избавления от возвратов описаны Унге-

ром.

5. Список литературы

1. Грисс. Конструирование компиляторов для цифровых вы-

числительных машин. М., Мир, 1975г.

2. Ахо А., Ульман Дж. Теория синтаксического анализа, пере-

вода и компиляции. М. Мир 1978г.

3. Ф.Льюис, Д.Розенкранц, Р.Стирнз. Теоретические основы

проектирования компиляторов. М., Мир, 1979г.

4. Фельдман Дж., Грис Д. Системы построения трансляторов.

Сб. Алгоритмы и алгоритмические языки, вып.5, ВЦ АН СССР, 1971г.

_

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Хватит париться. На сайте FAST-REFERAT.RU вам сделают любой реферат, курсовую или дипломную. Сам пользуюсь, и вам советую!
Никита06:08:55 02 ноября 2021
.
.06:08:53 02 ноября 2021
.
.06:08:53 02 ноября 2021
.
.06:08:52 02 ноября 2021
.
.06:08:52 02 ноября 2021

Смотреть все комментарии (22)
Работы, похожие на Реферат: Алгоритм нисходящего разбора. Нисходящие распознаватели

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(288293)
Комментарии (4159)
Copyright © 2005-2021 HEKIMA.RU [email protected] реклама на сайте