Section outline

  • November 6th, Thursday (14:30-16:30)

    Context-free grammars

    • Definition of parse tree
    • Standard terminology for parse trees
    • Relation between derivations, leftmost/rightmost derivations, and parse trees
    • The relation between derivations and parse trees is not one-to-one
    • Ambiguous CFGs
    • Inherently ambiguous CFGs
    • Transforming a regular expression into an equivalent CFG
    • Transforming a FA into an equivalent CFG

    References

    • Hopcroft et al., chapter 5