Lecture 4: Parsing
In this lecture we study how to turn syntax definitions (context-free grammars) into parsers that turn program texts into parse trees.
- context-free grammars
- derivations, left-most derivations, right-most derivations
- parse trees, abstract syntax trees, terms
- grammar transformations
- left factoring, eliminating left recursion
- disambiguation with associativity and priority rules
- top-down parsing
- bottom-up parsing
- reductions, shift-reduce parsing, LR parsing
- first and follow
- parser generation
- Chapter 4 on Syntactic Analysis of “Compilers: Principles, Techniques, and Tools, 2nd Edition” by Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Pearson, 2007. Read Sections 4.1, 4.2, 4.3, 4.5, 4.6.
Software: `Parse’ language
The language that was used in the lecture to define context-free grammars, derivations, parse tables, and more is defined in this Spoofax project: