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

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

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

. ... ). Выходом являются соответствующие буквы, цифры и знаки пунктуации. Особое внимание обратить на организацию таблицы.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.

Метод рекурсивного спуска. КС-грамматики с действиями10. Дана грамматика с семантическими действиями:S   A  0; B  0  L {L}  if (A  5) ERROR( )  L  a  A  A1  | b  B  B1; if (B  2) ERROR( )  |c  if (B  1) ERROR( ) Какой язык описывает эта грамматика? (см. замечание к задаче 4)11. Дана грамматика:S  EE  ( ) | (E {, E}) | AAa|bВставить в заданную грамматику действия, контролирующие соблюдение следующих условий:уровень вложенности скобок не больше четырех;на каждом уровне вложенности происходит чередование скобочных и бесскобочныхэлементов.12.

Включить в правила вывода действия, проверяющие выполнение следующих контекстных условий:a) Пусть в языке L есть переменные и константы целого, вещественного и логического типов, а также есть оператор циклаS  for I  E step E to E do SВключить в это правило вывода действия, проверяющие выполнение следующих ограничений: тип I и всех вхождений Е должен быть одинаковым; переменная логического типа недопустима в качестве параметра цикла.Для каждой используемой процедуры привести ее текст на Си.Дан фрагмент грамматикиP  program D; begin S {; S } endD  ...

| label L{,L} |...S  L { , L } : S′ | S′S′  ...| goto L |...LIгде I — идентификатор.Вставить в грамматику действия, контролирующие выполнение следующих условий: каждая метка, используемая в программе, должна быть описана и только один раз; не должно быть одинаковых меток у различных операторов; если метка используется в операторе goto, то обязательно должен быть оператор, помеченный такой меткой.Для каждой используемой процедуры привести ее текст на Си.b)107Задачи / IV. Синтаксически управляемый переводIV. Синтаксически управляемый перевод1. Построить грамматику арифметического выражения, использующего операции , , ,  икруглые скобки (приоритет операций стандартный), простые аргументы операций — переменные a и b, например: a(ba) bab.

Предполагая, что анализ грамматики будет производиться РС-методом, вставить в нее действия вида cout << ′символ′ по переводу такихвыражений в ПОЛИЗ.2. Дана грамматика языка L1, в которую вставлены действия по переводу цепочек языка L1 вцепочки языка L2. Определить языки L1 и L2.a)S  a  a  1; b  0;  A A  a  if ( a ) { cout << ′a′; a  0; } else a;  A |bA  if ( b ) { cout << ′b′; b  0; } else b;  | εb)S   a  0;  E  cout << ′′ ; E  a  a  1; E  cout << ′a′ ;  |b  if (a  0) cout << ′b′; E  cout << ′b′ ;  | ε3.

Построить грамматику для языка L1. Вставить в нее действия по генерации цепочек языкаL2 в процессе анализа методом рекурсивного спуска. Соответствие между цепочками задается формальным переводом . В качестве действий можно использовать только операторы вида cout << ′символ′.a)n m nn nmn m n { ( a c b , 0 1b)i kL1 { a c b | n0, m1},L2 { 0 1 | i 0, k  i },) | n  0, m1 };L1 { c |  ∈ {a, b} , n1},n*n mL2 { a c | n1, m  0 }, { (c , a c ) |  ∈ {a, b} , n  1, m a (т.е.

m — количество символов а вцепочке  )};nc)n mL1  {a, b},*i jL2  { 1 0 | i  1, j  0; ij },nm n0 ) |  ∈ {a,b}, n a, m b }; { (, 1d)L1  {a, b}, L2  { 2  | n  0,  ∈ {a, b} },n { ( , 2 R ) |  ∈ {a,b}, n a (здесь R — реверс цепочки ) };ne)n m m ni kL1  {1 0 1 0 | m, n  0}, L2  {1 0 | k  i  0},n m m nm nm { ( 1 0 1 0 , 1 0f)) | m, n 0 };L1  { 1  2 …n  | n 1, i  {ab, ba} для 1  i  n },L2  { | ∈ {a, b} }, { (  1 2 … n ,  1  2 … n  ) | n 1; для 1  i  nесли i  ab,  i  a, если i ba };108i  {ab, ba},  i  b,Задачи / V. ПОЛИЗ, перевод в ПОЛИЗ4.

Построить грамматику для языка L1. Вставить в нее действия по генерации цепочек языкаL2 в процессе анализа методом рекурсивного спуска. Соответствие между цепочками задается формальным переводом . В качестве действий можно использовать любые операторы.m nkia)L1  { 1 0 | n, m 0}, L2  { 1 | k 0}  { 0 | i 0}  {},m nmn { ( 1 0 , 1b)m n) | m  n 0 } { ( 1 0 , 0nmL1  {i | i  0, i (i)2(т.е.

i —незначащих ведущих нулей) },m n) | n  m  0 }  {( 1 0 ,  ) | m  n};это двоичное представление числа i   безL2  {(i)R | i 1, i(i)2 (R — обращение цепочки ) },  { ( i, (i1)R ) | i  0, i (i)2, i1(i1)2 } ;c)L1  {  |   {a, b} },nL2{ b  | n  0,   {a, b} }, { ( , b R) |  ∈ {a, b} , n a ( n — количество символовцепочке , R — реверс цепочки )};nd)*L1{  |   {a, b} }, { ( , a[n/2]b[m/2]i k) |  ∈ {a, b}, n a, m b ( здесь [x] — ближайшее к x це-L1{  |   {a, b} }, { ( , a[f)(n+1)/3]b[вL2{ a b | i, k  0, ik  0 },лое, например: [1/2] = 1, [1/3] = 0, [5/3] = 2)e)а|m-n |/2]};i kL2{ a b | i, k  0, ik  0 },) |  ∈ {a, b}, n a, m b };L1 { | {0,1},   (i)2 R, i  0 (т.

е.  — реверс двоичной записи числа i ) },nL2 { | | n  0 }, { ( , | ) | {0,1},   (i)2 R, i  0 }.i5. Построить грамматику, описывающую целые двоичные числа (количество 0 и 1 четно,допускаются незначащие нули). Вставить в нее действия по переводу этих целых чисел вчетверичную систему счисления.6.

Построить грамматику для выражений, содержащих переменные, знаки операций , , ,,  и скобки ( ) с обычным приоритетом операций и скобок. Включить в эту грамматикудействия по переводу выражений в префиксную запись (операции предшествуют операндам). Предложить интерпретатор префиксной записи выражений.7. В грамматику, описывающую выражения, включить действия по переводу выражений изинфиксной формы (операция между операндами) в функциональную запись.Например,аb (a, b),abc(a, (b, c)).V.

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

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