Compiler Construction bio photo

Compiler Construction

Twitter Github

Edit on GitHub

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


Compiler Construction | Lecture 4 | Parsing from Eelco Visser

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: