Учебное пособие для студентов II курса (издание третье, переработанное и дополненное) Москва 2009 удк 519. 682. 1
 Скачать 2.2 Mb.
|
|
if (!E) goto l 1 ; S; goto l 0 ; l 1 : ..., а грамматика с действиями по контролю контекстных условий и переводу оператора цикла в ПОЛИЗ будет такой: S → while pl 0 prog.get_free ( ); E eqbool ( ); pl 1 prog.get_free ( ); prog.blank ( ); prog.put_lex (Lex (POLIZ_FGO)); do S prog.put_lex (Lex (POLIZ_LABEL, pl 0 ); prog.put_lex (Lex (POLIZ_GO) ); prog.put_lex (Lex (POLIZ_LABEL, prog.get_free( ) ), pl 1 ); Замечание Переменные pl i (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, Элементы теории трансляции / Генерация внутреннего представления программ 90 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; } else throw "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() ) Элементы теории трансляции / Генерация внутреннего представления программ 91 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: Элементы теории трансляции / Генерация внутреннего представления программ 92 args.push ( args.pop() == args.pop() ); break; case LEX_LSS: i = args.pop(); args.push ( args.pop() < i); break; case LEX_GTR: i = args.pop(); args.push ( args.pop() > i ); break; case LEX_LEQ: i = args.pop(); args.push ( args.pop() <= i ); break; case LEX_GEQ: i = args.pop(); args.push ( args.pop() >= i ); break; case LEX_NEQ: i = args.pop(); 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 while cout << "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" ); / I. Грамматики и языки. Классификация по Хомскому 93 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. Даны грамматика и цепочка. Построить вывод заданной цепочки. a) S T | T S | T S b) S aSBC | abC T F | F T CB BC F a | b bB bb Цепочка: a b a b bC bc cC cc Цепочка: aaabbbccc 2. Построить все сентенциальные формы для грамматики с правилами: S A B | B A A a B b 3. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? Указать максимально возможный номер типа грамматки и языка. a) S APA b) S A | SA | SB P | A a A a | b B b Задачи / I. Грамматики и языки. Классификация по Хомскому 94 c) S 1B d) S aQb | B B0 | 1 Q cSc e) S a | Ba f) S Ab B Bb | b A Aa | ba g) S 0A1 | 01 h) S AB 0A 00A1 AB BA A 01 A a B b i) S A | B j) S 0A | 1S A aAb | 0 A 0A | 1B B aBbb | 1 B 0B | 1B | k) S 0S | S0 | D l) S 0A | 1S | D DD | 1A | A 1A | 0B A 0B | B 0S | 1B B 0A | 0 m) S SS | A n) S AB A a | bb A a | cA B bA o) S aBA | p) S Ab | c B bSA A Ba AA c B cS r) 1. S KF 7. Bb bB 2. K KB | CB 8. Ab bA 3. C CA | DA 9. DF E 4. DA aAD 10. BE Eb 5. Aa aA 11. AE Ea 6. DB bBD 12. bE b s) 1. S DC 6. Ba aB 2. D aDA | bDB | aA |bB 7. Ab bA 3. AC aC 8. Bb bB 4. BC bC 9. C 5. Aa aA t) S aAc u) S 0A1 aA aaBbC | ab 0A 0B1 | 0 Bb bb | abbbc | aDbbbcc B1 0C11 | 01 C c C 0D | 00D1 | 0 D ab D 01 Задачи / I. Грамматики и языки. Классификация по Хомскому 95 4. Построить грамматику, порождающую заданный язык L. Каков тип построенной грамма- тики? Каков тип языка? a) L { a n b m | n, m 1}; b) L { c c c | , , {a,b} * (т.е. , , — любые цепочки из a и b) }; c) L { a 1 a 2 ... a n a n ... a 2 a 1 | a i { 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 2 m b m | m 1} для 1 i n }; k) L { a n 3 1 | n 1}; l) L { a n 2 | n 1}; m) L { a n 3 1 | n 1}. 5. К какому типу по Хомскому относится данная грамматика (указать максимально возмож- ный номер)? Какой язык она порождает? Каков тип языка? Выписать подтверждающую от- вет грамматику, в состав которой входит только один нетерминал — цель грамматики. a) S AB | ASB b) S 1A0 A a 1A 11A0 | 01 aB b bB bb 6. Эквивалентны ли грамматики с правилами: а) S AB и S AS | SB | AB A a | Aa A a B b | Bb B b b) S aSL | aL и S aSBc | abc L Kc cB Bc cK Kc bB bb K b Задачи / I. Грамматики и языки. Классификация по Хомскому 96 7. Построить КС-грамматику, эквивалентную грамматике с правилами: а) S aAb b) S AB | ABS aA aaAb AB BA A BA AB A a B b 8. Построить регулярную грамматику, эквивалентную грамматике с правилами: а) S A | AS b) S A.A A a | bb A B | BA B 0 | 1 9. Привести пример грамматики, каждое правило которой относится к одному из трех ви- дов A Bt, либо A t B, либо A t, для которой не существует эквивалентной регулярной грамматики. 10. Доказать, что грамматика с правилами: S aSBC | abC CB BC bB bb bC bc cC cc порождает язык L {a n b n c n | n 1}. Для этого показать, что в данной грамматике: I ) выводится любая цепочка вида a n b n c n (n 1) и II ) не выводятся никакие другие цепочки. 11. Дана грамматика с правилами: a) S S0 | S1 | D0 | D1 b) S if B then S | B E D H. E B | B E H 0 | 1 | H0 | H1 B a | b Построить восходящим и нисходящим методами дерево вывода для цепочки: a) 10.1001 b) if a then b a b b 12. Определить тип грамматики. Описать язык, порождаемый этой грамматикой. Построить для этого языка КС-грамматику. S P P 1P1 | 0P0 | T T 021 | 120R R1 0R R0 1R R 1 Задачи / I. Грамматики и языки. Классификация по Хомскому 97 13. Построить регулярную грамматику, порождающую цепочки в алфавите {a, b}, в которых символ a не встречается два раза подряд. 14. Построить КС-грамматику для языка L, построить дерево вывода и левосторонний вы- вод для цепочки aabbbcccc. L {a 2 n b m c 2 k | m n k, m 1}. 15. Построить грамматику, порождающую сбалансированные относительно круглых скобок цепочки в алфавите { a, ( , ), }. Сбалансированную цепочку определим рекурсивно: це- почка сбалансирована, если a) не содержит скобок, b) ( 1 ) или 1 2 , где 1 и 2 сбалансированы. 16. Построить КС-грамматику, порождающую язык L, и вывод для цепочки aacbbbcaa в этой грамматике. L {a n cb m ca n | n,m 0}. 17. Построить КС-грамматику, порождающую язык L, и вывод для цепочки 110000111 в этой грамматике. L {1 n 0 m 1 p | n p m; n, p, m 0}. 18. Дан язык L {1 3 n 2 0 n | n 0}. Определить его тип, построить грамматику, порождаю- щую L. Построить левосторонний и правосторонний выводы, дерево разбора для цепочки 1111111100. 19. Найти общие алгоритмы построения по данным КС-грамматикам G 1 и G 2 , порождаю- щим языки L 1 и L 2 , КС-грамматики для a) L 1 L 2 ; b) L 1 L 2 ; c) L 1 Замечание L L 1 L 2 — это конкатенация языков L 1 и L 2 , т.е. L { | L 1 , L 2 }; L L 1 — это итера- ция языка L 1 , т.е. объединение { } L 1 L 1 L 1 L 1 L 1 L 1 20. Построить КС-грамматику для L { i 2 i 1 R | i N, i (i) 2 — двоичное представление числа i (без незначащих нулей), R — обращение цепочки }. Построить КС-грамматику для языка L (см. замечание к задаче 19) 21. Показать, что грамматика E E E | E E | (E) | i неоднозначна. Как описать этот же язык с помощью однозначной грамматики? Задачи / I. Грамматики и языки. Классификация по Хомскому 98 22. Показать, что наличие в приведенной КС-грамматике правил вида a) A AA | b) A A A | c) A A | A | , где , , (T N) , A N, делает ее неоднозначной. Можно ли преобразовать эти правила таким образом, чтобы полученная эквивалентная грамматика была однозначной? 23. Показать, что грамматика G неоднозначна. Какой язык она порождает? Является ли этот язык однозначным? G: S aAc | aB B bc A b 24. Дана КС-грамматика G T, N, P, S . Предложить алгоритм построения множества X {A N | A }. 25. Для произвольной КС-грамматики G предложить алгоритм, определяющий, пуст ли язык L(G). 26. Построить приведенную грамматику, эквивалентную данной КС-грамматике. a) S aABS | bCACd b) S aAB | E A bAB | cSA | cCC A dDA | B bAB | cSB B bE | f C cS | c C cAB | dSD | a D eA E fA | g 27. Построить неукорачивающую КС-грамматику, эквивалентную данной, применив алго- ритм устранения правил с пустой правой частью. S aS | Sa | C C CC | bA | A aB | B a A | a 28. Язык называется распознаваемым, если существует алгоритм, который за конечное чис- ло шагов позволяет получить ответ о принадлежности любой цепочки этому языку. Если число шагов зависит от длины цепочки и может быть оценено до выполнения алгоритма, язык называется легко распознаваемым. Доказать, что язык, порождаемый неукорачиваю- щей грамматикой, легко распознаваем. 29. Доказать, что любой конечный язык является регулярным языком. 30. Доказать, что нециклическая КС-грамматика порождает конечный язык. |