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
s
a
®
a
s
to
R
;
for every
A
®
x
Î
P
in
G
:
add
x
s
®
A
s
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
#
S
s
®
f
that takes
M
to a
final state
f
40/50