Материалы (6) (Материалы к лекциям)

102Задача разбора (синтаксический анализ)Даны КС-грамматика G и цепочка x.x∈L(G) ?Если да, то построить дерево вывода для x(или левый вывод для x, или правый вывод для x ).Существуют различные методы синтаксического анализадля КС-грамматик;для некоторых подклассов есть эффективные методы,затрачивающие линейное время на Cn на анализ цепочкидлины n.Каждый метод синтаксического анализа предполагает свойспособ построения по грамматике программы-анализатора,которая будет осуществлять разбор цепочек.В основе анализатора может быть автомат с магазиннойпамятью. Мы рассмотрим другой способ – методрекурсивного спуска ( система рекурсивных процедур ).103104Анализатор некорректен, если:-- не распознает хотя бы одну цепочку, принадлежащую языку;-- распознает хотя бы одну цепочку, языку не принадлежащую;-- зацикливается на какой-либо цепочке.Метод анализа применим к данной грамматике, еслианализатор, построенный в соответствии с этим методом,корректен.Метод рекурсивного спуска (РС-метод)Пример: пусть дана грамматика G =({a,b,c, d}, {S,A,B}, P, S),гдеP: S → ABdA → a | cAB → bAи надо определить, принадлежит ли цепочка cabad языкуL(G).Построим левый вывод этой цепочки:S → ABd → cABd → caBd → cabAd → cabadСледовательно, цепочка принадлежит языку L(G).105106S → ABd → cABd → caBd → cabAd → cabadПостроение левого вывода эквивалентно построению деревавывода методом «сверху вниз» (нисходящим методом) :SS⇒S⇒A B⇒A BAcabacdaS⇒⇒A Bacaadca⇒adadA BAbbSA BAbdSAcabAAadcabМетод рекурсивного спуска (РС-метод):Для каждого нетерминала грамматики создается свояпроцедура с именем этого нетерминала; ее задача — начинаяс указанного места исходной цепочки найти подцепочку,которая выводится из этого нетерминала.Если подцепочку удалось найти, то работа процедурысчитается нормально завершенной и осуществляется возврат вточку вызова, иначе — разбор прекращается и сообщается обошибке, цепочка не принадлежит языку.Тело каждой такой процедуры пишется непосредственно поправилам вывода соответствующего нетерминала: терминалыиз правой части распознаются самой процедурой, анетерминалы соответствуют вызовам процедур, носящих ихимена.107Программа – анализатор для G1108#include <iostream.h>int c;void A ();void B ();void gc (){cin >> c;}G1 :S → ABdA → a | cAB → bA// считать символ из входного потокаvoid S (){cout << "S-->ABd, ";A();B();if ( c != 'd' )throw c;}// применяемое правило вывода109void A (){if ( c =='a' ){cout << "A-->a, ";gc ();}else if ( c =='c' ){cout << "A-->cA, ";gc ();A ();}elsethrow c;}G1 :S → ABdA → a | cAB → bA110void B (){if ( c =='b' ){cout << "B-->bA, ";gc ();A ();}elsethrow c;}G1 :S → ABdA → a | cAB → bA111int main (){G1 :tryS → ABd{A → a | cAgc ();B → bAS ();if ( c != '⊥' ) // проверяем, что достигнут конец// цепочкиthrow c;cout << "SUCCESS !!!" << endl;return 0;}catch ( int c ){cout << "ERROR on lexeme" << c << endl;return 1;}}112Достаточное условие применимости метода рекурсивногоспускаДля применимости метода рекурсивного спуска достаточно,чтобы каждое правило в грамматике имело вид:(а) либо X → α ,где α ∈ (T ∪ N )* и это единственное правило вывода дляэтого нетерминала;(б) либо X → a1α1 | a2α2 | ...

| anαn ,где ai ∈ T для всех i = 1, 2,..., n ; ai ≠ aj для i ≠ j; αi ∈ (T ∪ N )*,т. е. если для нетерминала X правил вывода несколько, то онидолжны начинаться с терминалов, причем все эти терминалыдолжны быть различными;Это условие не является необходимым.Найдем критерий применимости113РС-метод применим, если и только если левый вывод (илидерево нисходящим способом) можно построить, начиная сначального символа S, так, что на каждом шаге выводарешение о том, какое правило (альтернативу) применять длязамены левого нетерминала, безошибочно принимается попервому символу из непрочитанной части входной цепочки(т.

е. по «текущему» символу).Рассмотрим примерыG2:S →aA |B | dA →d | aAB →aA | aG2 неоднозначна, РС-метод неприменим.нельзя дать однозначный прогноз, что делать на первом шаге при анализецепочки, начинающейся с символа a (т. е. по текущему символу a невозможносделать однозначный выбор: S → aA или S → B )114G3 однозначна, но РС-метод неприменимG3:S →A | BA →aA | dB →aB | bОпределение: множество first (α) — это множествотерминальных символов, которыми начинаются цепочки, выводимыеиз цепочки α в грамматике G = 〈 T, N, P, S 〉, т. е.first (α) = { a ∈ T | α ⇒ aα′, где α ∈ ( T ∪ N )+, α′ ∈ ( T ∪ N )* }.Например: first (A) = { a, d }, first (B) = { a, b }.

