Лекции (1) (1119472), страница 2

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

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

имеют вид:СA → B11 | ... | Bnn | a11 | ... | ammB1 → 11 | ... | 1k...Bn → n1 | ... | np ,// A → B |// B → 1 | 2// С → 1 | 2где Bi  N; aj  T; i, j, ij  (T  N)*,то можно заменить вхождения нетерминалов Bi их правилами вывода внадежде, что правила вывода из нетерминала A станут удовлетворятьтребованиям метода рекурсивного спуска:A → 111 | ... | 1k1 | ...

| n1n | ... | npn | a11 | ... | amm// A → 1 | 12 | 1 | 2Преобразования грамматик3) Если в грамматике есть нетерминал, у которогонесколько правил вывода начинаются одинаковымитерминальными символами, т.е. имеют видA → a1 | a2 | ... | an | 1 | ... |m ,// A → a1 | a2 | где a  T; i,  j  (T  N)*,то непосредственно применять РС-метод нельзя. Можнопреобразовать правила вывода данного нетерминала,объединив правила с общими началами в одно правило:A → aA’ | 1 | ...

|mA’ → 1 | 2 | ... | n// A → aA’ | // A’ → 1 | 2Будет получена грамматика, эквивалентная данной.Преобразования грамматик4) Если в правилах вывода грамматики есть пустая альтернатива, т.е. естьправила видаA → a11 | ... | ann |  ,то метод рекурсивного спуска может оказаться неприменимым.Например, для грамматики G = ( { a, b }, { S, A }, P, S), гдеP: S → bAa// S → bAсA → aA | РС-анализатор, реализованный по обычной схеме, будет таким:void S ( ) {void A( ) {if (c == ‘b’) {if (c == ‘a’) {gc( ); A( );gc(); A(); }if (c != ‘a’) throw c; }}else throw c;}Тогда при анализе цепочки baa функция A( ) будет вызвана два раза; онапрочитает подцепочку аа, хотя второй символ а - это часть подцепочки, выводимойиз S. В результате окажется, что baa не принадлежит языку, порождаемомуграмматикой, но в действительности это не так.Т.е.

еслиFIRST(A)  FOLLOW(A)   , то метод рекурсивного спусканеприменим к данной грамматике.Итак, если в грамматике есть правила с пустой альтернативойвида: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)  ); следовательно,потребуются дальнейшие преобразования, и успех негарантирован.Пример преобразования грамматикиS  fASd | A  Aa | Ab | dB | fB  bcB | S  fASd | A  dBA' | fA'A'  aA' | bA' | B  bcB | FIRST(S) = { f }, FOLLOW(S) = { d };  = FIRST(A') = { a, b }, FOLLOW(A') = { f, d };  = FIRST(B) = { b }, FOLLOW(B) = { a, b, f, d };  = {b}  S  fASd | A  dB' | fA'B'  bcB' | A'B'  bcB' | aA' | bA' | A'  aA' | bA' | B  bcB |  - недостижимые правила, их можно убрать.S  fASd | A  dB' | fA'B'  bС | aA' | С  cB' | A'A'  aA' | bA' | С  cB' | aA' | bA' | S - не менялось,FIRST(B') = { a, b }, FOLLOW(B') = { f, d };  = FIRST(A') = { a, b }, FOLLOW(A') = { f, d };  = FIRST(C) = { a, b, c}, FOLLOW(C) = { f, d };  = Т.е. получили эквивалентную грамматику, к которой применим метод рекурсивного спуска.Синтаксический анализатор для М-языка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 ();elsethrow curr_lex;D1();if (c_type == LEX_SEMICOLON)gl ();elsethrow curr_lex;B ();if (c_type != LEX_FIN)throw curr_lex;}Другие методы распознавания КС-языков.Существуют другие методы анализа, анализаторы по которымприменимы к более широким подклассам КС-грамматик, чем РСанализатор, но обладающие теми же свойствами: входная цепочкасчитывается один раз слева направо, процесс разборадетерминирован, и в результате на обработку цепочки длины nрасходуется время cn.Например:Анализатор для LL(k)-грамматик осуществляет левостороннийвывод (анализ сверху-вниз) , принимая во внимание k входныхсимволов, расположенных справа, от текущей позиции .Анализатор для LR(k)-грамматик осуществляет правостороннийвывод (анализ снизу-вверх), принимая во внимание k входныхсимволов, расположенных справа, от текущей позиции.Анализатор для грамматик предшествования осуществляетправосторонний вывод (анализ снизу-вверх) , учитывая тольконекоторые отношения между парами смежных символов выводимойцепочки.Другие методы распознавания КС-языков.Любая грамматика, анализируемая РС-методом, являетсяLL(1)-грамматикой - обратное неверно.Любая LL-грамматика является LR-грамматикой - обратноеневерно.Левосторонний (нисходящий) синтаксический анализпредпочтителен с точки зрения процесса трансляции, поскольку наего основе легче организовать процесс порождения цепочекрезультирующего языка.Восходящий синтаксический анализ привлекательнее тем, чточасто для языков программирования легче построитьправоанализируемую грамматику, а на ее основе - правостороннийраспознаватель.Конкретный выбор анализатора зависит от конкретногокомпилятора, от сложности грамматики входного языкапрограммирования и от того, как будут использованы результатыработы анализатора..

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

Список файлов лекций