Ответы на задачи I. Порождающие грамматики. Языки, порождаемые грамматиками. Классификация грамматик и языков по Хомскому



Скачать 292.91 Kb.
Дата09.11.2016
Размер292.91 Kb.

Ответы на задачи

I. Порождающие грамматики. Языки, порождаемые грамматиками.
Классификация грамматик и языков по Хомскому

3. r) Тип гр - 0;

Язык L (G) = { an bm an bm | n, m >= 1 }, тип языка - 2.

s) Тип гар. - 0;

Язык L (G) = { xx | x {a,b}+ }, тип языка -1.

t) Тип гр. – 1 (неукор.),

L(G) = {an bn cn | n = 1,2,3,4}. Тип языка 3 (регулярный)

u) Тип гр. - 0,

L(G) ={0n 1n | n = 1,2,3,4,5}. Тип языка 3 (регулярный).
4. Построить грамматику, порождающую язык :

4a).


L = { an bm | n, m >= 1} S ® AB

A ® a | Aa

B ® b| Bb

4b).


L = { ccc | , , - любые цепочки из a и b} S ® AcAcAc

A ® aA | bA | ε

4с).

L = { a1 a2 ... an an ... a2 a1 | ai = 0 или 1, n >= 1}


S ® 0S0 | 1S1 | 00 | 11
4d). S -> 00A1 | 0 или S -> 0A1 | 0 или S -> 00S1 | 001 | 0

A -> 00A1 | 0 | ε A -> 0S | 0

Язык - КС, гр-ка КС
4e). S -> cA

A -> aAc | cB

B -> bB | ε

Язык - КС, гр-ка КС


4f).

L = { an bm | n m ; n, m >= 0} S ® aSb | A | B

A ® a | aA

B ® b | bB

4g).

L = { цепочки из 0 и 1 с неравным числом 0 и 1} S ® ASB | C | D



C ® CA | A

D ® DB | B

AB ® BA

A ® 0


B ® 1

4h).


L = { | {a,b}+} S ® DC

D ® aDA | bDB | aA | bB

AC ® aC

BC ® bC


Aa ® aA

Ba ® aB


Ab ® bA

Bb ® bB


C ® ε

4i).


L = { | {0,1}+ и содержит равное количество 0 и 1, причем любая подцепочка, взятая с левого конца, содержит единиц не меньше, чем нулей}
S ® 1A0

A ® AA | 01A | 1A0 | ε


4j).

L = { (a2m bm)n | m >= 1, n >= 0} S ® SA | ε

A ® aaAb | aab

4k).


L = { | n >= 1} S ® aKa

K ® KN | N

Na ® aaaN

N ®


4l).

L = { | n >= 1} S ® CFD

F ® AFB | AB

AB ® aBA

Aa ® aA

AD ® D


Ca ® aC

CB ® C


CD ® ε

4m).


L = { | n >= 1} S ® CFD

F ® EAFB | EAB

AB ® GBA

AG ® GA


AE ® EA

AD ® D


EG ® aGE

EB ® E


Ea ® aE

ED ® D


Ca ® aC

CG ® C


CD ® a

9.

S ® aA



A ® Sb | b L (G) = { an bn | n >= 1} – КС-язык.
12.

Определить тип грамматики. Описать язык, порождаемый этой грамматикой. Написать для этого языка КС-грамматику.

S ® P Тип грамматики 0.

P ® 1P1 | 0P0 | T

T ® 021 | 120R

R1 ® 0R


R0 ® 1

R ® 1


L = {bi 2 (bi+1)R | bi - двоичное представление числа i N, R – реверс цепочки }

КС-грамматика: S ® P | T1

P ® 1P1 | 0P0 | 0T1

T ® 1T0 | 2


19.

Написать общие алгоритмы построения по данным КС-грамматикам G1 и G2, порождающим языки L1 и L2, КС-грамматики для

19a). L1 L2

S ® S1 | S2

S1 ® ...

.....................

S2 ® ...

.....................

19b). L1 * L2

L = L1 * L2 - это конкатенация языков L1 и L2, т.е.L = { | L1, L2}

S ® S1S2

S1 ® ...

.....................

S2 ® ...

.....................

19c). L1*

