LR Parsing, LALR Parser GeneratorsOutlineBottom-up Parsing (Review)The Shift and Reduce Actions (Review)Key Issue: When to Shift or Reduce?LR(1) Parsing. An Example Representing the DFARepresenting the DFA. ExampleThe LR Parsing AlgorithmThe LR Parsing AlgorithmKey Issue: How is the DFA Constructed?LR(1) ItemsNoteConventionLR(1) Items (Cont.)LR(1) Items (Cont.)The Closure OperationConstructing the Parsing DFA (1) Constructing the Parsing DFA (2)The DFA TransitionsConstructing the Parsing DFA. Example.LR Parsing Tables. NotesShift/Reduce ConflictsShift/Reduce ConflictsMore Shift/Reduce ConflictsMore Shift/Reduce ConflictsMore Shift/Reduce ConflictsReduce/Reduce ConflictsReduce/Reduce ConflictsMore on Reduce/Reduce ConflictsUsing Parser GeneratorsLR(1) Parsing Tables are BigThe Core of a Set of LR ItemsLALR StatesA LALR(1) DFAConversion LR(1) to LALR(1). Example.The LALR Parser Can Have ConflictsLALR vs. LR ParsingA Hierarchy of Grammar ClassesNotes on ParsingNotes on Lisp LALR generatorSample input for lalr generatorSample table-output for lisp lalr generatorEach state is embodied in a subroutineSample output program for lalr generatorSupplement to LR Parsing Strange Reduce/Reduce ConflictsStrange Reduce/Reduce ConflictsA Few LR(1) StatesWhat Happened?A Few LR(1) States After FixProf. Fateman CS 164 Lecture 10 1LR Parsing, LALR Parser GeneratorsLecture 10Prof. Fateman CS 164 Lecture 10 2Outline• Review of bottom-up parsing• Computing the parsing DFA• Using parser generatorsProf. Fateman CS 164 Lecture 10 3Bottom-up Parsing (Review)• A bottom-up parser rewrites the input string to the start symbol • The state of the parser is described as αI γ– α is a stack of terminals and non-terminals– γ is the string of terminals not yet examined• Initially: I x1x2. . . xnProf. Fateman CS 164 Lecture 10 4The Shift and Reduce Actions (Review)• Recall the CFG: E → int | E + (E)• A bottom-up parser uses two kinds of actions:•Shiftpushes a terminal from input on the stackE + (I int ) ⇒ E + (int I )•Reducepops 0 or more symbols off the stack (the rule’s rhs) and pushes a non-terminal on the stack (the rule’s lhs)E + (E + ( E )I ) ⇒ E +(E I )Prof. Fateman CS 164 Lecture 10 5Key Issue: When to Shift or Reduce?• Idea: use a finite automaton (DFA) to decide when to shift or reduce– The input is the stack– The language consists of terminals and non-terminals• We run the DFA on the stack and we examine the resulting state X and the token tok after I–If X has a transition labeled tok then shift–If X is labeled with “A → β on tok”then reduceLR(1) Parsing. An Example intE → inton $, +accept on $E → E + (E)on $, ++E10E → inton ), +E → E + (E)on ), +(int9110 12 3 45687+E+)(E)I int + (int) + (int)$ shiftint I + (int) + (int)$ E → intE I + (int) + (int)$ shift(x3)E + (int I ) + (int)$ E → intE + (E I ) + (int)$ shiftE + (E) I + (int)$ E → E+(E)E I + (int)$ shift (x3)E + (int I )$ E → intE + (E I )$ shiftE + (E) I $ E → E+(E)E I $ acceptintProf. Fateman CS 164 Lecture 10 7Representing the DFA• Parsers represent the DFA as a 2D table– Recall table-driven lexical analysis• Lines correspond to DFA states• Columns correspond to terminals and non-terminals• Typically columns are split into:– Those for terminals: the action table– Those for non-terminals: the goto tableProf. Fateman CS 164 Lecture 10 8Representing the DFA. Example• The table for a fragment of our DFA:int + ( ) $ E…3s44s5 g65rE→ intrE→ int6s8 s77rE→ E+(E)rE→ E+(E)…E → inton ), +E → E + (E)on $, +int3(4567)Esk is shift and goto state krX → αis reducegk is goto state k,Prof. Fateman CS 164 Lecture 10 9The LR Parsing Algorithm• After a shift or reduce action we rerun the DFA on the entire stack– This is wasteful, since most of the work is repeated• Remember for each stack element on which state it brings the DFA; use extra memory.• LR parser maintains a stack〈 sym1, state1〉 . . . 〈 symn, staten〉statekis the final state of the DFA on sym1…symkProf. Fateman CS 164 Lecture 10 10The LR Parsing AlgorithmLet I = w$ be initial inputLet j = 0Let DFA state 0 be the start stateLet stack = 〈 dummy, 0 〉repeatcase action[top_state(stack), I[j]] ofshift k: push 〈 I[j++], k 〉reduce X → A: pop |A| pairs, push 〈X, Goto[top_state(stack), X]〉accept: halt normallyerror: halt and report errorProf. Fateman CS 164 Lecture 10 11Key Issue: How is the DFA Constructed?• The stack describes the context of the parse– What non-terminal we are looking for– What production rhs we are looking for– What we have seen so far from the rhs• Each DFA state describes several such contexts– E.g., when we are looking for non-terminal E, we might be looking either for an int or a E + (E) rhsProf. Fateman CS 164 Lecture 10 12LR(1) Items• An LR(1) itemis a pair:X →α•β, a–X → αβ is a production–ais a terminal (the lookahead terminal)– LR(1) means 1 lookahead terminal•[X →α•β, a] describes a context of the parser – We are trying to find an X followed by an a, and – We have (at least) α already on top of the stack– Thus we need to see next a prefix derived fromβaProf. Fateman CS 164 Lecture 10 13Note•The symbol I was used before to separate the stack from the rest of input– α I γ, where α is the stack and γ is the remaining string of terminals•In items • is used to mark a prefix of a production rhs:X →α•β, a–Here β might contain terminals as well• In both case the stack is on the leftProf. Fateman CS 164 Lecture 10 14Convention• We add to our grammar a fresh new start symbol S and a production S → E–Where E is the old start symbol• The initial parsing context contains:S →•E, $– Trying to find an S as a string derived from E$–The stack is emptyProf. Fateman CS 164 Lecture 10 15LR(1) Items (Cont.)• In context containingE → E + • ( E ), +–If ( follows then we can perform a shift to context containingE → E + (• E ), +• In context containingE → E + ( E ) •, +– We can perform a reduction with E → E + ( E )–But only if a + followsProf. Fateman CS 164 Lecture 10 16LR(1) Items (Cont.)•Consider the itemE → E + (• E ) , +• We expect a string derived from E ) +• There are two productions for EE → int and E → E + ( E)• We describe this by
View Full Document
Unlocking...