Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://al.cs.msu.ru/files/formal.languages.translation.theory.pdf Äàòà èçìåíåíèÿ: Thu Jun 12 10:57:51 2014 Äàòà èíäåêñèðîâàíèÿ: Sat Apr 9 22:37:08 2016 Êîäèðîâêà:

. . .


.. , .. , ..

.
II

( , )

2009


519.682.1 22.1973 67 - . . .

: ., ..-.. . . , ..-.. ..

. . , . . , . . . : II ( , ). -- .: . .. ( 05899 24.09.2001), 2009 -- 115 . ISBN 978-5-89407-395-8 ISBN 978-5-317-03085-8 , , , . . , . « » , . 519.682.1 22.1973

ISBN 978-5-89407-395-8 ISBN 978-5-317-03085-8 © . . . , 2009 © . . , . . , . . , 2009


/



, . , -- , ( ). - . . , , ­ , .


: -- . , «» . : V . : , , . . , V ; . : -- , ( ), ( ) . : . , ab cd, abcd. : . , , () () ( ). : ( ) , . R. , abcdef, R fedcba. : R . : n- ( ) n n : ... . n : 0 ;
n n-1 n



n-1

3


/

: -- ( ). , abbcaad, 7. | |. 0. : | |s s . , | babb |a 1, | babb |b 3, | babb |c 0. : V , V, . , V {0, 1}, V {, 0, 1, 00, 11, 01, 10, 000, 001, 011, ... }. : V , V, . , V V {}. : V -- * . L L V . [3]. . , , . : (). (), , , , . , «», . . ; -- «» . , -- , . : (). , , . 1) : (), . (). , , 2 ). .
* * *

1)

2)

« » , , , (). , , . : - ( ) , , . , ; (). «» , . ,

4


/ () (-). , -

; (, ), LIFO. - . (). - . . -- , . , . , . , . , , . V * V . , . , , , . : A B A B { (a, b) | a A, b B }. : G -- T, N, P, S , T -- ( );
N -- (), T N ; P -- ( T N) (T N) ; (, )

*

P ; , -- ; P ; S -- () , S N.
1



2

...



n

1 | 2 |...| n. i (i 1, 2, ..., n) . : Ge
xample

{0, 1}, {A, S}, P, S ,

P :

. , .

5


/

S 0A1 0A 00A1 A : ( T N ) ( T N ) G T, N, P, S ( G ), 12, 12, 1, 2, (T N ) , (T N ) P. G G , , . , 00A11 0A1 Gexample : 0A1 00A11. 0A, , , 00A1 , 1 , 2 1. : (T N ) (T N) G T, N, P, S ( G ), 0, 1, ..., n (n 0), , 0 1 ... n . 0, 1, ..., n n. G G , , . , S 000A111 Gexample (. ), .. S 0A1 00A11 000A111. 3. : , G T, N, P, S , L(G) { T * | S }. , L(G) -- T, S nn P. , L(Gexample) {0 1 | n 0}. : (T N)*, S , G T, N, P, S . , , , . : G1 G2 , L(G1) L(G2). . G1 {0,1}, {A,S}, P1, S G2 {0,1}, {S}, P2, S P1: P2: S 0A1 S 0S1 | 01 0A 00A1 A , . . L(G1) L(G2) {0 1 | n 0}. : G1 G2 , L(G1) {} L(G2) {}. , , , , , . , G1 {0,1}, {A, S}, P1, S G2 {0, 1}, {S}, P2, S
nn * * *

6


/

P1: S 0A1 0A 00A1 A
nn

P2: ,
nn

S 0S1 |

L(G1) {0 1 | n 0}, L(G2) {0 1 | n 0}, . . L(G2) L(G1) , L(G1) .


: 0, 1, 2, 3. 3) . i ( i 0, 1, 2, 3), i.

0
0. . 0 .

1
G T, N, P, S , P (. . P | | | | ). S , , S ( ) . 1 . 1 . G T, N, P, S - (), * P , 1A2, 12, A N, (T N ), 1, 2 (T N) . - S , , S ( ) . 1 , 2 . , - , .
, , - G T, N, P, S , , G S . . P S , - G .

3)

, .

7


/

1. L -- . : 1) - G1, L L(G1); 2) G2, L L(G2). , (1) (2): - (. ). , - . 1 , , , -. , - .

2
G T, N, P, S - (), * A , A N, ( T N ) . , - . , - , . 2 - . - , .. . 2. - G G', L(G) L(G'). 2, - - . , , S , S -- , P S . « » , - ( S , , S ).

3
G T, N, P, S , * A wB A w, A, B N, w T . G T, N, P, S , * A Bw A w, A, B N, w T . 3. L -- . : G1, L L(G1); G2, L L(G2). 8


/

3 , . . - . 3. () , , : A a A aB ( , , A a A Ba), A, B N, a T. 4) . , ( - ) . , . , , () - ( S , ; S ) 5). : 4. () G () G, L(G) L(G).


5. : -; - -; 0. 5 . , 2 4 , : 0
( A B , A B.)

- , , , , .

4) 5)

« » . . -, « », - .

9


/

6. : -, -, , : L {a b | n 0};

nn

- -, -, -, : L {a b c | n 0};
n nn

- 0 (. . ),

0, -, : , . 6) 6 : 3 () 2 () 1 () 0

. 1. .

. 1 . . ( 0) . 7. « , k (k 0, 1, 2), k 1?» . , k 1, 2, 3 k k 1 ( .1, k k 1). , , L (, ), k, L k, « L?» , , k (0, 1, 2, 3) L. , , La,b {a, b}, . La,b? : 3, , -,

6)

[10].

10


/

S a | b 3; -, k 3, L (. . 3 -- k, , La,b k).

a ,b

, , : «La,b 2», «La,b 1», «La,b 0». , , « La,b?». : G T, N, P, S «» -- , , , () , -- , -- . . G1 G2: G1: S 0A1 A 0A0 A (1) L(G1)?

G2: S

aSb |

(2) L(G2)?

1) G1 -, , . . 2, L(G1) 2 (, 1, 0). , nn (2n 1) L(G1) {00 0 1 | n 0} {0 1 | n 0} 3, : S 0A A 0B | 1 B 0A , k, L(G1) k, 3. 2) G2 2 3. , L(G2) 2. L(G2) 3? , (. . nn 3), L(G2) {a b | n 0}7). , k, L(G2) k, 2.


, , , , . . .

7)

{anbn | n 0} « ».

11


/


1) S aS | a () . n {a | n 0}. : S Sa | a. , . 2) S aS | {a | n 0}. (. 4). :
n

S

aA | a | a | aA

, ; , , . . . 3) S A | B A a | Ba B b | Bb | Ab ; , {a, b}, ( ) aa. a , b a. : { | {a, b}, aa }.

-
4) S aQb | accb Q cSc - () - {(ac) (cb) | n nn 0}, , {a b | n 0}, , . . . 5) S aSa | bSb | - {xx R, x{a, b} }. . , (. 2). : S A A| aAa | bAb | aa | bb
* n n

12


/

-
6) : S aSBC | abC CB BC bB bb bC bc cC cc {a nbnc n | n 0} , 1, 2 ( « -» [3, .1]). CB BC -. , CB D, CD BD, BD BC ( D N ), - , C B. , : S aSBC | abC CB CD CD BD BD BC bB bb bC bc cC cc

( 0)
7) 0 S SS SS . , : {}. , S ( -- ): S SS SS Sa | S , L {} L ( ) 3. , , L L, L , L -- , ( ). 8) , , - ( 1), - . 0. , 0 ( ) : . , 13


/

0, , . . , A, () X , A X X. , A , , - . , A , -- . , , -- Lself . , Lself 0. , 1, Lself . , 1 . , , , . , 1, Lself . , . . , 1, Lself , .


, , , . , , . , : I ) , , II ) . . , G :
(1, 2) (3) (4) (5) (6)

S CB bB bC cC



aSBC | abC BC bb bc cc
nnn

L(G) { a b c | n 1}. ( ). I ) a b c , n 1 c . n 1: S (2) abC (5) abc. n 1: S (1) aSBC (1) aaSBCBC ... (1) a S(BC) (2) a bC(BC ) (3) n n-1 n n n-2 n nn n nn n-1 nn n-2 ... (3) a bB C (4) a bbB C ... (4) a b C (5) a b cC (6) a b ccC ... nnn (6) a b c .
n-1 n-1 n n-1 nnn

14


/

II) : 1. , [b | B] C , . . , [b | B] [ | ]. 2. b, -- . 3. , [b | 4. 5.

(1), (2)

, . . B] [c | C].

b ( 2).

b, b, . . b b, b -- b . . (5) , (3), - cB . 3, 4 5 , b [c | C]. , , b ; nnn , b , b , , . . a b c , .


T , T, N, P, S , , S . (, , ) 8). : ( ), «» , . ., -- S . . - . , - . , . : T SN - G T, N, P, S , (), .
*

8)

, . . , () - .

15


/

: T SN - G T, N, P, S , (), . , , , . , a b a : Gexpr {a, b, }, {S, T}, {S T | T S ; T a | b}, S : (1) S T S T T S T T T a T T a b T a b a (2) S T S a S a T S a b S a b T a b a (3) S T S T T S T T T T T a T b a a b a (2) -- , (3) -- , (1) , , . - , , . : 9) ( ) - G T, N, P, S , : (1) N T {}, S; -- T {}; (2) A, -- a1, a2, ..., an, ai T N, A a1a2...an -- ; (3) A, , A -- . 2 a b a Gex
pr

*

: - G , L(G), . .
9)

, . ,
A A

a

b



b

a

.

16


/

, ( ) .

S T S T S T a + b + a
expr.

. 2. G

: , , , . : Gifthen

{if, then, else, a, b}, {S}, P, S ,

P {S if b then S else S | if b then S | a}. if b then if b then a else a , 3 (, ). , L(Gif-then) . Gif-then -- , . . , . else then. , else then, Gif-then, : S S' if b then S | if b then S' else S | a if b then S' else S' | a
S S S if b then if b then a else S a
if b then if b then S a else S a S S

)

)
if-then.

. 3. «if b then if b then a else a» G

17


/

8. , - (.. ), . , . 9. , - , . , -- , , . , , . , ( , 10), . . - ):
, , (T N )
*

(1) A (2) A (3) A (4) A ,

AA | AA | A | A | ( ) A | AA | , . , 9.

