Exercise 3        Name __________________        Score __/26

1. (6) Translate each of the following into a context-free grammar. Use | for alternation.
   1. ((xy*x)|(yx*y))?
       
   2. ((0|1)⁺"."(0|1)*)|((0|1)*"."(0|1)⁺)
       
2. (2) Give the context free grammar that defines statement lists that are:
1. separated by ; for example: s; s; s; s
    
2. terminated by ; for example: s; s; s; s;
    
3. (4) Assume the definition of class, public, static, void, main, string, id, lbracket [, rbracket ], lparen (, rparen ), lbrace {, rbrace }  tokens and statement, vardecl and methoddecl  productions. Give the context free grammar in SableCC for MiniJava (see Appendix) that defines:
   1. MainClass -
   2. ClassDecl -
       
4. (3) Using Grammar 3.8 give the parse tree for: 3*4+5/6-2
    
5. (4) Find FIRST sets for the grammar:
    

   E ® TQ                        Q ® +TQ | -TQ | є        T ® FR                       R ® *FR|/FR|є               F ® (E) | i

6. (4) Find FOLLOW sets for above grammar.
7. (3) Give the predictive parsing table for the Grammar in Question 5.