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))?
      auxy ® y auxy | є
      auxx ® x auxx | є
      opxy ® x | y | є
      answer ® (x auxy x | y auxx y) opxy
    2. ((0|1)+"."(0|1)*)|((0|1)*"."(0|1)+)
      1ormore = (0|1) 1ormore | (0|1)
      0ormore = (0|1) 0ormore | є
      1ormore "." 0ormore | 0ormore "." 1ormore
      3. (2)
  2. (2) Give the context free grammar that defines statement lists that are:
    1. separated by ; for example: s; s; s; s
      stmtlist ® stmt ; stmtlist | stmt
      stmt ® s
    2. terminated by ; for example: s; s; s; s;
      stmtlist ® stmt ; stmtlist | є
      stmt ® 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 - main_class = class id lbrace public static void main lparen string lbracket rbracket id  r_parenthese lbrace statement rbrace rbrace;
    2. ClassDecl - class_decl = class identifier lbrace vardecl* method_decl* rbrace;
       
    3. (3) Using Grammar 3.8 give the parse tree for: 3*4+5/6-2
                                  E     
                            /     |     \
                          E      -      T  
                      /   |   \          |
                    E    +   T         F
                 /  |  \    /  |  \     |
                T  *  F   T  /   F    2
                |      |    |       |
                F     4    F      6
                |           |
                3          5
    4. (4) Find FIRST sets for the grammar:
       
      E ® TQ                       
      Q ® +TQ | -TQ | є       
      T ® FR                      
      R ® *FR|/FR|є              
      F ® (E) | i                             		FIRST(E)=FIRST(T)=FIRST(F)={(,i}
      FIRST(Q)={+,-, є}
      FIRST(R)={*,/,є)
      FIRST(+TQ)={+}
      FIRST(-TQ)={-}
      FIRST(*FR)={*}
      FIRST(/FR)={/}
      FIRST((E)={(}
      FIRST(i)={i}

       

    5. (4) Find FOLLOW sets for above grammar.
      FOLLOW(E)={$,)} since E is start and on right-hand side E is F ® (E)

      FOLLOW(Q)={$,)}=FOLLOW(E) Q only appears at end (E ® TQ) so includes FOLLOW(E). Other productions have Q on left and right.

      FOLLOW(T)={+,-,),$}

      • includes FIRST(Q)-{є}={+,-}.
      • Q is nullable (FIRST(Q) includes є) include FOLLOW(E). To see why FOLLOW(E) included consider F ® (E). Substituting E ® TQ gives F ® (TQ). If Q=є then we have F ® (T) so now ) follows T.
      • Q productions add nothing since +TQ and -TQ.

      FOLLOW(R)=FOLLOW(T)={+,-,),$}

      FOLLOW(F)={+,-,*,/,),$} includes FIRST(R)-{є}={*,/}. R is nullable include FOLLOW(T).
       

    6. (3) Give the predictive parsing table for the Grammar in Question 5.
    E ® TQ                       
    Q ® +TQ | -TQ | є       
    T ® FR                      
    R ® *FR|/FR|є              
    F ® (E) | i                           		FIRST(E)=FIRST(T)=FIRST(F)={(,i}
    FIRST(Q)={+,-, є}
    FIRST(R)={*,/,є)
    FIRST(+TQ)={+}
    FIRST(-TQ)={-}
    FIRST(*FR)={*}
    FIRST(/FR)={/}
    FIRST((E))={(}
    FIRST(i)={i}    		 FOLLOW(E)={$,)}
    FOLLOW(Q)={$,)}
    FOLLOW(T)={+,-,),$}
    FOLLOW(R)={+,-,),$}
    FOLLOW(F)={+,-,*,/,),$}

    E ® TQ             FIRST(T)={(,i} so [E,(] and [E,i]=E ® TQ           
    Q ® +TQ          FIRST(+TQ)={+} so [Q,+]=Q ® +TQ
    Q ® -TQ           FIRST(-TQ)={-} so [Q,+]=Q ® -TQ
    T ® FR             FIRST(F)={(,i} so [T,(] and [T,i] = T ® FR         
    R ® *FR           FIRST(*FR)={*} so [R,*]=R ® *FR
    R ® /FR            FIRST(/FR)={/} so [R,/]=R ® /FR              
    F ® (E)            FIRST((E))={(} so [F,(]=F ® (E)
    F ®  i              FIRST(i)={i} so [F,i] = F ®  i