formal_languages_translation_theory (852748), страница 17
Текст из файла (страница 17)
д.Итак, записанная в ПОЛИЗе программа хранится в виде последовательности лексем вобъекте 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 | TS | TST F | FTFa|bЦепочка: ababa)b)S aSBC | abCCB BCbB bbbC bccC ccЦепочка: aaabbbccc2. Построить все сентенциальные формы для грамматики с правилами:S AB | BAAaBb3. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает?Каков тип языка? Указать максимально возможный номер типа грамматки и языка.a) S APAP|Aa|bb) S A | SA | SBAaBb93Задачи / I. Грамматики и языки.
Классификация по Хомскомуd) S aQb | Q cSce) S a | BaB Bb | bf) S AbA Aa | bag) S 0A1 | 010A 00A1A 01h) S ABAB BAAaBbi) 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 ABA 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 bBCu)S 0A10A 0B1 | 0B1 0C11 | 01C 0D | 00D1 | 0D 01t)94c) S 1BB B0 | 1S aAcaA aaBbC | abBb bb | abbbc | aDbbbccCcD abЗадачи / I. Грамматики и языки.
Классификация по Хомскому4. Построить грамматику, порождающую заданный язык L. Каков тип построенной грамматики? Каков тип языка?n ma) L { a b | n, m 1};*b) L { ccc | , , {a,b} (т.е. , , — любые цепочки из a и b)};c) L { a1 a2 ... an an ... a2 a1 | ai { 0, 1}, n 1};d) L { 0 n 1[n/2] | n1};e) L { ca n cb m c n | n0, m0 };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 | ASBAaaB bbB bbb)S 1A01A 11A0 | 016. Эквивалентны ли грамматики с правилами:а) S ABA a | AaB b | BbиS AS | SB | ABAaBbb) S aSL | aLL KccK KcKbиS aSBc | abccB BcbB bb95Задачи / I.
Грамматики и языки. Классификация по Хомскому7. Построить КС-грамматику, эквивалентную грамматике с правилами:а) S aAbaA aaAbAb) S AB | ABSAB BABA ABAaBb8. Построить регулярную грамматику, эквивалентную грамматике с правилами:а) S A | ASA a | bbb) S A.AA B | BAB0|19. Привести пример грамматики, каждое правило которой относится к одному из трех видовA Bt,либо A t B,либо A t, для которой не существуетэквивалентной регулярной грамматики.10. Доказать, что грамматика с правилами:S aSBC | abCCB BCbB bbbC bccC ccn n nпорождает язык L {a b c | n 1}.Для этого показать, что в данной грамматике:n n nI ) выводится любая цепочка вида a b c (n 1) иII ) не выводятся никакие другие цепочки.11.
Дана грамматика с правилами:a) S S0 | S1 | D0 | D1D H.H 0 | 1 | H0 | H1b) S if B then S | B EEB|BEBa|bПостроить восходящим и нисходящим методами дерево вывода для цепочки:a) 10.1001b) if a then b a b b12. Определить тип грамматики. Описать язык, порождаемый этой грамматикой. Построитьдля этого языка КС-грамматику.S PP 1P1 | 0P0 | TT 021 | 120RR1 0RR0 1RR 196Задачи / I. Грамматики и языки. Классификация по Хомскому13. Построить регулярную грамматику, порождающую{a, b}, в которых символ a не встречается два раза подряд.цепочкивалфавите14. Построить КС-грамматику для языка L, построить дерево вывода и левосторонний вывод для цепочки aabbbcccc.L {a2n bm c2k | m n k, m 1}.15.
Построить грамматику, порождающую сбалансированные относительно круглых скобокцепочки в алфавите { a, ( , ), }. Сбалансированную цепочку определим рекурсивно: цепочка сбалансирована, еслиa) не содержит скобок,b) (1) или 1 2, где 1 и 2 сбалансированы.16. Построить КС-грамматику, порождающую язык L, и вывод для цепочки aacbbbcaa вэтой грамматике.nmnL {a cb ca | n,m 0}.17.
Построить КС-грамматику, порождающую язык L, и вывод для цепочки 110000111 вэтой грамматике.n m pL {1 0 1 | n p m; n, p, m 0}.18. Дан язык L {13n2 0 n | n 0}. Определить его тип, построить грамматику, порождающую L. Построить левосторонний и правосторонний выводы, дерево разбора для цепочки1111111100.19. Найти общие алгоритмы построения по данным КС-грамматикам G1 и G2, порождающим языки L1 и L2, КС-грамматики дляa) L1L2 ;b) L1 L2 ;c) L1 .ЗамечаниеL L1 L2 — это конкатенация языков L1 и L2, т.е. L { | L1, L2}; L L1 — это итерация языка L1, т.е. объединение {} L1 L1L1 L1L1L1 ...20.
Построить КС-грамматику для L {i 2 i1R | i N, i (i)2 — двоичное представлениечисла i (без незначащих нулей), R — обращение цепочки }. Построить КС-грамматикудля языка L (см. замечание к задаче 19).21. Показать, что грамматикаE EE | EE | (E) | iнеоднозначна. Как описать этот же язык с помощью однозначной грамматики?97Задачи / I. Грамматики и языки.
Классификация по Хомскому22. Показать, что наличие в приведенной КС-грамматике правил видаa) A AA | b) A AA | c) A A | A | ,где , , (TN), A N, делает ее неоднозначной. Можно ли преобразовать эти правилатаким образом, чтобы полученная эквивалентная грамматика была однозначной?23. Показать, что грамматика G неоднозначна. Какой язык она порождает? Является ли этотязык однозначным?G: S aAc | aBB bcAb24. Дана КС-грамматика G T, N, P, S .
Предложить алгоритм построения множестваX {A N | A }.25. Для произвольной КС-грамматики G предложить алгоритм, определяющий, пуст лиязык L(G).26. Построить приведенную грамматику, эквивалентную данной КС-грамматике.a) S aABS | bCACdA bAB | cSA | cCCB bAB | cSBC cS | cb) S aAB | EA dDA | B bE | fC cAB | dSD | aD eAE fA | g27. Построить неукорачивающую КС-грамматику, эквивалентную данной, применив алгоритм устранения правил с пустой правой частью.S aS | Sa | CC CC | bA | A aB | B aA | a28.
Язык называется распознаваемым, если существует алгоритм, который за конечное число шагов позволяет получить ответ о принадлежности любой цепочки этому языку. Есличисло шагов зависит от длины цепочки и может быть оценено до выполнения алгоритма,язык называется легко распознаваемым. Доказать, что язык, порождаемый неукорачивающей грамматикой, легко распознаваем.29. Доказать, что любой конечный язык является регулярным языком.30. Доказать, что нециклическая КС-грамматика порождает конечный язык.ЗамечаниеНетерминальный символ A N — циклический, если в грамматике существует вывод A 1A2.
КС-грамматика называется циклической, если в ней имеется хотя бы один циклическийсимвол.98Задачи / II. Регулярные грамматики, конечные автоматы, разбор по ДС31. Показать, что условие цикличности грамматики (см. задачу 29) не является достаточнымусловием бесконечности порождаемого ею языка.32. Доказать, что язык, порождаемый циклической приведенной КС-грамматикой, содержащей хотя бы один эффективный циклический символ, бесконечен.ЗамечаниеЦиклический символ называется эффективным, если A A, где |A| 1; иначе циклическийсимвол называется фиктивным.II. Регулярные грамматики, конечные автоматы, разбор по ДС1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