Пересечениеэтих множеств непусто: first (A) ∩ first (B) = { a } ≠ ∅, и поэтомуметод рекурсивного спуска к G3 неприменим.115Итак, наличие в грамматике правил вида X → α | β, таких чтоfirst ( α ) ∩ first ( β ) ≠ ∅,делает метод рекурсивного спусканеприменимым.Рассмотрим еще несколько примеров.G4:first(aA) = { a }, first(BDc) = { b, c };S → aA |BDcfirst(BAa) = { a, b }, first(aB) = { a },A → BAa | aB | bfirst(b) = { b };B →εfirst(ε) = ∅;D →B | bfirst(B) = ∅, first(b) = { b }.Метод рекурсивного спуска неприменим к грамматике G4, так какfirst (BAa) ∩ first (aB) = { a } ≠ ∅.116G5:SACB→aA→BC | B→b | ε→εПересечение множеств first пусто, но РС-метод неприменим.Действительно, BC ⇒ ε и B ⇒ ε. Цепочка a имеет два различных деревавыводаSSAABaεBaεCε117Таким образом, если в грамматике для двух различныхправил X → α | β выполняются соотношения α ⇒ ε и β ⇒ ε, тометод рекурсивного спуска неприменим.Рассмотрим примеры с единственной альтернативой, из которойвыводится ε.G6:S →cAd | dA → aA | εМетод применим: если текущий символ a , то выбираемальтернативу A→aA иначе — A → εG7:S →BdB →cAa | aA →aA | εНеприменим, т.к.

для A невозможно правильно выбратьальтернативу без «заглядывания» на символ вперед.Определение: множество follow(A) — это множествотерминальных символов, которые следуют за цепочками,выводимыми из А в грамматике G = 〈T, N, P, S 〉, т. е.118follow(A) ={ a ∈ T | S ⇒ αAβ, β ⇒ a γ, A ∈ N, α, β, γ ∈ (T ∪ N)*}Тогда, если в грамматике есть пара правил X → α | β, такихчто β ⇒ ε, first(α) ∩ follow(X) ≠ ∅, то метод рекурсивного спусканеприменим к данной грамматике.Утверждение.

Пусть G — КС-грамматика. Метод рекурсивногоспуска применим к G, если и только если для любой пары альтернативвида X → α | β выполняются следующие условия:(1) first(α) ∩ first (β) = ∅ ;(2) справедливо не более чем одно из двух соотношений:α ⇒ ε, β ⇒ ε ;(3) если β ⇒ ε , то first(α) ∩ follow( X ) = ∅ .119Канонический вид для РС-метода(1) либо X → α,где α ∈ (T ∪ N)* и это единственное правило вывода дляэтого нетерминала;(2) либо X → a1α1 | a2α2 | ...

| anαn,где ai ∈ T для всех i = 1, 2,..., n ; ai ≠ aj для i ≠ j;αi ∈ (T ∪ N )*, т. е. если для нетерминала X правил выводанесколько, то они должны начинаться с терминалов, причемвсе эти терминалы должны быть попарно различными;(3) либо X → a1α1 | a2α2 | ... | anαn | ε ,где ai ∈ T для всех i = 1, 2,..., n; ai ≠ aj для i ≠ j;αi ∈ (T ∪ N )*, и first (X ) ∩ follow (X ) = ∅.Этот вид удобен для построения рекурсивных процедур, ноон дает только достаточное условие применимости.120Вопрос: если грамматика не удовлетворяеткритерию применимости РС-метода, то существуетли эквивалентная КС-грамматика, для которой методрекурсивного спуска применим?К сожалению, нет алгоритма, отвечающего на этотвопрос для произвольной КС-грамматики, т.е.

этоалгоритмически неразрешимая проблема.121Модификация метода для грамматик с итераторами:Для правил вида L → a {,a}( эквивалент L → a | a, L )рекурсию заменяем итерацией:void L(){ if (c != 'a') throw c;gc();while (c == ','){gc(); if (c != 'a') throw c; elsegc();}}Важно, чтобы в любой сентенциальной форме после L небыло запятой, иначе L прочитает «не свою» запятую. (Вместозапятой в данном примере может быть любой другой символ.)122Пример, когда анализатор по вышеприведенной схемене дает корректный ответ:G:S → LB⊥L → a {, a}B → ,bЕсли для этой грамматики написать анализатор,действующий РС-методом, то цепочка а,а,а,b будет признанаим ошибочной, хотя а,а,а,b∈L(G).В языках программирования после повторяющихсяконструкций обычно идет какой-нибудь новый символ,так что подобных проблем не возникает:var a,b,c,d : integer;илиint a,b,c,d;Если грамматику переписать без итератора { }S → LB⊥L →a MM →, a M | εB →, bто нетрудно видеть, что first (, a) ∩ follow (M ) = { , } ≠ ∅ ипоэтомуметодрекурсивногоспусканеприменим.123Эквивалентные преобразования для КС-грамматик, 124которые могут помочь перестроить исходнуюграмматику так, чтобы РС-метод был применим.1) Если в грамматике есть нетерминалы, правила выводакоторых леворекурсивны, т.е.

имеют видA → Aα1 | ... | Aαn | β1 | ... | βm,где αi ∈ (VT ∪ VN)+, βj ∈ (VT ∪ VN)*, i = 1, 2, ..., n; j =1, 2 ,..., m,то левую рекурсию всегда можно заменить правой:A → β1A’ | ... | βmA’A’ → α1A’ | ... | αnA’ | εБудет получена грамматика, эквивалентная исходной.1252) Если в грамматике есть нетерминал, у которогонесколько правил вывода начинаются одинаковымитерминальными символами, т.е. имеют видA → aα1 | aα2 | ... | aαn | β1 | ... |βm ,где a ∈ VT; αi, βj ∈ (VT ∪ VN )*,то можно преобразовать правила вывода данногонетерминала, объединив правила с общими началами в одноправило:A → aA’ | β1 | ... | βmA’ → α1 | α2 | ...