CS304: Compilers

Unit 5: Parsing and Syntax Analysis

• Upon successful completion of this unit, you will be able to:

  • Explain parsing in the context of the compilation process.
  • Describe several approaches or strategies used for parsing.
  • Specify the functions of a parser in performing syntax analysis.
  • Describe the handling of ambiguities.
  • Summarize the design and construction of a scanner.

• 5.1: Parser Introduction and Overview

  • Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 3: Syntax Analysis" URL

    Read Chapter 3 through section 3.1.
    

  • University of California, Berkeley: Paul Hilfinger's "Parsing" URL

    Read these notes. This material overlaps some of the readings later in the class. However, they add additional information and have a practical perspective.
    

• 5.2: Requirements of a Parser

  • Wikipedia: "Parsing" URL

    Read the following three paragraphs: "Programming languages," "Overview of the process," and "Types of Parsers." Requirements of a parser include: build internal representation of the input tokens (which come from the scanner); check that the input string of tokens is legal in the language of the compiler (i.e., that it can be derived from the start symbol); and determine the derivation steps for the input string of tokens. In addition, the parser should be reliable, efficient (how efficient depends on the intended use), user friendly (i.e., provide clear, accurate messages), and supportable (assuming that the parser will be used for a long time).

• 5.3: Functions of a Parser

  • Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 3: Syntax Analysis" URL

    Read subsections 3.4 - 3.6. The functions of a parser include: building an internal representation of the derivation tree and related parser information, and resolving ambiguities of the language pertaining to the input string of tokens.
    

  • Stanford University: Keith Schwarz's "Top-Down Parsing" URL

    Read slide 4. The first bullet is a requirement statement and the third bullet is a function statement. An additional function is the output of meaningful and accurate messages, including error messages.

• 5.4: Formal Language Considerations

  • Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 3: Syntax Analysis" URL

    This subsection is just a review of what has been covered in units 2 and 3. Read subsections 3.2 and 3.3. The main idea is that context free languages are used to build efficient parsers, but are supplemented with special techniques to resolve ambiguities.

• 5.5: Design of a Parser

  • 5.5.1: Top-Down Parsers

    • Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 3: Syntax Analysis" URL

      Read sections 3.7 to 3.13.
      

    • Stanford University: Keith Schwarz's "Top-Down Parsing" URL

      Read these notes, as well as these slides from Lecture 3 and Lecture 4.

    • Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Top-Down Parsing" URL

      This material overlaps some of the previous readings. However, it presents the material using examples. Scan over the slides, studying those that you feel will benefit you.
      

    • University of California, Berkeley: Paul Hilfinger's "Top-Down Parsers" URL

      This material overlaps previous readings, but provides a practical view. Look over the material and study the parts you feel will benefit you.
      

    • University of California, Berkeley: Paul Hilfinger's "Lecture 7" and "Lecture 8" Page

      Watch both lectures.

  • 5.5.2: Bottom-Up Parsers

    • Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 3: Syntax Analysis" URL

      Read sections 3.14 to 3.18.
      

    • Stanford University: Keith Schwarz's "Bottom-Up Parsing" URL

      Read the following notes:

      • Notes 10
      • Notes 11
      • Lecture 4
      • Lecture 5
      • Lecture 6

    • Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Introduction to Shift-Reduce Parsing" URL

      This material overlaps some of the previous readings. However, it presents the material using examples. Scan over the slides, studying those that you feel will benefit you.
      

    • University of California, Berkeley: Paul Hilfinger's "Earley's Algorithm" and "Bottom-Up Parsing" URL

      This material overlaps previous readings, but provides a practical view. Look over the material and study the parts you feel will benefit you.
      

      Read these notes, as well as the notes for Lecture 12.

    • University of California, Berkeley: Paul Hilfinger's "Lectures 10-14" Page

      Watch these lectures.

• 5.6: Construction of a Parser

  • Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 3: Syntax Analysis" URL

    Read sections 3.15 to the end of Chapter 3.

  • Stanford University: Keith Schwarz's "Bottom-Up Parsing" URL

    Read Notes 12, 14, and 16. Read the slides for lectures 5 (264 to the end), 6 (48 to the end), and 7 (91 to the end).
    

  • Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Parse Table Construction" URL

    This material overlaps, but also complements, some of the previous readings. Scan over the slides, studying those that you feel will benefit you. In particular, in the introduction to shift-reduce parsing, study slides 60 to the end.

• 5.7: Verification and Validation of a Parser

  • Tom Niemann's "Tutorial on LEX and YAC" Page

    In this exercise, you will be introduced to LEX and YACC, which stand for Lexer (short for lexical analyzer) and Yet Another Compiler-Compiler. They are generators, i.e. programs that generate other programs, in this case, a scanner and a parser. Our focus in this Assessment will be on YACC. Read the part of the tutorial on YACC. This tutorial explains YACC and how YACC and LEX interface. LEX and YACC are the original programs, and just as Flex is an open software version for LEX, Bison is an open software version for YACC.