Учебное пособие для студентов II курса (издание третье, переработанное и дополненное) Москва 2009 удк 519. 682. 1
 Скачать 2.2 Mb.
|
|
Определение: множество first ( ) в грамматике G T, N, P, S — это множество терминальных символов, которыми начинаются цепочки, выводимые в G из цепочки ( T N ) , т. е. first ( ) { a T | a , ( T N ) * }. Например, для альтернатив правила S → A | B в грамматике G 3 имеем: first (A) { a, d }, first (B) { a, b }. Пересечение этих множеств непусто: first (A) first (B) { a } , и поэтому метод рекурсивного спуска к G 3 непримени м. Итак, наличие в грамматике правила с альтернативами X → | , такими что first ( ) first ( ) , делает метод рекурсивного спуска неприменимым. Рассмотрим примеры грамматик с -правилами. G 4 : S → aA |BDc A → BAa | aB | b B → D → B | b first(aA) { a }, first(BDc) { b, c }; first(BAa) { a, b }, first(aB) { a }, first(b) { b }; first( ) ; first(B) , first(b) { b }. Метод рекурсивного спуска непримени м к грамматике G 4 , так как first (BAa) first (aB) { a } Следующий пример показывает еще одно свойство грамматик, наличие которого де- лает РС-метод неприменимым. G 5 : S → aA A → BC | B C → b | B → Элементы теории трансляции / Синтаксический анализ 55 Пересечение множеств first пусто для любой пары альтернатив грамматики G 5 , одна- ко наличие двух различных альтернатив, из которых выводится пустая цепочка, делает дан- ную грамматику неоднозначной и, следовательно, метод рекурсивного спуска к ней непри- мени м. Действительно, BC и B .Цепочка a имеет два различных дерева вывода : S a B A S a B A C Таким образом, если в грамматике для правила X → | выполняются соотно- шения и , то метод рекурсивного спуска неприменим. Осталось выяснить, как обстоят дела с применимостью метода, если для каждого не- терминала грамматики существует не более одной альтернативы, из которой выводится G 6 : S → cAd | d A → 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 обнаружит другой символ, ошибка будет зафиксирована. Таблица прогнозов для G 6 : a c d S S → cAd S → d A A → a A A → A → Итак, для грамматики G 6 , имеющей для каждого нетерминала не более одной альтер- нативы, из которой выводится пустая цепочка, метод рекурсивного спуска применим. Про- цедура A( )для нетерминала A, имеющего пустую альтернативу в грамматике G 6 , реализу- ется так: void A () { if ( c =='a' ) Элементы теории трансляции / Синтаксический анализ 56 { cout << "A->aA, "; gc (); A (); } else { cout << "A->epsilon, "; // след. символ не считывается } } Следующий пример показывает, что наличие альтернативы ,такой что , все же может сделать метод рекурсивного спуска неприменимым. G 7 : S → Bd B → cAa | a A → 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) , то метод рекурсивного спуска неприменим к данной граммати- ке. Итак, на примерах мы рассмотрели все случаи, когда можно построить однозначные прогнозы по грамматике. Подытожив их, сформулируем критерий применимости метода рекурсивного спуска. Элементы теории трансляции / Синтаксический анализ 57 Утверждение 11 (критерий применимости РС-метода). Пусть G — КС-грамматика. Метод рекурсивного спуска примени м к G, если и только если для любой пары альтернатив X → | выполняются следующие условия: (1) first( ) first ( ) ; (2) справедливо не более чем одно из двух соотношений: , ; (3) если , то first(X) follow( X ) Рассмотрим грамматику G 8 : S → BDC C → Bd D → aB | d B → 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) В наших примерах мы вычисляем first и follow «интуитивно», опираясь на определения. Алгоритмы вы- числения множеств first и follow можно найти в литературе (например, в [3]) или построить их самостоя- тельно. 20) Напомним, что алгоритмическая неразрешимость означает не то, что данную задачу нельзя решить для каждой конкретной грамматики, а то, что нет универсального способа решения, пригодного для всех грам- матик. Элементы теории трансляции / Синтаксический анализ 58 методом считывания следующего символа в случае X не происходит, ошибка в теку- щей позиции обнаружится чуть позже, — той процедурой, которая анализирует текущий символ. На 3-м шаге заполняются ячейки для терминалов, не входящих в first(X), что также соответствует ошибочным ситуациям. Поскольку считывания следующего символа в случае единственной альтернативы X → Y в процедуре X не происходит, обнаружение ошибки произойдет позже, — в процедуре, анализирующей текущий символ. Можно модифицировать построение таблицы прогнозов: третий шаг не выполнять вовсе (т.к. выбор единственной альтернативы уже осуществлен на шаге 1), на втором шаге каждое правило X → , такое что , помещать в ячейку M [X, a] для каждого термина- ла a follow(X) 21) ; незаполненные на 1-м и 2-м шагах ячейки строки X оставить пустыми. Это позволит раньше обнаруживать ошибки в исходной цепочке, однако усложнит поведе- ние самих процедур, так как им придется делать дополнительные проверки. Пример. Построим таблицу прогнозов для грамматики G 9 : S → A |BS |cS B → bB | d A → 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) . Грамматика удовлетворяет крите- рию применимости метода рекурсивного спуска, и можно построить таблицу однозначных прогнозов: a b c d e S S → A S → BS S → cS S → BS S → A A A → aA A → A → A → A → E B B → bB B → d E E → e Построим для G 9 анализатор в виде системы рекурсивных процедур. Поведение про- цедур определяется полученной таблицей прогнозов. Заметим, что при выборе альтернативы, начинающейся с нетерминала, новый символ со входа не считывается, а сразу вызывается процедура, соответствующая этому нетерминалу. #include 21) Множество follow(X) должно в этом случае содержать хотя бы один символ, — для этого предполагается, что в конце каждой входной цепочки языка есть маркер Элементы теории трансляции / Синтаксический анализ 59 int c; void S (); void A (); void B (); void E (); 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 (); } else A (); // возможно 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' ) Элементы теории трансляции / Синтаксический анализ 60 { cout << "B-->bB, "; gc (); B (); } else if ( c =='d' ) { cout << "B-->d, "; gc (); } else throw c; } void E () { if ( c =='e' ) { cout << "E-->e, "; gc (); } else throw 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; } } Рекурсивный спуск без построения прогнозов Выделим подкласс грамматик, по которым можно строить систему рекурсивных про- цедур, минуя построение таблицы прогнозов. Будем говорить, что правила КС-грамматики имеют канонический(для РС-метода) вид, если каждая группа правил с одинаковым нетерминалом в левой части относится к од- ному из перечисленных ниже видов и выполняются дополнительные условия: Элементы теории трансляции / Синтаксический анализ 61 а) X → , где (T N) * и это единственное правило вывода для этого нетерминала; б) X → a 1 1 | a 2 2 | ... | a n n , где a i T для всех i 1, 2,..., n ; a i a j для i j; i (T N ) * , т. е. если для не- терминала X правил вывода несколько, то они должны начинаться с терминалов, причем все эти терминалы попарно различны; в) X → a 1 1 | a 2 2 | ... | a n n | , где a i T для всех i 1, 2,..., n; a i a j для i j; i (T N ) * , и first (X ) follow (X ) Если правила вывода имеют такой вид, то рекурсивный спуск может быть реализован без промежуточного построения прогнозов: для правил с несколькими альтернативами вы- бирается альтернатива a i i , если текущий символ совпадает с a i , иначе выбирается - альтернатива, если она присутствует; если нет совпадения текущего символа ни с одним из a i и нет -альтернативы — фиксируется ошибка. Канонический вид правил грамматики дает достаточное, но не необходимое условие применимости РС-метода. Грамматику с правилами канонического вида называют 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 → a M M → , a M | 22) Бэкуса-Наура формула. Элементы теории трансляции / Синтаксический анализ 62 Метод примени м к данной грамматике, так как 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; else gc (); } } Рассмотрим пример еще одной грамматики. G sequence : S → LB L → a {, a} B → , b Если для этой грамматики сразу написать анализатор, не убедившись в применимости метода к преобразованной (без итерации) грамматике, то цепочка а,а,а,b будет признана таким анализатором ошибочной, хотя в действительности а,а,а,b принадлежит порождае- мому G sequence языку. Это произойдет потому, что процедура L( )захватит чужую запятую — ту, что выводится из B, и далее не обнаружив символ а, сообщит об ошибке. Следует сначала проверить применимость метода, исключив из грамматики итерацию рассмотренным выше способом: S → LB L → a M M → , a M | B → , b Как видим, first (, a) follow (M ) { , } и поэтому метод рекурсивного спуска непри- мени м 23) . Можно попытаться поискать другую эквивалентную грамматику, к которой метод примени м. Некоторые полезные для этого эквивалентные преобразования грамматик будут 23) Если бы в G sequenc e последовательность терминалов, перечисляемых через запятую, завершалась отличным от запятой символом (например, точкой с запятой), как это обычно и бывает в реальных языках программи- рования, то метод рекурсивного спуска был бы примени м. Элементы теории трансляции / Синтаксический анализ 63 рассмотрены ниже. Однако, как следует из утверждения 12, успех в поиске эквивалентной грамматики, для которой метод примени м, не гарантирован. Преобразования грамматик Если грамматика не удовлетворяет требованиям применимости метода рекурсивного спуска, то можно попытаться |