- Start with
`S`

- Store
**immediate derivations**in a**stack** - Match characters to
`w`

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

- Augment our grammer to include
`⊢`

and`⊣`

- Include a new state
`S'`

to begin our parsing

1 | Push S' onto the stack |

- 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}

$$

$$

\begin{aligned}

S’ &\rightarrow \,\vdash S \dashv \\

S &\rightarrow AcB\\

A &\rightarrow ab\\

A &\rightarrow ff\\

B &\rightarrow def\\

B &\rightarrow ed

\end{aligned}

$$

- Push
`S'`

onto the stack - Since stack is non-empty, $\alpha = S’$ = pop from stack. (Stack is empty now)
- $\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)

- Stack is non-empty. $\alpha= \, \vdash $ = pop from stack. (Stack becomes $ \dashv S $ now)
- $\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\,$)

- Stack is non-empty. $ \alpha= $ pop from stack = $S$.
- $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.

- Stack is non-empty. $\alpha = A$. (Stack = $\dashv Bc$)
- $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

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

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

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

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

- Stack is non-empty. $\alpha = B$. (Stack = $\dashv $)
- $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$. - Push $fed$ onto the stack. (Stack = $\dashv fed$)

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

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

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

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

)

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