.
, . ( , ) :
à
à
à
à
à
à .
, , . .
, (, ), , , . (-). .
, , , [1, 2, 3, 4, 5, 8].
P program D1; B^
D1 var D {,D}
D I {,I}: [ int | bool ]
B begin S {;S} end
S I:= E | if E then S else S | while E do S | B | read (I) | write (E)
E E1 [ = | < | > |!= ] E1 | E1
E1 T {[ + | - | or ] T}
T F {[ * | / | and ] F}
F I | N | L | not F | (E)
L true | false
I C | IC | IR
N R | NR
C a | b |... | z | A | B |... | Z
R 0 | 1 | 2 |... | 9
:
a) {a} a, .. e, a, aa, aaa ..
b) [ a | b ] , a, b.
c) P - ; ^ - .
:
1. , , .
2. .
3. .
4. .
5. ; .
, , , {< , } ^ >}.
True, false, read write - ( , ).
, .
|
|
, . , .
: , , .
, G = (VT, VN, P, S) , A Bt A t, A Î VN, B Î VN, t Î VT.
: , ^ - .
, , ( ):
(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) , , .. , , . . .
, .
, , ( ).
, , - . - , "-", .
, G = ({a, b, ^}, {S, A, B, C}, P, S), :
|
|
a | b | ^ | |||
P: S C^ | C | A | B | S | |
C Ab | Ba | A | - | C | - | |
A a | Ca | B | C | - | - | |
B b | Cb | S | - | - | - |
"-" , "-" .
() - , :
(1) , ( - ), , , (, H). . H - .
(2) :
a) W t H W ( H W) t;
) W Vt V W ( V W) t;
G (. ):
:
(1) H;
(2) ( , ) : , . , , .
( , ):
(1) ; , ; S. , L(G).
(2) ; "" ; , S. , L(G).
(3) , . , L(G).
(4) , , , , . . .
, , , , . - , - . (, ) ( , ).
: () - (K, VT, F, H, S),
K - ;
VT - ;
F - K ´ VT K, ; F ;
H Î K - ;
S Î K - ( ).
F(A, t) = B , A t B.
: a1a2...an, F(H,a1) = A1; F(A1,a2) = A2;...; F(An-2,an-1) = An-1; F(An-1,an) = S, ai Î VT, Aj Î K,
j = 1, 2,...,n-1; i = 1, 2,...,n; H - , S - .
|
|
: , , .
:
a) , , , ;
b) , , , .
c) (ER); , .
.
, G = ({a,b, ^}, {S,A,B,C}, P, S),
P: S C^
Ab | Ba
A a | Ca
B b | Cb
:
#include <stdio.h>
int scan_G(){
enum state {H, A, B, C, S, ER}; /* */
state CS; /* CS - */
FILE *fp;/* , */
int c;
CS=H;
fp = fopen ("data","r");
c = fgetc (fp);
do {switch (CS) {
case H: if (c == 'a') {c = fgetc(fp); CS = A;}
else if (c == 'b') {c = fgetc(fp); CS = B;}
else CS = ER;
break;
case A: if (c == 'b') {c = fgetc(fp); CS = C;}
else CS = ER;
break;
case B: if (c == 'a') {c = fgetc(fp); CS = C;}
else CS = ER;
break;
case C: if (c =='a') {c = fgetc(fp); CS = A;}
else if (c == 'b') {c = fgetc(fp); CS = B;}
else if (c == '^') CS = S;
else CS = ER;
break;
}
} while (CS!= S && CS!= ER);
if (CS == ER) return -1; else return 0;
}