# Top-Down Parsing

• Start with S
• Store immediate derivations in a stack
• Match characters to w

## Every time we pop from the stack…

• consumed input + reverse of stack = an intermediate step in our derivation

What does it mean? I don’t understand…

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

## Before we get started

• Augment our grammer to include ⊢ and ⊣
• Include a new state S' to begin our parsing

## Example

• w = $\vdash$abcdef$\dashv$
• The CFG is

\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.