## 1 The grammar G
i) L E C F V T
ii) a b c d 0 1 2 3 if + – * print （ ）
iii) L
iv) L $\rightarrow$ E $\rightarrow$ (C) $\rightarrow$ (if E E) $\rightarrow$ (if (F) E )
$\rightarrow$ (if (-L) E ) $\rightarrow$ (if (-LE) E ) $\rightarrow$ (if (-EE) E )
$\rightarrow$ (if (-TE) E ) $\rightarrow$ (if (-1E) E )
$\rightarrow$ (if (-1V) E ) $\rightarrow$ (if (-1a) E ) $\rightarrow$ (if (-1a) (F) )
$\rightarrow$ (if (-1a) (print L) ) $\rightarrow$ (if (-1a) (print E) )
$\rightarrow$ (if (-1a) (print T) ) $\rightarrow$ (if (-1a) (print 1) )
v)
## 2 Prove G is not LL(1)
L $\rightarrow$ LE is left recursive, thus G is not LL(1).
## 3 Find an equivalent LL(1) grammar G′
using left factoring
E $\rightarrow$ (E’ | V | T
E’ $\rightarrow$ C) | F)
C $\rightarrow$ if E E C’
C’ $\rightarrow$ E | ε
remove left recursive
L $\rightarrow$ EL’
L’ $\rightarrow$ EL’ | ε
Above steps result in LL(1) grammar G’
L $\rightarrow$ EL’
L’ $\rightarrow$ EL’ | ε
E $\rightarrow$ (E’ |V |T
E’ $\rightarrow$ C) | F)
C $\rightarrow$ if EE C’
C’ $\rightarrow$ E | ε
F $\rightarrow$ +L|−L|∗L|printL
V $\rightarrow$ a|b|c|d
T $\rightarrow$ 0|1|2|3
### 4 LL(1) parse table
| Rule | First | Follow |
| ————– | —————– | —— |
| L $\rightarrow$ EL’ | a b c d 0 1 2 3 ( | |
| L’ $\rightarrow$ EL’ | a b c d 0 1 2 3 ( | |
| L’ $\rightarrow$ ε | ε | $ ) |
| E $\rightarrow$ (E’ | ( | |
| E$\rightarrow$ V | a b c d | |
| E$\rightarrow$ T | 0 1 2 3 | |
| E’ $\rightarrow$ C) | if | |
| E’ $\rightarrow$ F) | + – * print | |
| C $\rightarrow$ if EE C’ | if | |
| C’ $\rightarrow$ E | a b c d 0 1 2 3 ( | |
| C’ $\rightarrow$ ε | ε | ) |
| F $\rightarrow$ +L | + | |
| F $\rightarrow$ -L | – | |
| F $\rightarrow$ *L | * | |
| F $\rightarrow$ print L | print | |
| V $\rightarrow$ a | a | |
| V $\rightarrow$ b | b | |
| V$\rightarrow$ c | c | |
| V$\rightarrow$d | d | |
| T $\rightarrow$ 0 | 0 | |
| T$\rightarrow$1 | 1 | |
| T$\rightarrow$2 | 2 | |
| T$\rightarrow$3 | 3 | |
### Parse Table
| | ( | ) | if | + | – | * | print | a | b | c | d | 0 | 1 | 2 | 3 | $ |
| —- | —- | —- | ——– | —- | —- | —- | ——- | —- | —- | —- | —- | —- | —- | —- | —- | —- |
| L | EL’ | | | | | | | EL’ | EL’ | EL’ | EL’ | EL’ | EL’ | EL’ | EL’ | |
| L’ | EL’ | ε | | | | | | EL’ | EL’ | EL’ | EL’ | EL’ | EL’ | EL’ | EL’ | ε |
| E | (E’ | | | | | | | V | V | V | V | T | T | T | T | |
| E’ | | | C) | F) | F) | F) | F) | | | | | | | | | |
| C | | | if EE C’ | | | | | | | | | | | | | |
| C’ | E | ε | | | | | | E | E | E | E | E | E | E | E | |
| F | | | | +L | -L | *L | print L | | | | | | | | | |
| V | | | | | | | | a | b | c | d | | | | | |
| T | | | | | | | | | | | | 0 | 1 | 2 | 3 | |
## 5 Implementation
### Test Example 1
Input
“`
(if (-1 a) (print 1))
“`
Output
“`
(if(-1a)(print1))$ L$
(if(-1a)(print1))$ EL’$
(if(-1a)(print1))$ (E’L’$
if(-1a)(print1))$ E’L’$
if(-1a)(print1))$ C)L’$
if(-1a)(print1))$ ifEEC’)L’$
(-1a)(print1))$ EEC’)L’$
(-1a)(print1))$ (E’EC’)L’$
-1a)(print1))$ E’EC’)L’$
-1a)(print1))$ F)EC’)L’$
-1a)(print1))$ -L)EC’)L’$
1a)(print1))$ L)EC’)L’$
1a)(print1))$ EL’)EC’)L’$
1a)(print1))$ TL’)EC’)L’$
1a)(print1))$ 1L’)EC’)L’$
a)(print1))$ L’)EC’)L’$
a)(print1))$ EL’)EC’)L’$
a)(print1))$ VL’)EC’)L’$
a)(print1))$ aL’)EC’)L’$
)(print1))$ L’)EC’)L’$
)(print1))$ )EC’)L’$
(print1))$ EC’)L’$
(print1))$ (E’C’)L’$
print1))$ E’C’)L’$
print1))$ F)C’)L’$
print1))$ printL)C’)L’$
1))$ L)C’)L’$
1))$ EL’)C’)L’$
1))$ TL’)C’)L’$
1))$ 1L’)C’)L’$
))$ L’)C’)L’$
))$ )C’)L’$
)$ C’)L’$
)$ )L’$
$ L’$
$ $
ACCEPTED
“`
### Test Example 2
Input
“`
(print (+ 1 (print 2)) )
“`
output
“`
(print(+1(print2)))$ L$
(print(+1(print2)))$ EL’$
(print(+1(print2)))$ (E’L’$
print(+1(print2)))$ E’L’$
print(+1(print2)))$ F)L’$
print(+1(print2)))$ printL)L’$
(+1(print2)))$ L)L’$
(+1(print2)))$ EL’)L’$
(+1(print2)))$ (E’L’)L’$
+1(print2)))$ E’L’)L’$
+1(print2)))$ F)L’)L’$
+1(print2)))$ +L)L’)L’$
1(print2)))$ L)L’)L’$
1(print2)))$ EL’)L’)L’$
1(print2)))$ TL’)L’)L’$
1(print2)))$ 1L’)L’)L’$
(print2)))$ L’)L’)L’$
(print2)))$ EL’)L’)L’$
(print2)))$ (E’L’)L’)L’$
print2)))$ E’L’)L’)L’$
print2)))$ F)L’)L’)L’$
print2)))$ printL)L’)L’)L’$
2)))$ L)L’)L’)L’$
2)))$ EL’)L’)L’)L’$
2)))$ TL’)L’)L’)L’$
2)))$ 2L’)L’)L’)L’$
)))$ L’)L’)L’)L’$
)))$ )L’)L’)L’$
))$ L’)L’)L’$
))$ )L’)L’$
)$ L’)L’$
)$ )L’$
$ L’$
$ $
ACCEPTED
“`
### Test Example 3
Input
“`
(print (+ 1 (print 2)) )
“`
Output
“`
(print(+1(print2))$ L$
(print(+1(print2))$ EL’$
(print(+1(print2))$ (E’L’$
print(+1(print2))$ E’L’$
print(+1(print2))$ F)L’$
print(+1(print2))$ printL)L’$
(+1(print2))$ L)L’$
(+1(print2))$ EL’)L’$
(+1(print2))$ (E’L’)L’$
+1(print2))$ E’L’)L’$
+1(print2))$ F)L’)L’$
+1(print2))$ +L)L’)L’$
1(print2))$ L)L’)L’$
1(print2))$ EL’)L’)L’$
1(print2))$ TL’)L’)L’$
1(print2))$ 1L’)L’)L’$
(print2))$ L’)L’)L’$
(print2))$ EL’)L’)L’$
(print2))$ (E’L’)L’)L’$
print2))$ E’L’)L’)L’$
print2))$ F)L’)L’)L’$
print2))$ printL)L’)L’)L’$
2))$ L)L’)L’)L’$
2))$ EL’)L’)L’)L’$
2))$ TL’)L’)L’)L’$
2))$ 2L’)L’)L’)L’$
))$ L’)L’)L’)L’$
))$ )L’)L’)L’$
)$ L’)L’)L’$
)$ )L’)L’$
$ L’)L’$
$ )L’$
REJECTED
“`
## 6 Extension
I choose a) Use the FIRST and FOLLOW sets to implement an error recovery feature.
### Method
When there is no find entry in the parse table for the current top stack variable and the current terminal in the string, we can determine which terminals are expected through the first and follow set of the current top stack variable.
The expected terminals for variable X is the first set of variable X plus the follow set of variable X if ε in the first set of variable X. For example the expected terminals for L is a b c d 0 1 2 3 ( and the exepected terminals for L’ is a b c d 0 1 2 3 ( ).
### Usage
When the parser outputs message for user to delete. The user should input y or n.
When the parser prompt message for user to add, the user should add one terminal.
### Test Examples
### Example 1
“`
(if (-1 a) (print 1) 2 0)
“`
“`
(if(-1a)(print1)20)$ L$
(if(-1a)(print1)20)$ EL’$
(if(-1a)(print1)20)$ (E’L’$
if(-1a)(print1)20)$ E’L’$
if(-1a)(print1)20)$ C)L’$
if(-1a)(print1)20)$ ifEEC’)L’$
(-1a)(print1)20)$ EEC’)L’$
(-1a)(print1)20)$ (E’EC’)L’$
-1a)(print1)20)$ E’EC’)L’$
-1a)(print1)20)$ F)EC’)L’$
-1a)(print1)20)$ -L)EC’)L’$
1a)(print1)20)$ L)EC’)L’$
1a)(print1)20)$ EL’)EC’)L’$
1a)(print1)20)$ TL’)EC’)L’$
1a)(print1)20)$ 1L’)EC’)L’$
a)(print1)20)$ L’)EC’)L’$
a)(print1)20)$ EL’)EC’)L’$
a)(print1)20)$ VL’)EC’)L’$
a)(print1)20)$ aL’)EC’)L’$
)(print1)20)$ L’)EC’)L’$
)(print1)20)$ )EC’)L’$
(print1)20)$ EC’)L’$
(print1)20)$ (E’C’)L’$
print1)20)$ E’C’)L’$
print1)20)$ F)C’)L’$
print1)20)$ printL)C’)L’$
1)20)$ L)C’)L’$
1)20)$ EL’)C’)L’$
1)20)$ TL’)C’)L’$
1)20)$ 1L’)C’)L’$
)20)$ L’)C’)L’$
)20)$ )C’)L’$
20)$ C’)L’$
20)$ E)L’$
20)$ T)L’$
20)$ 2)L’$
0)$ )L’$
Error: got 0, but expected [)]
Delete input? (y/n): y
)$ )L’$
$ L’$
$ $
ACCEPTED
“`
#### Example 2
“`
(print (+ 1 (print 2)
“`
“`
(print(+1(print2)$ L$
(print(+1(print2)$ EL’$
(print(+1(print2)$ (E’L’$
print(+1(print2)$ E’L’$
print(+1(print2)$ F)L’$
print(+1(print2)$ printL)L’$
(+1(print2)$ L)L’$
(+1(print2)$ EL’)L’$
(+1(print2)$ (E’L’)L’$
+1(print2)$ E’L’)L’$
+1(print2)$ F)L’)L’$
+1(print2)$ +L)L’)L’$
1(print2)$ L)L’)L’$
1(print2)$ EL’)L’)L’$
1(print2)$ TL’)L’)L’$
1(print2)$ 1L’)L’)L’$
(print2)$ L’)L’)L’$
(print2)$ EL’)L’)L’$
(print2)$ (E’L’)L’)L’$
print2)$ E’L’)L’)L’$
print2)$ F)L’)L’)L’$
print2)$ printL)L’)L’)L’$
2)$ L)L’)L’)L’$
2)$ EL’)L’)L’)L’$
2)$ TL’)L’)L’)L’$
2)$ 2L’)L’)L’)L’$
)$ L’)L’)L’)L’$
)$ )L’)L’)L’$
$ L’)L’)L’$
$ )L’)L’$
Error: got $, but expected [)]
Add input? )
)$ )L’)L’$
$ L’)L’$
$ )L’$
Error: got $, but expected [)]
Add input? )
)$ )L’$
$ L’$
$ $
ACCEPTED
“`
### Example 3
“`
(print ( (+ 1 (print 2)))
“`
“`
(print((+1(print2)))$ L$
(print((+1(print2)))$ EL’$
(print((+1(print2)))$ (E’L’$
print((+1(print2)))$ E’L’$
print((+1(print2)))$ F)L’$
print((+1(print2)))$ printL)L’$
((+1(print2)))$ L)L’$
((+1(print2)))$ EL’)L’$
((+1(print2)))$ (E’L’)L’$
(+1(print2)))$ E’L’)L’$
Error: got (, but expected [+, -, *, print, if]
Add input? +
+(+1(print2)))$ E’L’)L’$
+(+1(print2)))$ F)L’)L’$
+(+1(print2)))$ +L)L’)L’$
(+1(print2)))$ L)L’)L’$
(+1(print2)))$ EL’)L’)L’$
(+1(print2)))$ (E’L’)L’)L’$
+1(print2)))$ E’L’)L’)L’$
+1(print2)))$ F)L’)L’)L’$
+1(print2)))$ +L)L’)L’)L’$
1(print2)))$ L)L’)L’)L’$
1(print2)))$ EL’)L’)L’)L’$
1(print2)))$ TL’)L’)L’)L’$
1(print2)))$ 1L’)L’)L’)L’$
(print2)))$ L’)L’)L’)L’$
(print2)))$ EL’)L’)L’)L’$
(print2)))$ (E’L’)L’)L’)L’$
print2)))$ E’L’)L’)L’)L’$
print2)))$ F)L’)L’)L’)L’$
print2)))$ printL)L’)L’)L’)L’$
2)))$ L)L’)L’)L’)L’$
2)))$ EL’)L’)L’)L’)L’$
2)))$ TL’)L’)L’)L’)L’$
2)))$ 2L’)L’)L’)L’)L’$
)))$ L’)L’)L’)L’)L’$
)))$ )L’)L’)L’)L’$
))$ L’)L’)L’)L’$
))$ )L’)L’)L’$
)$ L’)L’)L’$
)$ )L’)L’$
$ L’)L’$
$ )L’$
Error: got $, but expected [)]
Add input? )
)$ )L’$
$ L’$
$ $
ACCEPTED
“`