Материалы (6) (1115033)

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

Текст из файла

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 | ...

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы