Skip to main content
  • Courses
  • Programs
  • Help
    Getting Started Discussion Forums Help Center & FAQ
Saylor Academy
    Close
    Toggle search input
  • Log in or Sign up
Courses
Programs
Help
Getting Started
Discussion Forums
Help Center & FAQ
  • CS304: Compilers
  • Sections
  • Course Introduction
  • Unit 1: Introduction to Compilers
  • Unit 2: Formal Languages and Formal Grammar
  • Unit 3: Finite State Machines
  • Unit 4: Scanning and Lexical Analysis
  • Unit 5: Parsing and Syntax Analysis
  • Unit 6: Syntax Directed Translation and Semantic Analysis
  • Unit 7: Runtime Environment
  • Unit 8: Code Generation
  • Unit 9: Code Optimization
  • Unit 10: Compiler Verification and Validation
  • Unit 11: Compiler Summary and Next Steps
  • Final Exam
  • Resources
  • Activities
  • Quizzes
  • Home
  • My programs

CS304: Compilers

Competencies
  1. Home
  2. Courses
  3. (hidden)
  4. CS304: Compilers
  5. Sections
  6. Unit 5: Parsing and Syntax Analysis

Learn new skills or earn credit towards a degree at your own pace with no deadlines, using free courses from Saylor Academy. We're committed to removing barriers to education and helping you build essential skills to advance your career goals. Start learning here, or check out our full course catalog.

Log in or Sign up to enroll in courses, track your progress, gain access to final exams, and get a free certificate of completion!

Sign up now
Back to course 'CS304: Compilers'
  • Unit 5: Parsing and Syntax Analysis

    The next step of the compilation process is parsing. This step also has a foundation in formal languages and automata. Parsing takes input from the Lexical Analysis step and builds a parse tree, which will be used in future steps to develop the machine code. In this unit, we will define parsing and identify its uses. We will also discuss two parsing strategies, Top-Down Parsing and Bottom-Up Parsing, examining what it means to approach parsing from each standpoint and taking a look at an example of each. By the end of the unit, you will understand parsing techniques with regards to compilers, and be able to discuss each of the two main approaches.

    Completing this unit should take you approximately 28 hours.

    • 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.

    Skip Activities
    Activities
    • QuizQuizzes
    • Resources
    Skip Recent activity
    Recent activity
    Activity since Sunday, February 5, 2023, 9:10 AM
    Full report of recent activity...

    No recent activity

    Saylor Academy
    • About

    • Partners

    • Blog

    • Contact

    Saylor Academy

    © Saylor Academy 2010-2023 except as otherwise noted. Excluding course final exams, content authored by Saylor Academy is available under a Creative Commons Attribution 3.0 Unported license. Third-party materials are the copyright of their respective owners and shared under various licenses. See detailed licensing information.

    Saylor Academy®, Saylor.org®, and Harnessing Technology to Make Education Free® are trade names of the Constitution Foundation, a 501(c)(3) organization through which our educational activities are conducted.

    "CCBY"

    Sitemap | Terms of Use | Privacy Policy

    Data retention summary
    Get the mobile app
    Policies