• Input: LR-table for G=(N, T, P, S); x Î T*
• Output: Right parse of x if x Î L(G); otherwise, error
• Method:
• push(<$, q0>) onto
pushdown; state :=
q0;
• repeat
• let a = the current token
case a[state, a] of:
• sq: push(<a, q>) &
read next a from input
string &
state := q;
• rp: if
p: A ® X1X2… Xn Î P and
<?, q><X1,?><X2,?>…<Xn,?> is pushdown
top
then state := b[q, A] &
replace <X1,?><X2,?>…<Xn, ?> with <A, state>
on the pushdown & write r to output
else error
• J: success
• blank: error
until success or error