И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1119400), страница 17

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

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

Кроме того, можно дополнить функции семантического анализа действиями по генерации.Добавим в конец тела функции 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.

Грамматики и языки. Классификация по Хомскому4. Построить грамматику, порождающую заданный язык L. Каков тип построенной грамматики? Каков тип языка?n ma) L  { a b | n, m  1};*b) L  { ccc | , ,   {a,b} (т.е. , ,  — любые цепочки из a и b)};c) L  { a1 a2 ... an an ... a2 a1 | ai { 0, 1}, n  1};d) L  { 0 n 1[n/2] | n1};e) L  { ca n cb m c n | n0, m0 };f) L  { a n b m | n  m ; n, m  0};*g) L  {  |   {0,1} , ||0 ||1 } (т.е. все цепочки из 0 и 1 с неравным числом 0 и 1);h) L  {  |   {a,b}};i) L  {  |   {0,1}, ||0  ||1,  x,y {0,1} :   xy *(т.е.

все непустые цепочки,| x |1  | x |0}содержащие равное количество 0 и 1, причем любая подцепочка,взятая с левого конца, содержит единиц не больше, чем нулей) ;j) L  { 1 2…n | n  0, i { a 2m b m | m  1} для 1 i n };a 3 1  | n  1};n2L  { a | n  1};nk) L  {l)a n 1 | n  1}.3m) L  {5. К какому типу по Хомскому относится данная грамматика (указать максимально возможный номер)? Какой язык она порождает? Каков тип языка? Выписать подтверждающую ответ грамматику, в состав которой входит только один нетерминал — цель грамматики.a)S  AB | ASBAaaB  bbB  bbb)S  1A01A  11A0 | 016.

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

Список файлов книги