# 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