CSc 4340/6340, Introduction to Compilers
Fall 2004
Assignment 3 Solutions
Solutions to Chapter 2 problems
In the form of Prolog
code (please decipher into state transition diagram yourself).
3.5
Grammar:
1. S1 --> S$
2. S --> epsilon |
3. XS
4. B --> \ begin { WORD }
5. E --> \ end { WORD }
6. X --> B S E |
7. { S } |
8. WORD |
9. begin |
10. end |
11. \ WORD
FIRST sets:
B: \
E: \
S: epsilon \ { WORD begin end
S1: $ \ { WORD begin end
X: \ { WORD begin end
FOLLOW sets:
B: \ { WORD begin end
E: \ { WORD begin end DOLLAR }
S: $ \ }
S1:
X: \ { WORD begin end $ }
LL(1) Parse Table (Production Rule numbers are listed)
\ begin end WORD { } $
S1 1 1 1 1 1
S 2,3 3 3 3 3 2 2
B 4
E 5
X 6,11 9 10 8 7
3.6
Grammar
1. S --> uBDz
2. B --> Bv |
3. w
4. D --> EF
5. E --> y |
6. epsilon
7. F --> x |
8. epsilon
FIRST sets:
B: w
D: y x epsilon
E: y epsilon
F: x epsilon
S: u
FOLLOW sets:
B: v y x z
D: z
E: x z
F: z
S:
LL(1) Parse Table (Production Rule numbers are listed)
u v w x y z
S 1
B 2,3
D 4 4 4
E 6 5 6
F 7 7
Replace the rules B --> Bv | w
By B --> vB' | w
B' --> B