Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

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

    Uploaded by

    Abdullah
    The document contains three 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.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

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

    Uploaded by

    Abdullah
    4 views6 pages
    The document contains three 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.

    Original Title

    HW4

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document contains three 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.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    4 views6 pages

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

    Uploaded by

    Abdullah
    The document contains three 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.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 6

    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
    8 R3
    9 R2
    10 R4
    SLR(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 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
    Answer to Q2)
    S' → S., $
    S → Aa., $

    S → A.a, $
    S' → .S, $ S → bA.c, $ S → bAc., $
    S → .Aa, $
    S → .bAc, $ S → b.Ac, $
    S → b.Ba, $ S → bB.a, $ S → bBa., $
    S → .Bc, $
    S → .bBa, $ A → .d, c
    A → .d, a B → .d, a
    A → d., c
    B → .d, c B → d., a
    S → B.c, $

    S → Bc., $
    A → d., a
    B → d., c

    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
    6
    7 S11
    8 S10
    9 R6 R5
    10 R3
    11 R2
    12 R4

    No multiple actions in the same box so it is LR(1) but when we make the
    LALR(1) table we will merge I5 and I9 and we will have a reduce-reduce
    conflict as shown in red above.
    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 --> RR. R --> .b
    R --> .RR R → R. | R
    R --> .R* R --> R.R
    R' --> .R R --> .(R) R --> R.*
    R → .R | R R --> .a R → .R | R
    R --> .RR R --> .b R --> .RR
    R --> .R*
    R --> .R*
    R --> .(R)
    R --> .(R)
    R --> .a R --> (.R)
    R --> .a
    R --> .b R → .R | R
    R --> .b
    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 --> b. R → .R | R
    R --> .RR
    R --> .R*
    R --> .(R)
    R --> .a
    R --> .b
    SLR Parsing Table
    Action Go to
    State
    | * ( ) a b $ R
    0 S2 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