LALR 1 Parsing | Compiler Design

LALR (1) Parsing

The LALR parsing refers to the "lookahead LR" that has many lesser steps than typical parsers based on LR(1) items. For constructing the LALR(1) parsing table, the canonical collection of LR(1) items is used. In the LALR(1) parsing, the LR(1) items with the same productions but have different lookahead are grouped together to form a single set of items. It is generally the same as CLR(1) parsing except for the one difference that is the parsing table.

Example

Suppose we have the following grammar:

E => BB
B => cB / d

Then add augment production and insert '.' symbol at the beginning of every production in the grammar G.  Next, add the lookahead also.

E’ => .E, $

E => .BB,$

B => .cB, c/d

B => .d, c/d

I0 state

Add starting production to the I0 State and Compute the Closure.

I0 = closure (E’ => .E)

Add all the production beginning with E into I0 State because "." is at the first place of production before the non-terminal. So, the I0 State becomes:

I0 = E’ => .E, $

    E => .BB, $

Add all the production beginning with "B" in modified I0 State because "." is at the first place of production before the non-terminal. So, the I0 State becomes:

E’ => .E, $

E => .BB, $

B => .cB, c/d

B => .d, c/d

I1 = Go to on (I0 E) = closure (E’ => E., $)

I1 = E’ => E., $

I2 = Go to on (I0 B) = Closure (E => B.B, $)

Add all the productions beginning with B into I2 State because "." is at the first place of production before the non-terminal. So, the I2 state becomes:

E => B.B, $

B => .cB, $

B => .d, $

I3 = Go to on (I0 c) = Closure (B => c.B, c/d)

 Add productions beginning with B in I3.

B => c.B, c/d

B => .cB, c/d

B => .d, c/d

Goto on (I3 c) = Closure (B => c. B, c/d)                       (Same as I3)

Goto on (I3 d) = Cllosure (B => d., c/d)                            (Same as I4)

I4 = Goto on (I0 d) = Closure (B => d. , c/d) = B => d. , c/d

I5 = Goto on (I2 B) = Closure (E => BB. , $) = E => BB. , c/d

I6 = Goto on (I3 c) = Closure (B =>c.B, $)

Add all productions beginning with B into I6 State because "." is at the first place of production before the non-terminal. So, the I6 state becomes:

B => c.B, $

B => .cB, $

B => .d, $

Goto on (I6, c) = Closure (B => c.B, $) = (same as I6)

Goto on (I6, d) = Closure (B => d., $) = (same as I7)

I7 = Goto on (I2 d) = Closure (B => d., $)

I8 = Goto on (I3 B) = Closure (B => cD., c/d)

I9 = Goto on (I6 B) = Closure (cB., $)

We can see that the LR(0) items of I3 and I6 are the same, but the only difference is their lookahead.

I3 = {B => c.B, c/d

         B => .cB, c/d

         B => .d, c/d

       }

I6 = {B => c.B, $

            B => .cB, $

            B => .d, $

         }

We can combine I3 and I6 as I36.

I36 = {B => c.B, c/d/$

            B => .cB, c/d/$

            B => .d, c/d/$

          }

The I4 and I7 states are same, but the lookahead symbol is distinct in both case, so we have combined both states and named as I47.

I47 = {B => d., c/d/$}

The I8 and I9 states are same, but the lookahead symbol is distinct in both case, so we have combined both states and named as I89.

I89 = {B => Cb., c/d/$ }

Drawing DFA

LALR 1 Parsing  Compiler Design

LALR(1) Parsing Table

StatesActionGo To
 c                                d                                $E                                B
I0S36                             S47                                  2
I1  
I2S36                               S47                                   5
I36S36                               S47                                   89
I47r3                                  r3                              r3 
I5                                                                    r1 
I89r2                                 r2                             r2 

Related Topics

LEX

LEX Lex is a tool/computer program that generates a Lexical analyzer. Lex is developed by Vern Paxson in C around 1987. Lex works together with the YACC parser generator. It allows...

3 minutes read.

