Top-Down Parsing


Top-Down Parsing

Every time we pop from the stack…

What does it mean? I don’t understand…

Don’t worry. We will see an example shortly.

Before we get started

Show me the code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Push S' onto the stack
while stack is non-empty do
a = pop from stack
if a is a non-terminal symbol or S' then
Push symbols of b of a valid production rule a -> b in reverse order on the stack
else
c = read_char()
if c != a then
Reject
end if
end if
end while
if read_char() = EOF then
Accept
else
Reject
end if

Example

$$
\begin{aligned}
S &\rightarrow AcB\\
A &\rightarrow ab\\
A &\rightarrow ff\\
B &\rightarrow def\\
B &\rightarrow ed
\end{aligned}
$$

Preparation

$$
\begin{aligned}
S’ &\rightarrow \,\vdash S \dashv \\
S &\rightarrow AcB\\
A &\rightarrow ab\\
A &\rightarrow ff\\
B &\rightarrow def\\
B &\rightarrow ed
\end{aligned}
$$

Iteration 1

  1. Push S' onto the stack
  2. Since stack is non-empty, $\alpha = S’​$ = pop from stack. (Stack is empty now)
  3. $\alpha$ is S'. We have the production rule $S’ \rightarrow \, \vdash S \dashv $. We push symbols $\vdash S \dashv $ in reverse order on the stack. (Stack looks like $ \dashv S \vdash$ now)

Iteration 2

  1. Stack is non-empty. $\alpha= \, \vdash $ = pop from stack. (Stack becomes $ \dashv S $ now)
  2. $\alpha$ is a terminal symbol, so we must read a char. The char read is $\vdash$. We go on to the next iteration because the char read matches $\alpha$. (The remaining $w= abcdef\,\dashv\,$)

Iteration 3

  1. Stack is non-empty. $ \alpha= $ pop from stack = $S$.
  2. $S$ is non-terminal. The production rule with $S$ on the LHS is $S\rightarrow AcB$. We push the RHS onto the stack in reverse order. (Stack looks like $\dashv BcA$. Then go on.

Iteration 4

  1. Stack is non-empty. $\alpha = A​$. (Stack = $\dashv Bc​$)
  2. $A$ is non-terminal. We have $A \rightarrow ab$ and $A\rightarrow ff$

As a human, we want to choose the rule $A\rightarrow ab$. Since the first char is $a$

But as for an algorithm, we will see later a way to determine which rule to apply

  1. Push $ba$ onto the stack. (Stack = $\dashv B c b a ​$)

Iteration 4

Stack is non-empty. $\alpha = a$ is a terminal symbol. The char matches it so we keep going. (Stack = $\dashv B c b$)

Iteration 5

Stack is non-empty. $\alpha = b$ is a terminal symbol. The char matches it so we keep going. (Stack = $\dashv B c $)

Iteration 6

Stack is non-empty. $\alpha = c$ is a terminal symbol. The char matches it so we keep going. (Stack = $\dashv B $)

Iteration 7

  1. Stack is non-empty. $\alpha = B$. (Stack = $\dashv $)
  2. $B$ is a non-terminal symbol and there is a rule $B\rightarrow def$ and $B\rightarrow ed$. We choose the rule $B\rightarrow def$.
  3. Push $fed$ onto the stack. (Stack = $\dashv fed$)

Iteration 8

Stack is non-empty. $\alpha = d​$ is a terminal symbol. The char matches it so we keep going. (Stack = $\dashv fe​$)

Iteration 9

Stack is non-empty. $\alpha =e $ is a terminal symbol. The char matches it so we keep going. (Stack = $\dashv f$)

Iteration 10

Stack is non-empty. $\alpha =f ​$ is a terminal symbol. The char matches it so we keep going. (Stack = $\dashv ​$)

Iteration 11

Stack is non-empty. $\alpha =\dashv $ is a terminal symbol. The char matches it so we keep going. (Stack = Empty)

Iteration 12

Stack is empty and we read all the chars. Hence, accept.