L=L1* - это итерация языка L1, т.е. объединение {}L1L1*L1L1*L1*L1 ...

S ® S1S


S1 ® ...

.....................


20.

Написать КС-грамматику для L={i 2 i+1R | i N, i=(i)2 - двоичное представление числа i, R - реверс цепочки }. Написать КС-грамматику для языка L* (см. задачу 19 раздела I).


S ® 1B01 | 1A1 | 021

A ® 1A1 | 0A0 | 0B1 - без незначащих нулей

B ® 2 | 1B0
22.

A ® AA | A ® A |

(док-во для ) – порождаются подцепочки n (n >= 1);

A ® AA | A ® A |

(док-во для ) – порождаются подцепочки ()n (n >= 0);

A ® A | A | A ® A | B;

B ® B | , B VN

(док-во для ) – порождаются подцепочки n m (n, m >= 0);


24.

Дана КС-грамматика G={VT, VN, P, S}. Предложить алгоритм построения множества X = {A VN | A }.

Алгоритм:

1. N0 = , i = 1.

2. Ni = {A | (A ® ) P и (Ni-1 )} Ni-1.

3. Если Ni Ni-1, то i = i + 1 и переходим к шагу 2, иначе X = Ni.


25.

Для произвольной КС-грамматики G предложить алгоритм, определяющий, пуст ли язык L(G).

Алгоритм:

1. N0 = , i = 1.

2. Ni = {A | (A ® ) P и (Ni-1 VT)*} Ni-1.

3. Если Ni Ni-1, то i = i + 1 и переходим к шагу 2,

иначе, если S Ni – ответ «да», иначе «нет».

II. Регулярные грамматики, ДС, анализаторы по ДС.
Преобразовааание НКА к ДКА

4. a) S B b) S A

B Ay | By A By

A Ax | Bx | x B Cy

C Dy

D Ax | x



d) S ® A | B |

A ® B1 | 1

B ® A0 | B0 | 0
e) S ® B1 | C1 F (H, 1) = A S ® B1 | C1 | S1

B ® B1 | C1 | A1 F (A, 0) = C B ® A1

A ® 1 F (A, 1) = B A ® 1

C ® A0 | B0 | D0 F (B, 0) = C C ® A0 | B0 | D0 | S0

D ® C0 F (B, 1) = BS D ® C0

F (C, 0) = D

F (C, 1) = BS

F (D, 0) = C

F (BS, 0) = C

F (BS, 1) = BS//S


10. c).

L = {a {dn,(aa)m }* a | n, m >=0}


S B

B Aa


A Ba | Ad | a
11. Тип грамматики – УКС.

L = {0m (1 02*in )n 0k | in, n, m, k >=0}

НКА: S A | B | D | КА: S A | B | D | E |

A A0 | 0 A A0 | 0

B A1 | C0 | D1 | 1 B A1 | E1 | D1 | 1

C B0 C B0

D C0 | D0 D C0 | E0

E D0
12c). F(H,0)=AB F(AB,0)= F(C,0)=AB F(AC,0)=AB

F(H,1)=C F(AB,1)=AC F(C,1)= F(AC,1)=AC

F(H, )= F(AB,)= F(C, )=S F(AC, )=S


Пусть AB = X, AC = Y, тогда
G: S -> C | Y C ->1 Y -> Y1 | X1 X -> C0 | Y0 | 0
12d). F(H,a)=A F(A,a)= F(B,a)= F(AB,a)=

F(H,b)=B F(A,b)= F(B,b)=AB F(AB,b)=AB

F(H, )= F(A,)=S F(B,)= F(AB, )=S
Пусть AB = X, тогда
G: S -> A | X A ->a X -> Xb | Bb B -> b
12e). F(H,0) = AB AB A S B | D

F(AB,0) = BS BS B B B0 | A0

F(AB,1) = C S D A 0

F(BS,0) = BS Два заключительных D C0

F(C,0) = S состояния BS и S сводим C C1 | A1

F(C,1) = C в одно S' S с исп. .


12f). F(H,a) = A BC B S C | D

F(A,b) = BC BS D C Cc | Bc

F(BC,b) = BS CS C A a

F(BC,c) = CS Два заключительных D Db | Bb

