This course covers writing simple predictive parsers by hand in Java. We translate grammar rules to recursive methods and to classes using the Composite Pattern.
- You can download the lecture slides for my introduction to grammars and parsing for viewing on screen. Recommended: that way, you get colours and hyperlinks.
- The same material as notes for printing.
For weeks 7 and 8, there is a formative exercise on predictive parsing.
Some code examples:
- A mission statement generator, which works by essentially running a parser in reverse, nondeterministically.
- A canonical example: a parser for the Dyck language.
- A parser in Java that parses expressions and builds an Abstract Syntax Tree using the Composite Pattern.
Grammars and parsing are also covered in Models of Computation in a very abstract form, push-down automata. In this module, we cover writing simple parsers by hand.