SLR 1 Parsing Compiler Design

SLR(1) Parsing It is a simple LR parsing. Most of the function of this parsing is the same as LR(0) parsing. The parsing table for both the parser vary. The SLR(1)...

5 minutes read.

Intermediate-Code Generator Compiler Design

Intermediate-Code Generator The process of translating a source language into machine code for a given target machine is done by intermediate-code. It lies between the high-level language and the machine language....

2 minutes read.

Target Machine

Target Machine A target machine is a byte-addressable machine. This machine has n general-purpose registers, R0, R1,.....Rn-1. A Simple Target Machine Model has three-address instruction. A full-edged assembly language would have...

3 minutes read.

Machine-Independent Optimizations in Compiler Design

Machine-Independent Optimizations The main aim of machine-independent optimization is to improve the generated intermediate code so that compiler can get better target code. Eliminating unwanted code from the object code or replacing...

8 minutes read.

Translation of Array References in Compiler Design

Translation of Array References We can access the elements of an array stored in consecutive blocks very easily and quickly. In a programming language like C and Java, the size of...

2 minutes read.

Symbol Table Compiler Design

Symbol Table It is an important data structure used by the compiler. It stores information about various entities such as object, class, variable names, functions name, interfaces, procedure, literals, string etc.  The...

3 minutes read.

Finite State Machine

Finite State Machine A finite state machine is a simple machine to recognize patterns. It takes a string of symbols as the input and changes its state to another state, but...

3 minutes read.

Ambiguity Elimination Compiler Design

Ambiguity Elimination Ambiguity elimination makes the sentence clear and readable. A sentence is grammatically ambiguous if it can produce more than one parse tree for a particular grammar. In this article,...

3 minutes read.

S-attributed and L-attributed SDTs

S-attributed and L-attributed SDTs STD stands for Syntax Directed Translation. When we associate some informal notations called semantic rules and the grammar, they are known as STD. So we can say...

2 minutes read.

Shift Reduce Parsing in Compiler Design

Like the bottom-up parsing, the shift reduce parser also builds the parse tree from the leaves (bottom) to the root (up). The LR parser is a more versatile variation of...

4 minutes read.

Optimization of Basic Blocks in Compiler Design

Optimization of Basic Blocks We can apply the optimization process on a basic block. While optimization, there is no need to change the set of expressions computed by the block. The basic...

3 minutes read.

Run-Time Storage Management

Run-Time Storage Management Every executing program has its own logical address space. Logical address space is partitioned into: Code: It is responsible for storing the executable target code. Static: It is used to...

3 minutes read.

LR Parser in Compiler Design

LR Parser The most popular type of bottom-up parsing is LR(K) parsing. The LR() parser scans the input from left – to – right, which is the actual abbreviation of L...

2 minutes read.

Stack Allocation of Space

Stack Allocation of Space Almost all compilers for languages that use procedure, functions, or methods manage their run-time memory as a stack. Whenever a procedure is called, the local variable's space...

2 minutes read.

Regular Expression | Compiler Design

Regular Expression A regular expression is a set of patterns that can match a character or string. It can also match alternative characters or strings. The grammar defined by the regular...

3 minutes read.

Basic Blocks and Flow Graphs in Compiler Design

Basic Blocks and Flow Graphs In this section, we are going to learn how to work with basic block and flow graphs in compiler design. Basic Block The basic block is a set...

3 minutes read.

Syntax Analysis Compiler Design

Syntax Analysis This article will describe the parsing method used in the compiler. The grammatical rule of programming language can be constructed with the help of context-free grammars or BNF (Backus–Naur...

3 minutes read.

Switch Case Statement Compiler Design

Case Statement The “case” or “switch” statement is available in various languages. The following is the syntax for the case statement: switch (E)  {             case V1: S1             case V2: S2 ...

1 minute read.

LR Parser Compiler Design

LR Parser LR parsing is a type of bottom-up parsing that is used to parse the large class of grammars. Here "L" stands for left-to-right scanning of the input "R" stands...

6 minutes read.