G , . , A - a FIRST(). A , a. , = e *e. A , FOLLOW(A) $ $ FOLLOW(A).
4.6. .
. - G = (N, T, P, S).
. M[A, a] , A N, a T {$}.
. A 1 2. 3.
- a FIRST() A M[A, a].
- e FIRST(), A M[A, b] b FOLLOW(A). , e FIRST() $ FOLLOW(A), A M[A, $].
- .
4.5. 4.6 4.3. FIRST(TE') = FIRST(T) = {(, id }, E TE' M[E, (] M[E, id ] E TE'.
E' +TE' M[E', +] E' +TE'. E' e M[E',)] M[E', $] E' e, FOLLOW(E') = {), $}.
, 4.6 , . 4.3.
LL(1)-
4.6 -. . , , , .
, , LL(1)-. , LL(1)-, LL(1)-. L , , L , , 1 - .
, 4.6 LL(1)- G , L(G) . , G - LL(1)-, L(G) - -.
LL(1)-. G = (N, T, P, S) LL(1)- , A , A P (.. ) 2 :
- FIRST() FIRST() = ;
- e FIRST(), FIRST() FOLLOW(A) = .
, LL(1)-, LL(1)-. , , LL-, .
|
|
4.6. LL(1). G = ({S, E}, {if, then, else, a, b}, P, S) :
S if E then S | if E then S else S | a | |
E b | |
, . 4.6.
|
- , . , LL(1), LL(1)-. . . -, LL(1), , -, .
, .. A A , . A-:
i A.
A' - . A , , . , , . 4.7 .
4.7. .
. - G e- ( A e).
. - G' , G.
. 1 2.
- G .
- :
for (i=1;i<=n;i++){
for (j=1;j<=i-1;j++){
Aj 1 | 2 |... | k - Aj;
Ai Aj
Ai 1 | 2 |... | k ;
}
Ai Ai;
Ai;
}
(i - 1)- 2 Ak As , k < i, s > k. ( i) ( j) m Ai Am , m i. , Ai-, m i.
4.7 , e- ( A e). e- . e-.
O , , , A, A- , , .
A 1 | 2 - A- , , , . , A A'. , , A' 1 A' 2.
|
|
4.8. .
. - G.
. - G', G.
. A , . e, .. , A-
z , ,
A' - . , .
4.7. 4.6:
S if E then S | if E then S else S | a | |
E b | |
S if E then SS'| a | |
S' else S | e | |
E b | |
, , , LL(1).
- , . , ( , ), . , .
A , A ui, , ui *e (, , e), 1.1 1.2. 1.1 , FOLLOW(A). - . , , A.
void A(){ // A u1 | u2 |...| uk
if (InSym FIRST(ui)) // !
if (parse(ui))
result("A ui");
else error();
else
// 1:
if ( A ui , ui *e)
// 1.1
if (InSym FOLLOW(A))
result("A ui");
else error();
// 1.1
// 1.2:
result("A ui");
// 1.2
// 1
// 2:
if ( A ui , ui *e)
error();
// 2
}
boolean parse(u){ // u e!
v = u;
while (v e){ // v = Xz
if (X - a)
if (InSym a)
return(false);
else InSym = getInsym();
else // X - B
B();
v = z;
}
return(true);
}