PDAs
as Models of Top-Down Parsers 1/2
1)
M
contains
popping
rules that pops the
top
symbol from the
pushdown and reads the
inp
ut
symbol if both coincide:
for every
a
Î
S
:
add
a
s
a
®
s
to
R
;
x
y
s
2)
M
contains
expansion
rules that simulate the
application of a grammatical rule:
A
s
y
s
y
a
n
…
a
1
a
s
y
x
a
for every
A
®
a
1
…a
n
Î
P
in
G
,
add
A
s
®
a
n
…a
1
s
to
R
;
= reversal(
a
1
…a
n
)
Gist: An
PDA
M
underlies a
top-down
parser
45/50