CS304: Compilers

Unit 2: Formal Languages and Formal Grammar

• 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

    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.