Учебное пособие для студентов II курса (издание третье, переработанное и дополненное) Москва 2009 удк 519. 682. 1
 Скачать 2.2 Mb.
|
|
Замечание Нетерминальный символ A N — циклический, если в грамматике существует вывод A 1 A 2 . КС-грамматика называется циклической, если в ней имеется хотя бы один циклический символ. Задачи / II. Регулярные грамматики, конечные автоматы, разбор по ДС 99 31. Показать, что условие цикличности грамматики (см. задачу 29) не является достаточным условием бесконечности порождаемого ею языка. 32. Доказать, что язык, порождаемый циклической приведенной КС-грамматикой, содер- жащей хотя бы один эффективный циклический символ, бесконечен. Замечание Циклический символ называется эффективным, если A A , где | A | 1; иначе циклический символ называется фиктивным. II. Регулярные грамматики, конечные автоматы, разбор по ДС 1. Дана регулярная грамматика с правилами: S S0 | S1 | P0 | P1 P N. N 0 | 1 | N 0 | N 1 Построить по ней диаграмму состояний (ДС) и использовать ДС для разбора цепочек: 11.010, 0.1, 01., 100. Какой язык порождает эта грамматика? 2. Дана ДС. a) Осуществить разбор цепочек 1011 , 10 011 и 0 101 1 b) Восстановить регулярную грамматику, по которой была построена данная ДС. c) Какой язык порождает полученная грамматика? 3. Пусть имеется переменная cи функция gc(), считывающая в с очередной символ анализи- руемой цепочки. Дана ДС с действиями: a) Определить, что будет выдано на печать при разборе цепочки 1 101/ /p11 1000 /5 0,1 gc( ); 0,1 gc( ); b=2*b+c ’0’;gc( ); b=c ’0’;gc( ); printf(”%d”,b); H S H A S +, 0,1 0,1 0,1 ER B Задачи / II. Регулярные грамматики, конечные автоматы, разбор по ДС 100 b) Написать на Си анализатор по этой ДС. 4. Построить регулярную (автоматную) леволинейную грамматику для заданного языка, по ней построить ДС, а по ДС — написать программу анализатора: a) L { x y | x, y} } ; b) L { (xy 3 ) n | n 1 } ; с) L {(abb) k | k 1} ; d) L { | {0,1} , где за каждой 1 непосредственно следует 0} ; e) L {1 1 | {0,1} , где все подряд идущие 0 — подцепочки нечетной длины}. 5. Дана регулярная грамматика: S A A Ab | Bb | b B Aa Определить язык, который она порождает; построить ДС; написать на Си анализатор. 6. Построить ДС, по которой в заданном тексте, оканчивающемся на , выявляются все пар- ные комбинации , и и подсчитывается их общее количество. 7. Написать на Си анализатор, выделяющий из текста вещественные числа без знака (они определены как в Паскале) и преобразующий их из символьного представления в числовое. 8. Написать на Си анализатор, выделяющий из текста вещественные числа (они опреде- лены как в Си) и преобразующий их из символьного представления в числовое. 9. Даны две грамматики G 1 и G 2 G 1 : S 0C | 1B G 2 : S 0D | 1B B 0B | 1C | B 0C | 1C C 0C | 1C C 0D | 1D | D 0D | 1D Пусть L 1 L(G 1 ), L 2 L(G 2 ). Построить регулярную (автоматную) грамматику для: a) L 1 L 2 b) L 1 L 2 c) L 1 * \{ } d) L 2 * \ { } e) L 1 L 2 Если разбор по ней оказался недетерминированным, построить эквивалентную ей грамма- тику, допускающую детерминированный разбор. Задачи / II. Регулярные грамматики, конечные автоматы, разбор по ДС 101 10. Построить леволинейную регулярную грамматику, эквивалентную данной праволиней- ной, допускающую детерминированный разбор. a) S 0S | 0B b) S 0B B 1B | 1C B 1C | 1S C 1C | C c) S aB B aC | aD | dB C aB D 11. Для данной грамматики a) определить ее тип; b) определить порождаемый ею язык; c) построить эквивалентную автоматную грамматику; d) построить ДС и анализатор на Си S 0S | S0 | D D DD | 1A | A 0B | B 0A | 0 12. Построить ДС, соответствующую заданной леволинейной автоматной грамматике. Если ДС задает НКА, то построить эквивалентный ему ДКА, используя алгоритм. Для получен- ного ДКА построить анализатор. Построить соотвествующую ДКА грамматику. a) S Sa | Ab | b b) S Sb | Aa | a A Ab | Sa | a A Sb | a | b c) S C d) S A C A1 | B1 | 1 A Bb | a A A1 | C0 | 0 B Bb | b B C0 | 0 e) S B0 | C0 f) S Bb | Cc B B0 | 0 B Bb | Ab C C1 | A1 C Cc | Ab A 0 A a g) S S1 | A0 h) S Sa | Cc | a A B1 | C1 C Bb B A0 B Sa | a C C0 | 0 Задачи / II. Регулярные грамматики, конечные автоматы, разбор по ДС 102 i) S C j) S A C A1 | B1 | 1 A Bb | a A A1 | C0 | 0 B Bb | b B C0 | 0 k) S C l) S C B B1 | 0 | D0 C B1 C B1 | C1 B 0 | D0 D D0 | 0 D B1 m) S A0 n) S B0 | 0 A A0 | S1 | 0 B B0 | C1 | 0 | 1 C B0 o) S A0 | A1 | B1 | 0 | 1 p) S S0 | A1 | 0 | 1 A A1 | B1 | 1 A A1 | B0 | 0 | 1 B A0 B A0 r) S Sb | Aa | a | b A Aa | Sb | a 13. Грамматика G определяет язык L L 1 L 2 , причем L 1 L 2 . Построить регулярную (ав- томатную) грамматику G 1 , которая порождает язык L 1 L 2 (см. замечание к задаче 19 раздела I) . Для нее построить ДС и анализатор. S A A A0 | A1 | B1 B B0 | C0 | 0 C C1 | 1 14. Даны две грамматики G 1 и G 2 , порождающие языки L 1 и L 2 G 1 : S S1 | A0 G 2 : S A1 | B0 | E1 A A1 | 0 A S1 B C1 | D1 C 0 D B1 E E0 | 1 Построить регулярные (автоматные) грамматики для языков a) L 1 L 2 ; b) L 1 L 2 ; c) L 1 L 2 (см. замечание к задаче 19 раздела I). Для полученной грамматики построить ДС и анализатор. Задачи / III. Метод рекурсивного спуска. КС-грамматики с действиями 103 15. По данной грамматике G 1 построить регулярную грамматику G 2 для языка L 1 L 1 (см. заме- чание к задаче 19 раздела I ) , где L 1 L(G 1 ); по грамматике G 2 построить ДС и анализатор. G 1 : S S1 | A1 A A0 | 0 16. Построить лексический блок (преобразователь) для кода Морзе. Входом служит последова- тельность "точек", "тире" и "пауз" (например, .. ). Выходом являются соответствую- щие буквы, цифры и знаки пунктуации. Особое внимание обратить на организацию таблицы. III. Метод рекурсивного спуска. КС - грамматики с действиями 1. Определить, примени м ли РС-метод к грамматике. Ответ обосновать. а) S cA | B | d b) S aAbc | A A abA | c | A bB | cBc B bSc | aAb B bcB | a | ε c) S aSB | bAf | d) S aSB | bA A bAc | cS A aS | cA | B cB | d B bB | d e) S bABCb | d f) S aAb | cC A aA | cB | A a { bab } B Sc B cAc | aB | C a {bb} C Bb g) S aA{xx} h) S aSc | bA | A bA | cBx | A cS{da}bA | d B bSc i) S bS | aAB j) S aASb | cfAd A bcA | ccA | A bA | c | B cbB | k) S A | B l) S AS | B A bA | A b | c B cB | b | B dB | a | 2. Пусть имеется анализатор в виде системы рекурсивных процедур, построенных по некото- рой грамматике в соответствии с методом рекурсивного спуска ( S — начальный символ грам- матики). Задачи / III. Метод рекурсивного спуска. КС-грамматики с действиями 104 #include … void gc() {cin >> c;} // считать очередной символ void S() { … } // реализация процедур PC-метода void A() { … } … int main() { try { gc(); S(); if ( c != ' ' ) throw c; cout << "SUCCESS !!!" << endl; return 0; } catch (int c) { cout << "ERROR on lexeme " << c << endl; return 1; } } Восстановить грамматику по функциям, реализующим синтаксический анализ методом рекур- сивного спуска. Удовлетворяет ли полученная грамматика критерию применимости метода рекурсивного спуска? a) void S() { A(); if ( c != 'd') throw c; } void A() { B(); while ( c == 'a') { gc(); B(); } } void B() { if ( c == 'b' ) gc(); } b) void S() { if (c == 'a') { gc(); A(); } else if (c == 'b') { gc(); B(); } else throw c; } void A() { if ( c == ‘c’) { gc( ); S( ); } } void B() { while ( c == ',' ) { gc( ); if (c != ’b’) throw c; gc(); } } Задачи / III. Метод рекурсивного спуска. КС-грамматики с действиями 105 c) void S () { if (c == 'a') { gc(); S(); if (c == 'b') gc(); else throw c;} else A(); } void A () { if (c == 'b') gc(); else throw c; while (c == 'b') gc(); } d) void S () { A(); if ( c != 'd') throw c; } void A () { B(); while ( c == 'a' ) { gc(); B(); } B(); } void B () { if ( c == 'b' ) gc(); } e) void S () { if ( c == 'a' || c ==’b’ ) { A(); S();} else if ( c == 'с') B(); } void A () { if ( c == 'a') gc(); else if ( c == 'b') { gc(); B(); } } void B () { while ( c == 'c' ) { gc(); B(); } } 3. Задана КС-грамматика G T, N, P, S . По ней написать синтаксический анализатор, реа- лизующий РС-метод, предварительно преобразовав заданную грамматику, если это требует- ся для применимости РС-метода и если это возможно. a) S bS | aAB b) S aASb | cfAd A bcA | ccA | A bA | c | B cbB | c) S Sa | Sbb | fAc d) S cAd A aB | d A Aa | bB B abB | Sb B abB | e) S E f) S P : E | if E then S | E ( ) | (E {, E}) | A if E then S else S A a | b P I | I (E) E T { T} T F { F} F P | (E) I a | b Задачи / III. Метод рекурсивного спуска. КС-грамматики с действиями 106 g) F function I(I ) S; I: E end h) S SaAb | Sb | bABa S ; I: E S | A acAb | cA | E E I | E I | I B bB | i) S Ac | dBea j) S fASd | A Aa | Ab | daBc A Aa | Ab | dB | f B cB | B bcB | 4. Какой язык задает данная грамматика с действиями? Провести анализ цепочки (a,(b,a),(a,(b)),b) S k 0 E E A | ( k k 1; if (k 3) ERROR( ); E {,E}) k k 1 A a | b Замечание Функция ERROR( ) сообщает об ошибке и завершает работу программы. 5. Есть грамматика, описывающая цепочки в алфавите {0, 1, 2, }: S A A 0A | 1A | 2A | Дополнить эту грамматику действиями, исключающими из языка все цепочки, содержащие подцепочки 002. 6. Дана грамматика, описывающая цепочки в алфавите {a, b, c, }: S A A aA | bA | cA | Дополнить эту грамматику действиями, исключающими из языка все цепочки, в которых не выполняется хотя бы одно из условий: в цепочку должно входить не менее трех букв с ; если встречаются подряд две буквы а, то непосредственно за ними обязательно долж- на идти буква b. 7. Есть грамматика, описывающая цепочки в алфавите {0, 1}: S 0S | 1S | Дополнить эту грамматику действиями, исключающими из языка любые цепочки, содержа- щие подцепочку 101. 8. Построить КС-грамматику с действиями для порождения L {a m b n c k | m k n либо m k n}. 9. Построить КС-грамматику с действиями для порождения L {1 n 0 m 1 p | n p m, m 0}. |