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 input symbol if both coincide:
for every a Î S:
add asa ® s to R;
x
y
s
2) M contains expansion rules that simulate the
    application of a grammatical rule:
A
s
y
s
y
an  …  a1
a
s
y
x
a
for every A ® a1 …an Î P in G, add As ® an …a1s to R;
= reversal(a1 …an)
 Gist: An PDA M underlies a top-down parser
45/50