LL(1) 
< 
LR(1) 
LL(2) 
< 
LR(2) 
LL(3) 
< 
LR(3) 
... 
n =*=> \alpha ==
n ==> \alpha_1 ==> \alpha_2 ==> ...==> \alpha_n = \alpha.
\a1 [p1] \a2 B \a3
\a1 A \a2 B \a3 > \a1 \b \a2 B \a3
 
\a1 A \a2 [p2] \a3   \a1 \b \a2 [p2] \a3
 
v v
\a1 A \a2 \c \a3 > \a1 \b \a2 \c \a3
\a1 [p1] \a2 \c \a3
n =*=> \alpha ==we can transform it into a leftmost or rightmost derivation by looking at successive steps and transforming them into leftmost or rightmost form (respectively):
n ==> \alpha_1 ==> \alpha_2 ==> ...==> \alpha_n = \alpha
Every derivation has a unique equivalent rightmost and leftmost normal form.
s' > s.
r_1 s > (s)s r_2 . r_3 
s' ========> s =========> (s)s ======> (s) ====> ()r_1 r_2 (r_3)s ()r_3
A grammar is LR(k) if given any right sentential form \alpha \beta \gamma where \gamma is a list of terminals and b > \beta is a production,
 Whether \alpha [b > \beta] \gamma is a handle can be determined from knowledge of \alpha and (at most) the first k tokens of \gamma,
 Every right sentential form has at most one handle.