-: L {a b c | i, j, k 0, i j j k}. L , i j , , j k. , , i j k , , . , - L , [3, .1, . 235­236]. , L, : S AB | DC A aA | B bBc | C cC | D aDb | ; L . . ; , ,
i jk

10)

, , « ».

18


/

, () . S. -- ( ) S. , .


- , . : x T N G T, N, P, S , .


: - G T, N, P, S , : - G' T', N', P', S , , L(G) L(G'). : 1. V0 : {S }; i : 1. 2. Vi : Vi
-1

{x | x T N,

A x P, A Vi

-1

, , ( T N ) } .

Vi Vi - 1, i : i 1 2, N' : Vi N ; T' : Vi T ; P' P, Vi ; G' : T', N', P', S . : AN * G T, N, P, S , { T | A } .


: - G T, N, P, S . : - G' T, N', P', S , , L(G) L(G' ). : N0, N1, ... 1. N0 , i 1. 2. Ni Ni
-1

{A | A P (Ni

-1

T) }.

*

Ni Ni - 1, i : i 1 2, N' : Ni ; P' P, N' T ; G' T, N', P', S . : - G , .

19


/


1. . 2. . , )

.11

(1) (2), .

-. - , , . . - . - (. 2). , - . X, , . : * (1) X1 : { A | (A ) P }; i :2; (2) Xi : {A | (A ) P Xi - 1 } Xi - 1. , Xi Xi - 1 i (2). Xi -- X.


: - G T, N, P, S . : - G' T, N', P', S' , G' -- , L(G') L(G). : 1. {A N | A } ; N:N . 2. P, P . 3. S X, S, N, P S S | . S S. 4. P . * B 1A12A2...n Ann 1, Ai X i 1,..., n, i ( (N X) T ) i 1,..., n 1 (. . n i -- , X ), 2 , i i: B 12...nn 1 B 12...nAnn 1 ... B 12A2...nAnn 1 B 1A12A2...nAnn 1
11)

S -- , . P , S N, N , , -- .

20


/
i i 1, ..., n 1, B P.

5. , . ( ( ), 2­4).
() , () .

, , .



, . ( , ) :
, , , , , .

-

, , . .

, (, ), , , . (-). . , , , [1, 2, 3, 4, 5, 8].

21


/


, . , . : , , G T, N, P, S 12). , A Bt A t, A, B N, t T. : , -- . , , ( ): (1) a1a2...an A, A a1 ( , a1 A) (2) ( , ) : A ai B, B Aai (i 2, 3, .., n); -: , . : (1) ; ; S. , a1a2...an L(G). (2) ; ; , S. , a1a2...an L(G). (3) , . . A ai B, B Aai. , a1a2...an L(G). (4) , , . . , , . . . , .
12)

- , . -- () . .

22


/

, , ( ). , . (N), -- , . . , -- , «-», . , Gleft {a, b, }, {S, A, B, C}, P, S , P: S C C Ab | Ba A a | Ca B b | Cb , : a H C A B S A A -- C -- b B B C -- --


-- S -- -- --

«--» , . () -- , : (1) , ( -- ), , , , , H. . H -- . (2) : ) W t H W ( H W ) t; ) W Vt V W ( V W) t; Gleft (. ) .4:
H b b B a C S a A b a

. 4. Gleft.

23


/


(1) H; (2) ( , ) : , . , , . ( , ): 1) ; , ; S. , L(G). 2) ; «» ; , S. , L(G). 3) , . , L(G). 4) , , , , . . . , , , , . -- , - . (, ) ( , ). , . : () -- K, T, , H, S , K -- ; T -- ; -- K T K, ; H K -- ; S K -- ( S K).

:
(1) , , (), 24


/

. , , , S. 13) (2) : K T K . (A, t) B , A t B. K T ( ). (A, t) , «». : a1a2...an, (H, a1) A1; (A1, a2) A2 ; ... ; (An - 2, an - 1) An - 1; (An - 1, an) S, ai T, Aj K, j 1, 2, ..., n 1; i 1, 2, ..., n; H -- , S -- . : , , . : , , , ; , , , ; (ER); , . . , Gleft {a, b, }, {S, A, B, C}, P, S P: S C C Ab | Ba A a | Ca B b | Cb :
#include using namespace std; char c; // void gc () { cin >> c; } //

bool scan_G () { enum state { H, A, B, C, S, ER }; //
13)

-- , -- . W, t, W t; V W, t, W Vt. S . ( ), : W, t, W Ht, ; .

25


/

state CS; CS = H; do { gc (); s witch (CS) { case H: if ( c == { CS = A } else if ( { CS = B } else CS = E break ; case A: if ( c == { CS = C } else CS = E break ; case B: if ( c == { CS = C }

// CS ----

'a' ) ; c == 'b' ) ;

R; 'b' ) ;

R; 'a' ) ;

else CS = ER; break ; case C: if ( c =='a' ) { CS = A; } else if ( c == 'b' ) { CS = B; } else if ( c == '' ) CS = S; else CS = ER; break ; } } w hile ( CS != S && CS != ER); return CS == S; // true, CS != ER, } false

26


/


G abba. :

H a A b C b B a C S
, «-» Nt L, L Nt . Nt L ( ). , : abba Abba Cba Ba C S , () abba G. (. . 5).
S S S


A a b b a a b b a


A a

C



b

b

a



S C B B

S C B

S


A a

C


A

C


A

C

b

b

a



a

b

b

a



a

b

b

a



. 5. .


(. . 4) Gright : ( S ); V S ( ) V ; V W, t, V t W; 14) H .
14)

, V . S, V

27


/

Gr P: H A C B , (.

ig h t

{a, b, }, {H, A, B, C}, P, H

aA | bB bC bB | aA | aC L(Gright) L(Gleft), Gr . 4).

ight

Gl

e ft


ight

abba Gr :

. -

H a A b C b B a C S
, , «-» Gright. () , : H aA abC abbB abbaC abba (. . 6).
H H A
H A C







a

b

b

a



a

b

b

a



a

b

b

a



H A C

H A C B

H A C B C







B C a b b a

a

b

b

a



a

b

b

a



. 6. .


, , , (. 4 ). -

V, . V t W V W, t. H.

28


/

, , . , , , . , G {a, b, }, {S, A, B}, P, S , P: S A A a | Bb B b | Bb (.. A B -- Bb). . : () -- K, T, , H, S , K -- ; T -- ; -- K T K; H K -- ; S K -- . (A, t) {B1, B2,..., Bn} , A t Bi, i 1, 2, ..., n. , ( , ) (). K ; A B , t, B (A, t). ( ). -- ; -- . , , -- . ( ) , .
, , .

, () ; , ; , . , , , , , « » . , , , , .

29


/

10. L -- . : (1) L ; (2) L ; (3) L . (1) (2) -- . , (2) (3): (C, a) b (C, a) {b}, , . , , , (3) (2).


: M K, T, , H, S . : M1 K1, T, 1, H1, S1 , , : L(M) L(M1). : 1. K1, . . , . , K, K1 s 2 , s -- K. {1, A2, ..., An} A1A2...An. K1 , 1, , H1: H1 A1A2...An, 1, A2, ..., An H. , M H1 M1. K1 H1 ( K1, 1 .) 2. K1 A1A2...Am, «» t T :
1 ( A1A2...Am, t ) B1B2...Bk, 1 j k (Ai, t) Bj -

1 i m. , B1B2...Bk -- , t A1A2...Am. M1 t A1A2...Am B1B2...Bk. ( k 0, 1 ( A1A2...Am, t ) ).
K1 B1B2...Bk .

2 , K1 . 3. M1 , M: S1 : {A1A2...Am | A1A2...Am K1, Ai S 1 i m}.
S1 , . (: {a, b}, b).

30


/ . , ( , ). S, Q S1 : 1 (Q, ) S. S1 , S . , .

. 1. M { H, A, B, S }, {0, 1}, , {H }, {S } , (H, 1) {B} (A, 1) {B, S} (B, 0) { A } L(M) { 1(01) | n 1 }.
n

M .7.
H 1 B 1 1

0

A

S

. 7. M.

, M: S A1 A B0 B A1 | 1 , . H. 1(, 1) B 1(B, 0) A 1(A, 1) BS 1(BS, 0) A BS. , M1 {H, B, A, BS }, {0, 1}, 1, H, BS . M1 : BS S1, 1. M1 {H1, B1, A1, S1}, {0, 1}, { 1(1, 1) B1; 1(B1, 0) A1; 1(A1, 1) S1; 1(S1, 0) A1}, H1, S1 . , M1: S1 A11 A1 S10 | B10 B1 1 (. 8).

31


/

H1

1

B

0
1

A
1

1

0

S

1

. 8. M1.

2. G T, N, P, S P: S Sb | Aa | a A Aa | Sb | b, . , . : (H, a) {S} (H, b) {A} (A, a) {A, S} (S, b) {A, S} , H, :


a S AS AS

b A AS AS

H S A AS : 1(H, a) S 1(H, b) A 1 (S, b) AS 1(A, a) AS 1(AS, a) AS 1(AS, b) AS

S A ,

32


/

: A A, H H, AS Y, S X. X Y S, . S : 1(H, a) X 1(H, b) A 1(X, b) Y 1(X, ) S 1(A, a) Y 1(Y, a) Y 1(Y, b) Y 1(Y,) S G1, : G1: S X | Y Y Ya | Yb | Aa | Xb X a A b . . , - L = { a b | n 0} . ( ). , L . ( ) A ( K , , , I , F ) , L : L( A) L . ( 10, ). kk kk A k (k 0). a b L. L =L (A), a b L (A). kk , A T a b :
nn

p1 a p2 a a pk a pk 1 b pk 2 b b p2k b p2

k 1

,

pi K i 1, ,2k 1 . A k , p1, p2, ..., pk 1 . , i, j, 1 i < j k,

pi pj. , pi p j T .
a a

m (m 0, -- ). T , T , pi a a p j :

p1 a pi a a ( pi p j ) a a p j a pk 1 b p2

k 1

.

33


/

T

a

k m

b

k

. T -- ,

b L , , L L( A) . L L( A) . , , L , a

, , . . , : (), (). 15)

k m k

b L( A) . a

k m k



(),

L1 L2 L1 L2 ; L1L2 {| L1, L2} -- () L1 L2 ( , L1 L2); i 0, L0 = {}. L
*

. L, L1, L2 -- .

i- L L L
n

i

i 1



L





n 0

L

L.