F(BS,b) = BS состояния BS и CS сводим B Ab

F(CS,c) = CS в одно S' S с исп. .


12g). F(H,0) = C F(AS,0) = BS AS R S P | Q|R

F(C,0) = C F(AS,1) = S BS Q P P1 | R1

F(C,1) = A F(S,1) = S S P R Q1

F(A,0) = BS Три заключительных Q A0 | R0

F(BS,1) = AS состояния AS, BS и S сводим A C1

в одно S' S с исп. . C C0 | 0

12h). F(H,a) = BS BS X S X | Y

F(BS,a) = BS S Y X Xa | Ya |a

F(BS,b) = C Y Cc

F(C,c) = S Два заключительных C Xb

F(S,a) = BS состояния BS и S сводим

в одно S' S с исп. .


12i). F(H,0)=AB F(AB,0)= F(C,0)=AB F(AC,0)=AB

F(H,1)=C F(AB,1)=AC F(C,1)= F(AC,1)=AC

F(H, )= F(AB,)= F(C, )=S F(AC, )=S
Пусть AB = X, AC = Y, тогда

G: S -> C | Y

C ->1

Y -> Y1 | X1



X -> C0 | Y0 | 0
12j). F(H,a)=A Пусть AB = X, тогда G: S -> A | X

F(H,b)=B A ->a

F(A,)=S X -> Xb | Bb

F(B,b)=AB B -> b

F(AB,b)=AB

F(AB, )=S

13. L = {1n 0m 1 {0, 1}k | n, k >=0, m >= 1}

L1 = {0m 1 {0, 1}k | k >=0, m >= 1}

L2 = {1n 0m 1 {0, 1}k | k >=0, n, m >= 1}

L1 L2 = {0m 1 {0, 1}k 1n 0i 1 {0, 1}j | j, k >=0, n, m, i >= 1}

G(L1 L2): S E

E E0 | E1 | D1

D D0 | C0

C C1 | B1

B B0 | B1 | A1

A A0 | 0


15. L1 = { 0m 1n | n, m >= 1}

L1*L1 = { 0m 1n 0m1 1n1 | n, m, n1, m1 >= 1} S ® S1 | C1

C ® B0 | C0

B ® B1 | A1

A ® A0 | 0


III. Метод рекурсивного спуска (РС-метод), применимость РС-метода.
КС-грамматики с действиями

1c). S aSB | bAf |

A bAc | cS

B cB | d


FIRST(S) = {a, b}, FOLLOW(S) = {c, d, f } O.K.!
1d). S aSB | bA

A aS | cA | ε

B bB | d
FIRST(A) = {a, c}, FOLLOW(A) = {b, d } O.K.!
1e). S bABCb | d

A aA | cB |

B Sc

C a {bb} C aN N bbN |


FIRST(A)={a, c}, FOLLOW(A)={b, d}; =

FIRST(N)={b}, FOLLOW(N)= {b}; ={b}

РС-метод неприменим
1f). S aAb | cC

A a { bab } A aN N babN |

B cAc | aB |

C Bb
FIRST(B) = {a, c}, FOLLOW(B) = {b}; =

FIRST(N) = {b}, FOLLOW(N) = {b, c}; = {b}

РС-метод неприменим


1g). S aA{xx} S aAN

A bA | cBx | A bA | cBx |

B bSc B bSc

N xxN |


FIRST(N) = {x}, FOLLOW(N) = {c} ; =

FIRST(A) = {b, c}, FOLLOW(A) = {x, c} }; = {b}

РС-метод неприменим
1h). S aSc | bA | S aSc | bA |

A cS {da} bA | d A cSNbA | d

N daN |

Для приведенной грамматики, содержащей только правила вывода из S, РС-метод применим (!), но если (что неверно) рассматривать вторую строчку, то окажется, что

FIRST(N) = {d}, FOLLOW(N) = {b} ; =

FIRST(S) = {a, b}, FOLLOW(S) = {c, d, b}}; = {b}

РС-метод неприменим
1i). S bS | aAB

A bcA | ccA |

B cbB |

FIRST(A)={b,c}, FOLLOW(A)={c}; = {c} => РС-метод неприменим

FIRST(B)={c}, FOLLOW(B)=
1j). S aASb | cfAd

