Notes for week 6

Day 1

Constructing the Predictive Parser Table

1. Motivation
   1. The Stack holds the list of procedure names used in recursive calls and the current character
   2. The Table replaces the body of each of the procedures
      1. When the top is a terminal that matches an input symbol, the terminals are discarded.
      2. When the input symbol is in the first of one of the top-down procedures called from the current procedure (non terminal) replace the non-terminal by the production. (the if then else sequence in recursive descent.
      3. In the case of an e production, match on a non terminal in the follow .
2. Building the table.
   1. Compute the first and follow for each grammar item.
   2. For each non terminal A compute the first of each production A->b that produces A.
   3. In the row of the table that represents A, place A->b (b not e )in the column of every member of First[b] other than e.
   4. If A ->e or A->b where e is in First[b], then place A->e in the column of every member of Follow(A).
3. Example

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

   1. Compute Firsts and Follows.

      First(E) = First(T) = First(F) = { (, i}
      First(R) = {*, /, e}
      First(Q) = { +, - ,e}
      First(+TQ) = {+}
      First(-TQ) = {-}
      First(*RF) = {*}
      First(/RF) = {/}
      
      Follow(E) = {$, )}
      Follow(Q) = Follow(E)
      Follow(T) = {+,-,),$}
      Follow(R) = Follow(T)
      Follow(F) = {+,-,*,/,),$}
      

   2. Construct the table row with E.

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

4. Conflicts. (Ambiguous grammars)
   1. Conflict occurs when two or more entries could be placed in the same table position.
      1. How could two or more entries for a table exist?
         1. If the Firsts of two or more different productions with the same left-hand side share the same terminals.
         2. If Follow of the left-hand side and First of some right-hand sides share items and the is an e -production (or a first with e )
      2. What can be done.
         1. Rewrite the grammar using left factorization
         2. Decide which of the reductions best reflects the grammar and insert it into the table.
   2. Left factorization
      1. A->a b E | a c F
      2. Left factor by creating a new nonterminal that represents all of the product beyond the a

         A-> aQ
         Q-> bE | cF
         

   3. Left factorization doesn't work;

      S -> if E then S | if E then S else S | a | b
      E -> x | y
      

      1. Left factor

         S -> if E then S Q | a | b
         E -> x | y
         Q -> else S | e
         

         1.  First(S) = {if,a,b}
            	First(Q) = {else, e }
            	Follow(S) = {$,else}
            	Follow(Q) = Follow(S)
            

         2. Create table

            	if	x	y	then	a	b	else	$
            S	if E then S Q				a	b
            E
            Q							else S | e	e

      2. Choose the else S because it will give the result you want.

Day 2

1. Introduction to Bottom-up Parsing
   1. Right-most derivation
      E -> E + E | E * E| i
      1. derivation of i + i * i

         E 	=> E + E
         	=>  E + E * E
         	=>  E + E * i
         	=>  E + i * i
         	=>  i + i * i
         

      2. Bottom up derivation of i + i * i

         i + i * i	see first i use E-> i to reduce i to E
         E + i * i	ignore + for now reduce i to E
         E + E * i	ignore * reduce i to E
         E + E * E	reduce E*E
         E + E		reduce E + E
         E
         

   2. Bottom up parse gives the right-most derivation.
2. Parsing with a Stack
   1. Handle is a right-hand side of a production that we can reduce to get the preceding step in the derivation.
      1. example if the top of the stack is i and the next token is * or +, i is the right-hand side of E-> i which is the correct reduction in all cases.
      2. if E + E is in the stack and * is next, E-> E+E should not be applied now so it is not a handle.
   2. Trace the previous example using a stack to hold onto items parsed at the current time.

      line		Stack		Input		Production
      1				i + i * i				
      2		i		+ i * i
      3		E		+ i * i		E-> i
      4		E + 		i * i
      5		E + i		* i						
      6		E + E		* i		E ->i	why not reduce E-> E+E here?
      7		E + E *		i
      8		E + E * i							
      9		E + E * E			E->i
      10		E + E				E -> E*E
      11		E				E -> E+ E
      

3. Show how to trace the derivation using columns 2 and 3 above.
4. Compare parse trees for this parse and one with E + E reduce in line 6

1. Bottom-up parser of arithmetic expressions.
2. Precedence Table
   1. Precedence symbols •>, <•, = , a•>b a has greater precedence than b.
   2. The Grammar

      E-> E + E | E * E | (E) | i

   3. The table.
      
      
   4. The process: Let x be at the top of the stack, y be incoming
      1. if x <• y or x = y then shift y onto the stack
      2. if x •> y there is a handle between <• and •> Pop the handle and replace with the left-hand side.
      3. if table entry empty or if symbols pop do not match right-hand side of any production there is an error.
      4. repeat until x =$ , y =$ or error
   5. Example i + i * i

      	Stack	Input	Production
      1	$	<• i + i * i $
      2	$<•i	•> + i * i$	E -> i
      3	$E	<• + i * i$	See through E and compare + and $
      4	$<• E +	•> i * i$
      5	$<•E + <•i	•> * i$
      6	$<•E + E	•> * i$	E -> i
      7	$<•E + <•E *	•> i$
      8	$<•E + <•E * <•i	•> $	E->i
      9	$<•E + <•E * <•E	•> $	E->E * E
      10	$<•E + E	•> $	E -> E + E
      11	$E	$