• example:

          num  = [0-9]+
          id   = [a-z][a-z0-9]*
          expr = expr '+' expr | expr '*' expr | '(' expr ')' | num | id
  

• can remove or and just write as different ways to expand expr:

          num  = [0-9]+
          id   = [a-z][a-z0-9]*
          expr = expr '+' expr
          expr = expr '*' expr
          expr = '(' expr ')'
          expr = num
          expr = id
  

• but this sort of recursive definition means we don't need *, either:

          dig  = '0'
          dig  = '1'
          ...
          dig  = '9'
          num  = dig
          num  = dig num
  

• note we'll typically let the lexer take care of recognizing tokens (it's more concise), but the notion of iteration is important in general

Context-Free Grammars defined

• language: set of strings where each string is a finite sequence of symbols
• in parsing: string = source program, sequence of symbols is a sequence of lexemes
• CFG describes a language
  • set of productions: symbol -> symbol symbol ... symbol
  • 0 or more symbols on right-hand side
  • symbols are terminal (can't replace; a lexeme) or nonterminal (appear on the left-hand side of some production)
  • no token on left-hand side of some production
  • one of the nonterminals designated as the start symbol
• See Grammar 3.1 (p. 40)
  • grammar:

            S → S; S
            S → id := E
            S → print ( L )
            E → id
            E → num
            E → E + E
            E → (S, E)
            L → E
            L → L, E
    

  • start symbol: S
  • terminals: id print num , + ( ) := ;
  • generate "id := num; id := id + num; print(id)"
    • note id, num are really token types
    • original text (before lexical analysis) could be "a := 5; a := a + 5; print(a)"
• derivation: start with start symbol, replace variables until reach original string
  • shows string a member of the language
  • leftmost derivation: always replace leftmost nonterminal
  • rightmost derivation: always replace rightmost nonterminal
• parse tree: tree constructed by attaching each symbol to the one from which it was derived
  • an expression tree is just a special case of a parse tree
• ambiguous grammar: grammar which allows two distinct parse trees for at least one sentence
  • example: parse trees for "id := id + id + id"
  • [ask:] can you give a sentence which shows above definition of expr is ambiguous?
  • often-but not always-ambiguity leads to multiple meanings
  • will generally prefer unambiguous grammars
• unambiguous grammar for expressions: grammar 3.8, p. 44:

          E → E + T          T → T * F          F → id
          E → E - T          T → T / F          F → num
          E → T              T → F              F → ( E )
  

  • give * higher precedence than +
  • associate operators to the left: 3 - 4 - 5 interpreted as (3 - 4) - 5
  • usually: can convert ambiguous grammar to unambiguous grammar
    • There are inherently ambiguous languages, but they are odd; eg:
      {aⁿ b^m c^m dⁿ | n, m > 0 } union {aⁿ bⁿ c^m d^m | n, m > 0 }
      ; can show aⁿ bⁿ cⁿ dⁿ has more than one parse tree in any grammar
    • hard to write programs in an inherently ambiguous language!

Predictive Parsing

• one form: recursive descent
  • each grammar production gives one clause of a recursive function
  • each nonterminal results in one function
  • example: p. 46 (based on grammar 3.11)
  • negative example: bottom p. 46
    • fix for this case: factoring
    • not always possible to find a fix
  • basic concept: first terminal symbol provides enough information to choose between productions
  • tools exist for cases where first terminal symbol does not provide enough info
    • but recursive descent very easy to build for "nice" grammars; preferable when standard tools are not available or inappropriate
• constructing a predictive parser
  • while we probably wouldn't use tools to do so, the techniques are important for understanding other methods of constructing parsers
  • key issue: determining first and follow sets
    • let γ be a string of terminal and nonterminal symbols
    • FIRST(γ): set of all terminal symbols that can begin any string derived from γ
      • example: FIRST(T * F) = {id, num, (}
      • usefulness: Given X -> γ₁, X -> γ₂, if FIRST(γ₁) ∩ FIRST(γ₂) is non-empty, then cannot construct a predictive parser (without changing grammar)
      • trick in computing: see grammar 3.12 (p. 47): nullable symbols making computing FIRST mildly tricky
    • FOLLOW(X): set of terminals that can immediately follow X in some derivation
      • example: FOLLOW(T) = {+, -, *, /}
      • needed for computing FIRST
  • algorithm: see p. 49
    • note compute until no change: called a fixed point computation
    • application: grammar 3.12, possibly grammar 3.10 (p. 45)
  • Can generalize to strings of symbols:
    • FIRST(X γ) = FIRST[X] if not nullable[X]
    • FIRST(X γ) = FIRST[X] ∪ FIRST(γ) if nullable[X]
    • nullable(γ) iff each symbol in γ is nullable
  • Alternative version of algorithm (using above rules):

    -- initialize:
    for each terminal symbol t, FIRST[t] ← {t}
    for each nonterminal symbol X, FIRST[X] ← FOLLOW[X] ← {}
    repeat
        for each prodution X → γ
            if γ is nullable, nullable[X] ← true
    until nullable is not changed by the inner for loop
    -- compute FIRST, FOLLOW:
    repeat
        for each prodution X → γ
            for each symbol Y in γ and strings α, β where X → α Y β 
                if α is nullable, FIRST[X] ← FIRST[X] ∪ FIRST[Y]
                if Y is a nonterminal, then
                    if β is nullable, FOLLOW[Y] ← FOLLOW[Y] ∪ FOLLOW[X]
                    if β = β1β2 where β1 is nullable, FOLLOW[Y] ← FOLLOW[Y] ∪ FIRST(β2)
    until FIRST and FOLLOW do not change throughout an iteration
    

• using FIRST & FOLLOW to construct a predictive parser
  • write function for each nonterminal
  • write clause for each production
    • see table for which production to chose on each terminal
    • if more than one entry for some terminal, cannot construct predictive parser in this way
    • ambiguous grammar will always lead to duplicate entries
  • could create interpreter which does same thing; would use stack for pending productions
  • Formal construction: see below

Eliminating Left Recursion

• Issue with expression grammar: E → E + T is left-recursive
  • cannot construct a predictive parser for a left-recursive language
• To eliminate left recursion, use right recursion:
  • let E' be a new nonterminal
  • replace E → E + T, E → T by

            E → T E'
            E' → + T E'
            E' → ε
    

  • in general, given X → X γ, X → α (where α does not start with X), can rewrite it using right recursion
    • see p. 52 for a formal construction that handles this general case

Left Factoring

• consider

          S → if E then S else S
          S → if E then S
  

• This also causes problems with predictive parsing; no way to tell which string of symbols to pursue
• Solution: factor out the common bits:

          S → if E then S X
          X → ε
          X → else S
  

LL(1) Parser Construction

• LL(1) parser: a table-driven predictive parser
  • LL: left to right parse, leftmost derivation
  • left-to-right parse: read tokens in standard left-to-right reading order
  • right-to-left parsers generally not useful for (English-based) programming languages
  • leftmost derivation: always expand leftmost symbol; later we will look at rightmost derivations.
  • 1: one symbol of lookahead
  • Essentially a table-driven version of recursive-descent parsing
• Algorithm for constructing LL(1), parser:
  1. Eliminate left recursion
  2. Factor to eliminate multiple productions with the same prefix
  3. Augment grammar with S' → S $ (if necessary; $ used to denote end of input)
  4. Compute FIRST, FOLLOW, nullable
  5. Construct predictive parsing table:
     • for each production X → γ and each T in FIRST(γ), add X → γ to table[X][T]
     • for each production X → γ where nullable(γ) and each T in FOLLOW(X), add X → γ to table[X][T]
• Application to expression grammar 3.10 (p. 45):
  1. Eliminate left recursion giving grammar 3.15
  2. Compute nullable, FIRST, FOLLOW - see Table 3.16 on p. 52
  3. Construct predictive parse table 3.17 (p. 53)
• grammars for which predictive table contains no duplicate entries are LL(1)
• could generalize to LL(k) with k symbols of lookahead; results in a large table!
  • every LL(1) is LL(2), every LL(2) is LL(3)
  • no ambiguous grammar is LL(k) for any k
    • This means one must remove ambiguity before attempting to construct an LL parser
• Using the table to parse:
  • todo = [S] -- stack of symbols with start symbol on top
  • loop until todo is empty:
    • if top of stack is a terminal matching next input symbol, advance input and pop top of stack
    • if top of stack todo is a nonterminal X and next input is (terminal) y and table[X][y] is X → α, then pop the top of todo and push the symbols in α in reverse order; that is

              todo.pop()
              for s in reverse(α)
                 todo.push(s)
      

• Alternatively, can use the table to create a recursive descent parser: write a function for each nonterminal in which the terminal symbols in the table drive which productions you try to parse next
  • Table for above expression grammar: figure 3.17
  • For example, the table in figure 3.17 contains E' → +TE' at "+" and E' → ε at both ")" and "$"
  • The procedure to parse E' would try to parse + followed by T and E' on input +, and would simply return on inputs ) and $
  • Any other cases (such as * and id), the procedure to parse E' owuld raise an error
  • The procedure for S would attempt to parse the whole expression, "S → E $", on an "id" or "("; any other symbol being first would be an error

Error Handling

• A blank entry in the table indicates error condition: if variable X has no entry for input a, seeing an a when parsing an X indicates a problem
• simple solution: raise exception and report error
• better: print error message, recover from error, and continue as best as possible
• continuing proceeds by deleting, replacing, or inserting some tokens
  • example: in factor, if fail to find a right paren can just return as if it were there
  • problem: inserting can lead to an infinite loop!
    • deleting is safer: always terminates
  • recovery by deletion: skip tokens until token in FOLLOW set is reached
• usually need to adjust error handling to minimize cascades of errors

Review

• Context-free grammars
• LL(1) parsing
• Computing FIRST, FOLLOW, nullable
• Recursion removal
• Left factoring