Compiler Construction bio photo

Compiler Construction

Twitter Github

Edit on GitHub

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

CS4200 2019 | Lecture 3 | 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:

  • 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