CSc 453 — Compilers and Systems Software8 : Top-Down Parsing IIIChristian CollbergDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergOctober 12, 20091Predictive Parsing2 Predictive Parsing• Just as with lexical analysis, we can either hard-code a top-down parser, or build a generic table-driveninterpreter. The latter is called a Predictive Parser.• Instead of using recursion we store the current state of the parse on a stack:ErrorsINTERPRETERZX$Ya+b$Input:Parsing tableStack:3 Predictive Parsing. . .• The predictive parser has1. an input stream (list of tokens followed by the end-of-file-marker $),2. a stack with a sequence of grammar symbols, and an end-of-stack-marker $,3. a parsing table M[A, a] → P mapping a non-terminal A and a terminal a to a grammar productionP .• Initally, the stack holds the start symbol, S.14 Predictive Parsing. . .At each step, the interpreter looks at the top stack element (X) and the current input symbol (a). Thereare three cases:1. X = a = $ ⇒ success!2. M[X, a] = error ⇒ bail!3. X = a 6= $ ⇒ match(). Move to next token and pop off X.4. M[X, a] = {X → U V W } ⇒(a) Pop X off the stack, then(b) Push(W ), Push(V ), Push(U).The next slide shows the algorithm in more detail.5a := 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 = $6• The Predictive parsing table for the grammar below:id + * ( ) $E E → T E′E → T E′E′E′→ +T E′E′→ ǫ E′→ ǫT T → F T′T → F T′T′T′→ ǫ T′→ *F T′T′→ ǫ T′→ ǫF F → id F → (E)E → T E′E′→ +T E′| ǫT → F T′T′→ *F T′| ǫF → (27StackInput M[A, a] =$E id+id*id$$E′T id+id*id$ E → T E′$E′T′Fid+id*id$ T → F T′$E′T′idid+id*id$ F → id$E′T′+id*id$$E′+id*id$ T′→ ǫ$E′T + +id*id$ E′→ +T E′$E′Tid*id$8StackInput M[A, a] =$E′T′F id*id$ T → F T′$E′T′idid*id$ F → id$E′T′*id$$E′T′F * *id$ T′→ *F T′$E′T′Fid$$E′T′id id$ F → id$E′T′$$E′$ T′→ ǫ$ $ E′→ ǫ9Stack Input M [A, a] =$E id+*$$E′T id+*$ E → T E′$E′T′Fid+*$ T → F T′$E′T′idid+*$ F → id$E′T′+*$$E′+*$ T′→ ǫ$E′T ++*$ E′→ +T E′$E′T*$ Error!10 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] := error311E → 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 ) = {+, *, ), $}12 Predictive Parsing – Building the Tableid + * ( ) $E E → T E′E → T E′E′TT′F• We start by looking at production E → T E′.• Since FIRST(T E′) = FIRST(T ) = {(, id} we set M [E, (] = M [E, id] = E → T E′.13 Predictive Parsing – Building the Table. . .id + * ( ) $E E → T E′E → T E′E′E′→ +T E′TT′F• We next consider production E′→ +T E′.• Since FIRST(+T E′) = {+} we set M [E′, +] = E′→ +T E′.14 Predictive Parsing – Building the Table. . .id + * ( ) $E E → T E′E → T E′E′E′→ +T E′E′→ ǫ E′→ ǫTT′F4• We next consider production E′→ ǫ.• Since FOLLOW(E′) = {), $} we set M [E′, )] = M [E′, $] = E′→ ǫ.15 Predictive Parsing – Building the Table. . .id + * ( ) $E E → T E′E → T E′E′E′→ +T E′E′→ ǫ E′→ ǫT T → F T′T → F T′T′F• We next consider production T → F T′.• Since FIRST(F T′) = {(, id} we set M [T, (] = M [T, id] = T → F T′.16 Predictive Parsing – Building the Table. . .id + * ( ) $E E → T E′E → T E′E′E′→ +T E′E′→ ǫ E′→ ǫT T → F T′T → F T′T′T′→ ∗F T′F• We next consider production T′→ ∗F T′.• Since FIRST(∗F T′) = {*} we set M [T′, *] = T′→ ∗F T′.17 Predictive Parsing – Building the Table. . .id + * ( ) $E E → T E′E → T E′E′E′→ +T E′E′→ ǫ E′→ ǫT T → F T′T → F T′T′T′→ ǫ T′→ ∗F T′T′→ ǫ T′→ ǫF• We next consider production T′→ ǫ.• Since FOLLOW(T′) = {+, ), $} we set M [T′, +] = M [T′, )] = M [T′, $] = T′→ ǫ.18 Predictive Parsing – Building the Table. . .id + * ( ) $E E → T E′E → T E′E′E′→ +T E′E′→ ǫ E′→ ǫT T → F T′T → F T′T′T′→ ǫ T′→ ∗F T′T′→ ǫ T′→ ǫF F → id F → (E)5• 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.19 Parsing Expressions• Here’s a simple implementation of predictive parsing in Java.• Grammar symbols (both terminals and non-terminals) are represented by single characters: e representsE’, f represents F’, i represents id, "" represents epsilon, null represents error.• The function table(X,a) looks up the relevant production.20class 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};21static 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;6case ’t’ : XIdx=3; break;case ’F’ : XIdx=4; break; }return TABLE[XIdx][aIdx];}22static 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