formal_languages_translation_theory (852748), страница 12

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

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

Пусть G — КС-грамматика.Метод рекурсивного спуска применим к G, если и только если для любой пары альтернативX →  |  выполняются следующие условия:(1) first()  first ()   ;(2) справедливо не более чем одно из двух соотношений:   ,    ;(3) если   , то first(X)  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 , где 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 }, follow(S) ;first (bB)  { b }, first (d )  { d };first ( aA )  { a }, first (E )  { e }, follow(A) ;first (e )  { e }.Как видно, множества first для любой пары альтернатив не пересекаются, а также справедливы first ( A)  follow ( A)   и first ( S)  follow ( S)  . Грамматика удовлетворяет критерию применимости метода рекурсивного спуска, и можно построить таблицу однозначныхпрогнозов: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 ();}elseA (); // возможно A  }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-грамматикой. Рассмотренные выше s-грамматики являются q-грамматиками, обратное неверно.Итерации в КС-грамматикахПри описании синтаксиса языков программирования часто встречаются правила, описывающие последовательность однотипных конструкций, отделенных друг от друга какимлибо знаком-разделителем (например, список идентификаторов при описании переменных,список параметров при вызове процедур и функций и т.

п.). Такие правила обычно имеютвид: L → a | a, LВместо обычных правил КС-грамматик для описания синтаксиса языков программирования нередко используют их модификации, например БНФ 22). В БНФ, в частности, допускаются конструкции вида {}, где фигурные скобки — это спецсимволы для выделенияфрагмента , который может отсутствовать или повторяться произвольное число раз. Называют такую конструкцию итерацией.С помощью итерации грамматику L → a | a, L можно переписать так: L → a {, a}.Наоборот, если в грамматике есть правило вида X → {}, содержащее итерацию{}, то его можно заменить серией эквивалентных правил без итерации {}:X → YY → Y | ,где Y — новый нетерминальный символ, добавляемый в алфавит нетерминалов грамматики.Чтобы применить метод рекурсивного спуска для грамматики L → a {, a}, преобразуем эту грамматику в эквивалентную без итерации:L →aMM → ,aM|22)Бэкуса-Наура формула.61Элементы теории трансляции / Синтаксический анализМетод применим к данной грамматике, так как first ( , a )  follow (M )  .Можно построить систему рекурсивных процедур по преобразованной грамматике, нолучше, убедившись, что для преобразованной грамматики метод применим, вернуться кначальному варианту с итерацией.Реализовать итерацию {} (где   b, b  T ) удобно с помощью цикла: «пока текущий символ равен b, считать со входа следующий символ и проанализировать цепочку ».Для правила с итерацией L → a {, a} процедура-анализатор реализуется так:void L (){if ( c != 'a' )throw c;gc ();while ( c == ',' ){gc ();if ( c != 'a' )throw c;elsegc ();}}Рассмотрим пример еще одной грамматики.Gsequence:S → LBL → a {, a}B →,bЕсли для этой грамматики сразу написать анализатор, не убедившись в применимостиметода к преобразованной (без итерации) грамматике, то цепочка а,а,а,b будет признанатаким анализатором ошибочной, хотя в действительности а,а,а,b принадлежит порождаемому Gsequence языку.

Это произойдет потому, что процедура L( ) захватит чужую запятую —ту, что выводится из B, и далее не обнаружив символ а, сообщит об ошибке.Следует сначала проверить применимость метода, исключив из грамматики итерациюрассмотренным выше способом:S → LBL → aMM → ,aM|B → ,bКак видим, first (, a)  follow (M )  { , }   и поэтому метод рекурсивного спуска неприменим 23).

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

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