Lecture No. 20
Dated: 09-04-2025
Bottom up Parsing
It is more general and preferred method in practice and is also called LR parsing.
Lmeanstokens1 are read from left to right.Rmeans theparser2 constructs aright most derivation.
These parsers2 don't need left factored grammar and can handle left recursion grammars.3
A derivation consists of a series of rewrite steps
\[S \implies \gamma_0 \implies \gamma_1 \implies \ldots \implies \gamma_{n - 1} \implies \gamma_n \implies \text{sentence}\]
- If \(\gamma\) contains \(\ge 1\)
non terminals4 then it is calledsentential form. - If \(\gamma\) contains only
terminals4 then it is called asentence.
These parsers2 work by starting from the sentence and working up to the start symbol.
Grammar
\[S \to aABe\]
\[A \to Abc | b\]
\[B \to d\]
Sentence
\[abbcde\]
Derivation
Right Most
\[S \to aABe\]
\[\to aAde\]
\[\to aAbcde\]
\[\to abbcde\]
Example
Grammar
E -> E + (E)
| int
Sentence
\[\text{int } + \text{(int) } + \text{(int)}\]
Derivation (right most)
\[E\]
\[E + (E)\]
\[E + (\text{int})\]
\[E + (E) + (\text{int})\]
\[E + (\text{int}) + (\text{int})\]
\[\text{int} + (\text{int}) + (\text{int})\]
Reduction would take place from the left side.
Shift Reduce Parsing
Bottom up parsers uses only 2 kinds of actions.
- Shift
- Reduce