A bA | c |

FIRST(A)={b,c}, FOLLOW(A)={a,c,d}; = {c} => PC-метод неприменим
2a). S A 2b). S aA | bB

A B{aB} A cS | ε

B b | ε B {,b}

2c).


S aSb | A Метод рекурсивного спуска к данной

A b {b} грамматике неприменим.

2d)

S A Метод рекурсивного спуска к данной



A B {aB} B грамматике неприменим.

B b |
3a). S bS | aAB

A bcA | ccA |

B cbB |

FIRST(A)={b,c}, FOLLOW(A)={c}; = {c}

FIRST(B)={c}, FOLLOW(B)=

S bS | aA'

A' bcA' | ccA' | B bcA' | ccA' | cbB |

A bcA' | ccA' | - недостижимые правила, их можно убрать

B cbB |


S bS | aA'

A' bcA' | cA'' | O.K.!

A'' cA' | bB

B cbB |


3b). S aASb | cfAd

A bA | c |

FIRST(A)={b,c}, FOLLOW(A)={a,c,d}; = {c}

S aA' | cfAd

A' bA' | cSb | Sb bA' | cSb | a A'b | cfAdb

A bA | c |


S aA' | cfAd

A' bA' | a A'b | cA''

A'' Sb | fAdb aA'b | cfAdb | fAdb - O.K.!

A bA | c |


3c). S Sa | Sbb | fAc S fAcS' S fAcS'

A aB | d (левая рекурсия) S' aS' | bbS' | S' aS' | bbS' |

B abB | Sb => A aB | d => A aB | d

B abB | Sb B abB | fAcS'b

FIRST(S')={a,b}, FOLLOW(S')={b}; = {b}

S fAcS' S fAcS'

S' aS' | bbS' | S' aS' | bbS' |

A aB | d A aB | d

B abB | fAcS'' B abB | fAcS''

S'' aS'' | bbS'' | b S'' aS'' | bS '''

S ''' bS'' |

FIRST (S''')={b}, FOLLOW(S''')={c}; = O.K.!

3d). S cAd S cAd

A Aa | bB (левая рекурсия) A bBA'

B abB | => A' aA'|

B abB |

FIRST(B)={a}, FOLLOW(B)={a,d}; = {a}

FIRST(A')={a}, FOLLOW(A')={d}; =

S cAd S cAd S cAd S cAd

A bB' A bB' A bB' A bB'

A' aA'| A' aA'| A' aA'| A' aA'|

B' abB' | A' B' abB' | aA'| B' aB'' | B' aB'' |

B'' bB' | A' B''bB'|aA'|

FIRST(B')={a}, FOLLOW(B')={d}; =

FIRST(B'')={a,b}, FOLLOW (B'')={d}; = - O.K.!
3e).

S ® E S ® E S ® E

E ® () | (E {, E}) | A E ® () | (E {, E}) | a | b E ® (E’ | a | b

A ® a | b E’ ® ) | E {, E})

... дальше можно не преобразовывать, т.к. для E’ конфликта нет (E не начинается ‘)’).
3f).

1) S ® P := E | if E then S | if E then S else S ® aP’:=E | bP’:=E | if E then S S’

2) P ® I | I (E) P ® IP’ ® aP’ | bP’; P’ ® (E) | ε

3) E ® T {+T}

4) T ® F {*F}

5) F ® P | (E) ® aP’ | bP’ | (E)

6) I ® a | b
1) S ® aP’:=E | bP’:=E | if E then S S’

2) S’ ® else S | ε FIRST(S’)={else}; FOLLOW(S’)={else};-!!!

3) P ® aP’ | bP’

4) P’ ® (E) | ε FIRST(P’)={(}; FOLLOW(P’)={*,+,:=,then,)};-O.K.!

5) E ® T {+T} – O.K.!

6) T ® F {*F} – O.K.!

7) F ® aP’ | bP’ | (E)
Замечание: Вообще говоря, исходная грамматика неоднозначна и метод РС неприменим. Ее можно преобразовать. Но если формально писать анализатор РС-методом по этой грамматике, неоднозначность устранится сама по себе правильным образом (так устроены процедуры РС-метода), т.е. else будет относиться к ближайшему if.
3g).

