formal_languages_translation_theory (852748), страница 18

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

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

Дана регулярная грамматика с правилами:S  S0 | S1 | P0 | P1P  N.N  0 | 1 | N0 | N1Построить по ней диаграмму состояний (ДС) и использовать ДС для разбора цепочек:11.010, 0.1, 01., 100. Какой язык порождает эта грамматика?2. Дана ДС.a) Осуществить разбор цепочек 1011, 10  011 и 0 1011.b) Восстановить регулярную грамматику, по которой была построена данная ДС.c) Какой язык порождает полученная грамматика?0,10,1HAS0,1+,ERB3. Пусть имеется переменная c и функция gc(), считывающая в с очередной символ анализируемой цепочки.

Дана ДС с действиями:printf(”%d”,b);gc( );HS0,1b=c’0’;gc( );gc( );a)0,1b=2*b+c’0’;gc( );Определить, что будет выдано1101/ /p111000 /5  .напечатьприразборецепочки99Задачи / II. Регулярные грамматики, конечные автоматы, разбор по ДСb)Написать на Си  анализатор по этой ДС.4. Построить регулярную (автоматную) леволинейную грамматику для заданного языка, поней построить ДС, а по ДС — написать программу анализатора:a) L  { xy  | x, y}} ;nb) L  { (xy 3)  | n  1 } ;kс) L  {(abb) | k  1} ;d) L  { |   {0,1}, где за каждой 1 непосредственно следует 0} ;e) L  {11 |   {0,1} , где все подряд идущие 0 — подцепочки нечетной длины}.5.

Дана регулярная грамматика:S  AA  Ab | Bb | bB  AaОпределить язык, который она порождает; построить ДС; написать на Си анализатор.6. Построить ДС, по которой в заданном тексте, оканчивающемся на , выявляются все парные комбинации  ,  и  и подсчитывается их общее количество.7. Написать на Си анализатор, выделяющий из текста вещественные числа без знака (ониопределены как в Паскале) и преобразующий их из символьного представления в числовое.8.

Написать на Си анализатор, выделяющий из текста вещественные числа (они определены как в Си) и преобразующий их из символьного представления в числовое.9. Даны две грамматики G1 и G2.G1: S  0C | 1BB  0B | 1C | C  0C | 1CПустьдля:L1  L(G1),G2: S  0D | 1BB  0C | 1CC  0D | 1D | D  0D | 1DL2  L(G2). Построить регулярную (автоматную) грамматикуa) L1L2b) L1L2*c) L1 \{}*d) L2 \ {}e) L1L2Если разбор по ней оказался недетерминированным, построить эквивалентную ей грамматику, допускающую детерминированный разбор.100Задачи / II. Регулярные грамматики, конечные автоматы, разбор по ДС10. Построить леволинейную регулярную грамматику, эквивалентную данной праволинейной, допускающую детерминированный разбор.a) S  0S | 0BB  1B | 1CC  1C | b) S  0BB  1C | 1SCc) S  aBB  aC | aD | dBC  aBD11.

Для данной грамматикиa) определить ее тип;b) определить порождаемый ею язык;c) построить эквивалентную автоматную грамматику;d) построить ДС и анализатор на Си.S  0S | S0 | DD  DD | 1A | A  0B | B  0A | 012. Построить ДС, соответствующую заданной леволинейной автоматной грамматике. ЕслиДС задает НКА, то построить эквивалентный ему ДКА, используя алгоритм. Для полученного ДКА построить анализатор.

Построить соотвествующую ДКА грамматику.a)S  Sa | Ab | bA  Ab | Sa | ab)S  Sb | Aa | aA  Sb | a | bc)S  CC  A1 | B1 | 1A  A1 | C0 | 0B  C0 | 0d)S  AA  Bb | aB  Bb | be)S  B0 | C0B  B0 | 0C  C1 | A1A0f)S  Bb | CcB  Bb | AbC  Cc | AbAag)S  S1 | A0A  B1 | C1B  A0C  C0 | 0h)S  Sa | Cc | aC  BbB  Sa | a101Задачи / II.

