Lecture notes for CSC 173, Tues. Oct. 18 -- , 2005 ------------------------------------------------- READING: Aho & Ullman chapter 11 ------------------------------------------------- Recursive Patterns and Context Free Grammars A context-free grammar is a set of recursive rewriting rules (or productions) used to generate patterns of strings. Context-free grammars are often used to define the syntax of programming languages. A parse tree displays the structure used by a grammar to generate an input string. Parse trees are typically used within a compiler to describe the structure of an input program in terms of the syntactic rules used to define valid programs. A parser is an algorithm that determines whether a given input string is in a language (and, as a side-effect, usually produces a parse tree for the input). There is a mechanical procedure for generating a parser from a given context-free grammar. --------------------------------------- A CFG consists of the following components: * a set of terminal symbols, which are the characters of the alphabet that appear in the strings generated by the grammar. * a set of nonterminal symbols, which are placeholders for patterns of terminal symbols that can be generated by the nonterminal symbols. * a set of productions, which are rules for replacing (or rewriting) nonterminal symbols (on the left side of the production) in a string with other nonterminal or terminal symbols (on the right side of the production). * a start symbol, which is a special nonterminal symbol that appears in the initial string generated by the grammar. By convention the start symbol is usually the LHS of the first production. To generate a string of terminal symbols from a CFG, we: * Begin with a string consisting of the start symbol; * Apply one of the productions with the start symbol on the left hand size, replacing the start symbol with the right hand side of the production; * Repeat the process of selecting nonterminal symbols in the string, and replacing them with the right hand side of some corresponding production, until all nonterminals have been replaced by terminal symbols. The resulting sequence of strings is called a *derivation*. --------------------------------------- A CFG for Arithmetic Expressions An example grammar that generates strings representing arithmetic expressions with the four operators +, -, *, /, and numbers as operands is: 1. expr --> number 2. expr --> ( expr ) 3. expr --> expr + expr 4. expr --> expr - expr 5. expr --> expr * expr 6. expr --> expr / expr The only nonterminal symbol in this grammar is expr, which is also the start symbol. The terminal symbols are {+,-,*,/,(,),number}. (We will interpret "number" to represent any valid number.) The first rule (or production) states that an expr can be rewritten as (or replaced by) a number. In other words, a number is a valid expression. The second rule says that an expr enclosed in parentheses is also an expr. Note that this rule defines an expression in terms of expressions, an example of the use of recursion in the definition of context-free grammars. Recursion is the ONE SINGLE thing that gives CFGs power that REs and FAs lack. The remaining rules say that the sum, difference, product, or division of two exprs is also an expr. --------------------------------------- Generating Strings from a CFG In our grammar for arithmetic expressions, the start symbol is , so our initial string is: expr Using rule 5 we can choose to replace this nonterminal, producing the string: expr * expr We now have two nonterminals to replace. We can apply rule 3 to the first nonterminal, producing the string: expr + expr * expr We can apply rule two to the first nonterminal in this string to produce: (expr) + expr * expr If we apply rule 1 to the remaining nonterminals (the recursion must end somewhere!), we get: (number) + number * number This is a valid arithmetic expression, as generated by the grammar. When applying the rules above, we often face a choice as to which production to choose. Different choices will typically result in different strings being generated. Given a grammar G with start symbol S, if there is some sequence of productions that, when applied to the initial string S, result in the string s, then s is in L(G), the language of the grammar. --------------------------------------- CFGs with Epsilon Productions A CFG may have a production for a nonterminal in which the right hand side is the empty string (which we denote by epsilon). The effect of this production is to remove the nonterminal from the string being generated. Here is a grammar for balanced parentheses that uses epsilon productions. P --> ( P ) P --> P P P --> epsilon Epsilon productions are commonly written with just an empty RHS: P --> We begin with the string P. We can replace P with epsilon, in which case we have generated the empty string (which does have balanced parentheses). Alternatively, we can generate a string of balanced parentheses within a pair of balanced parentheses, which must result in a string of balanced parentheses. Alternatively, we can concatenate two strings of balanced parentheses, which again must result in a string of balanced parentheses. This grammar is equivalent to: P --> ( P ) | P P | epsilon We use the notational shorthand '|', which can be read as "or", to represent multiple rewriting rules within a single line. Here the epsilon really is needed for clarity. --------------------------------------- Notational conventions Some authors (including A&U) put non-terminals in pointy brackets. A&U also distinguish between "abstract" and "concrete" terminals, putting the former in bold and the latter in italics. Others (including me) put non-terminals in italics and terminals in typewriter (monospace) font. Since fonts don't work in plain ascii, the parsing project uses uppercase for terminals and lowercase for non-terminals. Strictly speaking you don't need such conventions, since non-terminals are the symbols that appear on LHSs, and terminals are the ones that don't. --------------------------------------- CFG Examples A CFG describing strings of letters with the word "main" somewhere in the string: --> m a i n --> | epsilon --> A | B | ... | Z | a | b ... | z A CFG for the set of identifiers in Pascal: --> --> | | epsilon --> A | B | ... | Z | a | b ... | z --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 A CFG describing real numbers in Pascal: --> --> | epsilon --> '.' | epsilon --> 'E' | epsilon --> + | - | epsilon --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Note that all three of the above examples are regular sets; recursion is not required to define them. A CFG for C compound statements (more or less): --> { } --> | epsilon --> --> id : --> if ( ) --> if ( ) else --> while ( ) --> do while ( ) ; --> for ( ; ) --> switch ( ) { } --> | epsilon --> case : | default: --> break ; | continue ; | ; --> return ; | goto ; Note that this *does* require recursion (stmt's have stmt's inside) ------------------------------------------------------------------------ The quick story on CFGs and Regular Expressions (more later if we have time) CFGs are strictly more powerful: anything you can do with a RE you can do with a CFG, but not vice versa. The intuition is that CFGs give you concatenation and alternation, and can easily emulate Kleene closure, but they also let you define things recursively *in terms of themselves*, which REs don't. ------------------------------------------------------------------------ Parse Trees A parse tree for a grammar G is a tree where * the root is the start symbol for G * the interior nodes are nonterminals of G * the leaf nodes are terminal symbols of G. * the children of a node T (from left to right) correspond to the symbols on the right hand side of some production for T in G. Every terminal string generated by a grammar has at least one corresponding parse tree; every valid parse tree represents a string generated by the grammar (called the yield of the parse tree). Example: Given the following grammar, find a parse tree for the string 1 + 2 * 3: 1. E --> number 2. E --> ( E ) 3. E --> E + E 4. E --> E - E 5. E --> E * E 6. E --> E / E One parse tree is: E --> E --> N --> 1 + E --> E --> N --> 2 * E --> N --> 3 ======================================================================== October 19th 2004 lecture ended here -------------------------------------------------------- Ambiguous Grammars A grammar for which there are two different parse trees for the same terminal string is said to be ambiguous. The grammar for balanced parentheses given earlier is an example of an ambiguous grammar: P --> ( P ) | P P | epsilon We can prove this grammar is ambiguous by demonstrating two parse trees for the same terminal string. Here are two parse trees for the empty string: P --> P --> epsilon P --> epsilon P --> epsilon Here are two parse trees for (): P --> P --> ( P --> epsilon ) P --> epsilon P --> P --> epsilon P --> ( P --> epsilon ) While in general it may be difficult to prove an arbitrary grammar is ambiguous, the demonstration of two distinct parse trees for the same terminal string is sufficient proof that some particular grammar is ambiguous. An unambiguous grammar for the set of strings consisting of balanced parentheses is: P --> ( P ) P | epsilon --------------------------------------- The Problem of Ambiguous Grammars A parse tree is supposed to display the structure used by a grammar to generate an input string. This structure is not unique if the grammar is ambiguous. A problem arises if we attempt to impart meaning to an input string using a parse tree; if the parse tree is not unique, then the string has multiple meanings. We typically use a grammar to define the syntax of a programming language. The structure of the parse tree produced by the grammar imparts some meaning on the strings of the language. If the grammar is ambiguous, the compiler has no way to determine which of two meanings to use. Thus, the code produced by the compiler is not fully determined by the program input to the compiler. --------------------------------------- Ambiguous Precedence Recall the grammar for expressions given earlier: E --> number E --> ( E ) E --> E + E E --> E - E E --> E * E E --> E / E This grammar is ambiguous as shown by the two parse trees for the input string number + number * number: E --> E --> number + E --> E --> number * E --> number E --> E --> E --> number + E --> number * E --> number The first parse tree gives precedence to multiplication over addition; the second parse tree gives precedence to addition over multiplication. In most programming languages, only the former meaning is correct. As written, this grammar is ambiguous with respect to the precedence of the arithmetic operators. Note (THIS IS IMPORTANT): precedence is NOT a property of the context-free language consisting of syntactically valid expressions. It's a property of the *meaning* (semantics) we *choose* to apply to those strings. Using a grammar that "naturally" reflects predecence makes it easier for a compiler to implement the chosen semantics. --------------------------------------- Ambiguous Associativity Consider again the same grammar for expressions: E --> number E --> ( E ) E --> E + E E --> E - E E --> E * E E --> E / E This grammar is ambiguous even if we only consider operators at the same precedence level, as in the input string number - number + number: E --> E --> number - E --> E --> number + E --> number E --> E --> E --> number - E --> number + E --> number The first parse tree (incorrectly) gives precedence to the addition operator; the second parse tree gives precedence to the subtraction operator. Since we normally group operators left to right within a precedence level, only the latter interpretation is correct. As with precedence, associativity is NOT a property of the context-free expression language; it's a property of the semantics we choose to associate with that language. Second important note: computer arithmetic is not associative! Because of overflow, it may not always be the case that (a+b)+c gives the same result as a+(b+c). --------------------------------------- An Unambiguous Grammar for Expressions It is possible to write a grammar for arithmetic expressions that * is unambiguous * naturally reflects the precedence of * and / over + and - * naturally reflects left associativity Here is one such grammar: E --> E + T | E - T | T T --> T * F | T / F | F F --> ( E ) | number If we attempt to build a parse tree for number - number + number, we see there is only one such tree: E --> E --> E --> T --> F --> number - T --> F --> number + T --> number This parse tree correctly represents left associativity by using recursion on the left. If we rewrote the grammar to use recursion on the right, we would represent right associativity: E --> T + E | T - E | T T --> F * T | F / T | F F --> ( E ) | number Right associativity isn't usually what we want for addition, subtraction, multiplication, and division, but it may be appropriate for exponentiation. Our grammar also correctly represents precedence levels by introducing a new non-terminal symbol for each precedence level. According to our grammar, expressions consist of the sum or difference of terms (or a single term), where a term consists of the product or division of factors (or a single factor), and a factor is a nested expression or a number. ======================================================================== Parsing A parser is an algorithm that determines whether a given input string is in a language and, as a side-effect, usually produces a parse tree for the input. There is a procedure for generating a parser from a given context-free grammar. In fact, it is possible to parse any CFG in time cubic in the length of the input. There are two known algorithms for this, one due to Earley, the other to Cook, Younger, and Kasami. In practice, cubic time is too slow for most purposes. Fortunately, many (but not all!) grammars can be parsed in linear time. There are two major families of parsing algorithms that run in linear time. One family constructs the parse tree from the root downward; the other builds it from the leaves upward. We will study one form of top-down parser: recursive descent. ------------------------------------------------------------------------ Recursive-Descent Parsing Recursive-descent parsing is one of the simplest parsing techniques that is used in practice. The basic idea is to associate each non-terminal with a procedure. The goal of each such procedure is to read a sequence of input characters that can be generated by the corresponding non-terminal, and return a pointer to the root of the parse tree for the non-terminal. The structure of the procedure is dictated by the productions for the corresponding non-terminal. The procedure attempts to "match" the right hand side of some production for a non-terminal. * To match a terminal symbol, the procedure compares the terminal symbol to the input; if they agree, then the procedure is successful, and it consumes the terminal symbol in the input (that is, moves the input cursor over one symbol). * To match a non-terminal symbol, the procedure simply calls the corresponding procedure for that non-terminal symbol (which may be a recursive call, hence the name of the technique). --------------------------------------- Recursive-Descent Parser for Expressions As it turns out, the expression grammar we were using earlier can't be parsed top-down (more on why later). Here's one that can: E --> T Etail Etail --> + T Etail | - T Etail | epsilon T --> F Ttail Ttail --> * F Ttail | / F Ttail | epsilon F --> ( E ) | num We create procedures for each of the non-terminals. According to production 1, the procedure to match expressions (E) must match a term (by calling the procedure for T), and then more expressions (by calling the procedure Etail). procedure E T() Etail() Some procedures, such as Etail, must examine the input to determine which production to choose. procedure Etail switch next_token case + match(+) T() Etail() case - match(-) T() Etail() default return We've assumed here a global variable next_token and a utility routine named match: procedure match(expected) if next_token != expected error() else next_token = scan() // read next terminal symbol into global variable The error routine in a pure parser simply halts without accepting. In a compiler it prints a nice diagnostic message and then does something potentially really complicated (which I won't cover here) to patch up the parser tree and/or the input and continue looking for further errors. Here are the rest of the recursive descent routines: procedure T // very similar to E F() Ttail() procedure Ttail // very similar to Etail switch next_token case * match(*) F() Ttail() case / match(/) F() Ttail() default return procedure F switch next_token case ( match(() E() match()) case num match(num) default error() Notice that the default case in F is an error, whereas the default case in Etail and Ttail was to return without doing anything. The reason for the difference is that Etail and Ttail have epsilon productions: they are allowed to have an empty subtree under them in the parse tree. F does not have an epsilon production: it *has* to be either a number or a parenthesized expression. Look carefully also at the second call to march() within F. There is no guarantee that we will actually have a right parenthesis coming up in the input. That's why match() has a check inside. In larger, programming language-size grammars, there are lots of similar cases in which the check inside match is non-redundant. Finally, we need a main program: procedure main E match(eof) Here we adopt the convention that end-of-file is represented by a pseudo-token so we can use whatever standard error-detection/recovery mechanism we've built into the match routine. --------------------------------------- Tracing the Parser As an example, consider the following input: 1 + (2 * 3) / 4. We just call the procedure corresponding to the start symbol. next_token = "1" Call E Call T Call F next_token = "+" /* Match 1 with F */ Call Ttail /* Match epsilon */ Call Etail next_token = "(" /* Match + */ Call T Call F /* Match (, looking for E ) */ next_token = "2" Call E Call T Call F /* Match 2 with F */ next_token = "*" Call Ttail /* Match * */ next_token = "3" Call F /* Match 3 with F */ next_token = ")" Call Ttail /* Match epsilon */ Call Etail /* Match epsilon */ next_token = "/" /* Match ")" */ Call Ttail next_token = "4" /* Match "/" */ Call F /* Match 4 with F */ next_token = eof Call Ttail /* Match epsilon */ Call Ttail /* Match epsilon */ Call Etail /* Match epsilon */ /* Match eof */ --------------------------------------- Observations about Recursive-Descent Parsing * In procedure Etail and Ttail, we match one of the productions with an arithmetic operator if we see such an operator in the input; otherwise we simply return. A procedure that returns without matching any symbols is, in effect, choosing the epsilon production. * In our expression parser, we only choose the epsilon production if the next_token doesn't match the first terminal on the right hand side of the production. * We never attempt to read beyond the end marker (eof), which is matched only at the end of an outermost expression. In all other circumstances, the presence of the end marker signals a syntax error. * As written, our recursive-descent parser only determines whether or not the input string is in the language of the grammar; it does not give the structure of the string according to the grammar. We could easily build a parse tree incrementally during parsing. The book shows how in section 11.6. --------------------------------------- Lookahead in Recursive-Descent Parsing In order to implement a recursive-descent parser for a grammar, for each nonterminal in the grammar, it must be possible to determine which production to apply for that non-terminal by looking at only one upcoming input symbol. (We want to avoid having the compiler or other text processing program scan ahead in the input to determine what action to take next.) The lookahead symbol is simply the next terminal that we will try to match in the input. We use a single lookahead symbol to decide what production to match. Consider a production: A --> X1...Xm. We need to know the set of possible lookahead symbols that indicate this production is to be chosen. This set is clearly those terminal symbols that can begin a string produced by the symbols X1...Xm (which may be either terminals or non-terminals). We donote the set of symbols that could be produced first by X1...Xm as First(X1...Xm). ------------------------------------------------------------------------ First Sets To distinguish two productions with the same non-terminal on the left hand side, we examine the First sets for their corresponding right hand sides. We do this in 3 steps (1) figure out which non-terminals can generate epsilon (2) figure out FIRST sets for all non-terminals (3) figure out FIRST sets for right-hand sides Steps (1) and (2) start with "obvious" facts from the grammar and iterate until they can't learn any more. Consider step (1). If we have A --> epsilon B --> epsilon then clearly A and B are symbols that can generate epsilon. These are the "obvious" facts. Then in a second pass over the grammar, if we have C --> A B we can deduce that C is a symbol that can generate epsilon. If we have D --> C A B then in a third pass we can deduce that D is a symbol that can generate epsilon. We continue this process until we make a complete pass over the grammar without learning anything. Now consider step (2). If we have A --> b C D B --> c D e then clearly b is an element of FIRST(A) and c is an element of FIRST(B). These are obvious facts. Then in a second pass if we have C --> B A d clearly c is an element of FIRST(C), because it's an element of FIRST(B) and a C can start with a B. But if B can generate epsilon, then b is also an element of FIRST(C), because we can erase the B and generate the b from A. In each pass over the grammar we work our way through each RHS, adding elements to the FIRST set of the LHS, until we find a symbol in the RHS that cannot generate epsilon, at which point we move on to the next production. As in step (1) we keep making passes until we don't learn anything new. Finally, in step (3) we use our knowledge of FIRST sets for individual symbols to calculate FIRST sets for RHSs. Given the production A --> X1...Xm we must determine First(X1...Xm). We first consider the leftmost symbol, X1. * If this is a terminal symbol, then First(X1...Xm) = X1. * If X1 is a non-terminal, then we compute the First sets for each right hand side corresponding to X1. In our expression grammar above: First(E) = First(T Etail) First(T Etail) = First(T) First(T) = First(F Ttail) First(F Ttail) = First(F) = {(,num} If X1 can generate epsilon, then X1 can (in effect) be erased, and First(X1...Xm) depends on X2. * If X2 is a terminal, it is included in First(X1...Xm). * If X2 is a non-terminal, we compute the First sets for each of its corresponding right hand sides. Similarly, if both X1 and X2 can produce epsilon, we consider X3, then X4, etc. It is possible that X1, X2, ..., Xm can *all* produce epsilon. What then? The informal answer is that we should predict A --> X1...Xm if the lookahead symbol can come *after* an A in some line of the derivation. A formal treatment of this subject requires the notion of so-called Follow sets for symbols. In practice, we don't generally have to know about Follow sets when building a recursive-descent parser. Suppose we have three productions for A: A --> B c D A --> e f A --> G H where G and H can both generate epsilon. Our parsing routine then says: A() { switch (next_token) { case First(BcD): B match(c) D case e: match(e) match(f) default: G H If next_token is not in First(BcD) U {e}, we assume we can use the third production. If it turns out that next_token is not in First(GH) U Follow(A) either, then this was a bad decision, but nothing catastrophic happens: the calls to G and H will go ahead and generate epsilon, we'll return, and our caller will announce a syntax error -- just a bit later than we could have. --------------------------------------- LL(1) Grammars for Recursive-Descent Parsing (also known as "top-down" or "predictive" parsing) Recursive-descent parsing can only parse those CFG's that have disjoint predict sets for productions that share a common left hand side. CFG's that obey this restriction are called LL(1). From experience we know that it is usually possible to create an LL(1) CFG for a programming language. However, not all CFG's are LL(1) and a CFG that is not LL(1) may be parsable using some other (usually more complex) parsing technique. Two common properties of grammars that produce trouble for top-down parsing are: * Left recursion: any grammar containing productions with left recursion, that is, productions of the form A --> A X1...Xm, cannot be LL(1). The problem is that any symbol that predicts this production the first time will, of necessity, continue to predict this production forever (and never be matched). * Common prefix: any grammar containing two productions for the same non-terminal that share a common prefix on the right hand side cannot be LL(1). The problem is that any symbol that predicts the first production must also predict the second; since the predict sets for the two productions are not disjoint, the grammar is not LL(1). --------------------------------------- Creating an LL(1) Grammar Consider the following grammar for expressions: 1. E --> E + T 2. E --> E - T 3. E --> T 4. T --> T * F 5. T --> T / F 6. T --> F 7. F --> ( E ) 8. F --> number This grammar has left recursion, and therefore cannot be LL(1). We can replace the use of left recursion with right recursion as follows: 1. E --> T + E 2. E --> T - E 3. E --> T 4. T --> F * T 5. T --> F / T 6. T --> F 7. F --> ( E ) 8. F --> number The resulting grammar is still not LL(1); productions 1-3 share a common prefix, as do productions 4-6. We can eliminate the common prefix by defering the decision as to which production to pick until after seeing the common prefix. This technique is called factoring the common prefix. 1. E --> T Etail 2. Etail --> + T Etail | - T Etail | epsilon 3. T --> F Ttail 4. Ttail --> * F Ttail | / F Ttail | epsilon 5. F --> ( E ) | number And this is, of course, our top-down grammar for expressions. WARNING: while it is possible to mechanically eliminate left recursion and common prefixes from a grammar, this is not guaranteed to make the result LL(1). Some languages just can't be parsed top-down. Here's a grammar for one: G --> a B b G --> a C c B --> a B b B --> C --> a C c C --> The language consists of all strings of a's followed by an equal number of b's or by an equal number of c's. Left factoring doesn't solve the problem (try it!). ------------------------------------------------------------------------ Table-Driven Parsing In recursive-descent parsing, the decision as to which production to choose for a particular non-terminal is hard-coded into the procedure for the non-terminal. The problem with recursive-descent parsing is that it is inflexible; changes in the grammar can cause significant (and in some cases non-obvious) changes to the parser. Since recursive-descent parsing uses an implicit stack of procedure calls, it is possible to replace the parsing procedures and implicit stack with an explicit stack and a single parsing procedure that manipulates the stack. In this scheme, we encode the actions the parsing procedure should take in a table. This table can be generated automatically (with the grammar as input), which is why this approach adapts more easily to changes in the grammar. (BTW, we could automatically generate a recursive-descent parser, but that's no easier, and it's likely to be a little slower, so nobody bothers.) Note the analogy to scanning: table-driven top-down parsers are to recursive descent parsers as table-driven scanners are to nested-switch-statement scanners. --------------------------------------- A Table-Driven Parser The parse table encodes the choice of production as a function of the current non-terminal of interest and the lookahead symbol. T: Non-terminals x Terminals -> Productions U {Error} The entry T[A,x] gives the production number to choose when A is the non-terminal of interest and x is the current input symbol. The table is a mapping from non-terminals x terminals to productions. T[A,x] == A -> X1..Xm if x in Predict(A->X1..Xm) otherwise T[A,x] == Error The driver procedure is very simple. It stacks symbols that are to be matched or expanded. Terminal symbols on the stack must match an input symbol; non-terminal symbols are expanded according to the Predict sets, which are embedded in the parse table. The Predict set for a given production is basically the First set for its RHS. The possible exception arises for epsilon productions (including productions that can generate epsilon indirectly): for these we can, if we want, use Follow sets (mentioned but not described above) to avoid predicting an epsilon production when it's certain to lead to an error later on. --------------------------------------- Parse Table for Expressions Here is an LL(1) expression grammar, augmented to include the end marker: 1. S --> E eof 2. E --> T Etail 3. Etail --> + T Etail 4. Etail --> - T Etail 5. Etail --> epsilon 6. T --> F Ttail 7. Ttail --> * F Ttail 8. Ttail --> / F Ttail 9. Ttail --> epsilon 10. F --> ( E ) 11. F --> number The table for this expression grammar is as follows, where a blank entry corresponds to an error: ( ) + - * / Number eof ----------------------------------------------- S 1 1 ----------------------------------------------- E 2 2 ----------------------------------------------- Etail 5 3 4 5 ----------------------------------------------- T 6 6 ----------------------------------------------- Ttail 9 9 9 7 8 9 ----------------------------------------------- F 10 11 This table is constructed from the Predict sets described earlier. It's basically the same as the labels on the switch statements in the recursive descent parser. The only difference is that the tool used to generate the table has used Follow sets to distinguish between cases where predicting an epsilon production is a good idea and cases where predicting an epsilon production is certain to lead to an error later on. In effect, the recursive descent parser shown above has a '5' in every blank entry in the Etail row, and a '9' in every blank entry in the Ttail row. If we wanted we could use Follow sets to get earlier error detection in the recursive descent parser, too. The Etail and Ttail routines would then look like this: procedure Etail switch next_token case + match(+) T() Etail() case - match(-) T() Etail() case ), eof return default error() procedure Ttail switch next_token case * match(*) F() Ttail() case / match(/) F() Ttail() case ), eof, +, - return default error() --------------------------------------- Driver Procedure Under table-driven parsing, there is a single procedure that "interprets" the parse table. This "driver" procedure takes the following form: next_token : symbol PS : stack of symbol // explicit parsing stack PT : array[symbol, token] of production // parse table procedure parse PS.push(S) next_token := scan() while not PS.empty() do top : symbol = PS.top() if top is a nonterminal then prod : production = PT[top, next_token] if prod > 0 then PS.pop() for each symbol on RHS of prod do PS.push(symbol) else error() else if next_token == top then PS.pop() // match terminal symbol in input next_token = scan() else error() --------------------------------------- Example Parse Let's trace the parse for the input 1 + (2 * 3) eof Stack Contents Current input Action 1: S 1 + (2 * 3) eof 1 2: E eof 1 + (2 * 3) eof 2 3: T Et eof 1 + (2 * 3) eof 6 4: F Tt Et eof 1 + (2 * 3) eof 11 5: N Tt Et eof 1 + (2 * 3) eof match 6: Tt Et eof + (2 * 3) eof 9 7: Et eof + (2 * 3) eof 3 8: + T Et eof + (2 * 3) eof match 9: T Et eof (2 * 3) eof 6 10: F Tt Et eof (2 * 3) eof 10 11: ( E ) Tt Et eof (2 * 3) eof match 12: E ) Tt Et eof 2 * 3) eof 2 13: T Et ) Tt Et eof 2 * 3) eof 6 14: F Tt Et ) Tt Et eof 2 * 3) eof 11 15: N Tt Et ) Tt Et eof 2 * 3) eof match 16: Tt Et ) Tt Et eof * 3) eof 7 17: * F Tt Et ) Tt Et eof * 3) eof match 18: F Tt Et ) Tt Et eof 3) eof 11 19: N Tt Et ) Tt Et eof 3) eof match 20: Tt Et ) Tt Et eof ) eof 9 21: Et ) Tt Et eof ) eof 5 22: ) Tt Et eof ) eof match 23: Tt Et eof eof 9 28: Et eof eof 5 29: eof eof match 30: Done! --------------------------------------- The complexity of LL(1) parsing What is the Big-O complexity of our table-driven parser? The work inside the main loop is bounded by a constant: even when we push all the symbols of a right-hand side, the length of that RHS is bounded by a constant. So the real question is: how many times does the main loop execute? Things would be easy if we called scan() on every iteration: then we'd know the number of iterations was the same as the number of tokens in the input. But we don't scan on every iteration. The trick is to think about the parse tree. In every iteration of the main loop we either predict and expand a production (possibly an epsilon production) or we match a token. That means we have precisely as many iterations as there are nodes in the parse tree. The same observation holds in recursive descent parsing: we make exactly one subroutine call -- either to match() or to one of the non-terminal routines -- for every node in the parse tree. So how many nodes can there be in the parse tree? First, suppose we have no epsilon productions in our grammar. Then the number of leaves is equal to the number of tokens in the input. How about internal nodes? Well, because we know the grammar is unambiguous (this is crucial), we never have a node that derives only itself (if we did we could repeat the derivation an arbitrary number of times, generating different trees). This means that starting with any node in the tree, after at most P predictions, working downward, where P is the number of productions in the grammar, we have to get some fan-out. Informally, after generating some constant number of internal nodes, we have to double the number of leaves. You might be tempted, then, to think there could be N log N nodes in the tree, where N is the number of leaves, but fortunately that isn't so. Again speaking informally, note that N + N/2 + N/4 + N/8 + N/16 + ... doesn't sum to N log N: it sums to 2N. In the same way, the number of nodes in the parse tree turns out to be O(NP), and P is a constant -- O(N). ======================================================================== CFGs vs Regular Expressions Context-free grammars are strictly more powerful than regular expressions. * Any language that can be generated using regular expressions can be generated by a context-free grammar. * There are languages that can be generated by a context-free grammar that cannot be generated by any regular expression. As a corollary, CFGs are strictly more powerful than DFAs and NDFAs. The proof is in two parts: * Given a regular expression R , we can generate a CFG G such that L(R) == L(G). * We can define a grammar G for which there there is no FA F such that L(F) == L(G). --------------------------------------- Simulating a Regular Expression with a CFG To show that CFGs are at least as powerful as regular expressions, we show how to simulate a RE using a CFG. The construction is similar to the one used to simulate a regular expression with a FA; we build the CFG G in pieces, where each piece corresponds to the operands and operators in the regular expression. * Assume the RE is a single operand. Then if RE is epsilon or a character in the alphabet, add to G the production --> RE If RE is null, don't add a production. * Assume the RE is R1R2. Add to G the production --> and create productions for regular expressions R1 and R2. * Assume the RE is R1 | R2. Add to G the production --> | and create productions for regular expressions R1 and R2. * Assume the RE is R1*. Add to G the production --> | epsilon and create productions for regular expression R1. --------------------------------------- Example: RE to CFG We will build a CFG G for the RE (0|1)*111. First the operands: <0> --> 0 <1> --> 1 Now the innermost operator, union: --> <0> | <1> Now the closure operator: --> | epsilon Now the concatenation operators: --> R2 R3 R4 R5 --> <1> --> <1> --> <1> The final grammar G is: --> R2 R3 R4 R5 --> | epsilon --> <0> | <1> --> <1> --> <1> --> <1> <0> --> 0 <1> --> 1 --------------------------------------- A CFG with no Corresponding RE Recall that FA cannot count. Thus, no FA can recognize the language {0^n 1^n | n >= 1} (i.e., the set of strings containing one or more zeros followed by an equal number of ones). Assume such an FA exists, and it has N states. What happens when the input string has N+1 zeros in it, followed by N+1 ones? * Since the FA only has N states, we must visit some state sT twice on seeing N+1 zeros. * The FA cannot know whether we are entering sT for the first time, when we've seen i < N zeros, or the second time, when we've seen j > i zeros. * There must be a path from sT to an accepting state, since the input string is in the language. * The FA will accept an input string without an equal number of zeros and ones, since i != j, and there is a path to an accepting state from sT on the remaining input. This language is generated by the following CFG: 1. S --> 0 S 1 2. S --> 01 We can prove that this grammar generates the language by induction on n, the number of zeros and ones in the string. 1. For the basis step, n = 1, and the string is 01. This string is generated by applying the second production once. 2. For the inductive step, assume we can generate O^n1^n. The last production applied must have been production 2, so the string must have been 0^(n-1)S1^(n-1). If we apply production 1 and then production 2, we get 0^nS1^n, and then 0^(n+1)1^(n+1). Thus, we can generate all strings of the form {0^n 1^n|n>=1}. 3. Since we can only apply production 1 some number of times followed by production 2, these are the only strings generated by the grammar.