error(). . . .
A , , , FIRST(A), FOLLOW(A). A , - A .
, () , .
- -
- - , () (). w . , , , , (. 4.7). , LL(1)-, $.
|
, , , . , A , , A , .
, z - A z, , A z. , S r* A r , A , , . .
, , . , . . , w. w - , w = n, n - n- S = 0 r 1 r... r n-1 r n = w.
|
|
, n n n An n, (n - 1)- n-1. , .. n-1 n-1 , n-2. , , , S, . , , .
, - - .
LR(1)-
LR(1) L , -, R - , , , 1 , .
LR(1)- :
- LR(1)- - -;
- LR(1)- ;
- LR(1)- ;
- , LR(1)-, , (- LL(1)).
LR(1)- . 4.8. , , , (LR(1)-), - (Action) (Goto). LR(1)-, .
. , S0X1S1X2S2...XmSm (Sm - ). Xi - ( ), Si - .
, ( ) . , LR-.
|
Action[Sm, ai] Sm ai T {$}, :
- shift S (), S - ,
- reduce A ( A ),
- accept (),
- error ().
Goto[Sm, A] Sm A N, :
- S, S - ,
- error ().
LR(1)- , - , - :
, , . . , - , .
|
|
S0, - .
ai Sm .
LR(1)-
:
- Action[Sm, ai] = shift S, ,
, ai S, Action[Sm, ai]. ai+1.
- Action[Sm, ai] = reduce A , ,
S = Goto[Sm-r, A] r - , .
2r (r r ), Sm-r. A - , S - , Goto[Sm-r, A]. . LR(1)- Xm-r+1...Xm - , , - , .
LR(1)-, .. , , , , , .
, Goto , G, , G.
- Action[Sm, ai] = accept, .
- Action[Sm, ai] = error, , .
4.8. G = ({E, T, F}, {id, +, *}, P, E) :
(1) E E + T | |
(2) E T | |
(3) T T * F | |
(4) T F | |
(5) F id | |
. 4.9 Action Goto, LR(1)- . Si Action i, Rj - j, acc - , - . Goto i i, - .
id + id * id . 4.10. , LR- id. S6 id Action (. 4.9) 6 . : id 6 , id .
| ||
|
+, 6 + F id. ( ). . Goto F - 3, F 3 . , . .