Scribd
Upload
20 views5 pages

Homework 4: Programming Languages and Compilers (Cos 305) S - Aa - Bac - DC - Bda A - A

The document contains questions about programming language concepts. Question 1 asks to show that a grammar is LALR(1) but not SLR(1). Question 2 asks to show that a grammar is LR(1) but not LALR(1). Question 3 asks to construct an SLR parsing table for a grammar.

Uploaded by

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

Homework 4: Programming Languages and Compilers (Cos 305) S - Aa - Bac - DC - Bda A - A

The document contains questions about programming language concepts. Question 1 asks to show that a grammar is LALR(1) but not SLR(1). Question 2 asks to show that a grammar is LR(1) but not LALR(1). Question 3 asks to construct an SLR parsing table for a grammar.

Uploaded by

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

Homework 4: Programming languages and compilers (COS 305)

Q1) Show that the following grammar is LALR(1) but not SLR(1).
S --> Aa | bAc | dc | bda
A --> a

Q2) Show that the following grammar is LR(1) but not LALR(1).
S --> Aa | bAc | Bc | bBa
A --> d
B --> d

Q3) Construct an SLR parsing table for the following grammar:


R --> R | R
R --> RR
R --> R*
R --> (R)
R --> a
R --> b

Abdullah Abdulaziz Alsubaie - 441102593


Answer to Q1)

LR(1) Parsing Table


Action Go to
State
a b c d $ S A
0 S3 S4 1 2
1 Accept
2 S5
3 S7 6
4 R5 S8
5
6 S9
7 S10 R5
SLR(1) Parsing Table
8 R3
Action Go to
State
9 R2
a b c d $ S A
10 R4
0 S3 S4 1 2
1 Accept
2 S5
3 S7 6
4 R5 R5 S8/R5 R5 R5
5
6 S9
7 S10/R5 R5 R5 R5 R5
8 R3 R3 R3 R3 R3
9 R2 R2 R2 R2 R2
10 R4 R4 R4 R4 R4
LR(1) Parsing Table
Action Go to
State
a b c d $ S A B
0 S3 S4 1 2 4
1 accept
2 S6
3 S9 7 8
4 S10
5 R5 R6
Answer to Q2)
6 S' → S., $
7 S11 S → Aa., $

8 S10
S → A.a, $
9 R6 R5
S' → .S, $ S → bA.c, $ S → bAc., $
S → .Aa, $ 10 R3
S → .bAc, $ S → b.Ac, $
11 R2 $
S → bB.a, S → bBa., $
S → .Bc, $ S → b.Ba, $
S → .bBa, $ 12 A → .d, c R4
answer to Q3)

R→R|.R R → R | R.
R → .R | R R→R.|R
R --> .RR R --> R.R
R --> .R* R --> R.*
R --> .(R) R → .R | R
R' --> R. R --> .a R --> .RR
R → R. | R R --> .b R --> .R*
R --> R.R R --> .(R)
R --> R.* R --> .a
R → .R | R R --> .b
R --> .RR R --> RR.
R --> .R* R → R. | R
R --> .(R) R --> R.R
R --> .a R --> R.*
R' --> .R
R --> .b R → .R | R
R → .R | R
R --> .RR
R --> .RR
R --> .R*
R --> .R*
R --> .(R)
R --> .(R)
R --> .a
R --> .a R --> (.R)
R --> .b
R --> .b R → .R | R
R --> .RR
R --> .R*
R --> .(R)
R --> R*.
R --> .a
R --> .b

R --> (R.)
R→R.|R
R --> a. R --> R.R
R --> R.*
R --> (R).
R → .R | R
R --> b. SLR Parsing Table
R --> .RR
R Action
--> .R* Go to
State
| * ( R -->
) .(R) a b $ R
R --> .a
0 S2 R --> .b S3 S4 1
1 S5 S7 S2 S3 S4 accept 6
2 S2 S3 S4 8
3 R5 R5 R5 R5 R5 R5 R5
4 R6 R6 R6 R6 R6 R6 R6
5 S2 S3 S4 9
6 R2 R2/S7 R2 R2 R2 R2 R2 6
7 R3 R3 R3 R3 R3 R3 R3
8 S5 S7 S2 S10 S3 S4 6
9 R1 R1/S7 R1/S2 R1 R1/S3 R1/S4 R1 6
10 R4 R4 R4 R4 R4 R4 R4
We can see many shift-reduce conflicts in states I6 and I9

You might also like