CPS 140 - Mathematical Foundations of CSDr. S. RodgerSection: LR Parsing (handout)LR PARSINGLR(k) Parser• bottom-up parser• shift-reduce parser• L means: reads input left to right• R means: produces a rightmost derivation• k - number of lookahead symbolsLR parsing process• convert CFG to PDA• Use the PDA and lookahead symbolsConvert CFG to PDAIdea: To derive a string from a CFG with a rightmost derivation, start with the start symbol andrepeatedly apply productions replacing the rightmost variable at each step. In order to simulate thisprocess with an NPDA, we will simulate this process in reverse by starting with the input string, usingproductions in reverse (replacing rhs of a production by its lhs), and deriving the start symbol. Thus, theNPDA starts by shifting the symbols of the input string onto the stack. Whenever the top symbols on thestack match the rhs of a production, pop the rhs (may be several symbols) and replace it (or push) the lhson the stack. If replacements lead to only the start symbol on the stack, then the input string is in thelanguage of the grammar. To see the actual rightmost derivation the NPDA simulated, start with the startsymbol and apply the productions in the reverse order they were applied in the NPDA.The constructed NPDA:• three states: s, q, fstart in state s, assume z on stack• all rewrite rules in state s, backwardsrules pop rhs, then push lhs(s,lhs) ∈ δ(s,λ,rhs)Note: assuming stack can pop several symbols at once.This is called a reduce operation.1• additional rules in s to recognize terminalsFor each x∈ Σ, g∈ Γ, (s,xg) ∈ δ(s,x,g)This is called a shift operation.• pop S from stack and move into state q• pop z from stack, move into f, accept.Example: Construct a PDA.S → aSbS → bLR Parsing Actions1. shifttransfer the lookahead to the stack2. reduceFor X → w, replace w by X on the stack3. acceptinput string is in language4. errorinput string is not in language2LR(1) Parse Table• Columns:terminals, $ and variables• Rows:state numbers: represent patterns in a derivationLR(1) Parse Table Example1) S → aSb2) S → ba b $ S0 s2 s3 11 acc2 s2 s3 43 r2 r24 s55 r1 r1Definition of entries:• sN - Shift (or push) the terminal for this column onto the stack, and move to state (or row number)N.• N - Move to state (or row number) N.• rN - Reduce by rule number N. The rhs of this rule is on the top of the stack. Pop it and replace itby the lhs of the rule.• acc - The input string is accepted.• blank - Error.3LR(1) Parsing routine“entry” is a record with four parts: state, action, rule.rhs, rule.lhsstate = 0push(state)read(symbol) obtain the lookahead symbolentry = T[state,symbol] T is the LR parse tablewhile entry.action 6= accept doif entry.action == shift thenpush(symbol)state = entry.statepush(state)read(symbol)else if entry.action == reduce thendo 2∗size rhs times {pop()} pop entry.rule.rhs and statesstate := top-of-stack() do not pop!push(entry.rule.lhs)state = T[state,entry.rule.lhs]push(state)else if entry.action == blank thenerrorentry = T[state, symbol]end whileif symbol 6= $ then errorExample:Trace aabbb5b344 5bSS b222244aaaaSS22222221aaaaaaaS000000000S: z z z z z z z z zLookahead:aabbbbb$$Action:4To construct the LR(1) parse table:• Construct a dfa (transition diagram) to model the top of the stack whose states represent the currentcontents of the parsing stack.• Using the dfa, construct an LR(1) parse tableTo Construct the DFAIdea: The states in the DFA will contain marked productions that indicate what is currently on the top ofthe stack, and what additional symbols need to be pushed onto the stack in order for a rhs to be on top ofthe stack, so a reduce operation can occur.• Add a new production S’ → S to the grammar, where S’ is the new start symbol.• place a marker “ ” on the rhs of the production to indicate status of parsing process.S’ → SThe items in the rhs to the left of the marker are the items we have parsed (they are on the top ofthe stack), and the items to the right of the marker are the items we have not seen yet (still need tobe pushed onto the stack).Example: A → a Ab indicates that “a” is on top of the stack and we need to push “A” and “b” onthe stack before we can reduce “aAb” to “A”.• Compute the set of productions closure(S’ → S).Definition of closure:1. closure(A → v xy) = {A → v xy} if x is a terminal.2. closure(A → v xy) = {A → v xy}∪(closure(x → w) for all w (where w is the right hand sideof a production in which x is the left hand side)) if x is a variable.• The closure(S’ → S) is designated as state 0 and marked as “unprocessed”.• Repeat until all states have been processed– unproc = any unprocessed state– For each x that appears in A→u xv (where the A production is from the state “unproc”) do∗ Add a transition labeled “x” from state “unproc” to a new state with production A→ux v(Note: If there is more than one production in state “unproc” that has a marker before thex, then one new state is created and all of these productions are placed into the new state,with the marker moved to the right of the x)∗ The set of productions for the new state are: closure(A→ux v)(Note: If there was more than one production put in from the previous step, then closure isapplied to all of those productions).∗ If the new state is identical (has same productions and marker positions) to another state,then combine the two states into one state. Otherwise, mark the new state as “unprocessed”• Identify final states. Any state that has at least one production with “ ” at the end of the rhs is afinal state.5Example: Construct DFA(0) S’ → S(1) S → aSb(2) S → bBacktracking through the DFAShort Version:Consider aabbb• Start in state 0.• Shift “a” and move to state 2.• Shift “a” and move to state 2.• Shift “b” and move to state 3.Reduce by “S → b”Pop “b” and Backtrack to state 2.Shift “S” and move to state 4.• Shift “b” and move to state 5.Reduce by “S → aSb”Pop “aSb” and Backtrack to state 2.Shift “S” and move to state 4.6• Shift “b” and move to state 5.Reduce by “S → aSb”Pop “aSb” and Backtrack to state 0.Shift “S” and move to state 1.• Accept. aabbb is in the language.A More detailed explanation of the Backtracking:A state in the DFA represents what is currently on “top” of the