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 6: Syntax Directed Translation and Semantic 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 6: Syntax Directed Translation and Semantic Analysis

    Semantic Analysis takes input from the parsing process and prepares the code for the code-generation step. In this unit, we will discuss this process in detail, learning about scope and type-checking, type expression, type equations, and type inference.

    Completing this unit should take you approximately 33 hours.

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

      • Explain semantic analysis in the context of the compilation process.
      • Describe scope checking and type checking.
      • Specify the functions of semantic analysis.
      • Solve type equations and make inferences in a type calculus.
    • 6.1: Syntax-Directed Translation and Attribute Grammars

      • Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 5: Interpretation" URL

        Read Chapter 5 on interpretation, where execution of a program takes place as the derivation is produced.

      • Stanford University: Keith Schwarz's "Syntax-Directed Translation" URL

        Study the definitions and examples. Syntax-directed translation and attribute grammars are techniques for using the parser to drive the translation directly. Attributes are properties of grammar symbols, and the attributes take on values. Rules associated with each grammar production specify how to compute the value of the attributes.

    • 6.2: Intermediate Representation

      • Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Intermediate Formats" URL

        Study the slides on intermediate representations. Data, as well as computations and flow of control, have intermediate representations.

      • Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 4: Scopes and Symbol Tables" URL

        Read Chapter 4 on scope of names and symbol tables.

    • 6.3: Functions of Semantic Analysis

        • 6.3.1: Scope Checking of Names in a Program

          • Stanford University: Keith Schwarz's "Semantic Analysis" URL

            Read the notes and the slides for an overview of semantic analysis.

        • 6.3.2: Static vs. Dynamic Scope Checking

          • University of California, Berkeley: Paul Hilfinger's "Static Semantics Overview" URL

            Read these slides.

        • 6.3.3: Type Checking

          • Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 6: Type Checking" URL

            Read Chapter 6, which presents an overview of type checking, nicely organized: symbol table environment, type checking for expressions, functions, and then, for programs.

          • 6.3.3.1: Type Expressions, Type Equivalence, Type Inference, and What to Check

            • Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Semantic Analysis" URL

              Study the slides on type systems and what to check for when building intermediate representations for various language constructs.

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

              Read slides 2 through 14 and use them as a review or supplement to the above readings. Slides 15 through 31 give examples of type inference for the languages Prolog, Java, and Python. 

            • University of California, Berkeley: Paul Hilfinger's "Lectures 18-21" Page

              These lectures correspond to the notes and are optional. They may be helpful in understanding some of the notes.

          • 6.3.3.2: Type Systems as Proof Systems-Type Checking as Proofs

            • Stanford University: Keith Schwarz's "Type Checking" URL

              Study the very interesting presentation on type checking by proofs.

            • University of California, Berkeley: Paul Hilfinger's "Type Inference and Unification" URL

              Read slides 1 through 8. The slides are somewhat formal and present a "type calculus." Use these slides to add to your understanding of types.

            • University of California, Berkeley: Paul Hilfinger's "Lecture 22" Page

              This video corresponds to these notes and is optional. If it adds to the notes and helps you, watch it.

          • 6.3.3.3: Applications of Type Proofs

            • Stanford University: Keith Schwarz's "Type Checking II" URL

              Study the application of the type proof system (introduced above) to the detection of type errors.

          • 6.3.3.4: Type Equations, Unification and Binding of Type Expressions

            • University of California, Berkeley: Paul Hilfinger's "Type Inference and Unification" URL

              Study slides 8 through 19. The slides supplement the readings above with type examples. A binding is a substitution of a type expression for a type variable. 

      • 6.4: Verification and Validation of Semantic Analysis

        • Torben Ægidius Mogensen's "Basics of Compiler Design, Chapter 6: Type Checking" URL

          Complete exercises 6.1 and 6.2 on pages 143 and 144.

          These exercises will give you some practice with semantic analysis and are based on Chapter 6, which covers type checking. Then check your answers against the Answer Key.

    Skip Activities
    Activities
    • QuizQuizzes
    • Resources
    Skip Recent activity
    Recent activity
    Activity since Sunday, February 5, 2023, 10:55 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