CS 421: Programming Languages and Compilers

Syllabus and Study Guide for the final

Studying for this exam


  • Understand the lecture slides and discussions thoroughly.
  • Revisit the MPs, MLs and HWs and make sure you understand the solutions thoroughly. Repeat any you are not comfortable with.
  • Take the sample exam as a dry-run for the actual exam.



The exam will cover all the lectures in the course. It is a comprehansive exam. Listed here are topics not previously listed in midterm1.syllabus.html or midterm2.syllabus.html. They include writing parsers in ocamlyacc, Natural Semantics and Transition Semantics, Lambda Calculus, Evaluation strategies (eager and lazy evaluation), and Axiomatic Semantics. The following give examples of the kinds of questions you are likely to be asked for each topic:

  • Parsers
    • Be able to write a simple parser in ocmalyacc by providing an unambiguous attribute grammar using a tokens type and a family of types for abstract syntax.
    • Know how Action and Goto tables are used to implement an LR parser (we did not cover, and you are not responsible for how to generate these tables from a grammar).
    • Know what shift/reduce and reduce/reduce conflicts are, why they happen, and how they can be resolved.
  • Operational Semantics
    • Be able to derive the proof tree for the evaluation of an expression in Natural semantics.
    • Be able to derive the proof tree for the evaluation of an expression in Transition semantics.
    • Be able to compare Natural and Transition semantics.
    • Understand the evaluation rules in both semantics, and be able to write evaluation rules for new syntactic constructs.
    • Be able to implement Natural and Transition semantics rules as OCaml programs.
  • Lambda Calculus (LC)
    • Be able to parse a lambda term correctly (e.g. which variable is bound by which abstraction, which variable is free, what the scope of an abstraction is, what the grouping of a series of applications is, which application is top-most, etc.)
    • Describe and know how to apply α-conversions, α-equivalence and β-reductions.
    • Know the differences between and be able to demonstrate lazy/eager evaluation and unrestricted alpha-beta reduction.
  • Axiomatic Semantics
    • Be able to prove simple statements in Floyd-Hoare Logic, similar to the example of if x < 0 then y:= y-x else y:= y+x {y=a+|x|} that was done in class.
    • Be able to prove a statement about a simple while loop, as in the definition of factorial.
    • Be able to derive new Floyd-Hoare logic rules for new programming-language constructs.