shift[t]: (\alpha, t
\gamma)
> (\alpha t, \gamma) 
reduce[a > \b]:
(\alpha
\b , \gamma) > (\alpha a, \gamma) 
accept: (start, \epsilon)
> STOP 
reject: (\alpha, \gamma)
> FAIL 
s' > s
r_1 s > (s)s r_2  r_3 
Parse Stack 
Input 
Action 
"()" 
shift[(] 

( 
")" 
reduce(r_3) 
( s 
")" 
shift[)] 
( s ) 
"" 
reduce(r_3) 
( s ) s 
"" 
reduce(r_2) 
s 
"" 
reduce(r_1) 
s' 
ACCEPT 
{ a > \alpha . \beta  a > \alpha ++ \beta is a production of G}
x [ a > \a . x \b ] > [ a > \a x . \b ] 
[ A > \a . x \b
]
~~~~~~~~~~> [ x > .\d ] 
a > ( a )  A 
a' > a a > ( a )  A 
a' > . a 

a' > a . 
completed 
a > . (a) 

a > ( . a) 

a > (a . ) 

a > (a) . 
completed 
a > .A 

a > A. 
completed 
S0 = a' > . a
 a > . A a > . ( a ) 
S1* = a' > a .
 
S2 = a > A .
 
S3 = a > ( . a )
 a > . A a > . ( a ) 
S4 = a > ( a . )
 
S5* = a > ( a ) .

STACK 
INPUT 
ACTION 
S0 []> S0 
"((A))" 
shift 
S0 [(]> S3 
"(A))" 
shift 
S0 [((]> S3 
"A))" 
shift 
S0 [((A]> S2 
"))" 
reduce[a>A] 
S0 [((a]> S4* 
"))" 
shift 
S0 [((a)]> S5* 
")" 
reduce[a>(a)] 
S0 [(a]> S4

")"

shift 
S0 [(a)]> S5* 
"" 
reduce[a>(a)] 
S0 [a] > S1* 
"" 
reduce[a'>a] = accept 
e > e ADD t  t. t > f MUL t  f. f > VAR. 
e > t e+. e+ > ADD t e+ . t > f t+. t+ > MUL f t+ . f > VAR. 
S > ( S ) . 
S > ( S ) . 
S0 = s' > . s
 s > . (s) s > . 
S1 = s' > s
 
S2 = s > ( . s)
 s > . (s) s > . 
S3 = s > (s . )
 
S4 = s > (s) .
 
A grammar is an SLR(1) grammar if and only if in the for any state S in the LR(0)item automaton of the grammar the following two conditions are satisfied:
 For any item [a > \alpha . X \beta] in S (where X is terminal) there is no completed item [b > \beta .] in S with X in follow(b).
 For any two completed items [b > \beta.] and [b' > \beta'.] in S the sets follow(b) and follow(b') are disjoint.
e > e ADD t  t. t > t MUL f  f. f > VAR. 
stmt > call_stmt  assign_stmt. call_stmt > ID. assign_stm > var ASSIGN exp. var > var LSPAR exp RSPAR  ID. exp > var  NUM. 
s > a
A a B  b B b A. a > . b > . 
X
[(A > \a . X \b,t)
] > [(A
> \a X. \b,t)]

[ (A > \a . X \b,t)
] ~~~> [ (X
> .\d,t') ] 
X
[ (A > \a. X
\b,T) ]
> [ (A > \a X. \b,T') ]

[ (A > \a. X \b,T) ]
~~~~~~~> [ (X
> .\c, T') ] 
s > a A  B a C  D C  B D A. a > D. 
 s > . a A s > . B a C s > . D C s > . B D A a > . D 
S1* = s' > s .
 
S2 = a > D .
s > D . C  
S3 = s > B . a C
s > B . D A  a > .D 
S4* = s > D C .
 
S5* = a > B D . A
 a > D . 
S6* = a > B D A.
 
S7 = s > B a . C
 
S8* = s > B a C .
 
S9 = s > a . A
 
S10 = s > a A .
 
 s > . a A $ s > . B a C $ s > . D C $ s > . B D A $ a > . D A 
S1* = s' > s . $
 
S2 = a > D .
A
s > D . C $  
S3 = s > B . a C
$
s > B . D A $  a > .D C 
S4* = s > D C . $
 
S5* = s > B D . A
$
 a > D . C 
S6* = s > B D A.
$
 
S7 = s > B a . C
$
 
S8* = s > B a C .
$
 
S9 = s > a . A $
 
S10 = s > a A .
$
 
e > e ADD t  t. t > t MUL f  f. f > VAR. 
e' > e e > e ADD t  t. t > t MUL f  f. f > VAR. 
NT 
First 
Follow 
f 
{ VAR} 
{MUL,ADD.$} 
t 
{VAR} 
{MUL,ADD,$} 
e 
{VAR} 
{ADD,$} 
e' 
{VAR} 
{$} 
STACK 
INPUT 
ACTION 
s0 
"VAR ADD VAR MUL VAR ADD
VAR" 
shift 
s0[VAR]s5 
"ADD VAR MUL VAR ADD VAR" 
reduce[f
> VAR] 
s0[f]s7 
"ADD VAR MUL VAR ADD VAR" 
reduce[t
> f] 
s0[t]s6 
"ADD VAR MUL VAR ADD VAR" 
reduce[e
> t] follow(e) = {ADD,$} 
s0[e]s1 
"ADD VAR MUL VAR ADD VAR" 
shift[ADD] follow(e') = { $ } 
s0[e]s1[ADD]s2 
"VAR MUL VAR ADD VAR" 
shift[VAR] 
s0[e]s1[ADD]s2[VAR]s5 
"MUL VAR ADD VAR" 
reduce[f
> VAR] 
s0[e]s1[ADD]s2[f]s7 
"MUL VAR ADD VAR" 
reduce[t
> f] 
s0[e]s1[ADD]s2[t]s3 
"MUL VAR ADD VAR" 
shift[MUL] follow(e) = {ADD,$} 
s0[e]s1[ADD]s2[t]s3[MUL]s4 
"VAR ADD VAR" 
shift[VAR] 
s0[e]s1[ADD]s2[t]s3[MUL]s4[VAR]s5 
"ADD VAR" 
reduce[f
> VAR] 
s0[e]s1[ADD]s2[t]s3[MUL]s4[f]s8 
"ADD VAR" 
reduce[t
> t MUL f] 
s0[e]s1[ADD]s2[t]s3 
"ADD VAR" 
reduce[e
> e ADD t] 
s0[e]s1 
"ADD VAR" 
shift[ADD] follow(e') = { $ } 
s0[e]s1[ADD]s2 
"VAR" 
shift[VAR] 
s0[e]s1[ADD]s2[VAR]s5 
"" 
reduce[f
> VAR] 
s0[e]s1[ADD]s2[f]s7 
"" 
reduce[t
> f] 
s0[e]s1[ADD]s2[t]s3 
"" 
reduce[e
> e ADD t] 
s0[e]s1 
"" 
accept follow(e') = { $ } 