CSc 453Compilers and Systems Software8 : Top-Down Parsing IIIDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergPredictive ParsingPredictive ParsingJust as with lexical analysis, we can either hard-code atop-down parser, or build a generic table-driven interpreter.The latter is called a Predictive Parser.Instead of using recursion we store the current state of theparse on a stack:ErrorsINTERPRETERZX$Ya+b$Input:Parsing tableStack:Predictive Parsing. . .The predictive parser has1an input stream (list of tokens followed by theend-of-file-marker $),2a stack with a sequence of grammar symbols, and anend-of-stack-marker $,3a parsing table M[A, a] → P mapping a non-terminal A and aterminal a to a grammar production P.Initally, the stack holds the start symbol, S.Predictive Parsing. . .At each step, the interpreter looks at the top stack element (X)and the current input symbol (a). There are three cases:1X = a = $ ⇒ success!2M[X , a] = error ⇒ bail!3X = a 6= $ ⇒ match(). Move to next token and pop off X .4M[X , a] = {X → UVW } ⇒1Pop X off the stack, then2Push(W ), Push(V ), Push(U).The next slide shows the algorithm in more detail.a := first tokenrepeatX := top()if X is a terminal or $ thenif X = a thenpop()a := next tokenelse errorelseif M[X , a] = X → Y1Y2· · · Ykthenpop()push(Yk); · · · ; Push(Y1)else erroruntil X = $The Predictive parsing table for the grammar below:id + * ( ) $E E → TE′E → TE′E′E′→ +TE′E′→ ǫ E′→ ǫT T → FT′T → FT′T′T′→ ǫ T′→ *FT′T′→ ǫ T′→ ǫF F → id F → (E)E → T E′E′→ + T E′| ǫT → F T′T′→ * F T′| ǫF → ( E ) | idStack Input M[A, a] =$E id+id*id$$E′T id+id*id$ E → TE′$E′T′Fid+id*id$ T → FT′$E′T′idid+id*id$ F → id$E′T′+id*id$$E′+id*id$ T′→ ǫ$E′T ++id*id$ E′→ +TE′$E′Tid*id$Stack Input M[A, a] =$E′T′F id*id$ T → FT′$E′T′idid*id$ F → id$E′T′*id$$E′T′F * *id$ T′→ *FT′$E′T′Fid$$E′T′id id$ F → id$E′T′$$E′$ T′→ ǫ$ $ E′→ ǫStack Input M[A, a] =$E id+*$$E′T id+*$ E → TE′$E′T′Fid+*$ T → FT′$E′T′idid+*$ F → id$E′T′+*$$E′+*$ T′→ ǫ$E′T + +*$ E′→ +TE′$E′T*$ Error!Building the Parse Table. . .for each production A → α dofor each terminal a in FIRST(α) doM[A, a] := {A → α}if ǫ is in FIRST(α) thenfor each terminal b in FOLLOW(A) doM[A, b] := {A → α}if ǫ is in FIRST(α) and $ is in FOLLOW(A) thenM[A, $] := {A → α}for all undefined entries M[A, a] doM[A, a] := errorE → T E′E′→ +T E′| ǫT → F T′T′→ *F T′| ǫF → (E ) | idFIRST(E) = {(, id}FIRST(E′) = {+, ǫ}FIRST(T ) = {(, id}FIRST(T′) = {*, ǫ}FIRST(F ) = {(, id}FOLLOW(E) = {), $}FOLLOW(E′) = {), $}FOLLOW(T ) = {+, ), $}FOLLOW(T′) = {+, ), $}FOLLOW(F ) = {+, *, ), $}Predictive Parsing – Building the Tableid + * ( ) $E E → TE′E → TE′E′TT′FWe start by looking at production E → TE′.Since FIRST(TE′) = FIRST(T) = {(, id} we setM[E , (] = M[E , id] = E → TE′.Predictive Parsing – Building the Table. . .id + * ( ) $E E → TE′E → TE′E′E′→ +TE′TT′FWe next consider production E′→ +TE′.Since FIRST(+TE′) = {+} we set M[E′, +] = E′→ +TE′.Predictive Parsing – Building the Table. . .id + * ( ) $E E → TE′E → TE′E′E′→ +TE′E′→ ǫ E′→ ǫTT′FWe next consider production E′→ ǫ.Since FOLLOW(E′) = {), $} we setM[E′, )] = M[E′, $] = E′→ ǫ.Predictive Parsing – Building the Table. . .id + * ( ) $E E → TE′E → TE′E′E′→ +TE′E′→ ǫ E′→ ǫT T → FT′T → FT′T′FWe next consider production T → FT′.Since FIRST(FT′) = {(, id} we setM[T , (] = M[T , id] = T → FT′.Predictive Parsing – Building the Table. . .id + * ( ) $E E → TE′E → TE′E′E′→ +TE′E′→ ǫ E′→ ǫT T → FT′T → FT′T′T′→ ∗FT′FWe next consider production T′→ ∗FT′.Since FIRST(∗FT′) = {*} we set M[T′, *] = T′→ ∗FT′.Predictive Parsing – Building the Table. . .id + * ( ) $E E → TE′E → TE′E′E′→ +TE′E′→ ǫ E′→ ǫT T → FT′T → FT′T′T′→ ǫ T′→ ∗FT′T′→ ǫ T′→ ǫFWe next consider production T′→ ǫ.Since FOLLOW(T′) = {+, ), $} we setM[T′, +] = M[T′, )] = M[T′, $] = T′→ ǫ.Predictive Parsing – Building the Table. . .id + * ( ) $E E → TE′E → TE′E′E′→ +TE′E′→ ǫ E′→ ǫT T → FT′T → FT′T′T′→ ǫ T′→ ∗FT′T′→ ǫ T′→ ǫF F → id F → (E )We next consider production F → (E ).Since FIRST((E)) = {(} we set M[F , (] = F → (E ).We finally consider production F → id.Since FIRST(id) = {id} we set M[F, id] = F → id.Parsing ExpressionsHere’s a simple implementation of predictive parsing in Java.Grammar symbols (both terminals and non-terminals) arerepresented by single characters: e represents E’, f representsF’, i represents id, "" represents epsilon, null represents error.The function table(X,a) looks up the relevant production.class Expr {static String[] input = {"i","+","i","*","i","$"};static int current = 0;static boolean isTerminal(String S) {return S.equals("*") | S.equals("+") |S.equals("i") |S.equals("(") | S.equals(")");}static String[][] TABLE = {// id + * ( ) ${"Te", null, null, "Te", null, null}, // E{null, "+Te", null, null, "", ""}, // E’{"Ft", null, null, "Ft", null, null}, // T{null, "", "*Ft", null, "", ""}, // T’{"i", null, null, "(E)", null, null} // F};static String table(String X, String a){int aIdx, XIdx=-1;switch (a.charAt(0)) {case ’i’ : aIdx=0; break;case ’+’ : aIdx=1; break;case ’*’ : aIdx=2; break;case ’(’ : aIdx=3; break;case ’)’ : aIdx=4; break;case ’$’ : aIdx=5; break; }switch (X.charAt(0)) {case ’E’ : XIdx=0; break;case ’e’ : XIdx=1; break;case ’T’ : XIdx=2; break;case ’t’ : XIdx=3; break;case ’F’ : XIdx=4; break; }return TABLE[XIdx][aIdx];}static boolean interpret(){push("$"); push("E");String a, X;while(true) {a = input[current];X = top();if (isTerminal(X) | X.equals("$")) {if (a.equals(X)) {pop(); current++;}else return false;} else {pop();String prod = table(X,a);if (prod==null) return false;for(int i=prod.length()-1;i>=0;i--)push(prod.charAt(i));}if (X.equals("$")) return true;}}Error RecoveryError Recovery1Quit on first error. Considered unacceptable. But, with