homework-10.txt

TA: Jade Cheng (TA)
ICS 313
HW 10
Due 2/24/19
 
[Part 1]
 
1. Eliminate epsilon-productions from:
 
          V --> Bc
           B --> RT | NM
          N --> epsilon
          M --> KK
          K --> epsilon
 
  Solve:
 
    V --> Bc | c
    B --> RT | NM | N | M | epsilon
    N --> epsilon
    M --> KK | K | epsilon
    K --> epsilon
 
  Solution:
 
    V --> Bc | c
    B --> RT | NM | N | M
    M --> KK | K  
 
2. Eliminate unit productions from:
 
          S --> T | KK
          T --> S | PP
 
  Solution:
 
          S --> S | PP | KK
 
3. Eliminate the left recursion (in the order of A, S, B) from:
 
          S --> Ba | Ab
          A --> Sa | AAb | a
          B --> Sb | BBa | b
 
  Re-order the productions:
 
          A --> Sa | AAb | a
          S --> Ba | Ab
          B --> Sb | BBa | b
 
  Identify Productions that contain left recursions:
 
          1). A --> Sa | AAb | a
          2). S --> Ba | Ab
          3). B --> Sb | BBa | b
 
  Solve 1).
 
          A --> Sa | AAb | a
          alpha1 = Ab
          beta1  = Sa
          beta2  = a
 
        ==>   A --> Sa | a | SaP | aP
          P --> Ab | AbP
 
  Solve 2).
 
          S --> Ba | Ab
              --> Ba | Sab | ab | SaPb | aPb
          alpha1 = ab
           alpha2 = aPb
          beta1  = Ba
          beta2  = ab
          beta3  = aPb
 
        ==>   S --> Ba | ab | aPb | BaQ | abQ | aPbQ
          Q --> ab | aPb | abQ | aPbQ
 
  Solve 3).
 
          B --> Sb | BBa | b
              --> Bab | abb | aPbb | BaQb | abQb | aPbQb | BBa | b
          alpha1 = ab
          alpha2 = aQb
          alpha3 = Ba
          beta1  = abb
          beta2  = aPbb
          beta3  = abQb
          beta4  = aPbQb
          beta5  = b
 
      ==>   B --> abb | aPbb | abQb | aPbQb | b |
                      abbR | aPbbR | abQbR | aPbQbR | bR
          R --> ab | aQb | Ba | abR | aQbR | BaR
 
  Solution:
 
          A --> Sa | a | SaP | aP
          P --> Ab | AbP
          S --> Ba | ab | aPb | BaQ | abQ | aPbQ
          Q --> ab | aPb | abQ | aPbQ
          B --> abb | aPbb | abQb | aPbQb | b |
                      abbR | aPbbR | abQbR | aPbQbR | bR
          R --> ab | aQb | Ba | abR | aQbR | BaR
 
 
[Part 2]
 
1. Use the parsing machine to parse a+a+a*a
 
A represents the symbol stack
B represents the state number stack
C contains the remaining input
 
Solution:
 
===============================================================================
A:               A: a             A: T             A: E             A: E +
B: 0        =>   B: 0 4      =>   B: 0 3      =>   B: 0 1      =>   B: 0 1 2
C: a+a+a*a$      C: +a+a*a$       C: +a+a*a$       C: +a+a*a$       C: a+a*a$
-------------------------------------------------------------------------------
     A: E + a         A: E + T         A: E           A: E +         A: E + a
=>   B: 0 1 2 4  =>   B: 0 1 2 6  =>   B: 0 1    =>   B: 0 1 2  =>   B: 0 1 2 4
     C: +a*a$         C: +a*a$         C: +a*a$       C: a*a$        C: *a$
-------------------------------------------------------------------------------
     A: E + T         A: E + T *         A: E + T * a         A: E + T
=>   B: 0 1 2 6  =>   B: 0 1 2 6 5  =>   B: 0 1 2 6 5 7  =>   B: 0 1 2 6
     C: *a$           C: a$              C: $                 C: $
-------------------------------------------------------------------------------
     A: E         A:
=>   B: 0 1  =>   B: 0
     C: $         C: Accept
===============================================================================
 
2. (Exercise 7 on p198) Show a complete parse stack contents, input string, and
   action for the string id*(id+id), using the grammar and parse table in
   Section 4.5.3.
 
Grammar:
 
        1. E --> E + T
        2. E --> T
        3. T --> T * F
        4. T --> F
        5. F --> ( E )
        6. F --> id
 
Parse Table:
 
-------------------- Action ---------------------------|------ Goto -------
                                                       |
state   id      +       *       (       )       $      | E       T       F
0       S5                      S4                     | 1       2       3
1               S6                              accept |
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     |
-------------------------------------------------------|-------------------
 
A represents the symbol stack
B represents the state number stack
 
Solution:
 
-------------- Stack --------------|------ Input -------|----- Action ----
                                   |                    |
A:              B: 0               |     id*(id+id)$    |      shift  5
A: id           B:0 5              |     *(id+id)$      |      reduce 6
A: F            B:0 3              |     *(id+id)$      |      reduce 4
A: T            B:0 2              |     *(id+id)$      |      reduce 7
A: T *          B:0 2 7            |     (id+id)$       |      shift  4
A: T * (        B:0 2 7 4          |     id+id)$        |      shift  5
A: T * ( id     B:0 2 7 4 5        |     +id)$          |      reduce 6
A: T * ( F      B:0 2 7 4 3        |     +id)$          |      reduce 4
A: T * ( T      B:0 2 7 4 2        |     +id)$          |      reduce 2
A: T * ( E      B:0 2 7 4 8        |     +id)$          |      shift  6
A: T * ( E +    B:0 2 7 4 8 6      |     id)$           |      shift  5
A: T * ( E + id B:0 2 7 4 8 6 5    |     )$             |      reduce 6
A: T * ( E + F  B:0 2 7 4 8 6 3    |     )$             |      reduce 4
A: T * ( E + T  B:0 2 7 4 8 6 9    |     )$             |      reduce 1
A: T * ( E      B:0 2 7 4 8        |     )$             |      shift 11
A: T * ( E )    B:0 2 7 4 8 11     |     $              |      reduce 5
A: T * F        B:0 2 7 10         |     $              |      reduce 3
A: T            B:0 2              |     $              |      reduce 2
A: E            B:0 1              |     $              |      accept
-----------------------------------|--------------------|-----------------
 
 
Valid HTML 4.01 Valid CSS