Карпов - Основы построения трансляторов (2005) (943926), страница 23
Текст из файла (страница 23)
Хлава 5 посвящена изложению методов детерминированного нисходящего синтаксического анализа; каждый такой метод работает только для подкласса КС-грамматик. Алгоритм восходящего синтаксического анализа, или алгоритм "снизу вверх" работает следующим образом (рис. 4.3, в). Начиная от терминальной строки листьев дерева пытаемся найти так называемую связку — правую часть продукции грамматики, которую нужно заменить нетерминалом (левой частью продукции), чтобы получить новый узел синтаксического дерева. Формально связкой сентенциальной формы р называется самая левая цепочка Р (возможно, пустая), такая, что существует вывод Я ==>* аАу ==> а~у = ц.
С точки зрения грамматического вывода, восходящие алгоритмы синтаксического анализа восстанавливают такой вывод, двигаясь назад от результирующей цепочки к начальному символу грамматики. Основным повторяющимся вопросом здесь является следующий: какую подстроку в проме>куточной цепочке вывода — сентенциальной форме — нужно выбрать в качестве связки и каким нетерминалом ее заменить с получением предыдущей сентенциальной формы вывода исходной терминальной цепочки, чтобы, в конце концов, свернуть всю цепочку к начальному нетерминалу 5? 150 Глава 4 На рис.
4,3, в показаны несколько шагов простейшего алгоритма "грубой силы", пытающегося решить эту задачу простым перебором. На первом шаге в исходной терминальной цепочке аЬоссаЬс находим первую слева связку— подцепочку аК которая представляет собой правую часть одной из продукций грамматики, а именно продукции А-+аЬ. После замены связки нетерминалом А получаем цепочку АЬссабс. Применение этого алгоритма приводит через несколько шагов к тупиковой ситуации — цепочке АоАВ, в которой не может быть найдено никакой связки, и дальнейшие свертки невозможны. Поэтому и здесь требуется бэктрекинг, Чтобы его избежать и строить синтаксическое дерево без возвратов, для грамматики должен быть сформулирован критерий однозначного определения (например, самой левой) связки в любой сентенциальной форме порождаемого языка.
Возможных сентенциальных форм порождаемого языка в общем случае бесконечное число, поэтому найти такой критерий непросто. булава 6 посвящена изложению методов детерминированного восходящего синтаксического анализа; каждый такой метод работает только для подкласса КС-грамматик. Изучаемые в следующих двух главах подклассы КС-грамматик отличаются тем, что для каждого из них сформулированы более тонкие, чем в указанных алгоритмах "грубой силы", правила принятия решения при выполнении шагов либо нисходящего, либо восходящего синтаксического анализа.
Грамматика попадает в данный класс тогда, когда такие правила в этой грамматике дают однозначный ответ для каждой из возможных ситуаций ~среди бесконечного их числа) при выполнении шагов соответствующего алгоритма синтаксического анализа. На рис. 4.4 схематично представлено соотношение между различными подклассами КС-грамматик. Для всех КС-грамматик существуют общие неэффективные алгоритмы как нисходящего, так и восходящего синтаксического анализа. Выделенные собственные подклассы — это те КС-грамматики, для которых были найдены различные по простоте и эффективности специфические алгоритмы нисходящего либо восходящего синтаксического анализа. В некоторых случаях эквивалентные преобразования грамматик ~в частности, приведенные в данной главе) или даже некоторое изменение грамматики и языка„порождаемого ею, помогают привести исходную грамматику к виду, для которого проведение синтаксического анализа возможно некоторым эффективным алгоритмом.
Это, однако, следует делать осторожно, поскольку такие преобразования могут увести довольно далеко от поставленной цели построения корректного дерева вывода для всех цепочек языка: иос ге лреобразоваиия,иы буде и спгроипгь дерево вывода для грач.чагггики, опггичной опг исходиой! Теория контекстно-свободных языков Рис. 4.4. Подклассы КС-грамматик, допускающие эфФективные методы синтаксического анализа Задачи к главе 4 1. Редуцировать следующие грамматики, выбросив все бесполезные продукции. Какой язык порождает каждая из этих грамматик? б~. 1. 5-+а,ЯВс 2.  — +сВ 3.
5 — +ВаИ 4. С вЂ” +ЬСс 5. А-+Вс5 6. С-+с.ОА 7. А->асЬ 9. В-+Я~В 10. Е-+ВсАе ! О. Е-+се 2. Для грамматики арифметических выражений построить эквивалентную грамматику без сингулярных продукций (т. е. продукций вида А-+В). 3. По следующим грамматикам построить эквивалентные е-свободные грамматики: 61. '5-+АИА6 5-+ВОВа 1.
5 — >ЯАС 2.  — +Ес 3. 5 — +ВША 4. С вЂ” +ЬСС 5. А-+ВсЯ 6. С-+соА 7. А-ккЬ 8. Π— >САХ) 1. 5-+аС 2.  — +сАЬ 3. Ж вЂ” +ВгХ4 4. С.' — ~.ОВ 5. А-+с5 6. С-+сА 7. А-+а 8. 0 — +сСА.О Глава 4 4. По грамматике: Ь .Ь~ ~ Д ~ .. построить эквивалентную ациклическуго грамматику (грамматику, не допускающую выводов вида А =~* А). 5. Разработать алгоритм для избавления от прямой левой рекурсии в нескольких альтернативах, Преобразовать к виду без прямой левой рекурсии грамматику 5-+Ы ~ (5) ~ АаАЬ, А-+АЬЯа ~ иЬ. 6. Преобразовать следующие грамматики: а) в грамматики без левой рекурсии; б) в нормальную форму Хомского: : б2.
1.5 — +ЯАс: б». 1.5 — ~Вс/А 2. 5 — +ВША:: :2. Я вЂ” +5'СА 3. А-+АсВЛ' 4. А — +ас 3. А-+Ас 4.  — +сАЬ 5. В-+Ь: ::5. А-+и 6.  — ~Вс, '.:6.  — ьВБЬ 6..0-+с 7. Для следующих грамматик постройте .множества НКЯТ для всех альтернатив каждого нетерминала и множества 10П.0% дла каждого нетерминала: 6.: 1. Я вЂ” +ЯАс 2. 5-+е 3. А — +АсВ5 4. А-~ас 5.  — +с 6. В->Вс 6. Х) -н: 8. Для неукорачивающих КС-грамматик разработать общий рекурсивный алгоритм иисходяи~его синтаксического анализа, перебирающий все возможные альтернативы каждого нетерминала в некотором порядке при подстановке их на очередном шаге построения синтаксического дерева сверху вниз.
Применить его ко входной цепочке Ьссас в грамматике Ь'-+ЬЯс' ~ ЬАс ~ ЬАе„А-+И сА. 9. Для неукорачивающих КС-грамматик разработать общий рекурсивный алгоритм восходящего синтаксического анализа, последовательно перебирающий возможные связки в каждой промежуточной цепочке вывода на очередном шаге построения синтаксического дерева снизу вверх.
Применить его ко входной иепоике ЬссНс в грамматике У-+Ь:1с ~ ЬАс ~ ЬАе; А — и7~ сА. б1 '. 1. 5-+.ЯВс "  — +с.О 3. Я вЂ” +ВсИ 4.  — +Ь 5.  — +Х)Ва б1. .1. 5->Я~Вс 2. В-+со 3. Я вЂ” +ВсИ 4.  — +е 5. Π— +.0Ва б»'. 1. Я вЂ” +Вы~А 2. К вЂ” +5'сА 3. А — +Ас 4.  — +е 5. А — +а 6. В-+ВЫ ГЛАВА 5 Нисходящие методы синтаксического анализа В предыдущих главах было показано, что использование синтаксически-ориентированного подхода к обработке символьных цепочек очень удобно не только для трансляции языков программирования, но и для решения многих других задач преобразования символьных последовательностей. Основной идеей этого подхода является использование структуры входной цепочки для генерации требуемого выхода. Структура цепочки представляется ее выводом в заданной грамматике из начального символа.
Поэтому становится ясной необходимость при трансляции фазы восстановления вывода входной цепочки в заданной грамматике, т. е. фазы синтаксического анализа. В данной главе мы рассмотрим одну из стратегий синтаксического анализа для контекстно-свободных грамматик Хомского: нисходящую стратегию. Нисходящие алгоритмы синтаксического анализа, просматривая слева направо входную цепочку, пытаются восстановить левый канонический вывод этой цепочки из начального символа КС-грамматики.
В других терминах, нисходящая стратегия состоит в восстановлении дерева вывода заданной цепочки в заданной грамматике, начиная с корня дерева, т. е. сверху вниз. Простейший алгоритм, пытающийся решить эту задачу простым перебором, может пробовать очередную подстановку для самого левого нетерминала текущей сентенциальной формы. Если алгоритм не использует другой информации, кроме входной строки, проверяя, совпадает ли терминальный префикс новой сентенциальной формы с начальным префиксом входной строки, то в общем случае алгоритм ведет к многократным возвратам к предыдущим шагам. Однако для некоторых классов ~подмножеств) КС-грамматик выбор подстановки для самого левого нетерминала очередной сентенциальной формы можно сделать полностью однозначным, что позволяет для этих классов грамматик построить весьма эффективные алгоритмы нисходящего синтаксического анализа. К таким классам относятся автоматные грамма гики, ь-грамматики, грамматики рекурсивного спуска и 1 1 (~)-грамматики.
Глава 5 У54 Для трансляции автоматных грамматик метод нисходящего синтаксического анализа совершенно естественен и очень просто реализуется. Именно автоматными грамматиками описываются лексемы языка — минимальные единицы, имеющие смысл. Поэтому лексический анализ. составляющий первую фазу всех современных трансляторов, выполняется на основе автоматных грамматик. Проблема лексического анализа рассматривается в этой главе в качестве одного из примеров использования нисходящих методов синтаксического анализа.
В качестве другого примера рассматривается построение транслятора для языка Милан методом рекурсивного спуска. 5.1. Автоматные граииатики и конечные автоматы Автоматные грамматики — наиболее простой класс грамматик, допускающий простые и эффективные методы распознавания. Такими грамматиками могут быть описаны многие специализированные языки, в частности, языки задания информации для станков с программным управлением, входные языки пакетов прикладных программ моделирования электронных схем, лексемы языков программирования и т. д.
Мы рассмотрим здесь, как по любой автоматной грамматике, порождающей язык А, построить конечный автомат, распознающий Х,. Распознающий конечный автомат используется как основа трансляторов автоматных языков. В соответствии с классификацией Хомского, автоматные грамматики имеют следующие типы продукций: Рассмотрим пример автоматной грамматики: б»1. Я вЂ” +аЬ' ~ ЬА А — +аВ~ с  — +ЬА ~а Пусть 6 = ~Т, Х, Я, Л) — автоматная грамматика с конечным множеством терминалов Т, конечным множеством нетерминалов Ж, начальным нетерминалом Я и множеством продукций Я. Введем понятие "граф автоматной грамматики б".
Вершин у этого направленного графа ~ Ж~ ~-1, на единицу болыне, чем число нетерминальных символов грамматики б. Каждую из %вершин графа пометим одним из нетерминалов грамматики, а дополнительную вер- Нисходящие методы синтаксического анализа 155 шину пометим специальным символом Г. Назовем начальной вершиной ту, которая помечена начальным символом грамматики 5. Заключительной вершиной назовем дополнитнельную вершину Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
