Карпов - Основы построения трансляторов (2005) (943926), страница 22
Текст из файла (страница 22)
Если и =" * е, то ебНКЯТ(0). Формально, НК5Т(я) = (пе Т ~ (х ==>* ОЯ~ ~(е ~ (х =Ф* 8~. Рассмотрим правила вычисления множества НКЯТ для любой цепочки а грамматики О. Теория контекстно-свободных языков Обычно исходная грамматика преобразуется так, что вводится новый начальный символ У с правилом Т вЂ” +Я, где 3 — новый терминал (правый ограничитель вводимой цепочки символов), а Я вЂ” старый начальный символ, В этом случае никакой нетерминальный символ исходной грамматики не может оказаться крайним справа символом при выводе сентенциальных форм в этой грамматике. Рекурсивный алгоритм для нахождения множества ГОЬЬО%(А) просматривает последовательно все продукции грамматики, в правой части которых встречается символ А, и для каждой такой продукции вида  — эаАР все элементы Г1КЯТ(р) кроме символа с помещаются в ГОЬЬ0%(А).
Если в этой продукции ~3 =>* я, то все элементы ГОЬ1 0%(В) помещаются в ГОЬ1.0%(А). Рассмотрим в качестве примера грамматику арифметических выражений, свободную от левой рекурсии (преооразованную так же, как грамматика в примере 4.4). ПРИМЕР 4.?. Найдем множества Г1КЯТ и ГОЬЬОФ для каждого нетерми- нала следующей грамматики арифметических выражений: Я-+Е3 //добавлен правый ограничитель к каждой выводимой строке языка Е-+ ТЕ' Е'-+~-ТЕ' ~ я Т вЂ” +ЕТ' T-+ "ГТ' ~ я Г-+(Е)! к Решение Г1КЯТ(Е) = Г1КЯТ(Т) = Г1КЯТ(Г) = Я, г' ~; .
Г1КЗТ(Е') = ~+, е~,: Г1К5Т(T) = ~*, с~; Г01 1 0%(Е) = Г01 Ь0%(Е') = (3,) ~; Г01 1.0%(Т) = ГОЬЬО%(Т') = ~+,), 3~; ГОЬ 0%(У') = (+, *,),3~. Рассмотрим первую строку решения. Поскольку для нетерминала Е в грамматике имеется только одно правило Е-+ТЕ', в котором первый символ — не- терминал, то НК5Т(Е) = Г1К5Т(Т). Аналогично НКБТ(Т) = Г1К5Т(Г). Наконец, по двум правилам для т"' находим Г1К5Т(Г) = ~с, ~~. Нахождение функции ГОЬЬ0% также просто. Для нетерминала Е существует две продукции, в которых Е находится в правой части: Я вЂ” +Е$ и à — >(Е).
От- Глава 4 сюда Г01.1.0%(Е) = ~ 3,) ~. Для определения множества Г01 1 0%(Е') найдем продукции, в которых Е' входит в правую часть. Таких продукций две: Е-+ТЕ' и Е' — ь+ТЕ'. Поскольку в этих продукциях Е' — последний символ, то, в Г0110%(Е') следует включить множество Г01 1.0%(Е') и ГО11.0%(Е). Первое множество очевидно, второе нами найдено, это ~3,)~. Далее, для не- терминала Т в грамматике есть два правила Š— +ТЕ' и Е'-++ТЕ'.
Следовательно, в множество Г01.1 0%(Т) включаем множество Г1В5Т(Е') — (е~, т. е. множество (+~. Однако Е' ==>* а, поэтому к ГОП.ОФ(Т) следует добавить множество Г01.1.0%(Е'). Окончательно, Г01.1.0%(Т) = (+,), 3~. 4.4. Алгоритмические проблемы Проблема называется алгоритмически разрешимой, если существует разрешающий ее алгоритм (разрешающая процедура). Если такой процедуры не может существовать, проблема называется алгоритмически неразрешимой.
В классе КС-языков ряд алгоритмических проблем допускает решение. Среди других разрешимы следующие проблемы: 0 содержит ли КС-язык данную цепочку; П содержит ли КС-язык хотя бы одну цепочку; П содержит ли данный КС-язык бесконечное число цепочек. Однако большинство интересных алгоритмических проблем в классе КС- языков неразрешимо — соответствующих алгоритмов не существует. Среди таких проблем можно назвать следующие: Г3 проблема эквивалентности — порождают ли две КС-грамматики один и тот же язык; 0 проблема пересечения — пересекаются ли множества цепочек, порождаемых двумя КС-грамматиками; Г3 проблема существенной неоднозначности: можно ли для языка, порождаемого двусмысленной грамматикой, найти порождающую тот же язык недвусмысленную грамматику; Ч проблема определения того, является ли данная КС-грамматика двусмысленной; О проблема определения того, порождает ли данная КС-грамматика язык, включающий все терминальные цепочки.
Даже такая простая проблема — являешься ли автоматным язык, порождаемый КС-грамматикой, — также неразрешима. Можно получить ответы на часть из Теория контекстно-свободных языков этих вопросов, если грамматика принадлежит некоторому подходящему подклассу класса КС-грамматик, для которого поставленная проблема алгоритмически разрешима. В частности, все перечисленные проблемы разрешимы для такого подкласса КС-грамматик, как автоматные грамматики.
4.5. Синтаксический анализ КС-языков Рассмотрим пример КС-грамматики. ~-т4.5 1. 5 — +ЙИС 2. Я вЂ” >ЬА 3. А-+аЬ 4. А — +СВА 5. В-+ЬВС 6. В-+с Имея грамматику, мы можем построить вывод какой-либо терминальной цепочки. Пусть, например, в этой грамматике построен вывод: Я ==: аИс ==> аЬЬАс ==> аЬЬсВАс ==> аЬЬссАс ==> аЬЬссаЬс. Задача блока синтаксического анализа обратна: по заданной терминальной цепочке нужно восстановить вывод ее из начального символа грамматики: Что должно стоять вместо вопросительного знака? Синтаксический анализ можно понимать и как восстановление синтаксического дерева заданной входной цепочки.
Для этого дерева известны листья (входная цепочка) и корень (начальный символ грамматики). Рассуждения о восстановлении синтаксического дерева эквивалентны рассуждениям о восстановлении вывода цепочки из начального символа: восстановление каждого шага вывода соответствует добавлению очередного узла в дерево, и обратно. В терминах восстановления дерева вывода задача синтаксического анализа представлена на рис. 4.3, а.
Эту задачу можно решать, используя две различные стратегии: восстанавливая дерево от корня к листьям (синтаксический анализ сверху вниз, или нисходящий) и восстанавливая дерево от листьев к корню (синтаксический анализ снизу вверх, или восходящий). Анализ сверху вниз работает следующим образом (рис. 4.3, о).
Начиная от корня дерева пытаемся найти те продукции грамматики, которые нужно использовать для подстановки вместо каждого нетерминала, стоящего в узлах 148 Глава 4 синтаксического дерева, правых частей этих продукций. Основным повторяющимся вопросом здесь является следующий: какую из возможных альтернатив для данного нетерминала выбрать, чтобы в результате получить заданную терминальную цепочку. Критерием правильности выбора альтернатив является, конечно, совпадение выведенной и заданной терминальных цепочек, что может стать ясным после выполнения всех подстановок. Однако даже на промежуточных шагах вывода можно проверять совпадение терминального префикса получающейся цепочки и префикса той же длины заданной терминальной цепочки.
Несовпадение таких префиксов говорит об ошибке выбора альтернатив ца одном из предыдущих шагов, и требует возврата в алгоритме. в) Рис. 4.3. Задача синтаксического анализа: а) общая; б) нисходящая стратегия; в) восходящая стратегия Рассмотрим наиболее простой — переоорный — алгоритм такого рода, который можно назвать алгоритмом "грубой силы". На рис.
43, 6) показаны два шага этого алгоритма. На первом шаге для единственного нетерминала Я— корня дерева из двух альтернатив 5'(продукций Я-+аИс и 5 — >БА грамматики 6,15 с символом Я в левой части) выбираем первую. Это дает в качестве промежуточной цепочки аббас, которая после дальнейших подстановок должна совпасть с заданной цепочкой аЬЬссаЬс.
Максимальный левый терминальный префикс аЬ этой промежуточной цепочки совпадает с соответствующим префиксом заданной цепочки. что говорит о том, что пока сделанный шаг алго- Теория контекстно-свободных языков ритма не противоречит требованиям правильности вывода. Следующий шаг состоит также в выборе одной из этих же альтернатив для 5 так, чтобы из цепочки Лс могла быть выведена цепочка ЬссаЬс — остаток исходной цепочки. Выбор снова первой альтернативы дает цепочку аИсс, но сравнение левых терминальных префиксов (аЬ ~ 6с) говорит о том, что либо это решение неверно, либо ошибка в выборе альтернативы была сделана на предыдущем шаге. Результатом является оэктрекинг — откат в алгоритме назад на один шаг для попытки подстановки новой альтернативы. Ьэктрекинг неудобен по многим причинам.
Во-первых, алгоритмы с бэктрекингом требуют большого времени выполнения. Кроме того, в алгоритмах с бэктрекингом невозможно выполнение семантических действий одновременно с выполнением шага синтаксического анализа — при откате назад нужно будет нейтрализовать результаты части уже выполненных семантических действий. Чтобы избежать бэктрекинга при построении детерминированного алгоритма нисходящего синтаксического анализа„для заданной грамматики необходимо сформулировать однозначный критерий выбора альтернативы для каждого нетерминала А в каждом случае, когда нетерминал этот стоит в начале некоторой цепочки Ау, из которой следует вывести некоторую терминальную цепочку Р— остаток исходной цепочки. В общем случае различных подцепочек у и Р, для которых необходимо сформулировать подобные правила, бесконе ~ное число, поэтому это можно сделать только для узких классов грамматик.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
