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 ExampleRepresenting the DFARepresenting the DFA. ExampleThe LR Parsing AlgorithmSlide 10Key Issue: How is the DFA Constructed?LR(1) ItemsNoteConventionLR(1) Items (Cont.)Slide 16The Closure OperationConstructing the Parsing DFA (1)Constructing the Parsing DFA (2)The DFA TransitionsConstructing the Parsing DFA. Example.LR Parsing Tables. NotesShift/Reduce ConflictsSlide 24More Shift/Reduce ConflictsSlide 26Slide 27Reduce/Reduce ConflictsSlide 29More 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 ParsingStrange Reduce/Reduce ConflictsSlide 48A 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:•Shift pushes a terminal from input on the stack E + (I int ) E + (int I )•Reduce pops 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 ! int on $, +accept on $E ! inton ), +E ! E + (E)on $, +E ! E + (E)on ), +(+Eint109110 12 3 45687+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)$ shift E + (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 $ acceptintE)Prof. 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…3 s44 s5 g65rE! intrE! int6 s8 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 statek is 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) item is a pair: X ², a–X ! is a production–a is 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 containing E ! E + ² ( E ), +–If ( follows then we can perform a shift to context containing E ! E + (² E ), +•In context containing E ! 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 item E ! E + (² E ) , +•We expect a string derived from E ) +•There are two productions for E E ! int and E ! E + ( E)•We describe this by extending the context with two more items: E ! ² int, ) E ! ² E + ( E ) , )Prof. Fateman CS 164 Lecture 10 17The Closure
View Full Document
Unlocking...