И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 18
Текст из файла (страница 18)
Метод рекурсивного спуска. КС-грамматики с действиями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 == 'd')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. Построить КС-грамматику с действиями для порожденияnm 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 и всех вхождений Е должен быть одинаковым;• переменная логического типа недопустима в качестве параметра цикла.Для каждой используемой процедуры привести ее текст на Си++.b)Дан фрагмент грамматикиP → program D; begin S {; S } endD → ... | label L{,L} |...S → L { , L } : S′ | S′S′ → ...| goto L |...L→Iгде I — идентификатор.Вставить в грамматику действия, контролирующие выполнение следующих условий:• каждая метка, используемая в программе, должна быть описана и только один раз;• не должно быть одинаковых меток у различных операторов;• если метка используется в операторе goto, то обязательно должен быть оператор, помеченный такой меткой.Для каждой используемой процедуры привести ее текст на Си++.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},nL2 ={ 0 1 | i ≥0, k > i },) | n ≥ 0, m≥1 };*n mL1 ={ αc | α ∈ {a, b} , n≥1},nn mL2 ={ a c | n≥1, m ≥ 0 },*τ ={ (αc , a c ) | α ∈ {a, b} , n ≥ 1, m = |α|a (т.е.
m — количество символов а вцепочке α )};c)i jL1 = {a, b}+, L2 = { 1 0 | i ≥ 1, j ≥ 0; i≥j },n+m n0 ) | ω ∈ {a,b}+, n = |ω|a, m = |ω|b };τ ={ (ω, 1d)nL1 = {a, b}+, L2 = { 2 α | n ≥ 0, α ∈ {a, b}+ },nτ ={ ( ω, 2 ωR ) | ω ∈ {a,b}+, n = |ω|a (здесь ωR — реверс цепочки ω) };e)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−mm n) | n > m > 0 } ∪ {( 1 0 , ε ) | m = n};L1 = {ωi | i ≥ 0, ωi =(i)2 (т.е. ωi — это двоичное представление числа 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} },n*τ ={ (α ⊥ , b αR⊥) | α ∈ {a, b} , n = |α|a ( n — количество символовцепочке α, αR — реверс цепочки α)};d)L1={ ω⊥ | ω ∈ {a, b}+ },τ ={ (ω⊥ , a[e)f)вi kL2={ a b | i, k ≥ 0, i+k > 0 },n/2] [m/2]) | ω ∈ {a, b}+, n = |ω|a, m = |ω|b };bL1={ ω⊥ | ω ∈ {a, b}+ },τ ={ (ω⊥ , a[а(n+1)/3]b[| 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 ) },niL2 ={ | | n ≥ 0 }, τ ={ (ω⊥ , | ) | ω∈{0,1}+, ω = (i)2 R, i ≥ 0 }.5. Построить грамматику, описывающую целые двоичные числа (количество 0 и 1 четно,допускаются незначащие нули). Вставить в нее действия по переводу этих целых чисел вчетверичную систему счисления.6. Построить грамматику для выражений, содержащих переменные, знаки операций +, −, ∗,/, ∗∗ и скобки ( ) с обычным приоритетом операций и скобок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
