1 , .. . Þ.
, dÞh , h d .
. d=aAb h=anb. , a,n,b - ( ), . : An. N n. , d h.
2 . Þ*
, a0 Þ*an
, a0 = an, , a0 Þ a1 Þ a2 Þ an-1 Þ an
, L(G), G. L(G) w ( !) , (, ) S. L(G)={w|S Þ*w,w }.
w , w S. , . P , G.
.
1 G=(T,N,P,S)
T={x, y, w, z} . .
N={S, A, B} , S () . () P.
p={SAB, Ax,Ay, Bw, Bz}.
, S AB. Ax, Ay , x y .., , w , L(G).
L(G)={xw, yw, xz, yz}.
() , G.
.. . , , .
Ai ri,
Ai N i- ,
ri i- N U I.
() .
, , , :
SAB,
Ax|y,
Bw|z.
, . x y, w z.
2
={, , , , , , }
N={, , , }
|
|
Į
|
|
|
. , , . , , .
, , .
, .
.
, * , . .
.
, + * , , . .
: * +
. .
, , () .
2
() . , , . , .
, [[x]] L(G2), G2.
G2=(T2, N2, P2, A),
T2 = {, +, [, ]}
N2 ={,}
P2 = {, [], ®, ®+}
, , , 2.
Þ []Þ []Þ [[]]Þ [[]]Þ [[]]
, [[]] L(G2).
: . , w.
[[]] G2 . : []. [[]]. [], []. .
+.
, [] []. []. [] []. [[]]. [[]] . [[]]. , , . [[]] [[]]. , , , G2.
V ai w, Þ* nVb V n V a1, V a2, V an V. , , L(1) , V ai w.
|
|
LA(1) . , , .
LA(1) . ().
: , , , .
. N a, a - T U N, . , , .
.
.
, , a.
1
L(1) , .
.
, , (.. ) ( ).
, , , . , , .. Þ* w, , , w, .
3
.
, () ) .
( , .), (.. - ), .
- , .
, .
, , , , - () . , -, , ( ). - . .
, . , .
, , .
|
|
2
. . :
;
;
;
;
.
.
.
.
, .
() .
:
1) ;
2) ;
3) , ;
4) ;
5) .
, () . , - if, do, while, for, return, goto, char, int, float . - .
, . , + . , . , , (, ), ( main .), .
(, ) . . , . , , .
.
- - . , , - . . , , , , ..
4
SPL
. , , , , SPL. SPL (Simple Programming Language) . , . , .
SPL, , .
1) : A¸Z, a¸z ( );
2) : Ƹ9;
3) : +, -, *, /, %, (, ),,, =,\ ,\n,\t 13 .
|
|
SPL.
, . , . 1 40, (\ ), (\n) (\t) .
.
const. , = ( ) ( ). . .
, onst a=12, b=4, d=0;
, . . , , , .
:
int __1, __2;
, int x, y, z, teta;
+, -, * (), / (), % ( ).
, , . 11 : begin, end, read, print, return, if, then, while, do, int, const.
, SPL . , main, .. .
:
_ (_ )
begin
;
end
end .
. end . if :
if then end
. , then end. - if .
:
while do
End
if . , do end. . £ 0, .
SPL return , , - . , SPL , .
SPL, , main(), b. exp ().
exp (, b)
begin
int z;
z=1;
while b do
if b %2 then z=z*a end;
a=a*a;
b=b/2
end;
return z
end
main ()
begin
int x, y;
read x;
read y;
print exp (x, y)
end
x, y. print exp (x, y) exp (), a b x y. exp () return z main () , .
ab , 27.
5
, (!) SPL, TNM.
char TNM [400];
:
1) ;
2) ;
3) ;
4) ;
5) .
. + , - , * , / , % , = , ( , ) , , , ; .
ASCII (. , . , . .- : ,1988.- .512).
|
|
ASCII . 256 .
. L . , if while IFL, WHILEL .. .
enum {BEGINL=257, ENDL, READL, PRITL, RETRL, IFL, THENL, WHILEL, DOL, INTL, CONSTL, NUMB, IDEN };
NUMB ;
IDEN .
enum {}, BEGINL 257, ENDL 258 .. , , BEGINL 257, ENDL 258. , , BEGINL, ENDL .., 257, 258 ..
EOF. stdio.h #define EOF 1. , EOF 1.
SPL part1.c.
. enum {} .
int lex; // ( )
int lval; // . , TNM
int nst=0; // SPL
char nch=\n; // SPL
char TNM [400]; //
char * ptn=TNM; //
.
TNM [0], .. TNM
(.. )
.
FILE * PF; // SPL
FILE * padres // ,
TNM.
part1.c main () . main () :
void main (int av, char * av [ ])
ac ( );
char* av [ ] . .
, av [0] (, part1.exe).
av [1] SPL. , var2.s
, Borland C++, Run/arguments Enter. , . var2.s. Enter. , var2.s . Borland C++ , , , C:\\USER\\SPL\\var2.s part1.s ¿
part1.c, - .
-
void main (int ac, char * av [ ])
ac. , , part1.exe av [0] var2.s av [1]. , . SPL. var2.s, av [1]. , get (), .
|
|
|
|
|
{ lex=EOF;
return;
}
part1.c , SPL, , char TNM [400]. get () 1 while (nch!=EOF). SPL . while(isspace(nch)), , , .
nch, get (), , number() word().
nch , , (, ), + .., , ( 1). .
- void number ()
1 for (). lval . , nch - . , lval 2, lval 10, (nch) . ASCII 10 48, 1 49, 2 50 .. 16- (30)16, (31)16, (32)16 ..
, .
, SPL 541.
5 number (). lval=0. nch 5, .. (35)16. , , nch , . 2. lval=10*0+(35)16 (30)16 =5. nch. (34)16 4.
2 lval=10*5+(34)16 (30)16 =54.
1 lval=10*54+(31)16 (30)16=541.
, , . NUMB, .
- void word ()
2 for. p tx[0]. , nch . , 3. p, .. tx[0] nch. p 1, tx [1]. . nch. , 2. nch tx [1], tx [2] .. nch , . tx \0 . tx . , . () , char*serv []
( 5 6). tx lex int cdl [ ].
, tx end, end serv[1]. lex=ENDL, .. lex=258 (. enum={BEGINL=257, ENDL};).
, . lex=IDEN, .. 269, char TNM [400]. add (tx). char*. , int lval, lval=(int) add (tx).
- char*add(char*nm)
add (char*nm) nm tx ( - ). 2 3 , TNM . char*p. 2 p TNM, .. TNM [0]. p<ptn. , char*ptn TNM. p<ptn, , TNM add (). , . TNM \0.
p+=strlen (p) +1.
p<ptn ..
p<ptn , , TNM . ptn .
ptn+=strlen(nm)+1.
, , ptn TNM.
if ((ptn+=strlen(nm)+1)>TNM+400)
{
puts( TNM);
exit (1);
}
return (strcpy(p, nm));
, strcpy(), nm , word().
6