И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 10
Текст из файла (страница 10)
Вместопечати применяемых правил можно вставить действия по формированию дерева в динамической памяти в виде узлов, связанных указателями. Такое дерево может использоваться на последующих этапах трансляции.Заметим, что даже если специально не фиксировать структуру анализируемой цепочки, система рекурсивных процедур все равно неявно обходит дерево вывода этой цепочки.Действительно, распознавание терминала b процедурой B( ) соответствует в дереве выводаветви B, а вызов процедуры A( ) из процедуры B( ) соответствует ветви B. Добавив в процеду¹ºbAры анализа дополнительные действия, можно наряду с проверкой синтаксиса определятьсмысл (семантику) входной цепочки. Например, смыслом арифметического выражения является его значение, и оно может быть вычислено в процессе неявного обхода дерева при разборе этого выражения системой рекурсивных процедур.Выбор нужной альтернативы при анализе методом рекурсивного спуска легко осуществим, если все альтернативы начинаются с попарно различных терминальных символов.Сформулируем достаточное условие применимости метода рекурсивного спуска.Достаточное условие применимости метода рекурсивного спускаДля применимости метода рекурсивного спуска достаточно, чтобы каждое правило вграмматике удовлетворяло одному из двух видов:(а) X → α,*где α ∈ (T ∪ N ) и это единственное правило вывода для этого нетерминала;(б) X → a1α1 | a2α2 | ...
| anαn,51Элементы теории трансляции / Синтаксический анализ*где ai ∈ T для всех i = 1, 2,..., n ; ai ≠ aj для i ≠ j; αi ∈ (T ∪ N ) , т. е. если для нетерминала X правил вывода несколько, то они должны начинаться с терминалов, причем все эти терминалы должны быть попарно различными;Это условие не является необходимым. Грамматику, удовлетворяющую данному условию,называют s-грамматикой.Метод рекурсивного спуска является одной из возможных реализаций нисходящегоанализа с прогнозируемым выбором альтернатив. Прогнозируемый выбор означает, что пограмматике можно заранее предсказать, какую альтернативу нужно будет выбрать на очередном шаге вывода в соответствии с текущим символом (т.е.
первым символом из еще непрочитанной части входной цепочки). Далее мы подробно рассмотрим этот подход и сформулируем критерий его применимости.Нисходящий анализ с прогнозируемым выбором альтернативВ процессе построения левого вывода для произвольной цепочки в грамматикеG1:S → ABdA → a | cAB → bAможно отметить следующее:(1) любой вывод начинается с применения правила S → ABd ;∗(2) если на очередном шаге сентенциальная форма имеет вид wBα, где w ∈ T — начало анализируемой цепочки, нетерминал B — самый левый в сентенциальнойформе, то для продолжения вывода его нужно заменить на bA (других альтернатив нет);∗(3) если на очередном шаге сентенциальная форма имеет вид wAα, где w ∈ T — начало анализируемой цепочки, то выбор нужной альтернативы для замены A можно однозначно предсказать по тому, какой символ в анализируемой цепочке следует за начальной подцепочкой w: если символ a, то применяется альтернативаA → a, если символ c, то альтернатива A → cA; если какой-то иной символ —фиксируется ошибка: анализируемая цепочка не принадлежит языку L(G1);(4) если на каком-то шаге получилась сентенциальная форма вида wα, отличная от(2) и (3), где w — максимально длинное начало, состоящее только из терминалов,то если α пуста и w совпадает с анализируемой цепочкой, процесс вывода успешно завершается, иначе фиксируется ошибка: анализируемая цепочка не принадлежит языку L(G1).Отмеченные факты по поводу выбора нужной альтернативы на очередном шаге вывода в грамматике G1 представим в виде так называемой таблицы прогнозов (или таблицыпредсказаний):abcdSS → ABdS → ABdS → ABdS → ABdAA→aBA → cAB → bAИмея такую таблицу прогнозов (предсказаний) для КС-грамматики G, можно предложить следующий алгоритм нисходящего анализа (построение левого вывода):52Элементы теории трансляции / Синтаксический анализ1.
Начать построение вывода с сентенциальной формы, состоящей из одного начального символа S.2. Пока не будет получена цепочка, совпадающая с анализируемой, повторять следующие действия:∗Пусть wYα — очередная сентенциальная форма, где w ∈ T . Если w несовпадает с началом анализируемой цепочки, то прекратить построение выводаи сообщить об ошибке: цепочка не принадлежит L(G). В случае, когда w совпадает с началом, и следующим после w символом в анализируемой цепочке является символ z, заменить нетерминал Y на правую часть правила, которое находится в ячейке таблицы прогнозов на пересечении строки Y и столбца z.
Еслиуказанная ячейка пуста, прекратить построение вывода и сообщить об ошибке:цепочка не принадлежит L(G).Как мы видели выше, один из способов реализовать программу-анализатор для нисходящего анализа с прогнозируемым выбором альтернатив заключается в построении системы рекурсивных процедур17). Это метод рекурсивного спуска.Техника построения рекурсивных процедур уже была рассмотрена и продемонстрирована на примере, но остался открытым вопрос: как в общем случае «запрограммировать»процедуру на выбор нужной альтернативы по текущему символу.
Ответ теперь известен —использовать таблицу прогнозов.К сожалению, не для каждой КС-грамматики существует таблица с однозначнымипрогнозами, позволяющая безошибочно осуществить выбор альтернативы на каждом шагевывода. В некоторых случаях заранее спрогнозировать выбор альтернативы невозможно:может оказаться, что подходящими в данной ситуации являются сразу несколько альтернатив (неоднозначный прогноз)18).Таким образом, нисходящий анализ с прогнозируемым выбором альтернатив пригоден лишь для некоторого подкласса КС-грамматик.Метод рекурсивного спуска применим к грамматике, если для нее существует таблицаоднозначных прогнозов.О применимости метода рекурсивного спускаОчевидно, что метод рекурсивного спуска (без возвратов) неприменим к неоднозначным грамматикам.
Например, по грамматикеG2:S → aA |B | dA → d | aAB → aA | a17)18)Другой способ, с явным использованием стека для хранения нетерминальной части сентенциальной формы,известен как LL(1)-анализатор.Обобщение рассматриваемого метода — рекурсивный спуск с возвратами — «пробует» по очереди все возможные альтернативы в случае неоднозначного прогноза; о неудаче сообщается только в том случае, еслини одна из альтернатив не привела к успеху. Если грамматика неоднозначна, обобщенный метод построитвсе возможные деревья выводов.
Мы не рассматриваем подробно рекурсивный спуск с возвратами, поскольку время, затрачиваемое на анализ при таком подходе, может экспоненциально зависеть от длинывходной цепочки.53Элементы теории трансляции / Синтаксический анализнельзя дать однозначный прогноз, что делать на первом шаге при анализе цепочки, начинающейся с символа a, т.е. по текущему символу a невозможно сделать однозначный выбор: S → aA или S → B .Как показывает следующий пример, грамматика может быть однозначной, однако однозначных прогнозов для нее также не существует:G3:S → A|BA → aA | dB → aB | bДействительно, каждая цепочка, выводимая в G3 из S, оканчивается либо символом b,либо символом d, и имеет единственное дерево вывода.
Но невозможно предсказать, с какойальтернативы ( S → A или S → B ) начинать вывод, не просмотрев всю цепочку до конца ине увидев последний символ.Наличие в грамматике нетерминала X с правилами вида X → α и X → β, из правыхчастей которых выводятся цепочки, начинающиеся одним и тем же терминалом a, т.
е.α ⇒ aα′ и β ⇒ aβ′, делает неоднозначным прогноз по символу a. Так что нисходящий анализ с прогнозируемым выбором альтернатив невозможен по такой грамматике, и метод рекурсивного спуска неприменим. Сформулируем это условие более формально.Определение: множество first (α) — это множество терминальных символов, которыминачинаютсяцепочки,выводимыеизцепочкиαвграмматике*∗G = 〈 T, N, P, S 〉, т. е.
first (α) = { a ∈ T | α ⇒ aα′, где α ∈ ( T ∪ N ) , α′ ∈ ( T ∪ N ) }.Например, для альтернатив правила S → A | B в грамматике G3 имеем:first (A) = { a, d },first (B) = { a, b }.Пересечениеэтихмножествнепусто:first (A) ∩ first (B) = { a } ≠ ∅, и поэтому метод рекурсивного спуска к G3 неприменим.Итак, наличие в грамматике правила с альтернативами X → α | β, такими чтоfirst ( α ) ∩ first ( β ) ≠ ∅, делает метод рекурсивного спуска неприменимым.Рассмотрим примеры грамматик с ε-правилами.G4:SABD→→→→aA |BDcBAa | aB | bεB|bfirst(aA) = { a }, first(BDc) = { b, c };first(BAa) = { a, b }, first(aB) = { a }, first(b) = { b };first(ε) = ∅;first(B) = ∅, first(b) = { b }.Метод рекурсивного спускаfirst (BAa) ∩ first (aB) = { a } ≠ ∅.неприменимкграмматикеG4,таккакСледующий пример показывает еще одно свойство грамматик, наличие которого делает РС-метод неприменимым.G5:S → aAA → BC | BC → b|εB →ε54Элементы теории трансляции / Синтаксический анализПересечение множеств first пусто для любой пары альтернатив грамматики G5, однако наличие двух различных альтернатив, из которых выводится пустая цепочка, делает данную грамматику неоднозначной и, следовательно, метод рекурсивного спуска к ней неприменим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
