M3: Syntactical Analysis

This third modules provides an overview of the syntactical analysis component of a compiler. We discuss how one implements this component by hand or using an auto generated tool.

Pre-recorded Lectures and Required Readings

Please read over the below articles after our synchronous session:

  1. LL(1) Parsing by Andrew Begeel

  2. How to implement an LR(1) Parser by Kirill Andreev

  3. Abstract Syntax Trees by Ruslan Spivak

The pre-recorded lectures are available here: M3 Videos. You can also find the videos under the “Panopto” tab on the MPCS 51300 canvas site.

  • 3.0 Ambiguous Grammar

  • 3.1 Parsing Overview & Recursive Decent Parser

  • 3.2 Auto-generating a parser and lexer using ANTLR (Part 1)

  • 3.3 Auto-generating a parser and lexer using ANTLR (Part 2)

  • 3.4 Auto-generating a parser and lexer using ANTLR (Part 3)

  • 3.5: AST Construction using an ANTLR Parse Tree (Part 1)

  • 3.6: AST Construction using an ANTLR Parse Tree (Part 2)

Supplementary Resources

  • The slides and code presented in this module are accessible in the upstream repository for this course. Please contact Professor Samuels if you do not have access to them.

  • Engineering a Compiler readings:
    • Chapter 3.1 - 3.5

Synchronous Session

You will find the links to the Zoom sessions on Canvas. As a reminder here are the dates and times for the synchronous session for this module:

  • Dates/Times
    • Section 1: Wednesday June 28th @ 5:30pm-7:00pm

  • Discussion Outline
    • Overview of Syntactical Analysis

    • Expressing Syntax with Parsers

    • Top-Down Parsing: Recursive-Decent Parsing

  • Dates/Times
    • Section 1: Wednesday July 5th @ 5:30pm-7:00pm

  • Discussion Outline
    • Abstract Syntax Trees Overview

    • Coding Demo: Syntax errors detection and AST building using ANTLR for the Cal language.


Assignments are always due on Thursday evenings.