. -- , , , , , (, ). L(), : 1) a {, } ; L(a) {a} a {}; L() ; 2) -- , : ) () () -- ; ) ()() -- ; ) () -- ;
*

L ( () () ) L () L (); L ( ()() ) L () L (); L ( () ) ( L () ) ;
* *

3) 1 2. , «» , «» -- , . {a, b}: a b, : L( a b ) {a} {b} {a, b}, ( a b) ,
*

(aa (ab) bb) .

*

*

15)

, , . «» . , .

34


/

L( (a b) ) {a, b} , L( (aa (ab) bb) ) {}{ aa x1bb aa x2bb... xkbb | k 1, xi {(ab) | n 0} i 1, ..., k }. , [3]. , ; . ( , ) POSIX Perl.
* * n

*

*


() -- . , , , . : ) , , ; ) , ; ) , . , , . : , , . : _, ____ . : , . , -- , , , -- . , . , -. , (I ) :

35


/

I a | b| ...| z | Ia | Ib |...| Iz | I0 | I1 |...| I9 (N): N 0 | 1 |...| 9 | N0 | N1 |...| N9 . . , , , , . : , , ; ; , , _, ____ ; . , , -- -. :

A

t1, t2,..., tn D1; D2;...;Dm

B

ti : A ti - i 1, 2, ..., n, B, D1, D2, ..., Dm. . , , . S N N 0 | 1 |...| 9 | N0 | N1 |...| N9 ( : , 10 ( c char). , n int) n n.

0, 1,..., 9

H

n = c­'0';

N

cout << n*n;

S

0, 1,..., 9 n = n10 c ­'0';

36


/

-
P D1 D B S E E1 T F L I N C R program D1; B var D {,D } I {, I}: [ int | bool ] begin S {;S } end I E | if E then S else S | while E do S | B | read (I ) | write (E ) E1 [ | | | ! ] E1 | E1 T {[ | | or ] T } F {[ | / | and ] F } I | N | L | not F | (E ) true | false C | IC | IR R | NR a | b | ... | z | A | B | ... | Z 0 | 1 | 2 | ... | 9

:
) {} , ) [ | ] , , ; ) P -- ; -- , . . , , . .; .

:
1. , , . 2. . 3. . 4. . 5. ; . , , , { , «}» «» }. true, false, read write -- ( - ). , , .

37


/

. -- -; -- ( ). , , -. : , , , . , , , .


: , :
enum type_of_lex { LEX_NULL, LEX_AND, LEX_BEGIN, ... LEX_WRITE, LEX_FIN, LEX_SEMICOLON, LEX_COMMA, ... LEX_GEQ, LEX_NUM, LEX_ID, POLIZ_LABEL, POLIZ_ADDRESS, POLIZ_GO, POLIZ_FGO };

// // // // // // // // // //

0 18 19 35 36 37 38 39 40 41

-- (_, _). -- , , , , . : TW -- -; TD -- -; TID -- ; TW TD , . . ; TID . , , , , . Lex:

38


/

class Lex { type_of_lex t_lex; int v_lex; public: Lex ( type_of_lex t = LEX_NULL, int v { t_lex = t; v_lex = v; } type_of_lex get_type () { return t_l int get_value () { return v_lex; } friend ostream& operator << ( ostream { s << '(' << l.t_lex << ',' << l.v return s; } };

= 0)

ex; } &s, Lex l ) _lex << ");" ;

Ident:
class Ident { char * bool type_of_lex bool int public: Ident () { declare assign }

na de ty as va

me cl pe si lu

; are; ; gn; e;

= false ; = false ;

char *get_name () { return name; } void put_name (const char *n) { name = new char [ strlen(n) + 1 ]; strcpy ( name, n ); } bool get_declare () { return declare; }

void put_declare () { declare = true; }

39


/

type_of_lex get_type () { return type; } void put_type ( kind_of_lex t ) { type = t; } bool get_assign () { return assign; } void put_assign () { assign = true ; } int get_value () { return value; } void put_value (i nt v) { value = v; } };

tabl_ident :
class tabl_ident { ident * p; int size; int top; public: tabl_ident ( int max_size { p = new ident[size= top = 1; } ~tabl_ident () { delete []p; } ident& operator [] ( int k { return p[k]; } int put ( const char *buf };

) max_size];

)

);

int tabl_ident::put ( const char *buf ) {

40


/

f or ( int j=1; j
Scanner :
class Scanner { enum state static char * TW[]; static type_of_lex words[ static char * TD[]; static type_of_lex dlms[] state CS; FILE * fp; char c; char buf[80 int buf_to void clear () { buf_top = 0; for ( int j = 0; j < 80; ++j ) buf[j] = '\0'; } void add () { buf [ buf_top ++ ] = c; } int look ( c onst char *buf, char **list ) { int i = 0; while ( list[i] ) { if ( !strcmp(buf, list[i]) ) return i; ++i; } return 0; } void gc () { c = fgetc (fp); } public:

{ H, IDENT, NUMB, COM, ALE, DELIM, NEQ }; ]; ;

]; p;

41


/ Lex get_lex (); Scanner ( const char * program ) { fp = fopen ( program, "r" ); CS = H; clear(); gc(); } };

- , , :
char * { "" "a "b "b "d "e "e "i "f "i "n "o "p "r "t "t "v "w "w N }; Scanner::TW[] = // // // // // // // // // // // // // // // // // // // 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 0

nd eg oo o" ls nd f" al nt ot r" ro ea he ru ar hi ri UL

", in l" , e" ", , se ", ", , gr d" n" e" ", le te L

", , ,

",

am", , , , ", ",

0 1 2 3 4 5 6 7 8

char * Scanner:: { "" "@", ";", ",", ":", ":=", "(", ")", "=", "<", ">", "+", "-", "*", "/", "<=",

TD[] = // // // // // // // // // // // // // // // // 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 0

0 1 2 3 4 5

42


/ "!=", ">=", NULL }; tabl_ident TID(100); type_of_lex { LEX_NUL LEX_AND LEX_BEG LEX_BOO LEX_DO, LEX_ELS LEX_END LEX_IF, LEX_FAL LEX_INT LEX_NOT LEX_OR, LEX_PRO LEX_REA LEX_THE LEX_TRU LEX_VAR Scanner::words[] = L, , IN, L, E, , SE, , , GRAM, D, N, E, , // 16 // 17

LEX_WHILE, LEX_WRITE, LEX_NULL }; type_of_lex { LEX_NUL LEX_FIN LEX_SEM LEX_COM LEX_COL LEX_ASS LEX_LPA LEX_RPA LEX_EQ, LEX_LSS LEX_GTR LEX_PLU LEX_MIN LEX_TIM LEX_SLA LEX_LEQ LEX_NEQ LEX_GEQ LEX_NUL }; Scanner::dlms[] = L, , IC MA ON IG RE RE

OLON, , , N, N, N,

, , S, US, ES, SH, , , , L

43


/

gc(); '_' H add(); gc(); , clear(); add(); gc(); j look(buf, TW); Lex(words[j], j); j TID.put(buf); Lex(LEX_ID, j); d d*10 ( c ­´0´); gc( ); IDENT

d c´0´; gc();

NUMB gc( );

Lex(LEX_NUM, d);

{ gc();

COM

} gc(); ER

:,, clear(); add(); gc();

ALE jlook(buf, TD); Lex(dlms[j], j); add( ); gc( ); jlook(buf, TD); Lex(dlms[j], j); Lex(LEX_FIN); NEQ ER gc() ; Lex(LEX_NEQ);

! gc();

DELIM

,,,/,,,;,(,), clear( ); add( ); gc( ); jlook(buf, TD); Lex(dlms[j], j);

. 9. .

44


/

. 9 . . ; . : «», . Lex(k, l); return Lex(k, l);. , ER , . , , . . get_lex():
Lex Scanner::get_lex () { int d, j; CS = H; do { switch ( CS ) { case H: if ( c ==' ' || c ==' \n' || c=='\r' || c =='\t' ) gc (); else if ( isalpha(c) ) { clear (); add (); gc (); CS = IDENT; } else if ( isdigit(c) ) { d = c - '0'; gc (); CS = NUMB; } else if ( c== '{' ) { gc (); CS = COM; } else if ( c== ':' || c== '<' || c== '>') { clear (); add (); gc (); CS = ALE; } else if ( c == '@' ) return Lex(LEX_FIN);

45


/

ca

ca

ca

ca

else if ( c == '!' ) { clear (); add (); gc (); CS = NEQ; } else CS = DELIM; break ; se IDENT: if ( isalpha(c) || isdigit(c) ) { add (); gc (); } else if ( j = look (buf, TW) ) return Lex (words[j], j); else { j = TID.put(buf); return Lex (LEX_ID, j); } break ; se NUMB: if ( isdigit(c) ) { d = d * 10 (c - '0'); gc(); } else return Lex ( LEX_NUM, d ); break ; se COM: if ( c == '}' ) { gc (); CS = H; } else if (c == '@' || c == '{' ) throw c; else gc (); break ; se ALE: if ( c == '=' ) { add (); gc (); j = look ( buf, TD ); return Lex ( dlms[j], j ); } else {

46


/ j = look (buf, TD); return Lex ( dlms[j], j ); } break ; case NEQ: if ( c == '=' ) { add (); gc (); j = look ( buf return Lex ( L } else throw '!'; break ; case DELIM: clear (); add (); if ( j = look(buf, { gc (); return Lex ( d } else throw c; break ; } // end } while ( true ); }

, TD ); EX_NEQ, j );

TD) )

lms[j], j );

switch

get_lex(), gc() switch switch.


: 1) , , , 2) . , : , , , . , . , , .., , . , . -, * A , A N, (T N ) . , , ; , - .

47


/

, , - , , . ( ) , . ([3]), n Cn3 ( -), C -- , Cn2 ( ). , , ( , , ). , . , , -. , , , . -, . . , : , ; , ; - . , , , , . , -.


: G1 {a, b, c, d}, {S, A, B}, P, S , P: S A B ABd a | cA bA

, cabad L(G1). : S ABd cABd caBd cabAd cabad. , cabad L(G1). ( ), ( . 10):

48


/

S A

S B A

S B


c a b a d c a b a d


A c a b a d



S A B A

S B A

S B A b a d


A c a b a d


A c a b A a d


A c a

. 10. .

(-) - . , ; -- , . , , . , ; . , . ( ) : , . , , . , . (. . ). main( ). ( stdin) S( ), , S ( , , , S( ) ). , ( )16), main( ) . , main( ) M S, M -- .

16)

