Scribd
Upload
127 views8 pages

LALR Parser For A Grammar: Compiler Design

The document describes an LALR parser for a grammar. It defines the grammar and augmented grammar. It explains the need for a canonical collection of LR(1) items to construct the LALR(1) parsing table. It then describes how LR(1) table construction works using LR(1) items representing parser configurations. Finally, it shows an example LR(1) table and stack table demonstrating parsing of an input string according to the grammar.

Uploaded by

Nameet Jain
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
127 views8 pages

LALR Parser For A Grammar: Compiler Design

The document describes an LALR parser for a grammar. It defines the grammar and augmented grammar. It explains the need for a canonical collection of LR(1) items to construct the LALR(1) parsing table. It then describes how LR(1) table construction works using LR(1) items representing parser configurations. Finally, it shows an example LR(1) table and stack table demonstrating parsing of an input string according to the grammar.

Uploaded by

Nameet Jain
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

LALR parser for a Grammar

Compiler Design

Submitted By:
Nameet Kumar Jain (2K18/CO/221)
Pranjal Choudhary (2K18/CO/253)
Submitted to :
Geetanjali Garg Maam
Grammar & Augmented Grammar
Grammar Augmented Grammar
S -> N S’ -> S
S -> N
N -> V = E
N -> V = E
N -> E
N -> E
E -> V
E -> V
V -> x V -> x
V -> * E V -> * E

The purpose of this new starting production is to indicate to the parser when it should
stop parsing and announce acceptance of input.
Need of Canonical Collection of LR(1) Items

LALR refers to the lookahead LR. To construct the LALR (1) parsing table, we
use the canonical collection of LR (1) items. In the LALR (1) parsing, the LR (1)
items which have same productions but different look ahead are combined to
form a single set of items.
Canonical collection of Lr(1) items
LR(1) Table Construction

○ The LR(1) table construction algorithm uses LR(1) items to represent valid
configurations of an LR(1) parser
○ An LR(1) item is a pair [P, a], where P is a production A→β with a • at some
position in the rhs and a is a lookahead word (or EOF).
○ The • in an item indicates the position of the top of the stack.
○ [A→•βγ,a] means that the input seen so far is consistent with the use of A →βγ
immediately after the symbol on top of the stack.
○ [A →β•γ,a] means that the input seen so far is consistent with A →βγ at this point
in the parse, and that the parser has already recognized β.
○ [A →βγ•,a] means that the parser has seen βγ, and that a lookahead symbol of a is
consistent with reducing to A
LR(1) Table
LR table

Stat ACTION GOTO


e = x * $ S' S N E V
0 s5 s6 1 2 4 3

1 accept

2 r1

3 s7 r4

4 r3

5 r5 r5

6 s5 s6 8 9

7 s5 s6 10 9

8 r6 r6

9 r4 r4

10 r2
STACK Table of Input
Table
Step Stack Input Action
1 0 x=*x$ s5
2 0 x 5 =*x$ r5
3 0 V =*x$ 3
4 0 V 3 =*x$ s7
5 0 V 3 = 7 *x$ s6
6 0 V 3 = 7 * 6 x$ s5
7 0 V 3 = 7 * 6 x 5 $ r5
8 0 V 3 = 7 * 6 V $ 9
9 0 V 3 = 7 * 6 V 9 $ r4
10 0 V 3 = 7 * 6 E $ 8
11 0 V 3 = 7 * 6 E 8 $ r6
12 0 V 3 = 7 V $ 9
13 0 V 3 = 7 V 9 $ r4
14 0 V 3 = 7 E $ 10
15 0 V 3 = 7 E 10 $ r2
16 0 N $ 2
17 0 N 2 $ r1
18 0 S $ 1
19 0 S 1 $ accept
Parse Tree

A parse tree is an ordered, rooted tree


that represents the syntactic structure of
a string according to some context-free
grammar.
● All leaf nodes have to be terminals.
● All interior nodes have to be
non-terminals.
● In-order traversal gives original input
string.

You might also like