COS 320 Compilers David Walker last time context free grammars Appel 3 1 terminals non terminals rules derivations parse trees ambiguous grammars recursive descent parsers Appel 3 2 parse LL k grammars easy to write as ML programs algorithms for automatic construction from a CFG non terminals S E L terminals NUM IF THEN ELSE BEGIN END PRINT rules 1 S IF E THEN S ELSE S 4 L END 2 BEGIN S L 5 SL 3 PRINT E 6 E NUM NUM datatype token NUM IF THEN ELSE BEGIN END PRINT SEMI EQ val tok ref getToken fun advance tok getToken fun eat t if tok t then advance else error fun S case tok of IF eat IF E eat THEN S eat ELSE S BEGIN eat BEGIN S L PRINT eat PRINT E and L case tok of END eat END SEMI eat SEMI S L and E eat NUM eat EQ eat NUM Constructing RD Parsers To construct an RD parser we need to know what rule to apply when we have seen a non terminal X we see the next terminal a in input We apply rule X s when a is the first symbol that can be generated by string s OR s reduces to the empty string is nullable and a is the first symbol in any string that can follow X Computing Nullable Sets Non terminal X is Nullable only if the following constraints are satisfied computed using iterative analysis base case if X then X is Nullable inductive case if X ABC and A B C are all Nullable then X is Nullable Computing First Sets First X is computed iteratively base case if T is a terminal symbol then First T T inductive case if X is a non terminal and X ABC then First X First X U First ABC where First ABC F1 U F2 U F3 U and F1 First A F2 First B if A is Nullable F3 First C if A is Nullable B is Nullable Computing Follow Sets Follow X is computed iteratively base case initially we assume nothing in particular follows X Follow X is initially inductive case if Y s1 X s2 for any strings s1 s2 then Follow X First s2 U Follow X if Y s1 X s2 for any strings s1 s2 then Follow X Follow Y U Follow X if s2 is Nullable building a predictive parser Z X Y Z Z d Y c Y nullable Z Y X X a X b Y e first follow building a predictive parser Z X Y Z Z d Y c Y nullable Z no Y yes X no base case X a X b Y e first follow building a predictive parser Z X Y Z Z d Y c Y nullable Z no Y yes X no X a X b Y e first follow after one round of induction we realize we have reached a fixed point building a predictive parser Z X Y Z Z d Y c Y X a X b Y e nullable first Z no d Y yes c X no a b base case follow building a predictive parser Z X Y Z Z d Y c Y X a X b Y e nullable first Z no d a b Y yes c X no a b after one round of induction no fixed point follow building a predictive parser Z X Y Z Z d Y c Y X a X b Y e nullable first Z no d a b Y yes c X no a b follow after two rounds of induction no more changes fixed point building a predictive parser Z X Y Z Z d Y c Y X a X b Y e nullable first follow Z no d a b Y yes c X no a b base case building a predictive parser Z X Y Z Z d Y c Y X a X b Y e nullable first follow Z no d a b Y yes c e d a b X no a b c d a b after one round of induction no fixed point building a predictive parser Z X Y Z Z d Y c Y X a X b Y e nullable first follow Z no d a b Y yes c e d a b X no a b c d a b after two rounds of induction fixed point but notice computing Follow X before Follow Y would have required 3rd round Grammar Z X Y Z Z d Computed Sets Y c Y X a X b Y e Build parsing table where row X col T tells parser which clause to execute in function X with next token T a Z Y X b nullable first follow Z no d a b Y yes c e d a b X no a b c d a b if T First s then enter X s in row X col T if s is Nullable and T Follow X enter X s in row X col T c d e Grammar Z X Y Z Z d Computed Sets Y c Y X a X b Y e Build parsing table where row X col T tells parser which clause to execute in function X with next token T Z Y X a b Z XYZ Z XYZ nullable first follow Z no d a b Y yes c e d a b X no a b c e d a b if T First s then enter X s in row X col T if s is Nullable and T Follow X enter X s in row X col T c d e Grammar Z X Y Z Z d Computed Sets Y c Y X a X b Y e Build parsing table where row X col T tells parser which clause to execute in function X with next token T Z Y X a b Z XYZ Z XYZ nullable first follow Z no d a b Y yes c e d a b X no a b c e d a b if T First s then enter X s in row X col T if s is Nullable and T Follow X enter X s in row X col T c d Z d e Grammar Z X Y Z Z d Computed Sets Y c Y X a X b Y e Build parsing table where row X col T tells parser which clause to execute in function X with next token T Z Y X a b Z XYZ Z XYZ nullable first follow Z no d a b Y yes c e d a b X no a b c e d a b if T First s then enter X s in row X col T if s is Nullable and T Follow X enter X s in row X col T c d Z d Y c e Grammar Z X Y Z Z d Computed Sets Y c Y X a …