CSE411: Introduction to Compilers

SLR(1) Parsing

Jooyong Yi (UNIST)

How to Construct a Bottom-Up Parsing Table

┌─ I0 ───────┐   E    ┌─ I1 ───────┐                                                               (1) E : E + T   (2) E : T
│ E' → ·E    │------->| E' → E·    |                                                               (3) T : T * F   (4) T : F
└────────────┘        └────────────┘                                                               (5) F : (E)     (6) F : id
                            | $
                            ↓                                                                      ---------------------------------------------------
                          accept                                                                          |  Action                       |  Goto  
                                                                                                    State |-------------------------------------------
                                                                                                          | id    +    *    (    )    $   |  E  T  F
                                                                                                   ---------------------------------------------------
                                                                                                      0   |                               | 
                                                                                                      1   |                               |
                                                                                                      2   |                               |
                                                                                                      3   |                               |
                                                                                                      4   |                               | 
                                                                                                      5   |                               |
                                                                                                      6   |                               | 
                                                                                                      7   |                               | 
                                                                                                      8   |                               |  
                                                                                                      9   |                               |
                                                                                                     10   |                               |
                                                                                                     11   |                               |
                                                                                                   -------------------------------------------------- 

                                                                                                    ---------------------------------------------------
                                                                                                          |  Action                       |  Goto  
                                                                                                    State |-------------------------------------------
                                                                                                          | id    +    *    (    )    $   |  E  T  F
                                                                                                    --------------------------------------------------
                                                                                                      0   | s5             s4             |  1  2  3
                                                                                                      1   |       s6                  acc |
                                                                                                      2   |       r2  s7        r2     r2 |
                                                                                                      3   |       r4  r4        r4     r4 |
                                                                                                      4   | s5             s4             |  8  2  3
                                                                                                      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 |
                                                                                                    --------------------------------------------------

┌─ I0 ───────┐   E    ┌─ I1 ───────┐                                                               (1) E : E + T   (2) E : T
│ E' → ·E    │------->| E' → E·    |                                                               (3) T : T * F   (4) T : F
└────────────┘        └────────────┘                                                               (5) F : (E)     (6) F : id
                            | $
                            ↓                                                                      ---------------------------------------------------
                          accept                                                                          |  Action                       |  Goto  
                                                                                                    State |-------------------------------------------
                                                                                                          | id    +    *    (    )    $   |  E  T  F
                                                                                                   ---------------------------------------------------
                                                                                                      0   |                               |  1
                                                                                                      1   |                           acc |
                                                                                                      2   |                               |
                                                                                                      3   |                               |
                                                                                                      4   |                               | 
                                                                                                      5   |                               |
                                                                                                      6   |                               | 
                                                                                                      7   |                               | 
                                                                                                      8   |                               |  
                                                                                                      9   |                               |
                                                                                                     10   |                               |
                                                                                                     11   |                               |
                                                                                                   -------------------------------------------------- 

                                                                                                    ---------------------------------------------------
                                                                                                          |  Action                       |  Goto  
                                                                                                    State |-------------------------------------------
                                                                                                          | id    +    *    (    )    $   |  E  T  F
                                                                                                    --------------------------------------------------
                                                                                                      0   | s5             s4             |  1  2  3
                                                                                                      1   |       s6                  acc |
                                                                                                      2   |       r2  s7        r2     r2 |
                                                                                                      3   |       r4  r4        r4     r4 |
                                                                                                      4   | s5             s4             |  8  2  3
                                                                                                      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 |
                                                                                                    --------------------------------------------------