« » « ».

49


/

. G1: S A B :

ABd a | cA bA

#include using namespace std; int void void void { } void S () { cout << "S-->ABd, "; // A(); B(); if ( c != 'd' ) throw c; gc (); } void A () { if ( c =='a' ) { cout << "A-->a, "; gc (); } else if ( c =='c' ) { cout << "A-->cA, "; gc (); A (); } else throw c; } void B () { if ( c { co gc A } c; A (); B (); gc () cin >> c; //

//

=='b' ) ut << "B-->bA, "; (); ();

50


/ else throw c; } 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; } }

, S, ( ) , ( ). , . . , , . , b B( ) B, A( ) B( ) B . b A , () . , , . , . .


, : () X , (T N ) ; () X a11 | a22 | ... | ann,
*

51


/

ai T i 1, 2,..., n ; ai aj i j; i (T N ) , . . X , , ; . , , s-. . , , (.. ). .

*


G1: S ABd A a | cA B bA : (1) S ABd ; (2) wB, w T -- , B -- , bA ( ); (3) wA, w T -- , A , w: a, A a, c, A cA; - -- : L(G1); (4) - w, (2) (3), w -- , , w , , : L(G1). G1 ( ): a S A B S ABd Aa B bA b S ABd c S ABd A cA d S ABd


() - G, ( ): 52


/

1. , S. 2. , , : wY -- , w T . w , : L(G). , w , w z, Y , Y z. , : L(G). , - 17). . , : «» . -- . , - , . : , ( )18). , -. , .



, ( ) . , G2: S aA |B | d A d | aA B aA | a
17) 18)

, , LL(1)-. -- -- «» ; , . , . , , , .

53


/

, , a, .. a : S aA S B . , , : G3: S A|B A aA | d B aB | b , , G3 S, b, d, . , ( S A S B ) , . X X X , , a, . . a a, a. , . . : first () G T, N, P, S -- , , G ( T * N ), . . first () { a T | a, ( T N ) }. , S A | B G3 : first (A) { a, d }, first (B) { a, b }. : first (A) first (B) { a } , G3 . , X | , first ( ) first ( ) , . -. G4: S A B D aA |BDc BAa | aB | b B|b first(aA) { a }, first(BDc) { b, c }; first(BAa) { a, b }, first(aB) { a }, first(b) { b }; first() ; first(B) , first(b) { b }. G4,

first (BAa) first (aB) { a } .

, - . G5: S aA A BC | B C b| B

54


/

first G5, , , , , . , BC B . a :
S A B a

S A B a C

, X | , . , , , . G6: S cAd | d A aA | first ( cAd ) { c }, first (d ) { d }; S , first (cAd) first (d ) . A : a, A aA, A . , , A, d, . A( ) A , . S( ), A( ), , d. , . , d ( ) A( ), , S( ) d, d , . G6: a S A AaA c S cAd A d Sd A

, G6, , , . A( ) A, G6, :
void A () { if ( c =='a' )

55


/ { cout << "A->aA, "; gc (); A (); } else { cout << "A->epsilon, "; // . } }

, , , . G 7: S Bd B cAa | a A aA | first ( cAa ) { c }, first (a ) { a }; S S . B , first (cAa) first (a) . A a . , , A, : S Bd cAad ... ca...aAad. A , a, a (, d ). -- a -- a, A aA. - , ( ). , G 7 , cAad, A, , a, c A. A( ) a, A( ) (. . A aA) ( A ). . : follow(A) -- , G T, N, P, S A ( , A), .. follow(A) { a T | S A, a , A N, , , (T N) }. , X | , , first() follow(X) , . , , . , .
*

56


/

11 ( -). G -- -. G, X | : (1) first() first () ; (2) : , ; (3) , first(X) follow( X ) . G8: S C D B

BDC Bd aB | d bB | first (aB ) { a }, first ( d ) { d }; first (bB ) { b }, follow (B ) {a, b, d}, : BdC, BaBbd 19). first (bB) follow (B) { b } , . : , , . 12. , , , (. . 20)).


G, M : 1. X a first() X M [X, a]; 2. 13. X X , , X X. X Y , Y N, Y -- X, Y 1- 2- X.

2- , follow(X), . 19)

20)

first follow «», . first follow (, [3]) . , , , , , .

57


/

X , , -- , . 3- , first(X), . X Y X , , -- , . : (.. 1), X , , M [X, a] a follow(X) 21) ; 1- 2- X . , , . . G9: S B A E A |B S |cS bB | d aA | E | e

: first ( A) { a, e }, first ( BS ) { b, d }, first ( cS ) { c }, follow(S) ; first (bB) { b }, first (d ) { d }; first ( aA ) { a }, first (E ) { e }, follow(A) ; first (e ) { e }. , first , first ( A) follow ( A) first ( S) follow ( S) . , : a S A B E SA A aA b S BS A B bB c S cS A d S BS A Bd Ee e SA AE

G9 . . , , , , , .
#include using namespace std;
21)

follow(X) , -- , .

58


/ int c; v v v v o o o o id id id id S A B E (); (); (); ();

void gc () { cin >> c; }

//

void S () { if ( c =='a' || c =='e') { cout << "S-->A, "; // // gc () , A() A (); } else if ( c =='b' || c =='d') { cout << "S-->BS, "; // gc () ; B (); S (); } else if ( c =='c') { cout << "S-->cS, "; gc (); // 'c' S(), S (); } else A (); // A } void A () { if ( c =='a' ) { cout << "A-->aA, "; gc (); A (); } else if ( c =='e' ) { cout << "A-->E, "; // gc () ; E (); } else { // gc () ; cout << "A->epsilon, "; } } void B () { if ( c =='b' )

59


/ { cout << "B-->bB, "; gc (); B (); } else if ( c =='d' ) { cout << "B-->d, "; gc (); } e lse throw c; } void E () { if ( c =='e' ) { cout << "E-->e, "; gc (); } else throw c; } 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; }

}


, , . , - ( -) , :

60


/

) )

X, * (T N) ; X a11 | a22 | ... | ann , ai T i 1, 2,..., n ; ai aj i j; i (T N ) , . . X , , ;
*

)

X a11 | a22 | ... | ann | , * ai T i 1, 2,..., n; ai aj i j; i (T N ) , first (X ) follow (X ) .

, : ai i, ai, , ; ai - -- . , -. q-. s- q-, .

-
, , - (, , . .). : L a | a, L - , 22). , , {}, -- , . . L a | a, L : L a {, a}. , X {}, {}, {}: X Y Y Y | , Y -- , . L a {, a}, : L aM M ,aM|
22)

- .

61


/

, first ( , a ) follow (M ) . , , , , . {} ( b, b T ) : « b, ». L a {, a} - :
void L () { if ( c != 'a' ) throw c; gc (); while ( c == ',' ) { gc (); if ( c != 'a' ) throw c; else gc (); } }

. Gsequence: S LB L a {, a} B ,b , ( ) , ,,,b , ,,,b Gsequence . , L( ) -- , B, , . , : S LB L aM M ,aM| B ,b , first (, a) follow (M ) { , } 23). , .

23)

Gsequence , , (, ), , .

62


/

. , 12, , , .


, , . . , . (1) , , . . : A A1 | ... | An | 1 | ... | m, i (T N ) i 1, 2, ..., n; j (T N ) j 1, 2, ... , first(Ai) i k, j j first (i) follow (A) : A 1 A | ... | m A A 1 A | ... | n A | , , j {i}, i 1, 2, ..., n; j
+ *

, m, first(Ak) i 1, 2, ..., n.

.. A 1, 2, ..., m.

(2) , , . . A a1 | a2 | ... | an | 1 | ... |m, a T ; i, j (T N ) , j a, i 1, 2,..., n, j 1, 2,..., m, , . . first(ai) first(ak) i k. , : A aA | 1 | ... | m A 1 | 2 | ... | n , . (3) , , , , . . : A B11 | ... | Bnn | a11 | ... | amm B1 11 | ... | 1k ... Bn n1 | ... | np, Bi N; aj T; i, j, ij ( T N ) , Bi , A : A 111 | ... | 1k1 | ... | n1n | ... | npn | a11 | ... | am
m * *

63


/

(4) : A 1 A | ... | n A | 1 | ... | m| B A first(A) follow(A) (- ), : B A A 1A | ... | n A | 1 | ... | m | , . . B - {i} j {i} . A , (. . first(A) follow(A) ); , , . . Gorigin: Go
r ig in

S fASd | A Aa | Ab | dB | f B bcB |

first(Aa) first(Ab) {d, f } first(bcB) {b}, follow(B) {a, b, d, f } . Go
r ig in

Gorigin. (i) , 1 i 4 : : S A A' B

: S A B

fASd | Aa | Ab | dB | f bcB |

Gt
(1)

ransform1

fASd | dBA' | fA' aA' | bA' | bcB |



(4)

first(S) { f }, follow( S ) { d }, first (S) follow(S) ; first(A') {a, b}, follow(A') { f, d }, first (A') follow(A') ; first(B) {b}, follow(B) {a, b, f, d }, first(B) follow(B) {b} . G
(4 )

transform2

: S A B' A'

Gt fASd | dB' | fA' bcB' | A' aA' | bA' |
(3)

ransform3

: S A B' A'



fASd | dB' | fA' bcB' | aA' | bA' | aA' | bA' |

64


/

G
(2 )

transform4

: S A B' C A'

Go fASd | dB' | fA' bC | aA' | cB' | A' aA' | bA' |
(3 )

bject

: S A B' C A' fASd | dB' | fA' bC | aA' | cB' | aA' | bA' | aA' | bA' |

first(B') {a, b}, follow(B') {f, d}; first(B') follow(B') ; first(A') {a, b}, follow(A') {f, d}; first(A') follow(A') ; first(C) {a, b, c}, follow(C) {f, d}; first(C) follow(C) . . . Gobject, . Gobject , .


( ) . (1) - G x. : x L(G)? , x ( x, x) 24). , , . (2) - G x. : x L(G)? , x (, ). - , , . «» ( ). : « », , . , ( ) . Gif-then {if, then, else, a, b}, {S }, P, S, S , P { S if b then S S | a ; S else S | }. S else , first(else S) follow(S) {else} . if b then if b then a else a , . 101 (, ). S, , . 101 (), else ( ) if, ,
24)

. , .

65


/

. , - , ( ). , Gif-then : , . , - . .
S S if b then S


