Exercise 4        Name __________________        Score __/26

  1. (8) Find FIRST and FOLLOW sets for the grammar:
    Given a non-terminal A, the set FOLLOW(A) consists of terminals and possibly $ is defined as:
    1. if A is a start symbol then $ is in Follow(A).
    2. if production B ® a A g , then First(g)-{є} is in Follow(A)
    3. if production B ® a A g , such that є is in First(g), then Follow(A) contains Follow(B); since whatever follows B can follow A when g=є
    4. if production B ® a A, then Follow(A) contains Follow(B); since whatever follows B can follow A
    S ® ABC              
    A ® a | Cb | є   
    B ® c | dA | є     
    C ® e | f                  		FIRST(S)={a,c,d,e,f}
    FIRST(A)={a,e,f,є}
    FIRST(B)={c,d,є}
    FIRST(C)={e,f}    		 FOLLOW(S)={$} Rule 1.
    FOLLOW(A)=FIRST(B)ÈFIRST(C)ÈFOLLOW(B)={c,d,e,f} Rule 2, 3 and 4.
    FOLLOW(B)=FIRST(C)={e,f} Rule 2
    FOLLOW(C)=FIRST(b) ={b}ÈFOLLOW(S) = {b,$} Rule 2 and 4
  2. (4) Give the parse table for Question 1.
     
    Blank entries are error conditions. Rules for typical production X ® b are:
    1. For all terminals a in FIRST(b) except є, [X,a] = X ® b
    2. If b=є or if є is in FIRST(b) then: For all a in FOLLOW(X), [X,a]=X ® є
      a b c d e f $
    S S ® ABC   S ® ABC S ® ABC S ® ABC S ® ABC  
    A A ® a  
    A ®є
    A ®є    		 A ® Cb
    A ®є    		 A ® Cb
    A ®є    		  
    B     B ® c B ® dA B ® є B ® є  
    C         C ® e C ® f  


     

  3. (2) For grammar A ® Ac | Ad | e | f  which strings are valid?
    1. e Ö
    2. ccce
    3. cdccd
    4. ecdccdf
    5. fcdcd Ö
       
  4. (2) Remove left-recursion in the grammar:  A ® Ac | Ad | e | f

    A ® eA' | fA'
    A' ® cA' | dA' | є
     
  5. (4) Using GRAMMAR 3.1 and the LR parsing TABLE 3.19, give a bottom-up parse with the following of: x:=a+3

    x:=a+3
    Stack Input Action row,column entry
    1 x:=a+3$ shift 1,id s4
    1id4 :=a+3$ shift 4,:= s6
    1id4:=6 a+3$ shift 6,id s20
    1id4:=6id20 +3$ reduce E ® id 20,+ r4
          6,E g11
    1id4:=6E11 +3$ shift 11,+ s16
    1id4:=6E11+16 3$ shift 16,num s10
    1id4:=6E11+16num10 $ reduce E ® num 10,$ r5
          16,E g17
    1id4:=6E11+16E17 $ reduce E ® E+E 17,$ r6
          6,E g11
    1id4:=6E11 $ reduce S ® id:=E 11,$ r2
    1S $   1,S g2
    1S $ accept 2,$