F ® function I(I) S; I:=E end F ® function I(I) S; I:=E end

S ® ; I:=E S | S ® ; I:=E S |

E ® E*I | E+I | I E ® IE’

E’ ® *IE’ | +IE’ |

FIRST(S) = {;}, FOLLOW(S) = {;}; = {;}

FIRST(E') = {+ , *}, FOLLOW(E') = {; , end}; =

F ® function I(I) S’ F ® function I(I) S’

S’ ® ; I := ES’ | ; I := E end S’ ® ; I := ES”

S ® ; I:=E S | - недостижимые правила. S” ® S’ | end ; I := ES” | end

E ® IE’ E ® IE’

E’ ® *IE’ | +IE’ | E’ ® *IE’ | +IE’ | O.K.!


3h)

S ® SaAb | Sb | bABa S ® bABaS’

A ® acAb | cA | S’ ® aAbS’ | bS’ |

B ® bB | A ® acAb | cA |

B ® bB |

FIRST(S’) = {a, b}, FOLLOW(S’) =

FIRST(A) = {a, c}, FOLLOW(A) = {a, b}; = {a}

FIRST(B) = {b}, FOLLOW(B) = {a}; =

S ® bA’

A’ ® acAbBaS’ | cA’ | BaS’ ® acAbBaS’ | cA’ | bBaS’ |aS’

S’ ® aAbS’ | bS’ |

A ® acAb | cA |

B ® bB |

S ® bA’


A’ ® aA” | cA’ | bBaS’

A” ® cAbBaS’ | S’ ® cAbBaS’ | aAbS’ | bS’ |

S’ ® aAbS’ | bS’ |

A ® acAb | cA |

B ® bB |

FIRST(A”) = {a, b, c}, FOLLOW(A') = O.K.!


3i)

S Ac | dBea S Ac | dBea ® daBcA’c | dBea

A Aa | Ab | daBc A daBcA’ - недостижимые правила.

B cB | A’ aA’ | bA’ |

B cB |

S dS’


S’ aBcA’c | Bea ® aBcA’c | cBea | ea

A’ aA’ | bA’ |

B cB |

FIRST(A') = {a, b}, FOLLOW(A') = {c}; =

FIRST(B) = {c}, FOLLOW(B) = {c, e}; = {c}

S dS’


S’ aB’ | cBea | ea

B’ cB’ | cA’c B’ cB” ; B” B’ | A’c cB” | aA’c | bA’c | c

A’ aA’ | bA’ |

B cB |

S dS’

S’ aB’ | cBea | ea



B’ cB”

B” cB’” | aA’c | bA’c

B’” B” | cB’” | aA’c | bA’c |

A’ aA’ | bA’ |

B cB |

FIRST(B’”) = {a, b, c}, FOLLOW(B”) = O.K.!


3j).

S fASd | S fASd |

A Aa | Ab | dB | f A dBA' | fA'

B bcB | A' aA' | bA' |

B bcB |

FIRST(S) = {f}, FOLLOW(S) = {d}; =

FIRST(A') = {a, b}, FOLLOW(A') = {f, d}; =

FIRST(B) = {b}, FOLLOW(B) = {a, b, f, d}; = {b}

S fASd | S fASd |

A dB' | fA' A dB' | fA'

B' bcB' | A' bcB' | aA' | bA' | B' bС | aA' |

A' aA' | bA' | С cB' | A' cB' | aA' | bA' |

B bcB | - недостижимые правила. A' aA' | bA' |

S - не менялось,

FIRST(B') = {a, b}, FOLLOW(B') = {f, d}; =

FIRST(A') = {a, b}, FOLLOW(A') = {f, d}; = O.K.!

FIRST(C) = {a, b, c}, FOLLOW(C) = {f, d}; =
4.

Вложенные списки, где уровень вложенности скобок не более 2.


5.

S A

A 0 A | 1 A | 2 = 2) throw “ER!”; else k = 0;> A |
6.

S A

A a = 3) throw “ER!”;> A |

b A |

c A |
7.

S’ S

S 0 S |

1 S |


8.

S aA S a A

A aA | bB A a A | b B

B bB | cC B b B | c C

C cC | C c C |


9.

