CS453 Colorado State University ========================================== LL(1) grammars ========================================== ----------------------------- Plan for today LL(k) grammars, context and requirements ----------------------------- Predictive Parsing Complexity grammar classes LL(k) - left-to-right scan, left-most derivation, k tokens of lookahead General parsing versus top-down predictive - complexity of general parsing O(N^3), where N is number of tokens Earley parser does a form of dynamic programming: O(n^3) in the general case O(n^2) for unambiguous grammars O(n) for most LR(k) grammars http://en.wikipedia.org/wiki/Earley_parser - complexity of predictive parsing is O(N) - requirements on the grammar [can students derive these requirements from the algorithm for creating the predictive parsing table? write these on the board and then look at next slide] - for all the productions for nonterminal A - none of the FIRST(rhs) for A production rules can overlap' - if nullable(A)==true, then FOLLOW(A) must not overlap with FIRST(rhs) for any A->rhs ----------------------------- Left Factoring There is more than one way to specify a circle. What if we had the following two productions in the MiniSVG grammar? elem -> CIRCLE_START KW_CX EQ NUM KW_CY EQ NUM KW_R EQ NUM KW_FILL EQ COLOR ELEM_END and elem -> CIRCLE_START KW_X EQ NUM KW_Y EQ NUM KW_WIDTH EQ NUM KW_HEIGHT EQ NUM KW_FILL EQ COLOR ELEM_END Both production rules have the same FIRST set. Left factor as follows: elem -> CIRCLE_START circle circle -> KW_CX EQ NUM KW_CY EQ NUM KW_R EQ NUM KW_FILL EQ COLOR ELEM_END and circle -> KW_X EQ NUM KW_Y EQ NUM KW_WIDTH EQ NUM KW_HEIGHT EQ NUM KW_FILL EQ COLOR ELEM_END ----------------------------- Left Recursion -> show slide with modified MiniSVG grammar (slide 6) -> calculate nullable, FIRST, and FOLLOW sets -> create predictive parse table and observe problem -> show example parse tree for modified MiniSVG slide (slide 7) Removing Left Recursion - For lists, just make it right recursive. - For general case, see 4.3.3 in book. - Will not be tested on how to remove left recursion in the general case, but you should be able to make a left-recursive list grammar into a right-recursive list grammar. ----------------------------- Working with a partner Why? - No programmer is an island. You will be working with other people no matter where you go from here. - The MeggyJava compiler project is a significant class project. We would like to make a really good one from this class available on the internet. - Working with a partner should encourage planning ahead. - Two heads really are better than one. Each of you is ultimately responsible for making the compiler work. - The "My partner didn't do any work" or "My partner has taken over and won't let me do any work" problems will not change your programming assignment grade. - Make sure you know how the whole compiler works The tests will be over all aspects of the compiler. You will be dividing up the work, but make sure you do code reviews and explain your code to your partner until they understand how it works. - Come see me if you are having problems and we will discuss strategies to deal with such issues. Report and Evaluation of partner work - (joint) For each of PA3 through PA7, write a planning paragraph and timeline together and submit with your assignment. - Who is going to do what? The plan and the reality. - How is the testing going to be done? What actually happened. - Timeline for finishing portions of assignment. - Meeting schedule. - (separate) Email mstrout@cs.colostate.edu for each of PA3 through PA7 an assessment of the partner work by the deadline of the assignment. The assessment should be approximately 1/2 a page with information about the following: - What are some organizational strategies that you and your partner are using that are working well? - Specifically how did you and your partner divide the work? (e.g., I wrote the type checker for the following set of grammar rules...). - How could the division of work between the partners be improved? - How could the interaction between the partners be improved? - The final grade for the Partner Report will be completed and posted after PA7 has been submitted. - Your joint and separate evaluations will be graded based on the following criteria: - Have all of the relevant questions been addressed in a thoughtful manner. - How well do the reports match. - Clarity and succinctness of the writing. - There will be a subjective evaluation of how well the partners attempted to make the group programming experience work. ----------------------------- MeggyJava Intro How do we run a MeggyJava example? How does the opt_args file work? How is PA2 going to be graded? ------------------------ mstrout@cs.colostate.edu, 2/8/10