304CS 536 Spring 2007©ConfigurationsWe’ll use the notationX → A B•C Dto represent the fact that we aretrying to match the productionX → A B•C D with A and Bmatched so far.A production with a “•”somewhere in its righthand side iscalled a configuration.Our goal is to reach aconfiguration with the “dot” at theextreme right:X → A B C D•This indicates that an entireproduction has just beenmatched.305CS 536 Spring 2007©Since we may not know whichproduction will eventually be fullymatched, we may need to track aconfiguration set. A configurationset is sometimes called a state.When we predict a production, weplace the “dot” at the beginning ofa production:X →•A B C DThis indicates that the productionmay possibly be matched, but nosymbols have actually yet beenmatched.We may predict a λ-production:X →λ•When a λ-production is predicted,it is immediately matched, since λcan be matched at any time.306CS 536 Spring 2007©Starting the ParseAt the start of the parse, we knowsome production with the startsymbol must be used initially. Wedon’t yet know which one, so wepredict them all:S →•A B C DS →•e F gS →•h I...307CS 536 Spring 2007©ClosureWhen we encounter aconfiguration with the dot to theleft of a non-terminal, we knowwe need to try to match that non-terminal.Thus inX →•A B C Dwe need to match someproduction with A as its left handside.Which production?We don’t know, so we predict allpossibilities:A →•P Q RA →•s T...308CS 536 Spring 2007©The newly added configurationsmay predict other non-terminals,forcing additional productions tobe included. We continue thisprocess until no additionalconfigurations can be added.This process is called closure (ofthe configuration set).Here is the closure algorithm:ConfigSet Closure(ConfigSet C){repeatif (X → a•B d is in C &&B is a non-terminal)Add all configurations ofthe form B →•g to C)until (no more configurationscan be added);return C;}309CS 536 Spring 2007©Example of ClosureAssume we have the followinggrammar:S → AbA → CDC → DC → cD → dTo compute Closure(S →•Ab)we first include all productionsthat rewrite A:A →•CDNow C productions are included:C →•DC →•c310CS 536 Spring 2007©Finally, the D production is added:D →•dThe complete configuration set is:S →•AbA →•CDC →•DC →•cD →•dThis set tells us that if we want tomatch an A, we will need tomatch a C, and this is done bymatching a c or d token.311CS 536 Spring 2007©Shift OperationsWhen we match a symbol (aterminal or non-terminal), we shiftthe “dot” past the symbol justmatched. Configurations thatdon’t have a dot to the left of thematched symbol are deleted(since they didn’t correctlyanticipate the matched symbol).The GoTo function computes anupdated configuration set after asymbol is shifted:ConfigSet GoTo(ConfigSet C,Symbol X){B=φ;for each configuration f in C{if (f is of the form A →α•X δ)Add A →αX•δ to B;} return Closure(B);}312CS 536 Spring 2007©For example, if C is S →•AbA→•CDC →•DC →•cD →•dand X is C, then GoTo returnsA → C•DD →•d313CS 536 Spring 2007©Reduce ActionsWhen the dot in a configurationreaches the rightmost position,we have matched an entirerighthand side. We are ready toreplace the righthand sidesymbols with the lefthand side ofthe production. The lefthand sidesymbol can now be consideredmatched.If a configuration set can shift atoken and also reduce aproduction, we have a potentialshift/reduce error.If we can reduce more than oneproduction, we have a potentialreduce/reduce error.How do we decide whether to doa shift or reduce? How do wechoose among more than onereduction?314CS 536 Spring 2007©We examine the next token to seeif it is consistent with thepotential reduce actions.The simplest way to do this is touse Follow sets, as we did in LL(1)parsing.If we have a configurationA → α•we will reduce this productiononly if the current token, CT, is inFollow(A).This makes sense since if wereduce α to A, we can’t correctlymatch CT if CT can’t follow A.315CS 536 Spring 2007©Shift/Reduce and Reduce/Reduce ErrorsIf we have a parse state thatcontains the configurationsA →α•B →β•a γand a in Follow(A) then there is anunresolvable shift/reduce conflict.This grammar can’t be parsed.Similarly, if we have a parse statethat contains the configurationsA →α•B →β•and Follow(A) ∩ Follow(B) ≠φ,then the parser has anunresolvable reduce/reduceconflict. This grammar can’t beparsed.316CS 536 Spring 2007©Building Parse StatesAll the manipulations needed tobuild and complete configurationsets suggest that parsing may beslow—configuration sets need tobe updated after each token ismatched.Fortunately, all the configurationsets we ever will need can becomputed and tabled in advance,when a tool like Java Cup builds aparser.The idea is simple. We firstcompute an initial parse state, s0,that corresponds to predictingproductions that expand the startsymbol. We then just computesuccessor states for each tokenthat might be scanned. Acomplete set of states can becomputed. For typical317CS 536 Spring 2007©programming languagegrammars, only a few hundredstates are needed.Here is the algorithm that builds acomplete set of parse states for agrammar:StateSet BuildStates(){Let s0=Closure({S →•α, S →•β, ...});C={s0};while (not all states in C are marked){Choose any unmarked state, s, in CMark s;For each X interminals U nonterminals {if (GoTo(s,X) is not in C)Add GoTo(s,X) to C;}}return C;}318CS 536 Spring 2007©Configuration Sets for CSX-LiteState Cofiguration Sets0Prog →•{ Stmts } Eofs1Prog → {• Stmts } EofStmts →•Stmt StmtsStmts →λ•Stmt →• id = Expr ;Stmt →• if ( Expr ) Stmts2Prog → { Stmts•} Eofs3Stmts → Stmt•StmtsStmts →•Stmt StmtsStmts →λ•Stmt →• id = Expr ;Stmt →• if ( Expr ) Stmts4Stmt → id•= Expr ;s5Stmt → if• ( Expr ) Stmt319CS 536 Spring 2007©s6Prog → { Stmts }•Eofs7Stmts → Stmt Stmts•s8Stmt → id =•Expr ;Expr →•Expr + idExpr →•Expr - idExpr →•ids9Stmt → if (•Expr ) StmtExpr →•Expr + idExpr →•Expr - idExpr →•ids10Prog → { Stmts } Eof•s11Stmt → id = Expr•;Expr → Expr•+idExpr → Expr•-ids12Expr → id•s13Stmt → if ( Expr•) StmtExpr → Expr•+idExpr → Expr•-idState Cofiguration Set320CS 536 Spring 2007©s14Stmt → id = Expr