Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 100
Текст из файла (страница 100)
Под „окончанием цепочки с)ч подразумевается ее кратчайший суффикс, необходимый для определения значений 7'(а, е) и д(а, е). Реализация у и д в виде дерева решений приведена на рис. 5,18 Так как О=-О, то ветвление, соответствующее цепочкам длины л, отсутствует. Вершины с метками А и 5, лежащие ниже уровня 1, Опущены, так как все они, конечно, имеют выход о)нибка. 5А.2.
Грамматики смешанной стратегии предшествования К сожалению, реализация алгоритма а!= (1, д), построенного алгоритмом 5.17, требует довольно больших затрат памяти для хранения функций 1 и д. Можно определить класс грамматик 488 анализируемых методом „перенос — сверткаи с меньшими затратами, если использовать предшествование для локализации правого конца основы, а левый конец основы и нетерминал„которым надо ее заменить, определять с помощью лоКалЬНОГО КаптЕкета.
Рис. 5.)т. Функции перевеса и свертки. Пример 5.44. Рассмотрим (необратимую) грамматику слабого предшествовапия б с правялами 5 - ал(ЬВ Л -СЛ1) С1  — РВЕ! ~ РЕ1 С 0 Р 0 Š— 1 б порождает язык (аО" 1" ~ п~) 1) 11(ЬО" 1'" (п"=-: 1), который, как будет показано в гл, 8, не является языком простого пред- шествования. Отношения предшествоваиия для грамматики б даны иа рис.
5.19, Заметим, что б — необратимая грамматика, потому что 0--- правая часть двух правил: С 0 и Р— О. Однако ,Уачча(С) ((а, О, е), (С, О, е)) и Я,,(Р) =((Ь, О, е), (Р, О, е)). Поэтому если 0 выделен в качестве основы правовыводимой цепочки, то символ, расположенный непосредственно слева от О, определяет, свернуть ли 0 к С илн к Р.
А именно, первое из этих правил выбирается, если это символ а или С, а второе— если это Ь или Р П Пример 5.44 подсказывает следу)ощее определение, а.а ДРКГиг клАссы ГРАЯИАтик 493 гл. а. однопроходный синтлксичнскип лнллиз вез возвплтов Условия (1) и (2а) — это условия слабого предшествования. Таким образом, на простую ССП-грамматику можно смотреть как па (возможно, не обратимую) грамматику, в которой одного символа левого контекста достаточно, чтобы сделать правильный выбор из правил с одинаковыми правыми частями (условие (2б)), В этом и заключается смешанная стратегия разбора, использующая предшествование, для ССП-грамматик.
Алгоритм 5,18. Построение алгоритма разбора для ССП грамматик. Вход. (р, д; т, и)-ССП-грамматика 6= (Х, Х, Р, В) с зану. мерованнымн правилами. Выход. Алгоритм 4==-((, лг) типа ,„перенос †сверт" для грамматики б, Метод. (1) Пусть (сс(=р и 1х(=-д. Тогда (а) ~(а, х)=перенос, если ас х или а ' х, б) ) (а, х)=свертка, если а)х. (2) (8РВ, 54) =- допуск. (3) ) (Т, ш)=-ошибка в остальных случаях. (4) Пусть Яхм а(А) содержит (а, (1, х) и А- 5 — правило с номером г'. Тогда д(а(), х) — с'.
(5) к(Т, ш)=ошибка в остальных случаях. (д Теорема 5.24. Алгоритм 5 18 строигп алгоритм 4= (1, й), корректный длн грамматики б. Доказательство. Упражнение. Достаточно доказать, что каждая ССП-грамматика является ОПК-грамматикой, а за Гем показать, что функции ~ и д, определяемые алгоритмом 5.18, согласуются с функциями, определяемыми алгоритмом 5.17. () $.4.3. Грамматики операторного предшествоввння Существует эффективная процедура разбора для класса грам. матик, называемых грамматиками операторного предшествовання Разаор методом операторного предшествования прост для реалн.
зации. Он использовался во многих компиляторах. Определение. Операторной грамматикой называется приве. денная КС-грамматика без е-правил, в которой правые части правил не содержат смежных нетерминалов. Для операторной грамматики отношения предшествовання можно задать на множестве терминалов плюс символ $, игнорируя нетерминалы. Пусть 6=(Г1, Х, Р, В) — операторная грам- 492 матика и 3 — новый символ. Зададим отношения операторного предшествования на множестве Х 0 (5): (!) а Ь, если А- ссауЬ(1.ЕР и ТЕ(А(0(е), (2) а ° Ь, если А — ~ааВ5ЕР и В=Р+УЬ5, где ТЕХ0(е), (3) а егЬ, если А аВЬ56 Р и В~а биу, где ТЕ Х0(е), (4) 8(а, если В=>' Таа и у Е1Ч0 (е), (5) а) 5, если В=э' аау и у 6га 0(е). Операторная грамматика 6 называется грамматикой опера- торного предшествования, если между любыми двумя терминаль- ными символами выполняется ие более одного отношения опе- раторного предшествования.
Пример 5.45. Грамматика б,— классический пример грамма- тики операторного предшествования (1) Š— Е+ Т (2) Š— Т (3) Т- Т. Р (4) Т вЂ” Р (5) Р— (Е) (б) Р— а Отношения операторного предшествования для этой грамматики приведены на рис, 5.20. П Для грамматики операторного предшествования можно эффективно находить аостовные" разборы. Идея синтаксического ана- Г и " + ) 4 Рпс, 5.20. Отношении операторного предшестаоаапиа Аля грамматика Оа, лиза та же, что и для грамматик простого предшествовапня.
Легко убедиться в справедливости следующей теоремы. Теорема 5.25. Пусть 6=((А(, Х, Р, Я) — операторная грамматика и 885=>,"аАш=>гирш. Тогда (1) отношение операторною пргдшествования ( или ' выполняется между последовательными терминалами (и символом 5) цепочки и; Гл «одпопгоходный синтаксический лнллиз Без ВОЯВРАтОВ ьл. деигне классы го«ммхтик (2) отношение < выполняется между самым правым терми.
налом цепочки а и самым левым терминалом цепочки р; (3) отношении ' выполняется л!ежду последовательными терминалами цепочки)»; (4) отношение «» выполняется между самым правым терминалом цепочки»1 и первым символом цепочки ш. Доказательство. Упражнение, ь) Следствие. Если 6 — грамматика операторном предшество ванин, то к каждол«у из утверждений (1) — (4) теоремы 5.2о можно добавить слова „и никакие другие отношения не выполняются '. Д о к а з а т е л ь с т в о.
Вытекает непосредственно из определения грамматики операторного предшествования. Г) Итак, с помощью алгоритма разбора типа „перенос — свертка" легко выделить терминальные символы„входящие в основу. Однако возникают проблемы в связи с петерминальными символами, поскольку на них не определены отношения операторного предшествования. Тем пе менее тот факт, что мы располагаем операторной грамматикой, позволяет строить „остовный" правый разбор. Пример 5,46.
Разберем цепочку (а+ а)» а в соответствии с отношениями операторного предшествования для грамматики 6,, приведенными на рис. 5.20. Мы не будем заботиться о нетерминалах, а просто заменим каждый из них символом Е. Тогда нам не надо беспокоиться о том, свернуть ли г к Т или Т к г (хотя в данном случае с такими проблемами можно было бы справиться, выйдя за пределы метода операторного пред- шествования). Можно эффективно сделать разбор в соответствии с грамматикой 6 с правилами (1) Е. Е+ Е (3) Е- Е«Е (5) Š— «(Е) (6) Š— а полученной из 6, заменой всех иетерминалов символом Е и устранением всех цепных правил. (Заметим, что в операторной грамматике правилам, пе содержащим терминалов в правой части, может быть только цепное правило,) Грамматика 6, очевидно, не однозначная, но отношения операторного пред!пествовання гарантируют единственность искомого разбора.
Алгоритм разбора 4 для грамматики 6 задается определяемыми ниже фуикциямн ! и я. Цепочки, которые служат аргументами этих функций, будут состоять только из тер- 494 миналов грамматики 6, и символов $ и Е. Далее, у обозначает Е или пустую цепочку, Ь и с — терминалы или $. ~ перенос, если Ь(с или Ь ° о свертка, если Ь «» с, ( ) ! (Ьу с) =- ошибка в остальных случаях. (2) д(Ьуа, х) =--6, если Ьгаа, д(ЬЕ~ Е, х) =-3, если Ь(«, д(ЬЕ+Е, х)- 1, если Ь< +, д(Ьу(Е), х) = — 5, если Ь< ° (, д(а, х) =ошибка в остальных случаях.
Такйм образом, для входной цепочки (а+а)«а алгоритм А сделает такую последовательность шагов: [$, (а+а) «а$, е)» — '[$(, а+а) «а$, е) »-«[$(а +а)«$ г) »-"[$(Е + ). $. 6) »-'[$(Е+, а) «а$, 6) » '[$(Е+а, ) «а$, 6) » — "[$(Е+Е, )«а$, 66) » — "[$(Е, ) «а$, 661) »-'[$(Е), «а$, 66!) »-" [$Е, «а$, 66! 5) » — '[$Е«, а$, 66!5) » — *[$Е «а, $, 6615) »-'[$Е«Е, $, 66!56) »-"[$Е, $, 661563) »- допуск Можно убедиться в том, что 661563 — действительно остовный правый разбор цепочки (а+а)«а в грамматике 6. Этот остовный разбор цепочки (а-»-а) «а можно представить в виде дерева на рис. 5.21. Заметим, что можно было бы дополнить дерево остовного разбора иа рис. 5.21 так, чтобы получилось соответствующее дерево в грамматике 6„.
Но на практике в этом часто нет необходимости. Цель построения дерева — трансляция, а естественный перевод нетерминала Е, Т или Р грамматики 6,— это программа машины, вычисляющая выводимое из него выражение. Поэтому если применяется правило Š— Т или Т вЂ” Р, то перевод правой части будет скорее всего тот же, что и левой части. 495 гл. з. однопроходный синтлксическип лнллиз вез возврлтов Пример 5.46 представляет собой частный случай метода, работающего для многих грамматик, особенно для тех, которые определяют языки„являющиеся множествами арифметических выражений.
Этот метод включает построение новой грамматики, получаемой из старой заменой всех нетерминалов одним нетерминалом н устранением цепных правил. Для грамматики операторного предшествования всегда можно с помощью алгоритма а а Рве. 5.2!. Дерево оставвого разбора, типа „перенос †сверт" найти один разбор для каждой входной цепочки. Очень часто для целей трансляции достаточно новой грамматики и соответствующего ей анализатора. В таких ситуациях разбор методом операторного предшествования особенно прост и эффективен. Определение. Пусть 6 .((ч, л, Р, 5) †операторн грамматика. Остовной грамматикой для 6 назовем грамматику 6, =. ((5), л, Р', 5), содержащую каждое правило 5 — Х,...Х,„, для которого в Р найдется такое правило А- )'4...)', что для 1 =1~т (1) Хз- — 1'с если УгЕХ, (2) Х, = 5, если 1'; Е 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
