Lecture 3: Parsing
In this lecture we study how to turn syntax definitions (context-free grammars) into parsers that turn program texts into parse trees.
Topics
- 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
- shif-reduce parsing
- reductions, shift-reduce parsing, LR parsing
- nullable, first, follow
- SLR parser generation
Slides
Reading material
- 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:
- https://github.com/TUDelft-CS4200-2018/cc.syntax.parsing
Advanced Topics
Parsing is a vast area and could easily fill an entire course.
- Other parsing algorithms
- top-down, LL parsing
- generalized parsing: GLR, GLL
- parser combinators
- Error recovery