LR(k) -, -. G , G(VT,VN,P,S), :
G G, S G;
G G(VT,VN{S},P{SS},S), S G.
- , . , G S, , SS. , G G, L(G) = L(G).
LR(k) .
- G G :
1) S * αAw αβw,
2) S * γ αβy,
3) FIRST(k,w) = FIRST(k,y)
, αAw = γ ( α = γ, = = ), , G LR(k) . , G LR(k) .
, - S ( S ). , , . -, , LR(k)- .
LR(k)- . , . , . k (), ; , ( ).
|
|
:
( );
S ;
() ( , );
.
, , . , , . , . , , .
, . :
;
.
LR(k)- . , . , . S ( ) , .
LR(k)- :
1. () . . 2.
2. . , . 3.
3. :
, , , ;
() , , , ;
, ;
S, , , , .
. 4.
4. . , . 5.
|
|
5. , , ( ) . 2.
( ), , . , .
, . , LR(k)- , .