, LR(1)-.
G = (N, T, P, S) - -. G -
.. , S' S' S.
, , . , , S' S.
LR(1)- [A . , a], A - , a - $. .
, LR(1)- [A . , a] , S r* Aw r w, = a - w, w = e a = $.
, , - .
4.9. G = ({S, B}, {a, b}, P, S)
S BB | |
B aB | b | |
S r*aaBab raaaBab. , [B a.B, a] = aaa, = aa, A = B, w = ab, = a, = B. S r*BaB rBaaB. Baa [B a.B, $].
, , . , . , , .
, - -, . . LR-. , , , .
[A .B , a] , z. S r*yAax ry B ax, z = y . , ax bw. B q S r*zBbw rzqbw. [B .q, b] z [A B. , a] zB. b , , e ax r*bw b a. .. b FIRST( ax). , .. , closure.
|
|
LR(1)- LR(1)-. .
4.9. LR(1)-.
. - G = (N, T, P, S).
. C LR(1)- G.
. G' items, closure goto.
function closure(I){ /* I - */
do{
for ( [A .B , a] I,
B G',
b FIRST( a),
, [B . , b] I)
[B . , b] I;
}
while ( I );
return I;
}
function goto(I,X){ /* I - ;
X - */
J = {[A X. , a] | [A .X , a] I};
return closure(J);
}
procedure items(G'){ /* G' - */
I0 = closure({[S' .S, $]});
C = {I0};
do{
for ( I C,
X ,
goto(I, X) C)
goto(I, X) C;
}
while ( C );
I - , , goto(I, X) - , X.
C LR(1)- , C I0 = closure({[S' .S, $]}). goto C. -, goto(I, X) - I X.
, LR(1)- LR(1)-, .. LR(1)-.
4.10. LR(1)-.
. C = {I0, I1,..., In} LR(1)- G.
. Action Goto, LR(1)- G.
. i Action[i, a] Goto[i, X] Ii:
- (Action) i :
- [A .a , b] Ii (a - ) goto(Ii, a) = Ij, Action[i, a] = shift j;
- [A ., a] Ii, A S', Action[i, a] = reduce A ;
- [S' S., $] Ii, Action[i, $] = accept.
- i : goto(Ii, A) = Ij, Goto[i, A] = j ( A - ).
- Action Goto, 2 3, error.
- , [S' .S, $].
Action Goto, 4.10, LR(1)-. LR(1)-, , LR(1)-.
|
|
4.10. , 4.8:
(0) E' E | |
(1) E E + T | |
(2) E T | |
(3) T T * F | |
(4) T F | |
(5) F id | |
goto . 4.11. LR(1)- . 4.9.
|
LR(1)-
- G Action, 4.10, , LR(1)-.
L LR(1)-, LR(1)-.
LR(1)-. LR(1),
1. S' r*uAw ruvw,
2. S' r*zBx ruvy,
3. FIRST(w) = FIRST(y)
, uAy = zBx (.. u = z, A = B x = y).
, uvw uvy - , FIRST(w) = FIRST(y) A v - , uvw, A v uvy uAy. A v w, LR(1)- , FIRST(w) , , uv uA. , .
, .
LR(1), - , , , , ( /), , ( /).
, LR(1).
(1) S ru1 r... run rw,
(2) S rv1 r... rvm rw.
, LR(1)- ( LR(1)-) i, un-i vm-i.
4.11. :
S if E then S | if E then S else S | a | |
E b | |
- , else...$, ...if E then S, , if E then S , , . /. , else, S if E then S else, S if E then S else S. , , LR(1).
LR(1)- :
S M | U | |
M if E then M else M | a | |
U if E then S | if E then M else U | |
E b | |
LL(1)- LR(1)- . LR(1), , , . , LL(1)-, , , . , LL(1)- LR(1)-.
[2].
4.5. LR(1)- -.
|
|
4.6. L - -, LR(1)-, L.