Compilers: Principles and Practice

EXERCISES

1. Check which of the following are LL(1):

   (a) S –> A | B
        A –> aA | a    	 
        B –> bB | b
    (b) S –> AB   	    
        A –> Ba
        B –> Cb | c	
        C –> c  
    (c) S –> aAaB | bAbB
        A –> S | cb
        B –> cB | a
   

2. Have you wondered why we did not discuss LL(k), k > 1 parsers, say LL(2) parsers? Try to form a parsing function M() for LL(2) parser.
3. Try to convert the following grammar to a regular expression:

   S –> aA	  B –> bC
   A –> aA	  C –> cB
   A –> aB	  C –> c
   

4. Show that the following grammar is not LL(1):

   V –> S#	  
   S –> aAa | empty
   A –> abS | c
   

5. Give the rules by which you can distinguish the following types of grammars: Regular, LL(1) with and without empty rules, context-sensitive, LR(0) and SLR(1).
6. Check if the following grammar is SLR(1) or not:

   S –> E# E –> T E –> E;T T –> empty T –> ...