# Choosing correct action in bottom up parsing

Using grammar:

$$S \to aABe \\ A \to bcA \mid c \\ B \to b$$

to bottom parse a string $$abcccde$$, the course of action would be: $$\begin{array}{c|c|c|c} \hline Step & Stack & Input & Action \\ \hline 1 & \epsilon & abccde & Shift \\ 2 & a & bccde & Shift \\ 3 & ab & ccde & Shift \\ 4 & abc & cde & Shift \\ 5 & abcc & de & Reduce \, by \, A \to c \\ 6 & abcA & de & Reduce \, by \, A \to bcA \\ 7 & aA & de & Shift \\ 8 & aAd & e & Reduce \, by \, B \to d \\ 9 & aAB & e & Shift \\ 10 & aABe & \epsilon & Reduce \, by \, S \to aABe \\ 11 & S & \epsilon & Done \end{array}$$

My questions are:

1. At step 4, why do we choose to Shift rather than to reduce $$A \to c$$.
2. How would a parser decide which is correct to choose?

## 1 Answer

1. Because it will allow the string to be parsed. I know that is not a very satisfactory answer, but it really is the only answer. It is similar to asking why a particular step in a proof was chosen, and not some other step: because whoever wrote the proof (or, in this case, the derivation) somehow figured out how to do it.

2. That depends on the algorithm used by the parser. It might try one action, see if it works, and if not backtrack and try the next possibility. It might try both actions in parallel, reporting only the succesful one(s) at the end. It might have an analysis of the grammar that lets it know what to do in particular circumstances. You will probably see various different techniques as your course continues.