EPDAs as Models of Bottom-Up Parsers 1/2
 Gist: An EPDA M underlies a bottom-up parser
1) M contains shift rules that copy the input symbols
    onto the pushdown:
a
s
y
x
for every a Î S:
add sa ® as to R;
for every A ® x Î P in G: add xs ® As to R;
a
s
y
x
2) M contains reduction rules that simulate the
    application of a grammatical rule in reverse:
s
y
x
A
s
y
3) M also contains the rule #Ss ® f that takes M to a
    final state  f
40/50