S a S S

if

b

then

else

(a)
a S S if b then S else if b then S a S a S

()



. 10. if b then if b then a else a.

-
-. -, , , , , -- , n cn. LL(k)-, , , - -- ; LR(k)-, , , , - -- ; (., , [2], [3]). 66


/

LL(k)- , k , . . LR(k)- , k , . , . LR(k)- , . , . - , (, LL- LR-, ), Ñ . , , , , . , . , LR-, , LL-. , , .

-
, : ; , ; «» , . : -- - get_lex( ) Scanner, (class) Lex; curr_lex Lex , , c_val -- . - Parser . , . .

67


/

class Parser { Lex curr_lex; // type_of_lex c_type; int c_val; Scanner scan; Stack < int , 100 > st_int; Stack < type_of_lex, 100 > st_lex; v v v v v v v v v v v v v v v v o o o o o o o o o o o o o o o o id id id id id id id id id id id id id id id id P(); // - D1(); D(); B(); S(); E(); E1(); T(); F(); dec chec chec chec eq_t eq_b chec ( k k k y o k t _i _o _n pe ol _i yp d p ot ( ( d_ e_ () () ( ); ); in of_lex type); ; ; ); //

_read ();

void gl () // { curr_lex = c_type = cu c_val = cur } public: Poliz

scan.get_lex(); rr_lex.get_type(); r_lex.get_value();

prog;

//

Parser ( const char *program) : scan (program), prog (1000) {} void }; analyze(); //

void Parser::analyze () { gl (); P (); prog.print(); cout << endl << "Yes!!!" << endl; } void Parser::P () { if ( c_type == LEX_PROGRAM ) gl ();

68


/ else throw curr D1 (); if ( c_type == gl (); else throw curr B (); if ( c_type != throw curr } void Parser::D1 () { if ( c_type == LEX_VAR ) { gl (); D (); while ( c_type == LEX_COMMA ) { gl(); D(); } } else throw curr_lex; } void Parser::D () { st_int.reset(); if ( c_type != LEX_ID ) throw curr_lex; else { st_int.push ( c_val ); gl (); while ( c_type == LEX_COMMA ) { gl(); if (c_type != LEX_ID) throw curr_lex; else { st_int.push ( c_val ); gl(); } } if ( c_type != LEX_COLON ) throw curr_lex; else { gl (); if ( c_type == LEX_INT ) { dec ( LEX_INT ); gl(); } else _lex; LEX_SEMICOLON )

_lex; LEX_FIN ) _lex;

69


/

if ( c_type == LEX_BOOL ) { dec ( LEX_BOOL ); gl(); } else throw curr_lex; } } } void Parser::B () { if ( c_type == LEX_BEGIN ) { gl(); S(); while ( c_type == LEX_SEMICOLON ) { gl(); S(); } if ( c_type == LEX_END ) gl(); else throw curr_lex; } else throw curr_lex; } void Parser::S () { int pl0, pl1, pl2, pl3; if ( c_type == LEX_IF ) { gl(); E(); eq_bool(); pl2 = prog.get_free (); prog.blank(); prog.put_lex (Lex(POLIZ_FGO)); if ( c_type == LEX_THEN ) { gl(); S(); pl3 = prog. prog.blank( prog.put_le prog.put_le if (c_type { gl(); S();

g ) x x =

et ; ( ( =

_free(); Lex(POLIZ_GO)); Lex(POLIZ_LABEL, prog.get_free()),pl2); LEX_ELSE)

70


/ prog.put_lex(Lex(P OLIZ_LABEL,prog.get_free()),pl3); } else throw curr_lex; } else throw curr_lex; } //end if else if ( c_type == LEX_WHILE ) { pl0 = prog.get_free(); gl(); E(); eq_bool(); pl1 = prog.get_free(); prog.blank(); prog.put_lex (Lex(POLIZ_FGO)); if ( c_type == LEX_DO ) { gl(); S(); prog.put_lex (Lex (POLIZ_LABEL, pl0)); prog.put_lex (Lex ( POLIZ_GO)); prog.put_lex (Lex(POLIZ_LABEL, prog.get_free()),pl1); } else throw curr_lex; } //end while else if ( c_type == LEX_READ ) { gl(); if ( c_type == LEX_LPAREN ) { gl(); if ( c_type == LEX_ID ) { check_id_in_read(); prog.put_lex (Lex ( POLIZ_ADDRESS, c_val) ); gl(); } else throw curr_lex; if ( c_type == LEX_RPAR EN ) { gl(); prog.put_lex (Lex (LEX_READ)); } else throw curr_lex; } else throw curr_lex; } //end read else

71


/ if ( c_type == LEX_WRITE ) { gl(); if ( c_type == LEX_LPAREN ) { gl(); E(); if ( c_type == LEX_RPAREN ) { gl(); prog.put_lex (Lex(LEX_WRITE)); } else throw curr_lex; } else throw curr_lex; } //end write else if ( c_type == LEX_ID ) { check_id (); prog.put_lex (Lex(POLIZ_ADDRESS,c_val)); gl(); if ( c_type == LEX_ASSIGN ) { gl(); E(); eq_type(); prog.put_lex (Lex (LEX_ASSIGN) ); } else throw curr_lex; } //assign-end else B(); } void Parser::E () { E1(); if ( c_type == LEX_EQ || c_type == LEX_LSS || c_type == LEX_GTR || c_type == LEX_LEQ || c_type == LEX_GEQ || c_type == LEX_NEQ ) { st_lex.push (c_type); gl(); E1(); check_op(); } }

void Parser::E1 () { T(); while ( c_type==LEX_PLUS || c_type==LEX_MINUS || c_type==LEX_OR ) { st_lex.push (c_type); gl();

72


/ T(); check_op(); } } void Parser::T () { F(); while ( c_type==LEX_TIMES || c_type==LEX_SLASH || c_type==LEX_AND ) { st_lex.push (c_type); gl(); F(); check_op(); } } void Parser::F () { if ( c_type == LEX_ID ) { check_id(); prog.put_lex (Lex (LEX_ID, c_val)); gl(); } else if ( c_type == LEX_NUM ) { st_lex.push ( LEX_INT ); prog.put_lex ( curr_lex ); gl(); } else if ( c_type == LEX_TRUE ) { st_lex.push ( LEX_BOOL ); prog.put_lex (Lex (LEX_TRUE, 1) ); gl(); } else if ( c_type == LEX_FALSE ) { st_lex.push ( LEX_BOOL ); prog.put_lex (Lex (LEX_FALSE, 0) ); gl(); } else if ( c_type == LEX_NOT ) { gl(); F(); check_not(); } else if ( c_type == LEX_LPAREN ) {

73


/ gl(); E(); if ( c_type == LEX_RPAREN) gl(); else throw curr_lex; } else throw curr_lex; }

-
, -, : 1. , , . 2. . 3. . 4. . 5. ( ). . , , . Stack:
template class Stack

0;} top = 0; } ; ){ return top == 0; } { return top == max_size; }

template void Stack ::push(T i) { if ( !is_full() ) { s[top] = i; ++top; }

74


/ else throw "Stack_is_full"; } template T Stack ::pop() )

];

_is_empty";


, , . , , . , . , , . TID -, . . i- TID - LEX_ID, i . name; declare type . D I {, I}: [int | bool], . . (int bool) . (, TID) ( Stackint,100 st_int), , declare type . void Parser::dec (type_of_lex type) TID, , .
void Parser::dec ( type_of_lex type ) { int i; while ( !st_int.is_empty()) { i = st_int.pop(); if ( TID[i].get_declare() ) throw "twice";

75


/

else { TID[i].put_declare(); TID[i].put_type(type); } } }

: D st_int.reset( ) I st_int.push ( c_val ) {, I st_int.push (c_val) }: [ int dec ( LEX_INT ) | bool dec ( LEX_BOOL ) ]


Stack type_of_lex, 100 st_lex. _ true false, . -- -, , ; , . check_id( ):
void parser::check_id() { if ( TID[c_val].get_declare() ) st_lex.push(TID[c_val].get_type()); else throw "not declared"; }

-- ­ ­ ( ) check_op( ):
void Parser::check_op () { type_of_lex t1, t2, op, t = LEX_INT, r = LEX_BOOL; t2 = st_lex.pop(); op = st_lex.pop(); t1 = st_lex.pop(); if ( op==LEX_PLUS || op r = LEX_INT; if ( op == LEX_OR || op t = LEX_BOOL; if ( t1 == t2 && t1 == st_lex.push(r); else throw "wrong types } ==LEX_MINUS || op==LEX_TIMES || op==LEX_SLASH ) == LEX_AND ) t)

are in operation";

76


/

not check_not( ):

void Parser::check_not () { if (st_lex.pop() != LEX_BOOL) throw "wrong type is in not"; else { st_lex.push (LEX_BOOL); } }

: ? : , -- (, /, and), (, , or), . E E1 | E1 [ | | ] E1 E1 T { [ | | or ] T } T F { [ | / | and ] F} F I | N | [ true | false ] | not F | (E) - . . , , , (, ), i: G1: G4 : E E E | E E | (E) | I E T G2: F E E T | E T | T T i | (E) G3: E T TE|TE|T i | (E) , -

T|ET F|TF i | (E)

G5 : E T|TE T F|FT F i | (E) , (G1 -- , ; G1, G2, G3 -- ; G4, G5 -- , G2, G4 -- , , , G3, G5 -- ).

77


/

: E E T F
1



E1 | E1 [ | | ] st_lex.push(c_type) E1 check_op( ) T { [ | | or ] st_lex.push (c_type ) T check_op( ) } F { [ | / | and ] st_lex.push (c_type ) F check_op( ) } I check_id( ) | N st_lex (LEX_INT) | [ true | false ] st_lex.push (LEX_BOOL) | not F check_not( ) | (E)


S I : E | if E then S else S | while E do S | B | read (I) | write (E) 1. I : E : I E . E ( ); I , , ( check_id( ) ), :
void Parser::eq_type () { if ( st_lex.pop() != st_lex.pop() ) throw "wrong types are in :="; }

, : I check_id( ) : E eq_type( ) 2. if E then S else S | while E do S : . E ( ); , :

void Parser::eq_bool () { if ( st_lex.pop() != LEX_BOOL ) throw "expression is not boolean"; }

78


/

: if E eq_bool( ) then S else S | while E eq_bool( ) do S 3. read(I) :
void Parser::check_id_in_read () { if ( !TID [c_val].get_declare() ) throw "not declared"; }

: read ( I check_id_in_read( ) ) . - , . Parser :
class Parser { Lex curr_lex; type_of_lex c_type; int c_val; Scanner scan; Stack < int , 100 > st_int; Stack < type_of_lex, 100 > st_lex; void P(); void D1(); void D(); void B(); void S(); void E(); void E1(); void T(); void F(); v v v v v v v o o o o o o o id id id id id id id dec chec chec chec eq_t eq_b chec ( k k k y o k t _i _o _n pe ol _i yp d p ot ( ( d_ e_ () () ( ); ); in of_lex type); ; ; );

_read ();

void gl () { curr_lex = scan.get_lex(); c_type = curr_lex.get_type(); c_val = curr_lex.get_value(); } public: Parser ( const char *program) : scan (program) {} void analyze();

79


/ }; void Parser::analyze () { gl (); P (); cout << endl << "Yes!!!" << endl; }

D ( ):
void Parser::D () { st_int.reset(); if (c_type != LEX t hrow curr_lex; else { st_int.push ( c gl(); w hile (c_type = { gl(); if (c_type != throw curr_ e lse { st_int.push gl(); } } if (c_type != L t hrow curr_le e lse { gl(); if (c_type == LEX_INT) { dec ( LEX_INT ); gl(); } e lse if (c_type == LEX_BOOL) { dec ( LEX_BOOL ); gl(); } e lse throw curr_lex; } } }

_ID)

_val ); = LEX_COMMA)

LEX_ID) lex;

( c_val );

EX_COLON) x;

80


/


, . , .


: ) ; ) ; ) . : ) ; ) ; ) ; ) ; ) , . .
, , A B, A, B N.

