Parsing VII The Last Parsing LectureLR(1) Table ConstructionExample (grammar & sets)Example (building the collection)Slide 5Example (Summary)Example (Summary)Example (Summary)Filling in the ACTION and GOTO TablesExample (Filling in the tables)What can go wrong?Shrinking the TablesSummaryLeft Recursion versus Right RecursionAssociativityHierarchy of Context-Free LanguagesPowerPoint PresentationBeyond SyntaxSlide 19Slide 20Slide 21Slide 22Parsing VIIThe Last Parsing LectureHigh-level overviewBuild the canonical collection of sets of LR() Items, I aBegin in an appropriate state, s0[S’ •S,EOF], along with any equivalent itemsDerive equivalent items as closure( s0 )bRepeatedly compute, for each sk, and each X, goto(sk,X)If the set is not already in the collection, add itRecord all the transitions created by goto( ) This eventually reaches a fixed point2Fill in the table from the collection of sets of LR() itemsThe canonical collection completely encodes the transition diagram for the handle-finding DFALR() Table ConstructionExample (grammar & sets)Simplified, right recursive expression grammarGoal  ExprExpr  Term – ExprExpr  TermTerm  Factor * Term Term  FactorFactor  identExample (building the collection)Initialization Steps0  closure( { [Goal  •Expr , EOF] } ){ [Goal  • Expr , EOF], [Expr  • Term – Expr , EOF], [Expr  • Term , EOF], [Term  • Factor * Term , EOF], [Term  • Factor * Term , –], [Term  • Factor , EOF], [Term  • Factor , –], [Factor  • ident , EOF], [Factor  • ident , –], [Factor  • ident , *] }S  {s0 }Example (building the collection)Iteration s1  goto(s0 , Expr)s2  goto(s0 , Term)s3  goto(s0 , Factor)s4  goto(s0 , ident )Iteration 2s5  goto(s2 , – )s6  goto(s3 , * )Iteration 3s7  goto(s5 , Expr )s8  goto(s6 , Term )Example (Summary)S0 : { [Goal  • Expr , EOF], [Expr  • Term – Expr , EOF], [Expr  • Term , EOF], [Term  • Factor * Term , EOF], [Term  • Factor * Term , –], [Term  • Factor , EOF], [Term  • Factor , –], [Factor  • ident , EOF], [Factor  • ident , –], [Factor • ident, *] }S : { [Goal  Expr •, EOF] }S2 : { [Expr  Term • – Expr , EOF], [Expr  Term •, EOF] }S3 : { [Term  Factor • * Term , EOF],[Term  Factor • * Term , –], [Term  Factor •, EOF], [Term  Factor •, –] }S4 : { [Factor  ident •, EOF],[Factor  ident •, –], [Factor  ident •, *] }S5 : { [Expr  Term – • Expr , EOF], [Expr  • Term – Expr , EOF], [Expr  • Term , EOF], [Term  • Factor * Term , –], [Term  • Factor , –], [Term  • Factor * Term , EOF], [Term  • Factor , EOF], [Factor  • ident , *], [Factor  • ident , –], [Factor  • ident , EOF] }Example (Summary)S6 : { [Term  Factor * • Term , EOF], [Term  Factor * • Term , –], :[Term  • Factor * Term , EOF], [Term  • Factor * Term , –], [Term  • Factor , EOF], [Term  • Factor , –], [Factor  • ident , EOF], [Factor  • ident , –], [Factor  • ident , *] }S7: { [Expr  Term – Expr •, EOF] }S8 : { [Term  Factor * Term •, EOF], [Term  Factor * Term •, –] }Example (Summary)The Goto Relationship (from the construction) StateExprTermFactor-*I dent02342536457234683478Filling in the ACTION and GOTO TablesThe algorithm set sx  S  item i  sx if i is [A •ad,b] and goto(sx,a) = sk, a  T then ACTION[x,a]  “shift k” else if i is [S’S •,EOF] then ACTION[x , EOF]  “accept” else if i is [A •,a] then ACTION[x,a]  “reduce A”  n  NT if goto(sx ,n) = sk then GOTO[x,n]  kx is the number of the state for sxMany items generate no table entrye.g., [AB,a] does not, but closure ensures that all the rhs’ for B are in sxExample (Filling in the tables)The algorithm produces the following tableACTI ONGOTOI dent-*EOFExprTermFactor0s 423acc2s 5r 33r 5s 6r 54r 6r 6r 65s 47236s 4837r 28r 4r 4Plugs into the skeleton LR(1) parserWhat can go wrong?What if set s contains [A•a,b] and [B•,a] ?•First item generates “shift”, second generates “reduce” •Both define ACTION[s,a] — cannot do both actions•This is a fundamental ambiguity, called a shift/reduce error•Modify the grammar to eliminate it (if-then-else)•Shifting will often resolve it correctly What is set s contains [A•, a] and [B•, a] ?•Each generates “reduce”, but with a different production•Both define ACTION[s,a] — cannot do both reductions•This fundamental ambiguity is called a reduce/reduce error•Modify the grammar to eliminate it (PL/I’s overloading of (...))In either case, the grammar is not LR(1)EaC includes a worked exampleShrinking the TablesThree options:•Combine terminals such as number & identifier, + & -, * & /Directly removes a column, may remove a rowFor expression grammar, 98 (vs. 384) table entries •Combine rows or columns (table compression)Implement identical rows once & remap statesRequires extra indirection on each lookupUse separate mapping for ACTION & for GOTO•Use another construction algorithmBoth LALR() and SLR() produce smaller tablesImplementations are readily availableSummaryAdvantagesFastGood localitySimplicityGood error detectionFast Deterministic langs.AutomatableLeft associativityDisadvantagesHand-codedHigh maintenanceRight associativityLarge working setsPoor error messagesLarge table sizesTop-downrecursivedescentLR()Left Recursion versus Right Recursion•Right recursion•Required for termination in top-down parsers•Uses (on average) more stack space•Produces right-associative operators•Left recursion•Works fine in bottom-up parsers•Limits required stack space•Produces left-associative operators •Rule of thumb•Left recursion for bottom-up parsers•Right recursion for top-down parsers***wxyzw * ( x * ( y * z ) )***zwxy( (w * x ) * y ) * zAssociativity•What difference does it make?•Can change answers in floating-point arithmetic•Exposes a different set of common subexpressions•Consider