Spread Knowledge

CS606 - Compiler Construction - Lecture Handout 29

User Rating:  / 0

Related Content: CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

Shift/Reduce Conflicts

Consider the ambiguous grammar

E → E + E | E × E | int

We will DFA state containg

[E → E × E•, +]
[E → E • + E, +]

Again we have a shift/reduce conflict. We need to reduce because × has precedence over +

Reduce/Reduce Conflicts

If a DFA states contains both [X → α •, a] and [Y → β •, a], then on input “a” we don’t know which production to reduce with. This is called a reduce-reduce conflict. Usually due to gross ambiguity in the grammar.

LR(1) Table Size

LR(1) parsing table for even a simple language can be extremely large with thousands of entries. It is possible to reduce the size of the table. Many states in the DFA are similar.

The core of set of LR items is the set of first components without the lookahead terminals. For example the core of the item { [X → α•β, b], [Y → γ•δ, d] } is { X → α•β, Y → γ•δ }. Consider the LR(1) states

{ [X → α •, a], [Y → β •, c] }
{ [X → α •, b], [Y → β •, d] }

They have the same core and can be merged. The merged state contains

{ [X → α •, a/b], [Y → β •, c/d]}

These are called the LALR(1) states. LALR(1) stands for LookAhead LR(1). This leads to tables that have 10 times fewer states than LR(1).

Here is the algorithm to generate LALR(1) DFA.

Repeat until all states have distinct code
choose two distinct states with same core
merge states by creating a new one with the union of all the items
point edges from predecessors to new state
new state points to all the previous successors

LALR languages are not natural. They are an efficiency hack on LR languages. Any reasonable programming language has a LALR(1) grammar. LALR(1) has become a standard for programming languages and for parser generators.