( -- ). , , , . . , . , . . , . , . , (a b) a b, -- . , a b a b c, , . , , a b c b -

81


/

: a (b c). a b c b , . . «», «» ( , ), (a b) c. - : a b c d (( a b ) c) d . : 1) , -- ; 2) 1 2, -- , 1 2 , E1 E2 , E1 E2 -- 1 2 ; 3) E, -- , -- , E , E -- ; 4) () . . a b c a b c , a b c . a (b c).


, , -- , , (, ) . 1. . 2. , : ) ) ) ) . , -. , . (, ), , , -. , , , . ) , : , ( - ), , ( ), ; . ) , .

82


/

) , - , . , - . , -. , , . 3. , -. ( ; , .) , () a ( b c) (d e) / f : abcdef/
, , , , .

(. . ) .

,
1) (2) (3); 2) -- , ; 3) -- , ( ); , , ; 4) , , , -- , . . .
1. , , , . 2. , ; , «» , . «» : . , , : , . . , 0 ; ; , a. , .

83


/

I : E I E : «:» -- , I -- ; I , «:» I, . , , . , , , 1 (, ). , L, p, goto L p! «!» -- , p. . , if B then S1 else S2 B, S1, S2, : B S1 S2 if, B -- , S1 S2 -- S1, S2, if -- . S1, S2 , B, . if, while . ., . -- « » if (!B) goto L B L. !F, B p !F, p -- , , L, B -- . if then S1 else S2 : if (! ) goto L2; S1; goto L3; L2: S2; L3: ... ( -- !): p2 !F S1 p3 ! S2 ..., pi -- , , Li, i 2,3, -- . ,

84


/

-- S1 , S2 -- . . while do S : L0: if (! ) goto L1; S; goto L0; L1: ... . while ( -- !): p1 !F S p0 ! ..., pi -- , , Li, i 0,1, -- . - . read (I) I read; write (E) write, -- . , , , ( ; , , ). , . .


, . . , , . (. ). , , . . -- -- , . , . Gexpr: E T {T } T F {F } F a | b | (E) .

85


/

T {T cout ''; } F {F cout ''; } a cout 'a'; | b cout 'b'; | (E) a b Gexpr_polish a b , . , . , . : T1 T2 -- . -- * * T1 T2: (T1 T2 ). L() { | : (, ) }. ( ) L() { | : (, ) }. , T1 , , T2 , , (, ) (, ) . Gexpr_polish : . ; . , L1 L2 25). L1 L2, L1 L2. . L1 {0 1 nm 0 1 L1 : { (0 . { (0 1 , a b ) | n 0, m 0} . L1 : S 0S | 1A A 1A | a b: S A
25)

Gexpr E T F

_polish

:

*

*

nm

| n 0, m 0} -- : mn a b L2. nm mn 1 , a b ) | n 0, m 0 },
nm mn

, L2 L () L1

{a n , L

mn

b |n 0, m () L2

0, m 0} -- 0 .

mn

0 1 0S cout 'b'; | 1 cout 'a'; A 1 cout 'a'; A |
n

nm

, L1, L2 . , L1 {a | n 0}, L2 {b, c}. i {(ai, b)} {(an, c) | n i, i 0},

L(i) L1, L(i) L2. 86


/

L1 L2.

-
-- , . . _, _ . ( ) : POLIZ_GO -- «!»;
POLIZ_FGO -- «!F»; POLIZ_LABEL -- ; POLIZ_ADDRESS -- - (,

). , prog Poliz, : Poliz prog (1000);
class Poliz { lex *p; int size; int free; public: Poliz ( int max_size ) { p = new Lex [size = max_size]; free = 0; }; ~Poliz() { d elete []p; }; void put_lex(Lex l) { p[free]=l; ++free; }; void put_lex(Lex l, int place) { p[place]=l; }; void blank() { ++free; }; int get_free() { return free; }; lex& operator[] ( int index ) { if (index > size) throw "POLIZ:out of array"; else if ( index > free ) throw "POLIZ:indefinite element of array"; else return p[index]; }; void print() { for ( int I = 0; i < free; ++i ) cout << p[i]; }; };



87


/

prog Parser:
class Parser { Lex curr_lex; ... public: Poliz prog; Parser (const char *program ) : scan (program),prog (1000) {} void analyze(); };

, , ; , , . , . check_op( ) prog.put_lex (Lex (op) ); op, check_not( ) prog.put_lex (Lex (LEX_NOT) ); not ( ) . , , : E E T F E1 | E1 [ | | ] st_lex.push (c_type ) E1 check_op ( ) T { [ | | or ] st_lex.push (c_type ) T check_op ( ) } F { [ | / | and ] st_lex.push (c_type ) F check_op ( ) } I check_id ( ); prog.put_lex ( curr_lex ); | N st_lex.push (LEX_INT); prog.put_lex ( curr_lex ); | [ true | false ] st_lex.push (LEX_BOOL); prog.put_lex ( curr_lex ); | not F check_not( ); | (E)

1

, , : S I check_id ( ); prog.put_lex ( Lex ( POLIZ_ADDRESS, c_val ) ); : E eqtype ( ); prog.put_lex ( Lex ( LEX_ASSIGN ) ); prog . if E then S1 else S2 , « » : if (!E) goto l2; S1; goto l3; l2: S2; l3 :...

88


/

prog , , , . , , : S if E eqbool( ); pl2 prog.get_free( ); prog.blank( ); prog.put_lex ( Lex (POLIZ_FGO ) ); then S1 pl3 prog.get_free( ); prog.blank( ); prog.put_lex ( Lex (POLIZ_GO) ); prog.put_lex ( Lex (POLIZ_LABEL, prog.get_free( ) ), pl2); else S2 prog.put_lex ( Lex (POLIZ_LABEL, prog.get_free( ) ), pl3);

while E do S : L0: if (!E) goto l1; S; goto l0; l1: ..., : S while pl0 prog.get_free ( ); E eqbool ( ); pl1 prog.get_free ( ); prog.blank ( ); prog.put_lex (Lex (POLIZ_FGO)); do S prog.put_lex (Lex (POLIZ_LABEL, pl0); prog.put_lex (Lex (POLIZ_GO) ); prog.put_lex (Lex (POLIZ_LABEL, prog.get_free( ) ), pl1);
pli (i 0, 1, 2, 3) S, .

, : S read ( I check_id_in_read( ); prog.put_lex ( Lex (POLIZ_ADDRESS, c_val) ); ) prog.put_lex ( Lex (LEX_READ) ); S write ( E ) prog.put_lex ( Lex (LEX_WRITE) );


, , , . : ; , ; , , ( ) . . , prog Poliz. : - (, true,

89


/

false), - , - ( ) - ( -- TID). - , .
class Executer { Lex pc_el; public: void execute ( Poliz& prog ); }; void Executer::execute ( Poliz& prog ) { Stack < int , 100 > args; int i, j, index = 0, size = prog.get_free(); while ( index < size ) { pc_el = prog [ index ]; switch { ca ca ca ca ca ( pc_el.get_type () ) se se se se se LEX_TRUE: LEX_FALSE: LEX_NUM: POLIZ_ADDRESS: POLIZ_LABEL: args.push ( pc_el.get_value () ); break ; LEX_ID: i = pc_el.get_value (); if ( TID[i].get_assign () ) { args.push ( TID[i].get_value () ); break ; } else throw "POLIZ: indefinite identifier"; LEX_NOT: args.push( !args.pop() ); break ; LEX_OR: i = args.pop(); args.push ( args.pop() || i ); break ; LEX_AND: i = args.pop(); args.push ( args.pop() && i ); break ; POLIZ_GO: index = args.pop() - 1; break ; POLIZ_FGO: i = args.pop(); if ( !args.pop() )

case

case

case

case

case

case

90


/ index = i - 1; break ; case LEX_WRITE: cout << args.pop () << endl; break ; case LEX_READ: { int k; i = args.pop (); if ( TID[i].get_type () { cout << "Input int cout << TID[i].get_ cin >> k; } else { char j[20]; rep: cout << "Input bool cout << (true or fa

== LEX_INT ) value for"; name () << endl;

ean value; lse) for";

cout << TID[i].get_name() << endl; cin >> j; if ( !strcmp(j, "true") ) k = 1; else if ( !strcmp(j, "false") ) k = 0; else { cout << "Error in input:true/false"; cout << endl; goto rep; } } TID[i].put_value (k); TID[i].put_assign (); break ;} LEX_PLUS: args.push ( args.pop() + args.p break ; LEX_TIMES: args.push ( args.pop() * args.p break ; LEX_MINUS: i = args.pop(); args.push ( args.pop() - i ); break; LEX_SLASH: i = args.pop(); if ( !i ) { args.push ( args.pop() / i break ; } else throw "POLIZ:divide by zer LEX_EQ:

case

op() );

case

op() );

case

case

);

o";

case

91


/

args.push ( args.pop() == args.pop() ); break ; case LEX_LSS: i = args. args.push break ; case LEX_GTR: i = args. args.push break ; case LEX_LEQ: i = args. args.push break ; case LEX_GEQ: i = args. args.push break ; case LEX_NEQ: i = args.

pop(); ( args.pop() < i);

pop(); ( args.pop() > i );

pop(); ( args.pop() <= i );

pop(); ( args.pop() >= i );

pop(); args.pop() != i );

args.push ( break ; case LEX_ASSIGN: i = args.pop j = args.pop TID[j].put_v TID[j].put_a break ; default : throw "POLIZ } ++index;

() () al ss

; ; ue(i); ign();

: unexpected elem"; // end of switch

}; //end of while cout << "Finish of executing!!!" << endl; } class Interpretator { Parser pars; Executer E; public: Interpretator ( c har* program ): pars (program) {}; void interpretation (); }; void Interpretator::interpretation () { pars.analyze (); E.execute ( pars.prog ); } int main () { try { Interpretator I ( "program.txt" );

92


/ I. .

I.interpretation (); return 0; } catch ( char c ) { cout << "unexp return 1; } catch ( Lex l ) { cout << "unexp cout << l; return 1; } catch ( const char { cout << source return 1; } }

ected symbol " << c < < endl;

ected lexeme";

*source ) << endl;


I. .
1. . . a) S T F : T | TS | TS F | FT a|b a b a b b) S aSBC | abC CB BC bB bb bC bc cC cc : a a a b b b c c c

