CS 331 Spring 2009
Notes on the Final Exam

Final Exam Information

The Final Exam will be given on Wednesday, May 6, 1–3 p.m., in the classroom. It will be worth 100 points. The exam will be comprehensive, emphasizing the material covered after the Midterm Exam.

Referring to books, electronic devices, or other people during the exam will not be permitted. Limited use of notes will be permitted; see below.

Bringing Notes to the Final

Students will be allowed to bring one sheet of handwritten notes to the Final Exam. Notes brought to the final must conform to the following guidelines, which will be ruthlessly enforced.

1. You may bring no more than one sheet of notes; both the front and the back may be used.
2. Notes must be on paper no larger than standard notebook paper (U.S. letter [8.5" x 11"], U.S. Legal [8.5" x 14"], or ISO A4 [210 mm x 297 mm])
3. Notes must be handwritten. In particular, the following are prohibited: photocopies (including photocopies of handwriting), computer-printed pages, pages from books, typewritten notes, photographs.

Topics

Here are the notes I wrote myself for the semester review I did in class on Monday, May 4. Topics earlier in the class are given in more detail (as a memory aid).

• Evaluating languages.
  • Remember “orthogonality”, etc.
• Describing syntax.
  • Chomsky hierarchy (regular language, context-free language, recursively enumerable language).
  • Recognizer vs. generator.
  • Grammars (terminal, nonterminal, derivation, leftmost & rightmost derivation).
  • Parse tree, ambiguity, precedence & associativity w/ grammars
  • BNF
• Static semantics: attribute grammars
• Dynamic semantics
  • Operational semantics:
    • Express high-level lang in low-level lang.
  • Axiomatic semantics
    • Here is what the program is supposed to do; prove that it does that.
    • Start at end & work backwards using weakest preconditions.
  • Denotational semantics
    • Represent program state mathematically.
    • Actions are transformations of state.
• Lexical analysis.
• Syntax analysis (parsing).
  • Top down (LL, recursive-descent).
  • Bottom up (LR).
• Haskell Language. Some important concepts:
  • Pure functional language.
  • Side effect.
  • Strong typing.
  • Static typing.
  • Implicit typing.
  • First-class functions.
  • Lazy evaluation.
  • Currying.
  • High-level list operations & list comprehensions.
  • Monadic I/O.
  • Significant indentation.
• Names in Programming Languages.
• Python Language Some important concepts:
  • Scripting language.
  • Dynamic typing.
  • Generator expression.
• Expressions in Programming Languages.
• Forth Language. Some important concepts:
  • Concatenative language.
  • Stack-based language.
  • Reflective language.
• Logic programming.
• Prolog Language.

CS 331 Spring 2009: Notes on the Final Exam / Updated: 5 May 2009 / Glenn G. Chappell / ffggc@uaf.edu