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.