2. : S AB | BA Aa Bb 3. ? ? ? . a) S APA P| Aa|b b) S A | SA | SB Aa Bb

93


/ I. .

c) S 1B B B0 | 1 e) S a | Ba B Bb | b g) S 0A1 | 01 0A 00A1 A 01 i) S A | B A aAb | 0 B a Bbb | 1 k) S D A B 0S | DD 0B | 0A | S0 | D | 1A | 0

d) S aQb | Q cSc f) S Ab A Aa | ba h) S AB AB BA Aa Bb j) S 0A | 1S A 0A | 1B B 0B | 1B | l) S 0A | 1S | A 1A | 0B B 0S | 1B n) S AB A a | cA B bA p) S Ab | c A Ba B cS 7. 8. 9. 10. 11. 12. 6. 7. 8. 9. u) Bb Ab DF BE AE bE bB bA E Eb Ea b

m) S SS | A A a | bb o) S aBA | B bSA AA c r) 1. 2. 3. 4. 5. 6. 1. 2. 3. 4. 5. S KF K KB | C CA | DA aA Aa aA DB bB

CB DA D D

s)

S DC D aDA | bDB | aA |bB AC aC BC bC Aa aA

Ba aB Ab bA Bb bB C S 0A1 0A 0B1 | 0 B1 0C11 | 01 C 0D | 00D1 | 0 D 01

t)

S aAc aA aaBbC | ab Bb bb | abbbc | aDbbbcc Cc D ab

94


/ I. .

4. , L. ? ? a) L { a b | n, m 1}; b) L { c c c | , , {a,b} (.. , , -- a b)}; c) L { a1 a2 ... an an ... a2 a1 | ai { 0, 1}, n 1}; d) L { 0 n 1[n/2] | n1}; e) L { ca n cb m c n | n0, m0 }; f) L { a n b m | n m ; n, m 0}; g) L { | {0,1} , ||0 ||1 } (.. 0 1 0 1); h) L { | {a,b}}; i) L { | {0,1}, ||0 | |1, x,y {0,1} : xy
(.. , , , ) ;
* * * nm

| x |1 | x |0}

0 1, ,

j) L { 1 2... n | n 0, i { a k) L { l) L { m) L {

2m

b m | m 1} 1 i n };

a3 an

n

1
2

| n 1};

| n 1}; | n 1}.

a

n 1

3

5. ( )? ? ? , -- . a) S AB | ASB Aa aB b bB bb b) S 1A0 1A 11A0 | 01

6. : ) S AB A a | Aa B b | Bb b) S aSL | aL L Kc cK Kc Kb S AS | SB | AB Aa Bb S aSBc | abc cB Bc bB bb



95


/ I. .

7. -, : ) S aAb aA aaAb A b) S AB | ABS AB BA BA AB Aa Bb

8. , : ) S A | AS A a | bb b) S A.A A B | BA B0|1

9. , A Bt, A t B, A t, . 10. , : S aSBC | abC CB BC bB bb bC bc cC cc L {a b c | n 1}. , : nnn I ) a b c (n 1) II ) . 11. : a) S S0 | S1 | D0 | D1 D H. H 0 | 1 | H0 | H1 b) S if B then S | B E EB|BE Ba|b
nnn

: a) 10.1001 b) if a then b a b b 12. . , . -. S P T R R R P 1P1 | 0P0 | T 021 | 120R 1 0R 0 1R 1

96


/ I. .

13. , {a, b}, a .







14. - L, a a b b b c c c c . L {a2n bm c2k | m n k , m 1}. 15. , { a, ( , ), }. : , a) , b) (1) 1 2, 1 2 . 16. -, L, a a c b b b c a a . L {a cb ca | n , m 0 }. 17. -, L, 110000111 . L {1 0 1 | n p m ; n , p , m 0 }. 18. L {13n2 0 n | n 0}. , , L. , 1111111100 . 19. - G1 G2, L1 L2, - a) L1L2 ; b) L1 L2 ; c) L1 .
L L1 L2 -- L1 L2, .. L { | L1, L2}; L L1 -- L1, .. {} L1 L1L1 L1L1L1 ...


n

m

n

nmp

20. - L {i 2 i1R | i N, i (i)2 -- i ( ), R -- }. - L (. 19). 21. , E E E | E E | ( E ) | i . ?

97


/ I. .

22. a) b) c)

, - A AA | A AA | A A | A | ,

, , (TN), A N, . , ? 23. , G . ? ? G: S aAc | aB B bc Ab 24. - G T, N, P, S . X {A N | A }. 25. - G , , L(G). 26. , -. a) S A B C aABS | bCACd bAB | cSA | cCC bAB | cSB cS | c b) S A B C D E aAB | E dDA | bE | f cAB | dSD | a eA fA | g

27. -, , . S C A B aS | CC aB | aA | Sa | C | bA | a , . , , -

28. , . , , .

29. , . 30. , - .
A N -- , A 1A 2. - , .

98


/ II. , ,

31. , (. 29) . 32. , , -, , .
, A A, |A| 1; .

II. , ,
1. : S S0 | S1 | P0 | P1 P N. N 0 | 1 | N0 | N1 () : 11.010, 0.1, 01., 100. ? 2. . a) 1011, 10 011 0 1011. b) , . c) ?
0,1

H

0,1

A
+,



S

0,1

ER

B

3. c gc(), . :
printf("%d",b);

gc( );

H

0,1 b=c'0';gc( );

S
0,1

gc( );

b=2*b+c'0';gc( );

a)

, 1101/ / p11 1 0 0 0 /5 .











99


/ II. , ,

b)

.

4. () , , -- : a) L { x y | x, y}} ; b) L { (xy 3) | n 1 } ; ) L {(abb) | k 1} ; d) L { | {0,1}, 1 0} ; e) L {11 | {0,1} , 0 -- }. 5. : S A A Ab | Bb | b B Aa , ; ; . 6. , , , , . 7. , ( ) . 8. , ( ) . 9. G1 G2. G1: S 0C | 1B B 0B | 1C | C 0C | 1C : a) L1L2 b) L1L2 c) L1 \{} d) L2 \ {} e) L1L
2

n

k

G2: S B C D



0D 0C 0D 0D

| | | |

1B 1C 1D | 1D

L1 L(G1),

L2 L(G2). ()

* *

, , .

100


/ II. , ,

10. , , . a) S 0S | 0B B 1B | 1C C 1C | c) S B C D aB aC | aD | dB aB


b) S 0B B 1C | 1S C

11. a) ; b) ; c) ; d) . S D A B 0S | DD 0B | 0A | S0 | D | 1A | 0

12. , . , , . . . a) S Sa | Ab | b A Ab | Sa | a S C A B S B C A S A B C C A1 | B1 | 1 A1 | C0 | 0 C0 | 0 B0 | C0 B0 | 0 C1 | A1 0 S1 | A0 B1 | C1 A0 C0 | 0 b) S Sb | Aa | a A Sb | a | b S A A Bb | a B Bb | b

c)

d)

e)

f)

S B C A

Bb | Cc Bb | Ab Cc | Ab a

g)

h)

S Sa | Cc | a C Bb B Sa | a

101


/ II. , ,

i)

S C A B S B C D



C A1 | B1 | 1 A1 | C0 | 0 C0 | 0 C B1 | 0 | D0 B1 | C1 D0 | 0

j)

S A A Bb | a B Bb | b

k)

l)

S C B D



C B1 0 | D0 B1

m)

S A0 A A0 | S1 | 0 S A0 | A1 | B1 | 0 | 1 A A1 | B1 | 1 B A0 S Sb | Aa | a | b A Aa | Sb | a

n)

S B0 | 0 B B0 | C1 | 0 | 1 C B0 S S0 | A1 | 0 | 1 A A1 | B0 | 0 | 1 B A0

o)

p)

r)

13. G L L1L2, L1 L2 . () G1, L1L2 (. 19 I). . S A B C A A0 | A1 | B1 B0 | C0 | 0 C1 | 1

14. G1 G2, L1 L2. G1: S S 1 | A0 A A1 | 0 G2: S A B C D E A1 | B0 | E 1 S1 C1 | D1 0 B1 E0 | 1

() a) L1 L2 ; b) L1 L2 ; c) L
1



L

2

(. 19 I).

.

102


/ III. . -

15. G1 G2 L1L1 (. 19 I ), L1 L(G1); G2 . G1: S S 1 | A1 A A0 | 0

16. () . "", "" "" (, .. . . ... ). , . .

III. . -
1. , - . . ) S cA | B | d A ab A | c | B bSc | aA b S aS B | bAf | A bAc | cS B cB | d S A B C bABCb | d aA | cB | Sc a {bb} b) S aA bc | A A bB | cBc B bcB | a | S aS B | bA A aS | cA | B bB | d S A B C aA b | cC a { bab } cAc | aB | Bb

c)

d)

e)

f)

g)

