И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1119400), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Начать построение вывода с сентенциальной формы, состоящей из одного начального символа 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  — это множествотерминальных символов, которыми начинаются цепочки, выводимые в G из цепочки   ( T* N ), т. е. first ()  { a  T |   a,   ( 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, однако наличие двух различных альтернатив, из которых выводится пустая цепочка, делает данную грамматику неоднозначной и, следовательно, метод рекурсивного спуска к ней неприменим.

Действительно, BC   и B  . Цепочка a имеет два различных дерева вывода :SSAABaaBCТаким образом, если в грамматике для правила X →  |  выполняются соотношения    и   , то метод рекурсивного спуска неприменим.Осталось выяснить, как обстоят дела с применимостью метода, если для каждого нетерминала грамматики существует не более одной альтернативы, из которой выводится .G6:S → cAd | dA → aA | first ( cAd )  { c }, first (d )  { d };Однозначные прогнозы для выбора альтернативы нетерминала S существуют, так какfirst (cAd)  first (d )  .Выбор альтернативы для A в данной грамматике также можно однозначно спрогнозировать: если текущим символом является a, применяется правило A → aA, иначе правилоA → . Это возможно благодаря тому, что за любой подцепочкой, выводимой из A, следуетсимвол d, который сам в эту подцепочку не входит.

Процедура A( ) при выборе альтернативыA →  просто возвращает управление в точку вызова, не считывая следующий символ входной цепочки. Процедура S( ), получив управление после вызова A( ), проверяет, что текущимсимволом является d. Если это не так, фиксируется ошибка. Конечно, проверку символа d(без считывания следующего символа из входной цепочки) могла бы сделать и сама A( ), ноэто излишне, так как S( ) все равно будет проверять d, и если вместо d обнаружит другойсимвол, ошибка будет зафиксирована. Таблица прогнозов для G6:aSAA→aAcdS → cAdS→dA→A→Итак, для грамматики G6, имеющей для каждого нетерминала не более одной альтернативы, из которой выводится пустая цепочка, метод рекурсивного спуска применим.

Процедура A( ) для нетерминала A, имеющего пустую альтернативу в грамматике G6, реализуется так:void A (){if ( c =='a' )55Элементы теории трансляции / Синтаксический анализ{cout << "A->aA, ";gc ();A ();}else{cout << "A->epsilon, "; // след. символ не считывается}}Следующий пример показывает, что наличие альтернативы , такой что   , всеже может сделать метод рекурсивного спуска неприменимым.G 7:S → BdB → cAa | aA → aA | first ( cAa )  { c }, first (a )  { a };У нетерминала S правая часть единственна и проблема выбора альтернативы для S нестоит.

Для выбора альтернативы нетерминала B существуют однозначные прогнозы, поскольку first (cAa)  first (a)   .Однако для нетерминала A прогноз по символу a неоднозначен. Дело в том, что любой вывод, содержащий A, имеет вид: S → Bd → cAad → … → ca…aAad. Поэтому альтернативу A →  следует применять только тогда, когда текущим символом является a,а следующий за ним символ отличен от a (например, d ). Если текущий — a и следующий заним символ — тоже a, то выбирается альтернатива A → aA.

Но сделать однозначный выбортолько по текущему символу в пользу какой-то одной из этих альтернатив невозможно,так как анализатор не умеет заглядывать вперед (в непрочитанную часть анализируемой цепочки).Как видим, в G 7 существует сентенциальная форма, например cAad, в которой посленетерминала A, имеющего в грамматике пустую альтернативу, стоит символ a, c котороготакже начинается и непустая альтернатива для A.

В таком случае процедура A( ) не сможетправильно определить по текущему символу a, считывать ли следующий символ и вызыватьA( ) (т. е. применять правило A → aA) или возвращать управление без считывания символа(правило A → ). Опишем эту ситуацию более формально.Определение: множество follow(A) — это множество терминальных символов, которые могут появляться в сентенциальных формах грамматики G  T, N, P, S  непосредственно справа от A (или от цепочек, выводимых из A), т.е.*follow(A) { a  T | S  A,   a , A  N, , ,   (T  N) }.Тогда, если в грамматике есть правило X →  | , такое что   ,first()  follow(X)  , то метод рекурсивного спуска неприменим к данной грамматике.Итак, на примерах мы рассмотрели все случаи, когда можно построить однозначныепрогнозы по грамматике.

Характеристики

Список файлов книги