Scribd
Upload
17 views28 pages

Introduction To Simple LR Parsing Example

The document provides an introduction to Simple LR Parsing, explaining the concepts of LR parsing, including left-to-right scanning and rightmost derivation. It details the LR(0) automaton for an expression grammar and includes parsing tables for both SLR(1) and LR(0) parsing methods. Additionally, it illustrates the moves of an SLR(1) parser with a specific example.

Uploaded by

abdurrahman.ibne.masud
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
17 views28 pages

Introduction To Simple LR Parsing Example

The document provides an introduction to Simple LR Parsing, explaining the concepts of LR parsing, including left-to-right scanning and rightmost derivation. It details the LR(0) automaton for an expression grammar and includes parsing tables for both SLR(1) and LR(0) parsing methods. Additionally, it illustrates the moves of an SLR(1) parser with a specific example.

Uploaded by

abdurrahman.ibne.masud
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

Introduction to Simple LR Parsing

Prepared By: Sukarna Sarker


In LR parsing:
1. L means Left to right scanning and R means rightmost derivation
2. k for the number of input symbols of lookahead that are used in making parsing
decisions
3. When (k) is omitted, k is assumed to be 1

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) automaton for the expression grammar(Step by step)

E’ -> E
E -> E + T | T
T -> T * F | F
F -> (E) | id

Prepared By: Sukarna Sarker


LR(0) Parsing table for expression grammar

State Action Go - To
id + * ( ) $ E T F
0 S5 S4 1 2 3

(1) E -> E + T 1 S6 Accept


(2) E -> T 2 R2 R2 S7 R2 R2 R2 R2
(3) T -> T * F 3 R4 R4 R4 R4 R4 R4
(4) T -> F
4 S5 S4 8 2 3
(5) F -> (E)
(6) F -> id 5 R6 R6 R6 R6 R6 R6
6 S5 S4 9 3
7 S5 S4 10
8 S6 S11
9 R1 R1 R1 S7 R1 R1 R1
10 R3 R3 R3 R3 R3 R3
11 R5 R5 R5 R5 R5 R5

Prepared By: Sukarna Sarker


First and Follow

Line First Follow

E -> E + T
First(E) = { ( , id } Follow(E) = { $ , + , ) }
E -> T

T -> T * F
First(T) = { ( , id} Follow(T) = { * , $ , + , ) }
T -> F

F -> (E)
First(F) = { ( , id} Follow(F) = { * , $ , + , ) }
F -> id

Prepared By: Sukarna Sarker


SLR(1) Parsing table for expression grammar

State Action Go - To
id + * ( ) $ E T F
0 S5 S4 1 2 3
1 S6 Accept
(1) E -> E + T
(2) E -> T 2 R2 S7 R2 R2
(3) T -> T * F 3 R4 R4 R4 R4
(4) T -> F
4 S5 S4 8 2 3
(5) F -> (E)
(6) F -> id 5 R6 R6 R6 R6
6 S5 S4 9 3
7 S5 S4 10
8 S6 S11
9 R1 S7 R1 R1
10 R3 R3 R3 R3
11 R5 R5 R5 R5

Prepared By: Sukarna Sarker


Moves of an SLR(1) parser on id * id

Line Stack Symbol Input Action

1 0 $ id * id$ Shift to 5

2 05 $id * id$ Reduce by F -> id


(1) E -> E + T
(2) E -> T 3 03 $F * id$ Reduce by T -> F
(3) T -> T * F
(4) T -> F 4 02 $T * id$ Shift to 7
(5) F -> (E)
(6) F -> id 5 027 $T * id$ Shift to 5

6 0275 $T * id $ Reduce by F ->id

7 0 2 7 10 $T * F $ Reduce by T -> T * F

8 02 $T $ Reduce by E -> T

9 01 $E $ Accept

Prepared By: Sukarna Sarker

You might also like