И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 13
Текст из файла (страница 13)
Корректность необходимо дополнительно проверять.SS′bifSthenbifεthenSS′aSelse(a)aSS′ifbSthenelseif(б)bthenSaSS′aεРис. 10. Деревья вывода для цепочки if b then if b then a else a.О других методах распознавания КС-языковМетод рекурсивного спуска применим к достаточно узкому подклассу КС-грамматик.Известны более широкие подклассы КС-грамматик, для которых существуют эффективныеанализаторы, обладающие тем же свойством, что и анализатор, построенный методом рекурсивного спуска, — входная цепочка считывается один раз слева направо и процесс разбораполностью детерминирован, в результате на обработку цепочки длины n расходуется времяcn. К таким грамматикам относятся LL(k)-грамматики, по которым, как правило, реализуетсяанализ сверху-вниз — нисходящий; LR(k)-грамматики, грамматики предшествования, по которым, как правило, реализуется анализ снизу-вверх — восходящий; и некоторые другие(см., например, [2], [3]).66Элементы теории трансляции / Синтаксический анализАнализатор для LL(k)-грамматик просматривает входную цепочку слева направо иосуществляет детерминированный левый вывод, принимая во внимание k входных символов,расположенных справа от текущей позиции.
Выбор альтернативы осуществляется на основезаранее составленной таблицы прогнозов.Анализатор для LR(k)-грамматик просматривает входную цепочку слева направо иосуществляет детерминированный правый вывод, принимая во внимание k входных символов, расположенных справа от текущей позиции. Вывод строится методом сверток, как приразборе по леволинейной автоматной грамматике. Предварительно по LR(k)-грамматикестроится таблица, которая на каждом шаге вывода позволяет анализатору однозначно выбрать нужную свертку.Анализатор для грамматик предшествования просматривает входную цепочку слеванаправо и осуществляет детерминированный правый вывод, учитывая только некоторые отношения между парами смежных символов выводимой цепочки.Часто одна и та же КС-грамматика может быть отнесена не к одному, а сразу к нескольким классам грамматик (например, любая LL-грамматика является LR-грамматикой,обратное неверно), допускающих построение линейных по временнóй сложности распознавателей.
Но, на вопрос, какой лучше распознаватель выбрать, нисходящий или восходящий,нет однозначного ответа.Нисходящий синтаксический анализ предпочтителен с точки зрения процесса трансляции, поскольку на его основе легче организовать процесс порождения цепочек результирующего языка.
Восходящий синтаксический анализ привлекательнее тем, что часто дляданного языка программирования легче построить LR-грамматику, поскольку ограниченияна правила слабее, чем для LL-грамматик.Конкретный выбор зависит от конкретного компилятора, от сложности грамматикивходного языка программирования и от того, как будут использованы результаты работыраспознавателя.Синтаксический анализатор для М-языкаБудем считать, что синтаксический и лексический анализаторы взаимодействуют следующим образом: анализ исходной программы идет под управлением синтаксического анализатора; если для продолжения анализа ему нужна очередная лексема, то он запрашивает ееу лексического анализатора; тот выдает одну лексему и «замирает» до тех пор, пока синтаксический анализатор не запросит следующую лексему.Соглашения: наш лексический анализатор — это функция-член get_lex( ) класса Scanner, котораяв качестве результата выдает лексемы типа (class) Lex; в переменной curr_lex типа Lex будем хранить текущую лексему, выданную лексическим анализатором, а в переменной c_val — ее значение.Анализатор методом рекурсивного спуска для М-языка реализуем в виде на Си + + ввиде класса Parser .
Кроме синтаксического анализа, процедуры данного класса осуществляют действия по семантическому контролю и переводу программы во внутреннее представление. Объяснение этих дополнительных действий и вспомогательных объектов будетдано в следующих разделах.67Элементы теории трансляции / Синтаксический анализclass Parser{Lexcurr_lex; // текущая лексемаtype_of_lex c_type;intc_val;Scannerscan;Stack < int, 100 > st_int;Stack < type_of_lex, 100 > st_lex;voidvoidvoidvoidvoidvoidvoidvoidvoidP(); // процедуры РС-методаD1();D();B();S();E();E1();T();F();voidvoidvoidvoidvoidvoidvoiddec ( type_of_lex type);check_id ();check_op ();check_not ();eq_type ();eq_bool ();check_id_in_read ();// семантичиеские действияvoid gl ()// получить очередную лексему{curr_lex = scan.get_lex();c_type = curr_lex.get_type();c_val = curr_lex.get_value();}public:Polizprog;// внутреннее представление программыParser ( const char *program) : scan (program), prog (1000) {}voidanalyze(); // анализатор с действиями};void Parser::analyze (){gl ();P ();prog.print();cout << endl << "Yes!!!" << endl;}void Parser::P (){if ( c_type == LEX_PROGRAM )gl ();68Элементы теории трансляции / Синтаксический анализelsethrow curr_lex;D1 ();if ( c_type == LEX_SEMICOLON )gl ();elsethrow 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();}}elsethrow 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();}else69Элементы теории трансляции / Синтаксический анализif ( c_type == LEX_BOOL ){dec ( LEX_BOOL );gl();}elsethrow 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();elsethrow curr_lex;}elsethrow 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();70Элементы теории трансляции / Синтаксический анализprog.put_lex(Lex(POLIZ_LABEL,prog.get_free()),pl3);}elsethrow curr_lex;}elsethrow curr_lex;} //end ifelseif ( 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);}elsethrow curr_lex;} //end whileelseif ( 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();}elsethrow curr_lex;if ( c_type == LEX_RPAREN ){gl();prog.put_lex (Lex (LEX_READ));}elsethrow curr_lex;}elsethrow curr_lex;} //end readelse71Элементы теории трансляции / Синтаксический анализ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));}elsethrow curr_lex;}elsethrow curr_lex;} //end writeelseif ( 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) );}elsethrow curr_lex;} //assign-endelse 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();72Элементы теории трансляции / Синтаксический анализ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();}elseif ( c_type == LEX_NUM ){st_lex.push ( LEX_INT );prog.put_lex ( curr_lex );gl();}elseif ( c_type == LEX_TRUE ){st_lex.push ( LEX_BOOL );prog.put_lex (Lex (LEX_TRUE, 1) );gl();}elseif ( c_type == LEX_FALSE ){st_lex.push ( LEX_BOOL );prog.put_lex (Lex (LEX_FALSE, 0) );gl();}elseif ( c_type == LEX_NOT ){gl();F();check_not();}elseif ( c_type == LEX_LPAREN ){73Элементы теории трансляции / Синтаксический анализgl();E();if ( c_type == LEX_RPAREN)gl();elsethrow curr_lex;}elsethrow curr_lex;}Семантический анализатор для М-языкаКонтекстные условия, выполнение которых нам надо контролировать в программахна М-языке, таковы:1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
