Задачи - Формальные грамматики и языки. Элементы теории трансляции, страница 2

Выписать соотвествующую ДКАграмматику.a)S → Sa | Ab | bA → Ab | Sa | ab)S → Sb | Aa | aA → Sb | a | bc)S → C⊥d)S → A⊥C → A1 | B1 | 1A → A1 | C0 | 0B → C0 | 0A → 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 | ai)S → C⊥C → A1 | B1 | 1A → A1 | C0 | 0B → C0 | 0k)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 | aj)S → A⊥A → Bb | aB → Bb | b13. Грамматика 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. Построить регулярныеграмматики дляa) L1 ∪ L2b) L1 ∩ L2c) L1 * L2 (см. задачу 19 раздела I.)G1: S → S1 | A0A → A1 | 0G2: S → A1 | B0 | E1A → S1B → C1 | D1C→0D → B1E → E0 | 1Для полученной грамматики построить ДС и анализатор.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 | ε2.

Восстановить грамматику по функциям, реализующим синтаксический анализ методомрекурсивного спуска. Можно ли было по этой грамматике вести анализ методомрекурсивного спуска?a).#include <iostream.h>int c;void A();void B();void gc() {cin >> c;}void S() {A();if ( c != '⊥')throw c;}void A() {B();while ( c == 'a') {gc();B();}}void B() {if ( c == 'b' )gc();}int main() {try { gc();S();cout << "SUCCESS !!!" << endl;return 0;}catch (int c) {cout << "ERROR on lexeme" << c << endl;return 1;}}b).#include <iostream.h>int c;void A();void B();void gc() {cin >> c;}void S() {if (c == ′a′) {gc();A();}elseif (c == ‘b′ ) {gc();B();}elsethrow c;}void A() {if ( c == ‘c′) {gc();S();}}void B() {while ( c == ',' ) {gc();if (c != ′b′)throw c;gc();}}int main() {try { gc();S();cout << "SUCCESS !!!" << endl;return 0;}catch (int c) {cout << "ERROR on lexeme" << c << endl;return 1;}}c)#include <iostream.h>int c;void A();void gc() {cin >> c;}void S (void) {if (c == 'a'){gc();S();if (c == 'b')gc();elsethrow c;}else A();}void A (void) {if (c == 'b')gc();elsethrow c;while (c == 'b')gc();}int main() {try { gc();S();cout << "SUCCESS !!!" << endl;return 0;}catch (int c) {cout << "ERROR on lexeme" << c << endl;return 1;}}d)#include <iostream.h>int c;void A();void B();void gc() {cin >> c;}void S (void) {A();if ( c != '⊥')throw c;}void A (void) {B();while ( c == 'a' ) {gc();B();}B();}void B (void) {if ( c == 'b' )gc();}int main() {try { gc();S();cout << "SUCCESS !!!" << endl;return 0;}catch (int c) {cout << "ERROR on lexeme" << c << endl;return 1;}}3.

Задана КС-грамматика G=(VT, VN, 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|bg)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 | εf)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|b4. Какой язык порождает заданная грамматика? Провести анализ цепочки(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|b5.

Есть грамматика, описывающая цепочки в алфавите {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 = {am bn ck | m+k = n либо m-k = n}.9. Написать КС-грамматику с действиями для порожденияL = {1n 0m 1p | n+p > m, m ≥ 0}.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() >Какой язык описывает эта грамматика ?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, то обязательно должен быть оператор,помеченный такой меткой.Для каждой используемой процедуры привести ее текст на Си.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. Вставить в нее действия по переводу цепочек языкаL1 в соответствующие цепочки языка L2.В качестве действий можно использовать только оператор cout << … .СУ-перевод происходит во время анализа методом рекурсивного спуска.a)L1={ ancmbn, n ≥ 0, m ≥ 1}L2={ 0n1n+m, n ≥ 0, m ≥ 1}b)L1={ αcn, α ∈ (a,b)*, n ≥ 1}L2={ ancm, где m – количество символов а в цепочке α}c)L1 = { ω ∈ {a,b}+, где содержится n символов a и m символов b,расположенных в произвольном порядке; n, m ≥ 0; n+m > 0 }n+m nL2 = { 1 0 | n, m ≥ 0; n+m > 0 }d)L1 = { ω ∈ {a,b}+ , где содержится n символов a,расположенных в произвольном порядке; n ≥ 0}n RRL2 = { 2 ω | n ≥ 0, ω — реверс цепочки ω }e)L1 = {1n 0m 1m 0n | m, n > 0}L2 = {1m 0n+m | m, n > 0}f)L1={ ω⊥ | ω ∈ {a, b}+ , ω=αn, где α=ab | ba, n ≥ 1}L2={ ω⊥ | ω = βn , где β={ b, если α=ab; либо a, если α=ba} }4.

Написать грамматику для языка L1. Вставить в нее действия по переводу цепочек языкаL1 в соответствующие цепочки языка L2.В качестве действий можно использовать любые операторы.СУ-перевод происходит во время анализа методом рекурсивного спуска.a)L1 = { 1m 0n | n,m>0}L2 = { 1m-n | если m>n;0n-m | если m<n;ε | если m=n}b)L1 = {bi | bi =(i)2, т.е. bi -это двоичное представление числа i ∈ N}L2 = {(bi+1)R | bi+1=(i+1)2, ωR - перевернутая цепочка ω}c)L1={ α⊥ | α ∈ {a,b}∗ }L2={ β⊥ | β = bnαR , где n - количество символов b в цепочке α,предшествующих первому вхождению символа a; αR - реверс цепочки α}d)L1={ ω⊥ | ω ∈ {a,b}+ , где содержится n символов a и m символов b,расположенных в произвольном порядке}L2={ ω ∈ {a,b}* | ω = a[n/2] b[m/2] }e)L1={ω⊥ | ω∈{0, 1}+ и представляет (bi)R , т.е. реверс двоичного числа i }L2={ω ∈ {/}* , ω = /i , т.е.