More on HW#3: - Last time we got through grammar for parsing factors. Now, we turn to parsing productions. This turns out to be more complicated due to left recursion in the * and / productions. Consider the production ::= * Here, a call to a naively constructed parse_term would attempt to recursively call parse_term an infinite number of times. - To solve the left recursion problem, we define a new intermediate nonterminal , and modify the grammar to be the following: ::= ::= * | / | Here we make the necessary assumption that every will begin with a (which it must since is the next step in the descent), and be followed by a * or / or nothing at all. - Unlike the other parse_ functions, the parse_term_tail function takes two arguments: the abstract syntax for the preceding of the production as well as the remaining token list after removing that . This must be done since the parse_term_tail must be responsible for constructing the abstract syntax for the entire production since only it is aware of the necessary operation (* or /). Thus, parse_term itself only returns what parse_term_tail returns it. - The DRAWING link shows the flow diagram for the parsing of the string "1*2/3". Each parse_ function takes a list of tokens, but for brevity in the diagram, the token list is represented by the string. For instance, wherever there is "1*2/3" in the diagram, it is understood that this means (list "1" "*" "2" "/" "3") and similarly, a "*2/3" represents (list "*" "2" "/" "3"). Note also that in the homework, the supplied lexical analysis function, string->tokenlist is responsible for the initial breakup into tokens. That is, the initial parse_fmla call should be (parse_fmla (string->tokenlist "1*2/3")). Finally, the flow chart assumes we are still using a dummied parse_fmla function that just passes the input onto parse_term. - There are some conventions used in the drawing. First, flow always go from top to bottom whenever possible, though each line should only be followed once. Similarly, when two down lines are possible, the left one should be done first, and when the flow returns, the right one should be done. A "notice " implies that the function above it recognizes the , uses this recognition to indicate what block of a conditional structure it should be in, and removes the from the token list by passing rest (i.e. everything but the ) onto the next function in the flow. - Note that a similar modification to the grammar must be performed for the productions, as the same left recursion problem arises there. This involves redefining the grammar and adding the grammar. More on Scheme: - In the language you have the following: atoms empty cons list append Atoms are essentially everything that isn't a list, with a few exceptions. - Atoms, empty, and cons form what is called a constructor system for lists. A constructor system must be one-to-one, that is every construction method must produce a unique product and every product has only one method of production. For instance, cons is one-to-one, since (cons x y) = (cons w z) iff x = w & y = z - list also forms a constructor system with atoms, but not when including empty, as empty = (list), and thus breaks down the one-to-one requirement. - (cons x y) as a function cannot be defined in terms of (list ...), and thus if you are building up an arbitrarily long list, we must use cons. - list and append together can define cons: (cons x y) = (append (list x) y) However, this definition of cons is not a constructor system, since it is not one-to-one.