Учебное пособие для студентов II курса (издание третье, переработанное и дополненное) Москва 2009 удк 519. 682. 1
 Скачать 2.2 Mb.
|
|
преобразовать ее, т. е. получить эквивалентную грамматику, пригодную для анализа этим методом. (1) Если в грамматике есть нетерминалы, правила вывода которых непосредственно леворекурсивны, т. е. имеют вид: A → A 1 | ... | A n | 1 | ... | m , где i (T N ) + для i 1, 2, ..., n; j (T N ) * для j 1, 2, ..., m, то в таком случае приме- нять метод рекурсивного спуска нельзя, поскольку first(A i ) first(A k ) для некоторых i k, или j для некоторого j и first (А i ) follow (A) для i 1, 2, ..., n. Левую рекурсию всегда можно заменить правой: A → 1 A′ | ... | m A′ A′ → 1 A′ | ... | n A′ | Будет получена грамматика, эквивалентная данной, т.к. из нетерминала A по- прежнему выводятся цепочки вида j { i }, где i 1, 2, ..., n; j 1, 2, ..., m. (2) Если в грамматике есть нетерминал, у которого несколько правил вывода начина- ются одинаковыми терминальными символами, т. е. имеют вид A → a 1 | a 2 | ... | a n | 1 | ... | m , где a T ; i , j (T N ) * , j неначинаетсяс a, i 1, 2,..., n, j 1, 2,..., m,то непосред- ственно применять метод рекурсивного спуска нельзя, т. к. first(a i ) first(a k ) для i k. Можно преобразовать правила вывода данного нетерминала, объединив правила с об- щими началами в одно правило: A → aA′ | 1 | ... | m A′ → 1 | 2 | ... | n Будет получена грамматика, эквивалентная данной. (3) Если в грамматике есть нетерминал, у которого несколько правил вывода, и среди них есть правила, начинающиеся нетерминальными символами, т. е. имеют вид: A → B 1 1 | ... | B n n | a 1 1 | ... | a m m B 1 → 11 | ... | 1 k … B n → n 1 | ... | np , где B i N; a j T; i , j , ij ( T N ) * , то можно заменить вхождения нетерминалов B i их правилами вывода в надежде, что правила нетерминала A станут удовлетворять услови- ям применимости метода рекурсивного спуска: A → 11 1 | ... | 1 k 1 | ... | n 1 n | ... | np n | a 1 1 | ... | a m m Элементы теории трансляции / Синтаксический анализ 64 (4) Если есть правила с пустой альтернативой вида: A → 1 A | ... | n A | 1 | ... | m | B → A и first(A) follow(A) (из-за вхождения А в правила вывода для В), то можно построить такую грамматику: B → A′ A′ → 1 A′ | ... | n A′ | 1 | ... | m | Полученная грамматика будет эквивалентна исходной, т. к. из B по-прежнему выво- дятся цепочки вида { i } j либо { i } Однако правило вывода для нетерминального символа A′ будет иметь альтернативы, начинающиеся одинаковыми терминальными символами (т. к. first(A) follow(A) ); сле- довательно, потребуются дальнейшие преобразования, и успех не гарантирован. Пример. Рассмотрим грамматику G origin : G origin S → fASd | A → Aa | Ab | dB | f B → bcB | first(Aa) first(Ab) {d, f } first(bcB) {b}, follow(B) {a, b, d, f } Условия применимости метода рекурсивного спуска не выполняются для G origin . С помощью преобразований приведем эту грамматику к каноническому виду для рекурсивного спуска. Будем подчеркивать не удовлетворяющие каноническому виду правила и при переходе к новой грамматике указывать номер примененного преобразования ( i ) , 1 i 4 : G origin : S → fASd | A → Aa | Ab | dB | f B → bcB | (1) G transform 1 : S → fASd | A → dBA' | fA' (4) A' → aA' | bA' | B → bcB | first(S) { f }, follow( S ) { d }, first (S) follow(S) ; first(A') {a, b}, follow(A') { f, d }, first (A') follow(A') ; first(B) {b}, follow(B) {a, b, f, d }, first(B) follow(B) {b} (4) G transform 2 : S → fASd | A → dB' | fA' B' → bcB' | A' A'→ aA' | bA' | (3) G transform 3 : S → fASd | A → dB' | fA' B' → bcB' | aA' | bA' | A' → aA' | bA' | Элементы теории трансляции / Синтаксический анализ 65 (2) G transform 4 : S → fASd | A → dB' | fA' B' → bC | aA' | C → cB' | A' A' → aA' | bA' | (3) G object : S → fASd | A → dB' | fA' B' → bC | aA' | C → cB' | aA' | bA' | A' → aA' | bA' | first(B') {a, b}, follow(B') {f, d}; first(B') follow(B') ; first(A') {a, b}, follow(A') {f, d}; first(A') follow(A') ; first(C) {a, b, c}, follow(C) {f, d}; first(C) follow(C) Т. е. получили эквивалентную грамматику G object , к которой примени м метод рекурсивного спуска. G object удобна для построения системы рекурсивных процедур, так как ее правила имеют канонический вид. Задача разбора для неоднозначных грамматик Для неоднозначных грамматик задача синтаксического анализа (задача разбора) мо- жет быть поставлена двумя основными способами. (1) Даны КС-грамматика G и цепочка x. Требуется проверить: x L(G)? Если да, то построить все деревья вывода для x (или все левые выводы для x, или все правые выводы для x) 24) Для решения этой задачи можно обобщить метод рекурсивного спуска, чтобы он ра- ботал с возвратами, пробуя различные подходящие альтернативы. (2) Даны КС-грамматика G и цепочка x. Требуется проверить: x L(G)? Если да, то построить одно дерево вывода для x (возможно, наиболее подходящее в некотором смысле). При такой постановке для некоторых неоднозначных грамматик удается модифици- ровать обычный РС-метод без возвратов так, что получаемый анализатор корректен, и стро- ит наиболее подходящее в некотором смысле дерево. Неприменимость метода рекурсивного спуска в «чистом» виде для неоднозначных грамматик обусловлена невозможностью однозначно спрогнозировать выбор альтернативы при разборе цепочки (прогноз может состоять из нескольких подходящих альтернатив). Мо- дификация метода состоит в следущем: одна из альтернатив объявляется «наиболее подхо- дящей», и процедура анализа всегда выбирает эту альтернативу, игнорируя другие. Рассмотрим пример, иллюстрирующий ситуацию с условными (полным и сокращен- ным) операторами в языке Паскаль. G if-then {if, then, else, a, b}, {S }, P, S, S′ , где P { S → if b then S S′ | a ; S′ → else S | }. В этой грамматике прогноз для S′ по else неоднозначен, так как first(else S) follow(S′) {else} . Для цепочки if b then if b then a else a можно построить два различных дерева вывода, показанных на рис. 101 (а, б). Если при построении анализатора отдать предпочтение непустой альтернативе для S′, то такой анализатор построит дерево, изображенное на рис. 101 (а), в котором else соотно- сится с ближайшим (на его уровне вложенности) if, что соответствует правилам, принятым в 24) Цепочка в неоднозначной грамматике может иметь и бесконечно много деревьев вывода. В таком случае можно ограничиться построением всех деревьев, высота которых не превосходит некоторой константы. Элементы теории трансляции / Синтаксический анализ 66 языке Паскаль при разрешении подобных неоднозначностей в комбинациях условных опера- торов. Итак, мы модифицировали РС-метод для данного примера неоднозначной граммати- ки, отдав предпочтение одной из альтернатив (и получив тем самым подходящее для семан- тики языка Паскаль дерево разбора). Нетрудно убедиться, что получаемый для грамматики G if-then анализатор корректен: он не зацикливается, распознает правильные цепочки и отвергает неправильные. Отметим, что подобная модификация РС-метода не всегда приводит к построению корректного анализатора. Корректность необходимо дополнительно проверять. (a) (б) Рис. 10. Деревья вывода для цепочки if b then if b then a else a. О других методах распознавания КС - языков Метод рекурсивного спуска применим к достаточно узкому подклассу КС-грамматик. Известны более широкие подклассы КС-грамматик, для которых существуют эффективные анализаторы, обладающие тем же свойством, что и анализатор, построенный методом рекур- сивного спуска, — входная цепочка считывается один раз слева направо и процесс разбора полностью детерминирован, в результате на обработку цепочки длины n расходуется время cn. К таким грамматикам относятся LL(k)-грамматики, по которым, как правило, реализуется анализ сверху-вниз — нисходящий; LR(k)-грамматики, грамматики предшествования, по ко- торым, как правило, реализуется анализ снизу-вверх — восходящий; и некоторые другие (см., например, [2], [3]). S if then b else if b then a a S S S S′ S′ S if then b else if b then a a S S S S′ S′ Элементы теории трансляции / Синтаксический анализ 67 Анализатор для LL(k)-грамматик просматривает входную цепочку слева направо и осуществляет детерминированный левый вывод, принимая во внимание k входных символов, расположенных справа от текущей позиции. Выбор альтернативы осуществляется на основе заранее составленной таблицы прогнозов. Анализатор для LR(k)-грамматик просматривает входную цепочку слева направо и осуществляет детерминированный правый вывод, принимая во внимание k входных симво- лов, расположенных справа от текущей позиции. Вывод строится методом сверток, как при разборе по леволинейной автоматной грамматике. Предварительно по LR(k)-грамматике строится таблица, которая на каждом шаге вывода позволяет анализатору однозначно вы- брать нужную свертку. Анализатор для грамматик предшествования просматривает входную цепочку слева направо и осуществляет детерминированный правый вывод, учитывая только некоторые от- ношения между парами смежных символов выводимой цепочки. Часто одна и та же КС-грамматика может быть отнесена не к одному, а сразу к не- скольким классам грамматик (например, любая LL-грамматика является LR-грамматикой, обратное неверно), допускающих построение линейных по временнóй сложности распозна- вателей. Но, на вопрос, какой лучше распознаватель выбрать, нисходящий или восходящий, нет однозначного ответа. Нисходящий синтаксический анализ предпочтителен с точки зрения процесса транс- ляции, поскольку на его основе легче организовать процесс порождения цепочек результи- рующего языка. Восходящий синтаксический анализ привлекательнее тем, что часто для данного языка программирования легче построить LR-грамматику, поскольку ограничения на правила слабее, чем для LL-грамматик. Конкретный выбор зависит от конкретного компилятора, от сложности грамматики входного языка программирования и от того, как будут использованы результаты работы распознавателя. Синтаксический анализатор для М - языка Будем считать, что синтаксический и лексический анализаторы взаимодействуют сле- дующим образом: анализ исходной программы идет под управлением синтаксического ана- лизатора; если для продолжения анализа ему нужна очередная лексема, то он запрашивает ее у лексического анализатора; тот выдает одну лексему и «замирает» до тех пор, пока синтак- сический анализатор не запросит следующую лексему. Соглашения: наш лексический анализатор — это функция-член get_lex( ) класса Scanner, которая в качестве результата выдает лексемы типа (class) Lex; в переменной curr_lex типа Lex будем хранить текущую лексему, выданную лекси- ческим анализатором, а в переменной c_val — ее значение. Анализатор методом рекурсивного спуска для М-языка реализуем в виде на Си в виде класса Parser . Кроме синтаксического анализа, процедуры данного класса осуществ- ляют действия по семантическому контролю и переводу программы во внутреннее пред- ставление. Объяснение этих дополнительных действий и вспомогательных объектов будет дано в следующих разделах. Элементы теории трансляции / Синтаксический анализ 68 class Parser { Lex curr_lex; // текущая лексема type_of_lex c_type; int c_val; Scanner scan; Stack < int, 100 > st_int; Stack < type_of_lex, 100 > st_lex; void P(); // процедуры РС-метода void D1(); void D(); void B(); void S(); void E(); void E1(); void T(); void F(); void dec ( type_of_lex type); // семантичиеские действия void check_id (); void check_op (); void check_not (); void eq_type (); void eq_bool (); void check_id_in_read (); void gl () // получить очередную лексему { curr_lex = scan.get_lex(); c_type = curr_lex.get_type(); c_val = curr_lex.get_value(); } public: Poliz prog; // внутреннее представление программы Parser ( const char *program) : scan (program), prog (1000) {} void analyze(); // анализатор с действиями }; void Parser::analyze () { gl (); P (); prog.print(); cout << endl << "Yes!!!" << endl; } void Parser::P () { if ( c_type == LEX_PROGRAM ) gl (); Элементы теории трансляции / Синтаксический анализ 69 else throw curr_lex; D1 (); if ( c_type == LEX_SEMICOLON ) gl (); else throw curr_lex; B (); if ( c_type != LEX_FIN ) throw curr_lex; } void Parser::D1 () { if ( c_type == LEX_VAR ) { gl (); D (); while ( c_type == LEX_COMMA ) { gl(); D(); } } else throw curr_lex; } void Parser::D () { st_int.reset(); if ( c_type != LEX_ID ) throw curr_lex; else { st_int.push ( c_val ); gl (); while ( c_type == LEX_COMMA ) { gl(); if (c_type != LEX_ID) throw curr_lex; else { st_int.push ( c_val ); gl(); } } if ( c_type != LEX_COLON ) throw curr_lex; else { gl (); if ( c_type == LEX_INT ) { dec ( LEX_INT ); gl(); } else Элементы теории трансляции / Синтаксический анализ 70 if ( c_type == LEX_BOOL ) { dec ( LEX_BOOL ); gl(); } else throw curr_lex; } } } void Parser::B () { if ( c_type == LEX_BEGIN ) { gl(); S(); while ( c_type == LEX_SEMICOLON ) { gl(); S(); } if ( c_type == LEX_END ) gl(); else throw curr_lex; } else throw curr_lex; } void Parser::S () { int pl0, pl1, pl2, pl3; if ( c_type == LEX_IF ) { gl(); E(); eq_bool(); pl2 = prog.get_free (); prog.blank(); prog.put_lex (Lex(POLIZ_FGO)); if ( c_type == LEX_THEN ) { gl(); S(); pl3 = prog.get_free(); prog.blank(); prog.put_lex (Lex(POLIZ_GO)); prog.put_lex (Lex(POLIZ_LABEL, prog.get_free()),pl2); if (c_type == LEX_ELSE) { gl(); S(); Элементы теории трансляции / Синтаксический анализ 71 prog.put_lex(Lex(POLIZ_LABEL,prog.get_free()),pl3); } else throw curr_lex; } else throw curr_lex; } //end if else if ( c_type == LEX_WHILE ) { pl0 = prog.get_free(); gl(); E(); eq_bool(); pl1 = prog.get_free(); prog.blank(); prog.put_lex (Lex(POLIZ_FGO)); if ( c_type == LEX_DO ) { gl(); S(); prog.put_lex (Lex (POLIZ_LABEL, pl0)); prog.put_lex (Lex ( POLIZ_GO)); prog.put_lex (Lex(POLIZ_LABEL, prog.get_free()),pl1); } else throw curr_lex; } //end while else if ( c_type == LEX_READ ) { gl(); if ( c_type == LEX_LPAREN ) { gl(); if ( c_type == LEX_ID ) { check_id_in_read(); prog.put_lex (Lex ( POLIZ_ADDRESS, c_val) ); gl(); } else throw curr_lex; if ( c_type == LEX_RPAREN ) { gl(); prog.put_lex (Lex (LEX_READ)); } else throw curr_lex; } else throw curr_lex; } //end read else Элементы теории трансляции / Синтаксический анализ 72 if ( c_type == LEX_WRITE ) { gl(); if ( c_type == LEX_LPAREN ) { gl(); E(); if ( c_type == LEX_RPAREN ) { gl(); prog.put_lex (Lex(LEX_WRITE)); } else throw curr_lex; } else throw curr_lex; } //end write else if ( c_type == LEX_ID ) { check_id (); prog.put_lex (Lex(POLIZ_ADDRESS,c_val)); gl(); if ( c_type == LEX_ASSIGN ) { gl(); E(); eq_type(); prog.put_lex (Lex (LEX_ASSIGN) ); } else throw curr_lex; } //assign-end else B(); } void Parser::E () { E1(); if ( c_type == LEX_EQ || c_type == LEX_LSS || c_type == LEX_GTR || c_type == LEX_LEQ || c_type == LEX_GEQ || c_type == LEX_NEQ ) { st_lex.push (c_type); gl(); E1(); check_op(); } } void Parser::E1 () { T(); while ( c_type==LEX_PLUS || c_type==LEX_MINUS || c_type==LEX_OR ) { st_lex.push (c_type); gl(); Элементы теории трансляции / Синтаксический анализ 73 T(); check_op(); } } void Parser::T () { F(); while ( c_type==LEX_TIMES || c_type==LEX_SLASH || c_type==LEX_AND ) { st_lex.push (c_type); gl(); F(); check_op(); } } void Parser::F () { if ( c_type == LEX_ID ) { check_id(); prog.put_lex (Lex (LEX_ID, c_val)); gl(); } else if ( c_type == LEX_NUM ) { st_lex.push ( LEX_INT ); prog.put_lex ( curr_lex ); gl(); } else if ( c_type == LEX_TRUE ) { st_lex.push ( LEX_BOOL ); prog.put_lex (Lex (LEX_TRUE, 1) ); gl(); } else if ( c_type == LEX_FALSE ) { st_lex.push ( LEX_BOOL ); prog.put_lex (Lex (LEX_FALSE, 0) ); gl(); } else if ( c_type == LEX_NOT ) { gl(); F(); check_not(); } else if ( c_type == LEX_LPAREN ) { Элементы теории трансляции / Синтаксический анализ 74 gl(); E(); if ( c_type == LEX_RPAREN) gl(); else throw curr_lex; } else throw curr_lex; } Семантический анализатор для М - языка Контекстные условия, выполнение которых нам надо контролировать в программах на М-языке, таковы: 1. Любое имя, используемое в программе, должно быть описано и только один раз. 2. В операторе присваивания типы переменной и выражения должны совпадать. 3. В условном операторе и в операторе цикла в качестве условия возможно только логическое выражение. 4. Операнды операции отношения должны быть целочисленными. 5. Тип выражения и совместимость типов операндов в выражении определяются по обычным правилам (как в Паскале). Проверку контекстных условий совместим с синтаксическим анализом. Для этого в синтаксические правила вставим вызовы процедур, осуществляющих необходимый кон- троль, а затем перенесем их в процедуры рекурсивного спуска. Для реализации семантического анализа будем использовать следующий шаблонный класс Stack: template { T s[max_size]; int top; public: Stack(){top = 0;} void reset() { top = 0; } void push(T i); T pop(); bool is_empty(){ return top == 0; } bool is_full() { return top == max_size; } }; template { if ( !is_full() ) { s[top] = i; ++top; } Элементы теории трансляции / Синтаксический анализ 75 else throw "Stack_is_full"; } template T Stack { if ( !is_empty() ) { --top; return s[top]; } else throw "Stack_is_empty"; } Обработка описаний Для контроля согласованности типов в выражениях и типов выражений в операторах, необходимо знать типы переменных, входящих в эти выражения. Кроме того, нужно прове- рять, нет ли повторных описаний идентификаторов. Эта информация становится известной в тот момент, когда синтаксический анализатор обрабатывает описания. Следовательно, в син- таксические правила для описаний нужно вставить действия, с помощью которых будем за- поминать типы переменных и контролировать единственность их описания. Лексический анализатор запомнил в таблице идентификаторов TID все идентифика- торы-лексемы, которые были им обнаружены в тексте исходной программы. Информация о типе переменных и о наличии их описания заносится в ту же таблицу. i-ая строка таблицы TID соответствует идентификатору-лексеме вида LEX_ID, i Лексический анализатор заполнил поле name; значения полей declare и type будем за- полнять на этапе семантического анализа. Раздел описаний имеет вид D → I {, I}: [ |