S aA {xx } A bA | cBx | B bSc S bS | aA B A bcA | ccA | B cb B | SA|B A bA | B cB | b |

h)

S aSc | bA | A cS{da}bA | d S a A S b | cf A d A bA | c | S AS | B Ab|c B dB | a |

i)

j)

k)

l)

2. , ( S -- ).

103


/ III. . - #include using namespace std; int c; // void S();// , void A(); ... void gc() {cin >> c;} // void S() { void A() { ... 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; } } ...} ...} // PC-

, . ?
a)
void S() { void A() { A(); if ( c != 'd') throw c; } }

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;} e lse A(); } void A () { if (c == 'b') gc(); else while (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 | aA B A bcA | ccA | B cbB | S Sa | Sb b | fA c A aB | d B ab B | Sb S E E ( ) | (E {, E}) | A Aa|b b) S aA Sb | cf A d A bA | c |

c)

d)

S cAd A Aa | bB B ab B | SP if PI| ET TF FP Ia| : E | if E then S | E then S else S I (E ) {T} {F} | (E) b

e)

f)

105


/ III. . -

g)

F function I(I ) S; I:E end S ; I:E S | E EI | EI | I S Ac | dBea A Aa | Ab | da Bc B cB |

h)

S SaAb | Sb | bABa A acAb | cA | B bB | S f ASd | A Aa | Ab | dB | f B bcB |

i)

j)

4. ? ( a ,( b , a ) , ( a ,( b ) ) , b ) . S k 0 E E A | ( k k1; if (k 3) ERROR( ); E {,E}) k k1 Aa|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 0 S | 1S | , , 101. 8. - L {a b c | m k n m k n}. 9. - L {1 0 1 | n p m, m 0}.
nmp mnk

106


/ III. . -

10. : S A 0; B 0 L {L} if (A 5) ERROR( ) L a A A1 | b B B1; if (B 2) ERROR( ) | c if (B 1) ERROR( ) ? (. 4) 11. : S E E ( ) | (E {, E}) | A Aa|b , : ; .

12. , : a) L , , S for I E step E to E do S , : I ; . . b) P program D; begin S {; S } end D ... | label L{,L} |... S L { , L } : S | S S ...| goto L |... LI 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 ; | S a 0; E cout << ; E a a 1; E cout << a ; | b if (a 0) cout << b; E cout << b ; |

b)

3. L1. L2 . . cout << . a) L1 { a c b | n0, m1}, { ( a c b , 0 1 b)
n nmn n nm * nmn

L2 { 0 1 | i 0, k i },

ik

) | n 0, m1 }; L2 { a c | n1, m 0 },
* nm

L1 { c | {a, b} , n1},
n nm

{ (c , a c ) | {a, b} , n 1, m a (.. m -- )}; c) L1 {a, b}, { (, 1 d) L2 { 1 0 | i 1, j 0; i j }, 0 ) | {a,b}, n a, m b };
n ij

nm n

L1 {a, b}, L2 { 2 | n 0, {a, b} }, { ( , 2 R ) | {a,b}, n
n a

( R -- ) };

e)

L1 {1 0 1 0 | m, n 0}, L2 {1 0 | k i 0}, { ( 1 0 1 0 , 1 0
nmmn m nm

nmmn

ik

) | m, n 0 }; L2 { | {a, b} }, i {ab, ba}, i b,

f)

L1 { 1 2 ... n | n 1, i {ab, ba} 1 i n },

{ ( 1 2 ... n , 1 2 ... n ) | n 1; 1 i n i ab , i a, i ba };

108


/ V. ,

4. L2 . . mn a) L 1 { 1 0 | n , m 0 }, { ( 1 0 , 1 b)
mn mn

L1. . L2 { 1 | k 0 } { 0 | i 0 } {},
mn nm k i

) | m n 0 } { ( 1 0 , 0

) | n m 0 } {( 1 0 , ) | m n };
i

mn

L1 {i | i 0 , i (i)

(.. i -- 2 ) },

L2 {(i)R | i 1 , i(i)2 (R -- ) }, { ( i, (i1)R ) | i 0 , i (i)2, i1(i1)2 } ; c) L1 { | {a, b} },
n

L2{ b | n 0, {a, b} },
* a

n



{ ( , b R) | {a, b} , n , R -- )}; d) L1{ | {a, b} }, { ( , a e)
[n/2]

( n --





L2{ a b | i, k 0, i k 0 },

ik

b

[m/2]

) | {a, b}, n a, m b ( [x] -- x -

, : [1/2] = 1, [1/3] = 0, [5/3] = 2)

};

L1{ | {a, b} }, { ( , a
[(n+1)/3]

L2{ a b | i, k 0, i k 0 }, ) | {a, b}, n a, m b };
i

ik

b

[ |m-n |/2]

f)

L1 { | {0,1}, (i)2 R, i 0 (. . -- i ) }, L2 { | | n 0 },
n

{ ( , | ) | {0,1}, (i)2 R, i 0 }.

5. , ( 0 1 , ). . 6. , , , , , , ( ) . ( ). . 7. , , ( ) . , b ( a , b ), a b c ( a , ( b , c )) .

V. ,
1. : ) a b c c) a /( b c ) a b) a b c / a d) ( a b ) / ( c a b ) 109


/ V. ,

e) a and b or c g) x y x / y

f ) not a or b and a h) ( x x y y 1 ) and ( x 0)

2. : ) ab c d) ab bc / a g ) 2x2x 3. , ) x y x y b) a 2b / c) a b not d) x y 0 b) abc / e) a not b and not / b 4 and a or not y 2 x a nd c) ab c f) a b c a and or and

: x 8, y 2; a 4, b 3; a b true; x y 1.

4. : a) b) c) d) e) f) g) h) i) j) k) S 0; i 1; while ( i 10) { S S ( i i ) ; i ; } if ( (x1) (2y) ) x y ; else y (xy)2; i 1; S 0; while ( i 10 && S 40 ) { S S f(i); i; } if (zxy5) a xy, z (x6)/(ay); else z y 2; a x y z(t x) ? (a b)/(cd)2 : x5; S x y; i 1; for (j 0; j n; j) { S S ijS; i ix; } i 1; S 0; while ( i 10 && S 40 ) { S S f(i); i; } if (zxy5) a xy, z (x6)/(ay); else z y 2; do {x y; y 2y;} while (x k); S 0; for (i 1; i k; i i 1) S ii; switch (k) { case 1: a ! a; break; case 2: b a || ! b; case 3: a b ; }

. ( ) . , for (expr1; expr2; expr3) {body} expr3 body. , , ( ). ( , , -), " ".

110


/ V. , , + # ­ # , + # ­ . , . -- . , -- .

5. ( ). a) x y z a x 5 y / z 6 8 ; 6.
1 y 19 2 15 20 ; 3 4 ; 22 y 5 x 23 2 6 x 24 7 a 25 8 b 26 ; 9 c 27 y 10 2 28 10 11 / 29 12 1 30 5 13 + 31 !F 14 * 32 15 33 16 * 34 17 a 35

b)

x a x z y / z 6 a

=
21 y

18

-

=

-

=

<=

(, 1): y 15; do {x x ( a b ( c /2 1 ) ) a ; y y 2 ;} while (y 10); , , . 7.
1 i 19 2 2 1 20 + 3 4 ; 22 5 i 23 * 6 n 24 5 7 < 25 + 8 36 26 9 !F 27 ; 10 a 28 i 11 a 29 i 12 b 30 2 13 + 31 + 14 1 32 15 16 x 34 5 17 y 35 ! 36

=
21 /

33 ;

18 y

-

=

=

: for ( i 1; i n; i i 2 ) a (a b 1)(xy /(y 2 ))5; , . 8. ) i b) xy 9. ) if b) xa : 10; s 0; while ( i 0 && s 40 ) { p + f ( i+s) ? i : s++ ; }; ( ). z a x 5 y / z 6 8

: (z x y 5 ) a x y ? (z x6): (z=ay); else z + y ; ( ). x z y / z 6 a

111


/ V. ,

10. : a) if ( E ) S1; S2; S3 : ; 0, S1 ; 0 -- S2, -- S3 . b) choice ( S1; S2; S3), E : ; i, Si i 1, 2, 3; choice . c) cycle ( E1; E2; E3), S for , S , , (.. 1 S, 3, -- 2, , for). 11. , , , , , / ( ). - . . 12. - -- . , . , , . 13. -, , E T {T} T F {F} F (E) | i , , (, a b c a ( b ) ( c ) . . . 14. , : E TE E TE | T FT T FT | F PF F ^ PF | P (E) | i . .

112



[1]. . . . -- .: , 1975. [2]. . , . , . . . -- .: , 1979. [3]. . , . . , . -- . 1,2. -- .: , 1979. [4]. . . . -- .: , 1977. [5]. . . . . -- .: , 1975. [6]. . . - . -- .: , 1970. [7]. . . . -- .: , 1975. [8]. . . . . -- .: , 1975. [9]. . . . - . -- .: , 1995. [10]. . . , . . , . . , . . . . . -- .:, 2006. [11]. . ., . , . . : , , . -- .: «», 2001. [12]. . , . , ., . . : , . -- .: «», 2008.

113



. . . ...................................................................................... 2 : .............................................................................................................. 2 ............................................. 3
.................................................................................................................................... 3 ......................................................................................... 3 ................................................................. 7 .......................................................... 7 ............................................................................................................... 9 ................................................................................................ 11 .......................................................................................................................... 12 -........................................................................................................ 12 - ..................................................................... 13 ( 0) .............................................................................. 13 .............................................................. 14 ........................................................................................................................ 15 .................................................................................................... 19 ................................................................... 19 ........................................................................ 19 ..................................................................................... 20 ..................................................... 20

............................................................................... 21
.................................................................................................................................. ...................................................................................... ....................................................................... ..................................................................................................... ....................................................................................... ....................................................................................................... .................................................................................................. -................................................................................ ........................................................................................................... ................................................................................................ ........................................ .................................................................. .................................................................. -.................................................................... - .......................................................................... - ........................................................................... ................................................................. ................................................................... ................................................................................ 114 21 22 24 27 28 34 35 37 47 48 52 53 65 66 67 74 81 81 85


- ....................................... 87 ................................................................ 89

..................................................................................................................... 93
I. . .......................................................... 93 II. , , ........................................... 99 III. . - ......................................... 103 IV. ............................................................................ 108 V. , .............................................................................................. 109

............................................................................................................ 113

115