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
-----------------------------------|--------------------|-----------------
