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