S’ S S’ a S < if (n <= m) throw “ER!”;>

S 1S | 0A | S 1 S | 0 A |

A 0A | 1B | A 0 A | 1 B

B 1B | B 1 B |

IV. Синтаксически управляемый перевод

1. E ® T {[ +, - ] T <cout << [ '+', '-' ] ; >}

T ® F {[ *, / ] F <cout << [ '*', '/' ] ; >}

F ® a <cout << 'a';> | b<cout << 'b';> | (E)

2a). L1 = { a | {a,b}* , где содержится n символов a и m символов b, расположенных в произвольном порядке}

L2 = { {a,b}* | = a[n/2] b[m/2] }


2b). L1={ | {a,b} }

L2={ | = bnR , где n - количество символов b в цепочке , предшествующих первому вхождению символа a; R - реверс цепочки }


3c). S ® a < cout <<’1’;> А < cout << ’0’;>| b < cout <<’1’;> А

А ® a < cout <<’1’;> А < cout << ’0’;>| b < cout <<’1’;> А |


3d). S ® a < cout <<’2’;> А < cout << ’a’;> | bА < cout << ’b’;>

А ® a < cout <<’2’;> А < cout << ’a’;> | bА < cout << ’b’;> |


3e). S ® 1A0 < cout << ‘0’; >

A ® 1A0 < cout << ‘0’; > | 0 < cout << ‘1’; > B1 < cout << ‘0’; >

B ® 0 < cout << ‘1’; > B1 < cout << ‘0’; >|
4a). S ® 1< m = 1; n = 0; > A < while (m > n) {cout << ‘1’; m--;}

while (n > m) {cout << ‘0’; n--;} >

A ® 1 < m++; > A | 0 < n++; > B

B ® 0 < n++; > B |


4b). S ® 0 < k = 1; > A < if (k) cout << '1'; else cout << '0'; > |

1 < k = 1; > A < if (k) cout << “01”; else cout << '1'; >

A ® 0A < if (k) {cout << '1'; k = 0;} else cout << '0'; > |

1A < if (k) cout << ‘0’; else cout << '1'; > |


4d). S ® a < n = 1; m = 0; >A | b < n = 0; m = 1; >A

A ® a < if (n) {cout << 'a'; n = o;} else n = 1;} > A |

b A < if (m) {cout << 'b'; m = o;} else m = 1;} > |

V. ПОЛИЗ, перевод в ПОЛИЗ

4a). S, 0, =, i, 1, =, i, 10, <, 24, !F, S, S, i, i, +, *, i, i, 1, +, 7, !,


4b). x, 1, +, 2, y, *, >, 15, !F, x, y, =, 22, !, y, x, y, +, 2, *, =,
4c). i,1,=,S,0,=,i,10,<,S,40,<,&&,26,!F,S,S,i,f,+,=,i,++,7,!

либо


i,1,=,S,0,=,i,10,<,S,40,<,&&,29,!F,S,S,i,f,+,=,i,i,1,+,=,7,!
4d). z, x, y, *, 5, +, <, 26, !F, a, x, y, <, =, z, x, 6, +, a, y, -, /, =, 31, ! z, y, 2, <<,=
4e) a, x, y, +, z, t, x, +, *, <, 25, !F, a, b, +, @, c, d, -, /, 2, *, 30, !, x, ++, 5, +, =,

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

@ - унарный минус
4f) S, x, y, +, =, i,1,=, j , 0, = , j, n, <, 39, !F, 23, !, j , ++,12, !, S, S, i, j, * , 5, *, +, =

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31


i, i, x, *, =, 19, !

32 33 34 35 36 37 38


4g). i,1,=,S,0,=,i,10,<,S,40,<,&&,26,!F,S,S,i,f,+,=,i,++,7,!

либо


i,1,=,S,0,=,i,10,<,S,40,<,&&,29,!F,S,S,i,f,+,=,i,i,1,+,=,7,!
4h). z, x, y, *, 5, +, <, 26, !F, a, x, y, <, =, z, x, 6, +, a, y, -, /, =, 31, ! z, y, 2, <<,=
5a). x = y = z = a*(x+5/y)-(z+6)*8
5b). x = a*(x+z/y)+z*(6-a)


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница