LR Parsers

KEY IDEAS.

• The LR parsing method is the most general non-backtrackingshift-reduce parsing method known.
• LR parsers can parse a strictly larger class of grammars than (top-down) predictive parsers.
• LR parsers can usually recognize all programming language construct that can be specified by context-free grammars.
• LR parsers detect errors fast.
• Drawback: it is too much work to construct an LR parser by hand.
• Fortunately, we can use an LR parser generator such as YACC.

THE LR PARSING PRINCIPLE

Figure 9: Model of an LR parser.

An LR-Parser uses

• states to memorize information during the parsing process,
• an action table to make decision (such as shift or reduce) and to compute states
• a goto table to compute states

These states are embedded with grammar symbols in a stack. More, precisely, after eahc iteration, the stack stores a word of the form s₀X₁s₁X₂ ^... s_m-1X_ms_m where s₀ is the end-of-stack symbol and s_m 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

• shift s' where s' is a state,
• reduce  A  $\longmapsto$  $\beta$,
• accept,
• error.

Algorithm 10