И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 16
Текст из файла (страница 16)
Действительно, пусть L1 = {a | n ≥ 0},L2 = {b, c}. Существует бесконечно много переводов τi = {(ai, b)} ∪ {(an, c) | n ≠ i, i ≥ 0}, гдеLвх(τi) = L1, Lц(τi) = L2.86Элементы теории трансляции / Генерация внутреннего представления программТеперь при анализе методом рекурсивного спуска цепочек языка L1 с помощью действий будут порождаться соответствующие цепочки языка L2.Генератор внутреннего представления программы на М-языкеКаждый элемент в ПОЛИЗе — это лексема, т. е. пара вида 〈 тип_лексемы, значение_лексемы 〉.
При генерации ПОЛИЗа будем использовать дополнительные типы лексем(для внутреннего представления операторов): POLIZ_GO — «!»; POLIZ_FGO — «!F»; POLIZ_LABEL — для ссылок на номера элементов ПОЛИЗа; POLIZ_ADDRESS — для обозначения операндов-адресов (например, в ПОЛИЗеоператора присваивания).Будем считать, что генерируемая программа размещается в объекте progPoliz, заданном описанием:классаPoliz prog (1000);class Poliz{lex *p;int size;int free;public:Poliz ( int max_size ){p= new Lex [size = max_size];free = 0;};~Poliz() { delete []p; };void put_lex(Lex l) { p[free]=l; ++free; };void put_lex(Lex l, int place) { p[place]=l; };void blank() { ++free; };int get_free() { return free; };lex& operator[] ( int index ){if (index > size)throw "POLIZ:out of array";elseif ( index > free )throw "POLIZ:indefinite element of array";elsereturn p[index];};void print(){for ( int I = 0; i < free; ++i )cout << p[i];};};87Элементы теории трансляции / Генерация внутреннего представления программОбъект prog для хранения внутреннего представления программы разместим в открытой части класса Parser:class Parser{Lex curr_lex;...public:Polizprog;Parser (const char *program ) : scan (program),prog (1000) {}voidanalyze();};Генерация внутреннего представления программы будет проходить во время синтаксического анализа параллельно с контролем контекстных условий, поэтому для генерацииможно использовать информацию, собранную синтаксическим и семантическим анализаторами; например, при генерации ПОЛИЗа выражений можно воспользоваться содержимымстека, с которым работает семантический анализатор.
Кроме того, можно дополнить функции семантического анализа действиями по генерации.Добавим в конец тела функции check_op( ) оператор prog.put_lex (Lex (op) ); записывающий в ПОЛИЗ знак операции op, а в конец функции check_not( ) добавим операторprog.put_lex (Lex (LEX_NOT) ); записывающий лексему not (во внутреннем представлении) вПОЛИЗ.Тогда грамматика, содержащая действия по контролю контекстных условий и переводу выражений модельного языка в ПОЛИЗ, будет такой:EE1TF→→→→E1 | E1 [ = | < | > ] 〈 st_lex.push (c_type ) 〉 E1 〈 check_op ( ) 〉T { [ + | − | or ] 〈 st_lex.push (c_type ) 〉 T 〈 check_op ( ) 〉 }F { [ ∗ | / | and ] 〈 st_lex.push (c_type ) 〉 F 〈 check_op ( ) 〉 }I 〈 check_id ( ); prog.put_lex ( curr_lex ); 〉 |N 〈 st_lex.push (LEX_INT); prog.put_lex ( curr_lex ); 〉 |[ true | false ] 〈 st_lex.push (LEX_BOOL); prog.put_lex ( curr_lex ); 〉 |not F 〈 check_not( ); 〉 | (E)Действия, которыми нужно дополнить правило вывода оператора присваивания, также достаточно очевидны:S → I 〈 check_id ( ); prog.put_lex ( Lex ( POLIZ_ADDRESS, c_val ) ); 〉 :=E 〈 eqtype ( ); prog.put_lex ( Lex ( LEX_ASSIGN ) ); 〉При генерации ПОЛИЗа выражений и оператора присваивания элементы объекта progзаполнялисьпоследовательно.Семантикаусловногооператораif E then S1 else S2 такова, что значения операндов для операций безусловного перехода и перехода «по лжи» в момент генерации операций еще неизвестны:if (!E) goto l2; S1; goto l3; l2: S2; l3 :…88Элементы теории трансляции / Генерация внутреннего представления программПоэтому придется оставлять соответствующие этим операндам элементы объектаprog незаполненными и запоминать их номера, а затем, когда станут известны их значения,заполнять пропущенное.Тогда грамматика, содержащая действия по контролю контекстных условий и переводу условного оператора модельного языка в ПОЛИЗ, будет такой:S→ if E 〈 eqbool( ); pl2 = prog.get_free( ); prog.blank( );prog.put_lex ( Lex (POLIZ_FGO ) ); 〉then S1 〈 pl3 = prog.get_free( ); prog.blank( );prog.put_lex ( Lex (POLIZ_GO) );prog.put_lex ( Lex (POLIZ_LABEL, prog.get_free( ) ), pl2); 〉else S2 〈 prog.put_lex ( Lex (POLIZ_LABEL, prog.get_free( ) ), pl3); 〉Семантика оператора цикла while E do S описывается так:L0: if (!E) goto l1; S; goto l0; l1: ...,а грамматика с действиями по контролю контекстных условий и переводу оператора цикла вПОЛИЗ будет такой:S → while 〈 pl0 = prog.get_free ( );〉 E 〈 eqbool ( );pl1 = prog.get_free ( ); prog.blank ( );prog.put_lex (Lex (POLIZ_FGO)); 〉do S 〈 prog.put_lex (Lex (POLIZ_LABEL, pl0);prog.put_lex (Lex (POLIZ_GO) );prog.put_lex (Lex (POLIZ_LABEL, prog.get_free( ) ), pl1); 〉ЗамечаниеПеременные pli (i = 0, 1, 2, 3) должны быть локализованы в процедуре S, иначе возникнет ошибкапри обработке вложенных операторов.Наконец, запишем соответствующие действия для операторов ввода и вывода:S → read ( I 〈 check_id_in_read( );prog.put_lex ( Lex (POLIZ_ADDRESS, c_val) ); 〉 )〈 prog.put_lex ( Lex (LEX_READ) ); 〉S→ write ( E ) 〈 prog.put_lex ( Lex (LEX_WRITE) ); 〉Интерпретатор ПОЛИЗа для модельного языкаПольская инверсная запись была выбрана нами в качестве языка внутреннего представления программы, в частности, потому, что записанная таким образом программа можетбыть легко проинтерпретирована.Идея алгоритма очень проста: просматриваем ПОЛИЗ слева направо; если встречаемоперанд, то записываем его в стек; если встретили знак операции, то извлекаем из стеканужное количество операндов и выполняем операцию, результат (если он есть) заносим встек и т.
д.Итак, записанная в ПОЛИЗе программа хранится в виде последовательности лексем вобъекте prog класса Poliz. Лексемы могут быть следующие: лексемы-константы (числа, true,89Элементы теории трансляции / Генерация внутреннего представления программfalse), лексемы-метки ПОЛИЗа, лексемы-операции (включая дополнительно введенные вПОЛИЗе) и лексемы-переменные (их значения или адреса — номера строк в таблице TID).В программе-интерпретаторе будем использовать некоторые переменные и функции,введенные нами ранее.class Executer{Lex pc_el;public:void execute ( Poliz& prog );};void Executer::execute ( Poliz& prog ){Stack < int, 100 > args;int i, j, index = 0, size = prog.get_free();while ( index < size ){pc_el = prog [ index ];switch ( pc_el.get_type () ){case LEX_TRUE:case LEX_FALSE:case LEX_NUM:case POLIZ_ADDRESS:case POLIZ_LABEL:args.push ( pc_el.get_value () );break;case LEX_ID:i = pc_el.get_value ();if ( TID[i].get_assign () ){args.push ( TID[i].get_value () );break;}elsethrow "POLIZ: indefinite identifier";case LEX_NOT:args.push( !args.pop() );break;case LEX_OR:i = args.pop();args.push ( args.pop() || i );break;case LEX_AND:i = args.pop();args.push ( args.pop() && i );break;case POLIZ_GO:index = args.pop() - 1;break;case POLIZ_FGO:i = args.pop();if ( !args.pop() )90Элементы теории трансляции / Генерация внутреннего представления программindex = i - 1;break;case LEX_WRITE:cout << args.pop () << endl;break;case LEX_READ:{int k;i = args.pop ();if ( TID[i].get_type () == LEX_INT ){cout << "Input int value for";cout << TID[i].get_name () << endl;cin >> k;}else{char j[20];rep:cout << "Input boolean value;cout << (true or false) for";cout << TID[i].get_name() << endl;cin >> j;if ( !strcmp(j, "true") )k = 1;else if ( !strcmp(j, "false") )k = 0;else{cout << "Error in input:true/false";cout << endl;goto rep;}}TID[i].put_value (k);TID[i].put_assign ();break;}case LEX_PLUS:args.push ( args.pop() + args.pop() );break;case LEX_TIMES:args.push ( args.pop() * args.pop() );break;case LEX_MINUS:i = args.pop();args.push ( args.pop() - i );break;case LEX_SLASH:i = args.pop();if ( !i ){args.push ( args.pop() / i );break;}else throw "POLIZ:divide by zero";case LEX_EQ:91Элементы теории трансляции / Генерация внутреннего представления программargs.push ( args.pop() == args.pop() );break;case LEX_LSS:i = args.pop();args.push ( args.pop()break;case LEX_GTR:i = args.pop();args.push ( args.pop()break;case LEX_LEQ:i = args.pop();args.push ( args.pop()break;case LEX_GEQ:i = args.pop();args.push ( args.pop()break;case LEX_NEQ:i = args.pop();< i);> i );<= i );>= i );args.push ( args.pop() != i );break;case LEX_ASSIGN:i = args.pop();j = args.pop();TID[j].put_value(i);TID[j].put_assign();break;default:throw "POLIZ: unexpected elem";}// end of switch++index;};//end of whilecout << "Finish of executing!!!" << endl;}class Interpretator{Parser pars;Executer E;public:Interpretator ( char* program ): pars (program) {};void interpretation ();};void Interpretator::interpretation (){pars.analyze ();E.execute ( pars.prog );}int main (){try{Interpretator I ( "program.txt" );92/ I.
Грамматики и языки. Классификация по ХомскомуI.interpretation ();return 0;}catch ( char c ){cout << "unexpected symbol " << c << endl;return 1;}catch ( Lex l ){cout << "unexpected lexeme";cout << l;return 1;}catch ( const char *source ){cout << source << endl;return 1;}}ЗадачиI. Грамматики и языки. Классификация по Хомскому1. Даны грамматика и цепочка. Построить вывод заданной цепочки.S → T | T+S | T−ST → F | F∗TF→a|bЦепочка: a−b∗a+ba)b)S → aSBC | abCCB → BCbB → bbbC → bccC → ccЦепочка: aaabbbccc2.
Построить все сентенциальные формы для грамматики с правилами:S → A+B | B+AA→aB→b3. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает?Каков тип языка? Указать максимально возможный номер типа грамматки и языка.a) S → APAP→+|−A→a|bb) S → A | SA | SBA→aB→b93Задачи / I. Грамматики и языки. Классификация по Хомскомуd) S → aQb | εQ → cSce) S → a | BaB → Bb | bf) S → AbA → Aa | bag) S → 0A1 | 010A → 00A1A → 01h) S → ABAB → BAA→aB→bi) S → A | BA → aAb | 0B → aBbb | 1j) S → 0A | 1SA → 0A | 1BB → 0B | 1B | ⊥k) S → 0S | S0 | DD → DD | 1A | εA → 0B | εB → 0A | 0l) S → 0A | 1S | εA → 1A | 0BB → 0S | 1Bm) S → SS | AA → a | bbn) S → AB⊥A → a | cAB → bAo) S → aBA | εB → bSAAA → cp) S → Ab | cA → BaB → cSr)1.2.3.4.5.6.S → KFK → KB | CBC → CA | DADA → aADAa → aADB → bBD7.8.9.10.11.12.Bb → bBAb → bADF → EBE → EbAE → EabE → bs)1.2.3.4.5.S → DCD → aDA | bDB | aA |bBAC → aCBC → bCAa → aA6.7.8.9.Ba → aBAb → bABb → bBC→εu)S → 0A10A → 0B1 | 0B1 → 0C11 | 01C → 0D | 00D1 | 0D → 01t)94c) S → 1BB → B0 | 1S → aAcaA → aaBbC | abBb → bb | abbbc | aDbbbccC→cD → abЗадачи / I.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
