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 2: Formal Languages and Formal Grammar

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 2: Formal Languages and Formal Grammar

    Formal languages and formal grammars are the theoretical foundation for computer languages and the compilation process. Formal languages are defined by their grammars, which specify the syntax of the languages.

    Completing this unit should take you approximately 6 hours.

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

      • Define a formal language.
      • Give examples of a formal language.
      • Define a formal grammar and explain its purpose.
      • Define syntax and semantics of a formal language.
    • 2.1: Motivation for Formal Languages

      • Massachusetts Institute of Technology: S. Amarasinghe and M. Rinard's "Specifying Languages with Regular Expressions and Context-Free Grammars" URL

        Study slides 2 - 8, and slides 38 - 41. Regular and context-free languages are introduced. Also, read slides 68 - 70.

      • Stanford University: Keith Schwarz's "Formal Grammars" URL

        Read pages 10 - 11, which give some history of FORTRAN and ALGOL.

    • 2.2: Formal Grammars

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

        Study slides 41-67.

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

        Read pages 1 - 10. Formal languages are defined by formal grammars. Regular and context-free grammars are applied in scanning and parsing of programming languages. Formal grammars define the syntax of a formal language.

    • 2.3: Syntax of Formal Languages

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

        Study the slides.

    • 2.4: Semantics of Formal Languages

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

        Study slides 1 - 7. Note that these slides are associated with the lecture below.

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

        Watch this video from 12:12 to 15:00, where Professor Hilfinger talks about semantics.

    • Unit 2 Assessment

      • Unit 2 Assessment Quiz
        Receive a grade

        Please take this assessment to check your understanding of the materials presented in this unit.

        Notes:

        • There is no minimum required score to pass this assessment, and your score on this assessment will not factor into your overall course grade.
        • This assessment is designed to prepare you for the Final Exam that will determine your course grade. Upon submission of your assessment you will be provided with the correct answers and/or other feedback meant to help in your understanding of the topics being assessed.
        • You may attempt this assessment as many times as needed, whenever you would like.
Skip Activities
Activities
  • QuizQuizzes
  • Resources
Skip Recent activity
Recent activity
Activity since Sunday, February 5, 2023, 9:00 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