┌─ I0 ───────┐   E    ┌─ I1 ───────┐                                                               (1) E : E + T   (2) E : T
│ E' → ·E    │------->| E' → E·    |                                                               (3) T : T * F   (4) T : F
| E → ·E + T |        └────────────┘                                                               (5) F : (E)     (6) F : id
| E → ·T     |              | $
└────────────┘              ↓                                                                      ---------------------------------------------------
                          accept                                                                          |  Action                       |  Goto  
                                                                                                    State |-------------------------------------------
                                                                                                          | id    +    *    (    )    $   |  E  T  F
                                                                                                   ---------------------------------------------------
                                                                                                      0   |                               |  1
                                                                                                      1   |                           acc |
                                                                                                      2   |                               |
                                                                                                      3   |                               |
                                                                                                      4   |                               | 
                                                                                                      5   |                               |
                                                                                                      6   |                               | 
                                                                                                      7   |                               | 
                                                                                                      8   |                               |  
                                                                                                      9   |                               |
                                                                                                     10   |                               |
                                                                                                     11   |                               |
                                                                                                   -------------------------------------------------- 

                                                                                                    ---------------------------------------------------
                                                                                                          |  Action                       |  Goto  
                                                                                                    State |-------------------------------------------
                                                                                                          | id    +    *    (    )    $   |  E  T  F
                                                                                                    --------------------------------------------------
                                                                                                      0   | s5             s4             |  1  2  3
                                                                                                      1   |       s6                  acc |
                                                                                                      2   |       r2  s7        r2     r2 |
                                                                                                      3   |       r4  r4        r4     r4 |
                                                                                                      4   | s5             s4             |  8  2  3
                                                                                                      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 |
                                                                                                    --------------------------------------------------