Регулярные грамматики, конечные автоматы, разбор по ДСi)S  CC  A1 | B1 | 1A  A1 | C0 | 0B  C0 | 0j)S  AA  Bb | aB  Bb | bk)S  CB  B1 | 0 | D0C  B1 | C1D  D0 | 0l)S  CC  B1B  0 | D0D  B1m)S  A0A  A0 | S1 | 0n)S  B0 | 0B  B0 | C1 | 0 | 1C  B0o)S  A0 | A1 | B1 | 0 | 1A  A1 | B1 | 1B A0p)S  S0 | A1 | 0 | 1A  A1 | B0 | 0 | 1B  A0r)S  Sb | Aa | a | bA  Aa | Sb | a13. Грамматика G определяет язык L L1L2, причем L1 L2 .

Построить регулярную (автоматную) грамматику G1, которая порождает язык L1L2 (см. замечание к задаче 19 раздела I). Длянее построить ДС и анализатор.S  AA  A0 | A1 | B1B  B0 | C0 | 0C  C1 | 114. Даны две грамматики G1 и G2, порождающие языки L1 и L2.G1: S  S1 | A0A  A1 | 0G2: S  A1 | B0 | E1A  S1B  C1 | D1C0D  B1E  E0 | 1Построить регулярные (автоматные) грамматики для языковa) L1  L2 ;b) L1  L2 ;c) L1  L2(см.

замечание к задаче 19 раздела I).Для полученной грамматики построить ДС и анализатор.102Задачи / III. Метод рекурсивного спуска. КС-грамматики с действиями15. По данной грамматике G1 построить регулярную грамматику G2 для языка L1L1 (см. замечание к задаче 19 раздела I ), где L1  L(G1); по грамматике G2 построить ДС и анализатор.G1:S  S1 | A1A  A0 | 016. Построить лексический блок (преобразователь) для кода Морзе. Входом служит последовательность "точек", "тире" и "пауз" (например, ... . ... ).

Выходом являются соответствующие буквы, цифры и знаки пунктуации. Особое внимание обратить на организацию таблицы.III. Метод рекурсивного спуска. КС-грамматики с действиями1. Определить, применим ли РС-метод к грамматике. Ответ обосновать.а)S  cA | B | dA  abA | c | B  bSc | aAbb)S  aAbc | AA  bB | cBcB  bcB | a | εc)S  aSB | bAf | A  bAc | cSB  cB | dd)S  aSB | bAA  aS | cA | B  bB | de)S  bABCb | dA  aA | cB | B  ScC  a {bb}f)S  aAb | cCA  a { bab }B  cAc | aB | C  Bbg)S  aA{xx}A  bA | cBx | B  bSch)S  aSc | bA | A  cS{da}bA | di)S  bS | aABA  bcA | ccA | B  cbB | j)S  aASb | cfAdA  bA | c | k)SA|BA  bA | B  cB | b | l)S  AS | BAb|cB  dB | a | 2. Пусть имеется анализатор в виде системы рекурсивных процедур, построенных по некоторой грамматике в соответствии с методом рекурсивного спуска ( S — начальный символ грамматики).103Задачи / III.

Метод рекурсивного спуска. КС-грамматики с действиями#include <iostream>using namespace std;int c; // текущий символvoid S();// объявления процедур, соответствующих нетерминалам грамматикиvoid A();…void gc() {cin >> c;} // считать очередной символvoid S() {void A() {…… }… }// реализация процедур PC-метода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(); }}104Задачи / III. Метод рекурсивного спуска. КС-грамматики с действиямиc)void S () { if (c == 'a') { gc(); S(); if (c == 'b') gc();else throw c;}else A();}void A () { if(c == 'b') gc(); elsewhile (c == 'b') gc();}throw c;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 | aABA  bcA | ccA | B  cbB | b)S  aASb | cfAdA  bA | c | c)S  Sa | Sbb | fAcA  aB | dB  abB | Sbd)S  cAdA  Aa | bBB  abB | e)S  EE  ( ) | (E {, E}) | AAa|bf)S  P : E | if E then S |if E then S else SP  I | I (E)E  T {T}T  F {F}F  P | (E)Ia|b105Задачи / III.

Метод рекурсивного спуска. КС-грамматики с действиямиg)F  function I(I ) S; I:E endS  ; I:E S | E  EI | EI | Ih)S  SaAb | Sb | bABaA  acAb | cA | B  bB | i)S  Ac | dBeaA  Aa | Ab | daBcB  cB | j)S  fASd | A  Aa | Ab | dB | fB  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. Построить КС-грамматику с действиями для порожденияm n kL  {a b c | m  k  n либо m  k  n}.9. Построить КС-грамматику с действиями для порожденияn m pL  {1 0 1 | np  m, m  0}.106Задачи / III. Метод рекурсивного спуска.

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

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