COS 320 Compilerslast timeSlide 3Constructing RD ParsersComputing Nullable SetsComputing First SetsComputing Follow Setsbuilding a predictive parserSlide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26predictive parsing tablesanother trickSlide 29summary of RD parsingSlide 31Bottom-up (Shift-Reduce) Parsingshift-reduce parsingshift-reduce parsing exampleSlide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Shift-reduce algorithmShift-reduce algorithm (a detail)Slide 52Slide 53shift-reduce errorsSlide 55Slide 56reduce-reduce errorsSummaryCOS 320CompilersDavid Walkerlast 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 CFG1. S ::= IF E THEN S ELSE S2. | BEGIN S L3. | PRINT E 4. L ::= END5. | ; S L6. E ::= NUM = NUM non-terminals: S, E, Lterminals: NUM, IF, THEN, ELSE, BEGIN, END, PRINT, ;, =rules: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 NUMval tok = ref (getToken ())fun advance () = tok := getToken ()fun eat t = if (! tok = t) then advance () else error ()datatype token = NUM | IF | THEN | ELSE | BEGIN | END | PRINT | SEMI | EQConstructing 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 XComputing 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 NullableComputing 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 Nullablebuilding a predictive parserZ ::= X Y ZZ ::= dY ::= cY ::= X ::= aX ::= b Y enullable first followZYXbuilding a predictive parserZ ::= X Y ZZ ::= dY ::= cY ::= X ::= aX ::= b Y enullable first followZ noY yesX nobase casebuilding a predictive parserZ ::= X Y ZZ ::= dY ::= cY ::= X ::= aX ::= b Y enullable first followZ noY yesX noafter one round of induction, we realize we have reached a fixed pointbuilding a predictive parserZ ::= X Y ZZ ::= dY ::= cY ::= X ::= aX ::= b Y enullable first followZ no dY yes cX no a,bbase casebuilding a predictive parserZ ::= X Y ZZ ::= dY ::= cY ::= X ::= aX ::= b Y enullable first followZ no d,a,bY yes cX no a,bafter one round of induction, no fixed pointbuilding a predictive parserZ ::= X Y ZZ ::= dY ::= cY ::= X ::= aX ::= b Y enullable first followZ no d,a,bY yes cX no a,bafter two rounds of induction, no more changes ==> fixed pointbuilding a predictive parserZ ::= X Y ZZ ::= dY ::= cY ::= X ::= aX ::= b Y enullable first followZ no d,a,b { }Y yes c { }X no a,b { }base casebuilding a predictive parserZ ::= X Y ZZ ::= dY ::= cY ::= X ::= aX ::= b Y enullable first followZ no d,a,b { }Y yes c e,d,a,bX no a,b c,d,a,bafter one round of induction, no fixed pointbuilding a predictive parserZ ::= X Y ZZ ::= dY ::= cY ::= X ::= aX ::= b Y enullable first followZ no d,a,b { }Y yes c e,d,a,bX no a,b c,d,a,bafter two rounds of induction, fixed point (but notice, computing Follow(X) before Follow (Y) would have required 3rd round)Z ::= X Y ZZ ::= dY ::= cY ::= X ::= aX ::= b Y enullable first followZ no d,a,b { }Y yes c e,d,a,bX no a,b c,d,a,bGrammar:Computed Sets:Build parsing table where row X, col Ttells parser which clause to execute infunction X with next-token T:a b c d eZYX• 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 TZ ::= X Y ZZ ::= dY ::= cY ::= X ::= aX ::= b Y enullable first followZ no d,a,b { }Y yes c e,d,a,bX no a,b c,e,d,a,bGrammar:Computed Sets:Build parsing table where row X, col Ttells parser which clause to execute infunction X with next-token T:a b c d eZ Z ::= XYZ Z ::= XYZYX• 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 TZ ::= X Y ZZ ::= dY ::= cY ::= X ::= aX ::= b Y enullable first followZ no d,a,b { }Y yes c e,d,a,bX no a,b c,e,d,a,bGrammar:Computed Sets:Build parsing table where row X, col Ttells parser which clause to execute infunction X with next-token T:a b c d eZ Z ::= XYZ Z ::= XYZ Z ::= dYX• 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 TZ ::= X Y ZZ ::= dY ::= cY ::= X ::= aX ::= b Y enullable first followZ no d,a,b { }Y yes c e,d,a,bX no a,b c,e,d,a,bGrammar:Computed Sets:Build parsing table where row X, col Ttells parser which clause to execute infunction X with next-token T:a b c d eZ Z ::= XYZ Z ::= XYZ Z ::= dY Y ::= cX• 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 TZ ::= X Y ZZ ::= dY ::= cY ::= X ::= aX ::= b Y enullable first followZ no d,a,b { }Y yes c e,d,a,bX no a,b c,e,d,a,bGrammar:Computed Sets:Build parsing table where row X, col Ttells parser which clause to execute infunction X with next-token T:a b c d eZ Z ::= XYZ Z ::= XYZ Z ::= dY Y ::= Y ::= Y ::= c …