┌─ I0 ───────┐   E    ┌─ I1 ───────┐                                                               (1) E : E + T   (2) E : T
│ E' → ·E    │------->| E' → E·    |                                                               (3) T : T * F   (4) T : F
| E → ·E + T |        └────────────┘                                                               (5) F : (E)     (6) F : id
| E → ·T     |              | $
| T → ·T * F |              ↓                                                                      ---------------------------------------------------
| T → ·F     |            accept                                                                          |  Action                       |  Goto  
| F → ·( E ) |                                                                                      State |-------------------------------------------
| F → ·id    |                                                                                            | id    +    *    (    )    $   |  E  T  F
└────────────┘                                                                                     ---------------------------------------------------
        | |                                                                                           0   |                               |  1
        | |                                                                                           1   |                           acc |
        | |  id                                                                                       2   |                               |
        | |-----> ┌─ I5 ───────┐                                                                      3   |                               |
        |         | F → id·    |                                                                      4   |                               | 
        |         └────────────┘                                                                      5   |                               |
        |                                                                                             6   |                               | 
        |  (                                                                                          7   |                               | 
        |--------> ┌─ I4 ───────┐                                                                     8   |                               |  
                   | F → (·E )  |                                                                     9   |                               |
                   └────────────┘                                                                    10   |                               |
                                                                                                     11   |                               |
                                                                                                   -------------------------------------------------- 

                                                                                                    ---------------------------------------------------
                                                                                                          |  Action                       |  Goto  
                                                                                                    State |-------------------------------------------
                                                                                                          | id    +    *    (    )    $   |  E  T  F
                                                                                                    --------------------------------------------------
                                                                                                      0   | s5             s4             |  1  2  3
                                                                                                      1   |       s6                  acc |
                                                                                                      2   |       r2  s7        r2     r2 |
                                                                                                      3   |       r4  r4        r4     r4 |
                                                                                                      4   | s5             s4             |  8  2  3
                                                                                                      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 |
                                                                                                    --------------------------------------------------

┌─ I0 ───────┐   E    ┌─ I1 ───────┐                                                               (1) E : E + T   (2) E : T
│ E' → ·E    │------->| E' → E·    |                                                               (3) T : T * F   (4) T : F
| E → ·E + T |        └────────────┘                                                               (5) F : (E)     (6) F : id
| E → ·T     |              | $
| T → ·T * F |              ↓                                                                      ---------------------------------------------------
| T → ·F     |            accept                                                                          |  Action                       |  Goto  
| F → ·( E ) |                                                                                      State |-------------------------------------------
| F → ·id    |                                                                                            | id    +    *    (    )    $   |  E  T  F
└────────────┘                                                                                     ---------------------------------------------------
        | |                                                                                           0   | s5              s4            |  1
        | |                                                                                           1   |                           acc |
        | |  id                                                                                       2   |                               |
        | |-----> ┌─ I5 ───────┐                                                                      3   |                               |
        |         | F → id·    |                                                                      4   |                               | 
        |         └────────────┘                                                                      5   |                               |
        |                                                                                             6   |                               | 
        |  (                                                                                          7   |                               | 
        |--------> ┌─ I4 ───────┐                                                                     8   |                               |  
                   | F → (·E )  |                                                                     9   |                               |
                   └────────────┘                                                                    10   |                               |
                                                                                                     11   |                               |
                                                                                                   -------------------------------------------------- 

                                                                                                    ---------------------------------------------------
                                                                                                          |  Action                       |  Goto  
                                                                                                    State |-------------------------------------------
                                                                                                          | id    +    *    (    )    $   |  E  T  F
                                                                                                    --------------------------------------------------
                                                                                                      0   | s5             s4             |  1  2  3
                                                                                                      1   |       s6                  acc |
                                                                                                      2   |       r2  s7        r2     r2 |
                                                                                                      3   |       r4  r4        r4     r4 |
                                                                                                      4   | s5             s4             |  8  2  3
                                                                                                      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 |
                                                                                                    --------------------------------------------------

┌─ I0 ───────┐   E    ┌─ I1 ───────┐                                                               (1) E : E + T   (2) E : T
│ E' → ·E    │------->| E' → E·    |                                                               (3) T : T * F   (4) T : F
| E → ·E + T |        └────────────┘                                                               (5) F : (E)     (6) F : id
| E → ·T     |              | $
| T → ·T * F |              ↓                                                                      ---------------------------------------------------
| T → ·F     |            accept                                                                          |  Action                       |  Goto  
| F → ·( E ) |   T                                                                                  State |-------------------------------------------
| F → ·id    |------->┌─ I2 ───────┐                                                                      | id    +    *    (    )    $   |  E  T  F
└────────────┘        | E → T·     |                                                               ---------------------------------------------------
      | | |           | T → T· * F |                                                                  0   | s5              s4            |  1
      | | |           └────────────┘                                                                  1   |                           acc |
      | | |  id                                                                                       2   |                               |
      | | |-----> ┌─ I5 ───────┐                                                                      3   |                               |
      | |         | F → id·    |                                                                      4   |                               | 
      | |         └────────────┘                                                                      5   |                               |
      | |                                                                                             6   |                               | 
      | |  (                                                                                          7   |                               | 
      | |--------> ┌─ I4 ───────┐                                                                     8   |                               |  
      |            | F → (·E )  |                                                                     9   |                               |
      |            └────────────┘                                                                    10   |                               |
      |   F                                                                                          11   |                               |
      |--------> ┌─ I3 ───────┐                                                                     -------------------------------------------------- 
                 | T → F·     |
                 └────────────┘                                                                     ---------------------------------------------------
                                                                                                          |  Action                       |  Goto  
                                                                                                    State |-------------------------------------------
                                                                                                          | id    +    *    (    )    $   |  E  T  F
                                                                                                    --------------------------------------------------
                                                                                                      0   | s5             s4             |  1  2  3
                                                                                                      1   |       s6                  acc |
                                                                                                      2   |       r2  s7        r2     r2 |
                                                                                                      3   |       r4  r4        r4     r4 |
                                                                                                      4   | s5             s4             |  8  2  3
                                                                                                      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 |
                                                                                                    --------------------------------------------------

┌─ I0 ───────┐   E    ┌─ I1 ───────┐                                                               (1) E : E + T   (2) E : T
│ E' → ·E    │------->| E' → E·    |                                                               (3) T : T * F   (4) T : F
| E → ·E + T |        └────────────┘                                                               (5) F : (E)     (6) F : id
| E → ·T     |              | $
| T → ·T * F |              ↓                                                                      ---------------------------------------------------
| T → ·F     |            accept                                                                          |  Action                       |  Goto  
| F → ·( E ) |   T                                                                                  State |-------------------------------------------
| F → ·id    |------->┌─ I2 ───────┐                                                                      | id    +    *    (    )    $   |  E  T  F
└────────────┘        | E → T·     |                                                               ---------------------------------------------------
      | | |           | T → T· * F |                                                                  0   | s5              s4            |  1  2  3
      | | |           └────────────┘                                                                  1   |                           acc |
      | | |  id                                                                                       2   |                               |
      | | |-----> ┌─ I5 ───────┐                                                                      3   |                               |
      | |         | F → id·    |                                                                      4   |                               | 
      | |         └────────────┘                                                                      5   |                               |
      | |                                                                                             6   |                               | 
      | |  (                                                                                          7   |                               | 
      | |--------> ┌─ I4 ───────┐                                                                     8   |                               |  
      |            | F → (·E )  |                                                                     9   |                               |
      |            └────────────┘                                                                    10   |                               |
      |   F                                                                                          11   |                               |
      |--------> ┌─ I3 ───────┐                                                                     -------------------------------------------------- 
                 | T → F·     |
                 └────────────┘                                                                     ---------------------------------------------------
                                                                                                          |  Action                       |  Goto  
                                                                                                    State |-------------------------------------------
                                                                                                          | id    +    *    (    )    $   |  E  T  F
                                                                                                    --------------------------------------------------
                                                                                                      0   | s5             s4             |  1  2  3
                                                                                                      1   |       s6                  acc |
                                                                                                      2   |       r2  s7        r2     r2 |
                                                                                                      3   |       r4  r4        r4     r4 |
                                                                                                      4   | s5             s4             |  8  2  3
                                                                                                      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 |
                                                                                                    --------------------------------------------------

┌─ I0 ───────┐   E    ┌─ I1 ───────┐   +    ┌─ I6 ───────┐                                         (1) E : E + T   (2) E : T
│ E' → ·E    │------->| E' → E·    |------->| E → E + ·T |                                         (3) T : T * F   (4) T : F
| E → ·E + T |        | E → E· + T |        └────────────┘                                         (5) F : (E)     (6) F : id
| E → ·T     |        └────────────┘       
| T → ·T * F |              ↓ $                                                                    ---------------------------------------------------
| T → ·F     |            accept                                                                          |  Action                       |  Goto  
| F → ·( E ) |   T                                                                                  State |-------------------------------------------
| F → ·id    |------->┌─ I2 ───────┐                                                                      | id    +    *    (    )    $   |  E  T  F
└────────────┘        | E → T·     |                                                               ---------------------------------------------------
      | | |           | T → T· * F |                                                                  0   | s5              s4            |  1  2  3
      | | |           └────────────┘                                                                  1   |       s6                  acc |
      | | |  id                                                                                       2   |                               |
      | | |-----> ┌─ I5 ───────┐                                                                      3   |                               |
      | |         | F → id·    |                                                                      4   |                               | 
      | |         └────────────┘                                                                      5   |                               |
      | |                                                                                             6   |                               | 
      | |  (                                                                                          7   |                               | 
      | |--------> ┌─ I4 ───────┐                                                                     8   |                               |  
      |            | F → (·E )  |                                                                     9   |                               |
      |            └────────────┘                                                                    10   |                               |
      |   F                                                                                          11   |                               |
      |--------> ┌─ I3 ───────┐                                                                     -------------------------------------------------- 
                 | T → F·     |
                 └────────────┘                                                                     ---------------------------------------------------
                                                                                                          |  Action                       |  Goto  
                                                                                                    State |-------------------------------------------
                                                                                                          | id    +    *    (    )    $   |  E  T  F
                                                                                                    --------------------------------------------------
                                                                                                      0   | s5             s4             |  1  2  3
                                                                                                      1   |       s6                  acc |
                                                                                                      2   |       r2  s7        r2     r2 |
                                                                                                      3   |       r4  r4        r4     r4 |
                                                                                                      4   | s5             s4             |  8  2  3
                                                                                                      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 |
                                                                                                    --------------------------------------------------

┌─ I0 ───────┐   E    ┌─ I1 ───────┐   +    ┌─ I6 ───────┐                                         (1) E : E + T   (2) E : T
│ E' → ·E    │------->| E' → E·    |------->| E → E + ·T |                                         (3) T : T * F   (4) T : F
| E → ·E + T |        | E → E· + T |        └────────────┘                                         (5) F : (E)     (6) F : id    FOLLOW(E) = {$, +, )}
| E → ·T     |        └────────────┘       
| T → ·T * F |              ↓ $                                                                    ---------------------------------------------------
| T → ·F     |            accept                                                                          |  Action                       |  Goto  
| F → ·( E ) |   T                                                                                  State |-------------------------------------------
| F → ·id    |------->┌─ I2 ───────┐                                                                      | id    +    *    (    )    $   |  E  T  F
└────────────┘        | E → T·     |                                                               ---------------------------------------------------
      | | |           | T → T· * F |                                                                  0   | s5              s4            |  1  2  3
      | | |           └────────────┘                                                                  1   |       s6                  acc |
      | | |  id                                                                                       2   |       r2            r2     r2 |
      | | |-----> ┌─ I5 ───────┐                                                                      3   |                               |
      | |         | F → id·    |                                                                      4   |                               | 
      | |         └────────────┘                                                                      5   |                               |
      | |                                                                                             6   |                               | 
      | |  (                                                                                          7   |                               | 
      | |--------> ┌─ I4 ───────┐                                                                     8   |                               |  
      |            | F → (·E )  |                                                                     9   |                               |
      |            └────────────┘                                                                    10   |                               |
      |   F                                                                                          11   |                               |
      |--------> ┌─ I3 ───────┐                                                                     -------------------------------------------------- 
                 | T → F·     |
                 └────────────┘                                                                     ---------------------------------------------------
                                                                                                          |  Action                       |  Goto  
                                                                                                    State |-------------------------------------------
                                                                                                          | id    +    *    (    )    $   |  E  T  F
                                                                                                    --------------------------------------------------
                                                                                                      0   | s5             s4             |  1  2  3
                                                                                                      1   |       s6                  acc |
                                                                                                      2   |       r2  s7        r2     r2 |
                                                                                                      3   |       r4  r4        r4     r4 |
                                                                                                      4   | s5             s4             |  8  2  3
                                                                                                      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 |
                                                                                                    --------------------------------------------------

(1) E : E + T   (2) E : T
(3) T : T * F   (4) T : F
(5) F : (E)     (6) F : id

---------------------------------------------------
       |  Action                       |  Goto  
 State |-------------------------------------------
       | id    +    *    (    )    $   |  E  T  F
 --------------------------------------------------
   0   | s5             s4             |  1  2  3
   1   |       s6                  acc |
   2   |       r2  s7        r2     r2 |
   3   |       r4  r4        r4     r4 |
   4   | s5             s4             |  8  2  3
   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 |
--------------------------------------------------

How to construct an LR(0) automaton

// Construct an LR(0) automaton
CS = ∅ // a set of closures
CS = CS ∪ Closure({E'→·E$}) // E is the starting nonterminal of a given grammar
Edges = ∅
repeat
   for each C in CS
      for each item A → α·Xβ in C // X is either a terminal or a nonterminal
         if X is not $
            let J be Goto(C, X)
            CS = CS ∪ {J}
            Edges = Edges ∪ {C -X-> J}
         else
            Edges = Edges ∪ {C -X-> accept}


Closure(I) =
   repeat       
      for any item A → α·Xβ in I // X is either a terminal or a nonterminal
         for any production X → γ
            I = I ∪ {X → ·γ}
   until I does not change
   return I

Goto(I, X) =
   J = ∅
   for any item A → α·Xβ in I
      J = J ∪ {A → αX·β}
   return Closure(J)