Bottom-Up ParsingOutlineTop-Down Parsing. ReviewSlide 4Slide 5Slide 6Predictive Parsing. Review.Notes on LL(1) Parsing TablesWhat next?Bottom Up ParsingBottom-Up ParsingAn Introductory ExampleThe IdeaA Bottom-up Parse in Detail (1)A Bottom-up Parse in Detail (2)A Bottom-up Parse in Detail (3)A Bottom-up Parse in Detail (4)A Bottom-up Parse in Detail (5)A Bottom-up Parse in Detail (6)Important Fact #1Where Do Reductions HappenNotationShift-Reduce ParsingShiftReduceShift-Reduce ExampleSlide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36The StackKey Issue: When to Shift or Reduce?LR(1) Parsing. An ExampleRepresenting the DFARepresenting the DFA. ExampleThe LR Parsing AlgorithmSlide 43LR Parsing NotesProf. Fateman CS 164 Lecture 9 1Bottom-Up ParsingLecture 9Prof. Fateman CS 164 Lecture 9 2Outline•Review LL parsing•Shift-reduce parsing•The LR parsing algorithm•Constructing LR parsing tablesProf. Fateman CS 164 Lecture 9 3Top-Down Parsing. Review•Top-down parsing expands a parse tree from the start symbol to the leaves–Always expand the leftmost non-terminalETE+int * int + intProf. Fateman CS 164 Lecture 9 4Top-Down Parsing. Review•Top-down parsing expands a parse tree from the start symbol to the leaves–Always expand the leftmost non-terminalEintT*TE+int * int + int•The leaves at any point form a string A– contains only terminals–The input string is b–The prefix matches–The next token is bProf. Fateman CS 164 Lecture 9 5Top-Down Parsing. Review•Top-down parsing expands a parse tree from the start symbol to the leaves–Always expand the leftmost non-terminalEintT*intTE+Tint * int + int•The leaves at any point form a string A– contains only terminals–The input string is b–The prefix matches–The next token is bProf. Fateman CS 164 Lecture 9 6Top-Down Parsing. Review•Top-down parsing expands a parse tree from the start symbol to the leaves–Always expand the leftmost non-terminalEintT*intTE+Tintint * int + int•The leaves at any point form a string A– contains only terminals–The input string is b–The prefix matches–The next token is bProf. Fateman CS 164 Lecture 9 7Predictive Parsing. Review.•A predictive parser is described by a table–For each non-terminal A and for each token b we specify a production A ! –When trying to expand A we use A ! if b follows next•Once we have the table–The parsing algorithm is simple and fast–No backtracking is necessaryProf. Fateman CS 164 Lecture 9 8Notes on LL(1) Parsing Tables•If any entry is multiply defined then G is not LL(1)–If G is ambiguous–If G is left recursive–If G is not left-factored–And in other cases as well•There are tools that build LL(1) tables.•Most programming language grammars are very nearly but not quite LL(1).Prof. Fateman CS 164 Lecture 9 9What next? •Good but we can do better with a more powerful parsing strategy that allows us to look at more of the input before deciding to do a reduction. We could try LL(2) but that would require a 3-D table. We have a better way.Prof. Fateman CS 164 Lecture 9 10Bottom Up ParsingProf. Fateman CS 164 Lecture 9 11Bottom-Up Parsing•Bottom-up parsing is more general than top-down parsing (handles more abstract languages)–And just as efficient–Builds on ideas in top-down parsing–Preferred method in practice•Also called LR parsing–L means that tokens are read left to right–R means that it constructs a rightmost derivation -->Prof. Fateman CS 164 Lecture 9 12An Introductory Example•LR parsers don’t need left-factored grammars and can also handle left-recursive grammars •Consider the following grammar: E E + ( E ) | int –Why is this not LL(1)?•Consider the string: int + ( int ) + ( int )Prof. Fateman CS 164 Lecture 9 13The Idea•LR parsing reduces a string to the start symbol by inverting productions:Str := input string of terminals repeat–Identify in str such that A is a production (i.e., str = )–Replace by A in str (i.e., str A )until str = SProf. Fateman CS 164 Lecture 9 14A Bottom-up Parse in Detail (1)int++int int( )int + (int) + (int)()Prof. Fateman CS 164 Lecture 9 15A Bottom-up Parse in Detail (2)Eint++int int( )int + (int) + (int)E + (int) + (int)()Prof. Fateman CS 164 Lecture 9 16A Bottom-up Parse in Detail (3)Eint++int int( )int + (int) + (int)E + (int) + (int)E + (E) + (int)()EProf. Fateman CS 164 Lecture 9 17A Bottom-up Parse in Detail (4)Eint++int int( )int + (int) + (int)E + (int) + (int)E + (E) + (int)E + (int)E()EProf. Fateman CS 164 Lecture 9 18A Bottom-up Parse in Detail (5)Eint++int int( )int + (int) + (int)E + (int) + (int)E + (E) + (int)E + (int)E + (E)E()EEProf. Fateman CS 164 Lecture 9 19A Bottom-up Parse in Detail (6)EEint++int int( )int + (int) + (int)E + (int) + (int)E + (E) + (int)E + (int)E + (E)EE()EEA rightmost derivation in reverseProf. Fateman CS 164 Lecture 9 20Important Fact #1Important Fact #1 about bottom-up parsing:An LR parser traces a rightmost derivation in reverseProf. Fateman CS 164 Lecture 9 21Where Do Reductions HappenImportant Fact #1 has an interesting consequence:–Let be a step of a bottom-up parse–Assume the next reduction is by A –Then is a string of terminalsWhy? Because A is a step in a right-most derivationProf. Fateman CS 164 Lecture 9 22Notation•Idea: Split string into two substrings–Right substring is as yet unexamined by parsing (a string of terminals)–Left substring has terminals and non-terminals•The dividing point is marked by a | or I –The I is not part of the string•Initially, all input is unexamined: Ix1x2 . . . xnProf. Fateman CS 164 Lecture 9 23Shift-Reduce Parsing•Bottom-up parsing uses only two kinds of actions:ShiftReduceProf. Fateman CS 164 Lecture 9 24ShiftShift: Move I one place to the right–Shifts a terminal to the left stringE + (I int ) shifts to E + (int I )Prof. Fateman CS 164 Lecture 9 25ReduceReduce: Apply an inverse production at the right end of the left string–If E E + ( E ) is a production, thenE + (E + ( E ) I ) reduces to E +(E I )Shift-Reduce ExampleI int + (int) + (int)$ shiftint++int int( )()Shift-Reduce ExampleI int + (int) + (int)$ shiftint I + (int) + (int)$ red. E intint++int int(
View Full Document
Unlocking...