И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 11
Текст из файла (страница 11)
Действительно, BC ⇒ ε и B ⇒ ε. Цепочка a имеет два различных дерева вывода :SSAABBaCaТаким образом, если в грамматике для правила 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) ≠ ∅, то метод рекурсивного спуска неприменим к данной грамматике.Итак, на примерах мы рассмотрели все случаи, когда можно построить однозначныепрогнозы по грамматике. Подытожив их, сформулируем критерий применимости методарекурсивного спуска.56Элементы теории трансляции / Синтаксический анализУтверждение 11.
Пусть G — КС-грамматика. Метод рекурсивного спуска применимк G, если и только если для любой пары альтернатив X → α | β выполняются следующие условия:(1) first(α) ∩ first (β) = ∅ ;(2) справедливо не более чем одно из двух соотношений: α ⇒ ε, β ⇒ ε ;(3) если β ⇒ ε, то first(α) ∩ follow( X ) = ∅.Рассмотрим грамматикуG8:S → BDCC → BdD → aB | dB → bB | εfirst (aB ) = { a }, first ( d ) = { d };first (bB ) = { b },follow (B ) = {a, b, d}, так как возможны следующие сентенциальные формы: BdC,BaBbd 19).
Поскольку first (bB) ∩ follow (B) = { b } ≠ ∅, метод рекурсивного спуска неприменим к данной грамматике.Естественно задаться вопросом: если грамматика не удовлетворяет критерию применимости метода рекурсивного спуска, то есть ли возможность построить эквивалентнуюграмматику, к которой данный метод применим.Утверждение 12. Не существует алгоритма, определяющего для произвольной КСграмматики, существует ли для нее эквивалентная грамматика, к которой метод рекурсивного спуска применим (т. е. это алгоритмически неразрешимая проблема20)).Построение таблицы прогнозовЕсли критерий применимости метода рекурсивного спуска выполняется для грамматики G, то таблицу M однозначных прогнозов можно построить следующим образом:1.
Для каждого правила X → α и для каждого терминала a ∈ first(α) помещаем X → αв ячейку M [X, a];2. Для каждого правила X → α, такого что α ⇒ ε, помещаем X → α во все незаполненные на 1-м шаге ячейки строки X.3. Для каждого правила X → Y β, где ∈ N, Y β — единственная альтернатива для X,помещаем X → Y β во все незаполненные на 1-м и 2-м шагах ячейки строки X.На 2-м шаге могут быть заполнены ячейки для терминалов, не входящих в множество follow(X), то есть соответствующих ошибочным ситуациям. Так как при анализе РС19)20)В наших примерах мы вычисляем first и follow «интуитивно», опираясь на определения.
Алгоритмы вычисления множеств first и follow можно найти в литературе (например, в [3]) или построить их самостоятельно.Напомним, что алгоритмическая неразрешимость означает не то, что данную задачу нельзя решить для каждой конкретной грамматики, а то, что нет универсального способа решения, пригодного для всех грамматик.57Элементы теории трансляции / Синтаксический анализметодом считывания следующего символа в случае X ⇒ ε не происходит, ошибка в текущей позиции обнаружится чуть позже, — той процедурой, которая анализирует текущийсимвол.На 3-м шаге заполняются ячейки для терминалов, не входящих в first(X), что такжесоответствует ошибочным ситуациям. Поскольку считывания следующего символа в случаеединственной альтернативы X → Yα в процедуре X не происходит, обнаружение ошибкипроизойдет позже, — в процедуре, анализирующей текущий символ.Можно модифицировать построение таблицы прогнозов: третий шаг не выполнятьвовсе (т.к. выбор единственной альтернативы уже осуществлен на шаге 1), на втором шагекаждое правило X → α, такое что α ⇒ ε, помещать в ячейку M [X, a] для каждого терминала a ∈ follow(X) 21) ; незаполненные на 1-м и 2-м шагах ячейки строки X оставить пустыми.Это позволит раньше обнаруживать ошибки в исходной цепочке, однако усложнит поведение самих процедур, так как им придется делать дополнительные проверки.Пример.
Построим таблицу прогнозов для грамматикиG9:S → A |BS |cSB → bB | dA → aA | E | εE →eВычислим необходимые для этого множества:first ( A) = { a, e }, first ( BS ) = { b, d }, first ( cS ) = { c };first (bB) = { b }, first (d ) = { d };first ( aA ) = { a }, first (E ) = { e }, follow(A) = ∅;first (e ) = { e }.Как видно, множества first для любой пары альтернатив не пересекаются, а для нетерминала с пустой альтернативой справедливо first ( A) ∩ follow ( A) = ∅.
Грамматика удовлетворяет критерию применимости метода рекурсивного спуска, и можно построить таблицу однозначных прогнозов:abcdeSS→AS → BSS → cSS → BSS→AAA → aAA→εA→εA→εA→EBEB → bBB→dE→eПостроим для G9 анализатор в виде системы рекурсивных процедур. Поведение процедур определяется полученной таблицей прогнозов. Заметим, что при выборе альтернативы,начинающейся с нетерминала, новый символ со входа не считывается, а сразу вызываетсяпроцедура, соответствующая этому нетерминалу.#include <iostream>using namespace std;21)Множество follow(X) должно в этом случае содержать хотя бы один символ, — для этого предполагается,что в конце каждой входной цепочки языка есть маркер ⊥.58Элементы теории трансляции / Синтаксический анализint c;voidvoidvoidvoidSABE();();();();void gc (){cin >> c;}// считать очередной символvoid S (){if ( c =='a' || c =='e'){cout << "S-->A, "; // применяемое правило вывода// gc () не вызывается,текущий символ будет распознан процедурой A()A ();}else if ( c =='b' || c =='d'){cout << "S-->BS, ";// gc () не вызывается;B ();S ();}else if ( c =='c'){cout << "S-->cS, ";gc (); // символ 'c' распознан процедурой S(), считываем следующийS ();}elsethrow c; // недопустимый символ}void A (){if ( c =='a' ){cout << "A-->aA, ";gc ();A ();}else if ( c =='e' ){cout << "A-->E, ";// gc () не вызывается;E ();}else{// gc () не вызывается;cout << "A->epsilon, ";}}void B (){if ( c =='b' )59Элементы теории трансляции / Синтаксический анализ{cout << "B-->bB, ";gc ();B ();}else if ( c =='d' ){cout << "B-->d, ";gc ();}elsethrow c;}void E (){if ( c =='e' ){cout << "E-->e, ";gc ();}elsethrow c;}int main (){try{gc ();S ();if ( c != '⊥' )throw c;cout << "SUCCESS !!!" << endl;return 0;}catch ( int c ){cout << "ERROR on lexeme" << c << endl;return 1;}}Рекурсивный спуск без построения прогнозовВыделим подкласс грамматик, по которым можно строить систему рекурсивных процедур, минуя построение таблицы прогнозов.Будем говорить, что правила КС-грамматики имеют канонический (для РС-метода)вид, если каждая группа правил с одинаковым нетерминалом в левой части относится к одному из перечисленных ниже видов и выполняются дополнительные условия:60Элементы теории трансляции / Синтаксический анализа)X→α,*где α ∈ (T ∪ N) и это единственное правило вывода для этого нетерминала;б)X → a1α1 | a2α2 | ...
| anαn ,*где ai ∈ T для всех i = 1, 2,..., n ; ai ≠ aj для i ≠ j; αi ∈ (T ∪ N ) , т. е. если для нетерминала X правил вывода несколько, то они должны начинаться с терминалов,причем все эти терминалы попарно различны;в)X → a1α1 | a2α2 | ... | anαn | ε ,*где ai ∈ T для всех i = 1, 2,..., n; ai ≠ aj для i ≠ j; αi ∈ (T ∪ N ) , иfirst (X ) ∩ follow (X ) = ∅.Если правила вывода имеют такой вид, то рекурсивный спуск может быть реализованбез промежуточного построения прогнозов: для правил с несколькими альтернативами выбирается альтернатива ai αi, если текущий символ совпадает с ai, иначе выбирается εальтернатива, если она присутствует; если нет совпадения текущего символа ни с одним из aiи нет ε-альтернативы — фиксируется ошибка.Канонический вид правил грамматики дает достаточное, но не необходимое условиеприменимости РС-метода.Грамматику с правилами канонического вида называют q-грамматикой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
