next up previous
Next: About this document ... Up: Parsing (II) Previous: Bottom-up parsing

LR Parsers

KEY IDEAS.


THE LR PARSING PRINCIPLE

Figure 9: Model of an LR parser.
\begin{figure}\htmlimage
\centering\includegraphics[scale=.5]{LR-Parser-Model.eps}
\end{figure}
An LR-Parser uses These states are embedded with grammar symbols in a stack. More, precisely, after eahc iteration, the stack stores a word of the form s0X1s1X2 ... sm-1Xmsm where s0 is the end-of-stack symbol and sm is the state on top of the stack.

For a state s and a terminal a, the entry action[s, a] has one of the four following forms

Algorithm 10  

\fbox{
\begin{minipage}{13 cm}
\begin{description}
\item[{\bf Input:}] A LR-Pars...
...} \\
\> \> {\bf else} \\
\> \> \> {\bf error} \\
\end{tabbing}\end{minipage}}



next up previous
Next: About this document ... Up: Parsing (II) Previous: Bottom-up parsing
Marc Moreno Maza
2004-12-02