Notes for week 5

Day 1

1. Problem: When do you choose the production A ->e ?
   1. The function Follow(A) is called to determine if the current symbol can follow A.
   2. General idea if you can see through what could you see in a legal string?
   3. How can you tell?
      1. The Start symbol is always followed by $ (the end of string marker)
      2. If Q -> x A y then y follows A. What is y?
         1. If y is terminal then
            Follow(A) includes y
         2. If y is nonterminal two things can happen.
            1. Things at the begining of y can follow A i.e. Follow(A) contains First(y) - e .
            2. If y -> e or y = e (A at the end of the production) then you can see throught y and anything that follows Q follows A.
               i.e. Follow(A) contains Follow(Q).
      3. Example.

         S -> Ab | Bc
         A -> Df  | CA
         B -> gA | e
         C -> dC | c
         D -> h | i
         
         First compute all of the firsts.
         First(S) = First(A)UFirst(B); ({h, i, d, c}U{g, e} ={h, i, d, c, g, e}
         First(A) = First(D)UFirst(C); (= {h, i}U{d, c} = {h, i, d, c})
         First(B) = {g, e}
         First(C) = {d, c}
         First (D) = {h, i}
         
         Start at the start symbol (in this case S)
         $ is in the follow of S. S does not appear on the right, so 
         Follow(S) = {$} (in most of our grammars Follow for start will be {$}
         
         
         Compute Follow(A)
         Step 1. Where does A appear on the right-hand side of a production?
         1) S -> Ab
         2) A -> CA
         3) B -> gA
         
         From 1) we know b is in Follow(A)
         2 tells us the Follow of A is in itself (we ignor all cases with A on left
         3. tells us that the Follow(B) is in the Follow(A), but we don't know the Follow(B)=> recursive call.
         
         Follow(B)
         1)  S -> Bc
          Follow(B)  = {c}
         Follow (A) = {b, c}
         
         Follow (B) is known 
         
         Find Follow(C);
         1. A -> C A  => C contains First(A) -e  = {h, i, d, c} no e in First(A) A is not in A-> e , So A does not contain Follow(A).
         2. C -> dC => no help
         Follow(C) = {h, i, d, c}
         
         Find Follow(D)
         A -> Df so 
         Follow(D) = {f}
         E. Example 2
         E -> TQ
         Q -> +TQ | -TQ | e 
         T -> FR
         R -> *FR | /FR | e 
         F -> (E) | i
         
         Compute Firsts.
         First(E) = First(T) = First(F) = { (, i}
         First(R) = {*, /, e }
         First(Q) = { +, - ,e }
         
         Compute Follows:
         Follow(E) contains {$} and from F -> (E) it contains ). {$, )}
         Follow(Q) = Follow(E) why? 
         
         Follow(T)
         1. E -> TQ
         2. Q -> + TQ
         3. Q -> - TQ
         
         All indicate Follow(T) contains First(Q) - e = {+, -}
         Q -> e  indicates that Follow(T) also contains Follow(E) and Follow(Q)
         Follow(T) = {+, -, ), $}
         
         Follow (R) = Follow(T)
         
         Follow(F)
         
         T -> FR
         R -> *FR | /FR | e 
         Follow(F) = {+, -, *, /, ), $)
         

2. Using First and Follow in a recursive descent parser
   1. Computer the Firsts for each right hand side. For each nonterminal write a procedure that parses the right-hand side of a product if the current token is in the First of that right-hand side.
   2. If the nonterminial produces e, then insert an else if the symbol is not the Follow of the nonterminal find an error. (This may be less useful than letting the next routine find the error).

Day 2

Table Driven Predictive Parsers.

1. Grammar

   E -> TQ
   Q -> +TQ | -TQ | e 
   T -> FR
   R -> *FR | /FR | e 
   F -> (E) | i
   
   

2. Table
3. Using the table to parse:
   1. Push $ into the stack
   2. Put $ at the end of the input string.
   3. Push the grammars start symbol - Start at the top
   4. While stack is not empty do

      begin
      	Let x be the top of the stack and a be the incoming token
      	If x is in the set of terminals T then
      		if x = a then 
      			pop x and go to next input item
      		else
      			error
      	else
      	if Table[x,a] nonblank then
      	begin
      		pop x;
      		push Table[x,a] onto stack in reverse order
      	end
      	else
      		error
      end
      

   5. Examples
      1. (i + i)*i
      2. i + i*(i + i)
      3. (i*) errors
      4. other errors if time