Derivation
tree:
PDAs as Models of Top-Down Parsers 2/2
Top-down construction of a derivation tree:
start
pushdown symbol
S
a1..ak
B
C
b1..bl
c1..cm
S
s
a1 … ak
b1 … bl
c1 … cm
C
B
s
ak … a1
a1 … ak
b1 … bl
c1 … cm
C
B
s
b1 … bl
c1 … cm
C
s
b1 … bl
c1 … cm
bl … b1
C
s
c1 … cm
s
c1 … cm
cm … c1
s
OK
OK
OK
Empty pushdown
46/50