[go: up one dir, main page]
Scribd
Upload
883 views4 pages

SLR (1) PARSER/LR (0) Parser: Example:1

The document discusses constructing an SLR or LR(0) parser given a grammar. It provides an example grammar and shows the steps to derive the transition diagram and parsing table and uses it to parse an input string.

Uploaded by

SHIVA P S (RA2111003011359)
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
883 views4 pages

SLR (1) PARSER/LR (0) Parser: Example:1

The document discusses constructing an SLR or LR(0) parser given a grammar. It provides an example grammar and shows the steps to derive the transition diagram and parsing table and uses it to parse an input string.

Uploaded by

SHIVA P S (RA2111003011359)
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/ 4

SLR(1) PARSER/LR(0) Parser

EXAMPLE :1
Construct SLR (or) LR(0) Parser
GIVEN GRAMMAR
S→CC
C→cC| C→d

SOLN:
Given GRAMMAR
1. S→CC
2. C→cC
3. C→d

STEP 0: AUGMENTED GRAMMAR


S’ → .S
STEP 1: DRAW Transition diagram for SLR Parser
STEP 2: Construct SLR Parsing Table
(Note : Require FIRST and FOLLOW computation)
STEP 3: Parse the given input string ‘w’

CLOSURE: if A→α.Bβ in the closure items (I0), if there production


B→z, then , include B→.z in the closure items(I0)
GOTO: If A→ α.Bβ then GOTO from I0 state to I1 state is A→ αB.β

A→ α.Bβ, A→ αB.β, A→. αBβ


STEP 1: SLR PARSING TRANSITION DIAGRAM
KERNEL ITEMS : (or) Canonical items (or) LR(0) items
ACCEPT
S’→.S GOTO[I0, S]

S’-> S. I1
S→.CC
C→.c C
GOTO[I0,C]
C→ .d S->C.C
I0 I2
GOTO[I0,d]] I4 C-> .c C
C-> .d
C->d.
C->c. C
GOTO[I0, c] C→ .c C
GOTO[I2,C]
C→ .d
I5
S->CC.
I3
GOTO[I2,d]
GOTO[I2,c]
I4 C->d.
C->c. C
C->.c C
GOTO[I3,d] I3
I4 C->d. C-> .d
GOTO[I3,c]

GOTO[I3,C]
I3
C->cC.
I6
1. S→CC
2. C→cC
3. C→d
STEP 2: SLR PARSING TABLE
S-SHIFT
r-Reduce
Input ACTION GOTO
state c d $ S C
s
I0 S3 S4 1 2

I1 Accep
t
I2 S3 S4 5

I3 S3 S4 6

I4 r3 r3 r3

I5 r1

I6 r2 r2 r2

TO FILL THIS TABLE , WE compute FIRST and FOLLOW

FIRST (S) ={c,d} FOLLOW(S)= {$}


FIRST (C ) = {c,d} FOLLOW (C)={$,c,d}
STEP 3: PARSE THE GIVEN INPUT STRING “ cdd”

STACK INPUT ACTIONS

$0 cdd$ S3 [Shift]
$0c3 dd$ S4 [Shift]
$0c3d4 d$ r3 [reduce C→d]

$0c3C6 d$ r2 [reduce C→cC]


$0C2 d$ S4
$0C2d4 $ r3 [reduce C→d]
$0C2C5 $ r1[reduce S→CC]
$0S1 $ Accept

You might also like