This is an old revision of the document!


CMPU-331 Compilers (Spring 2019)

Overview

The course has a single written examination. It focuses primarily on material from the textbook, though it will also touch on material covered in lectures.

The examination counts for 40% of your grade for the course.

Logistics

Schedule

The examination will be a take-home exam. It will be made available at the end of class on Thursday, 15th November, and will be collected at the beginning of class on Tuesday, 20th November.

Duration

The exam is intended to take between 3 and 4 hours to complete.

Reference Material

You may use:

  • The course textbook.
  • Any secondary reading material provided in class.
  • Class lecture slides.
  • Notes you have taken during lectures (hand-written or electronic).
  • Any solutions or working-out for homework assignments.
  • Notes from coaching hours or office hours.

You may not use:

  • The Internet. At all. (Surpriseā€¦)
  • Other textbooks besides the course textbook.
  • Your friends' exam paper.

Academic Integrity

This exam is provided as a take-home as I want to give you the best chance possible to do well. (This is also why there is no project work or homework scheduled for the week of the exam.)

Please don't cheat.

Examination Topics

This is a non-exhaustive but fairly comprehensive list of examination topics.

  1. Context-Free Grammars.
    • Ambiguity and how to resolve it.
    • Left recursion:
      • Why it causes a problem for top-down parsing.
      • How to resolve these problems.
    • Left factoring.
    • Leftmost and rightmost derivations.
    • Parse trees and derivations.
    • Programming language constructs which are not context-free (e.g. variable declaration, type constraints), and why.
  2. Syntax-Directed Translation.
    • Attribute grammars.
    • Syntax-directed definitions.
    • Synthesised vs inherited attributes.
    • Use of synthesised and inherited attributes.
    • Translation schemas.
    • Relations between DFS and translations.
    • Forms of output from translation (e.g. intermediate code, AST).
  3. Lexical Analysis.
    • Creating a DFA from a description.
    • Relevance of token types to input.
  4. Parsing.
    • Abstract syntax tree (AST) vs parse tree.
    • Use of AST in semantic analysis.
    • Top-down vs bottom-up.
    • Definitions of LL, LR, SLR, LALR and what they mean.
  5. Top-Down Parsing and LL(k) Grammars.
    • General notion of the top-down parsing algorithm.
    • Relation between grammar and contents of the parse stack.
    • Relation between a left-most derivation and top-down parse (including moves and stack contents).
    • LL grammars:
      • What makes a grammar not LL(1)?
      • Is a certain grammar not LL(1) but LL(2), etc.?
    • Construction of FIRST and FOLLOW sets for a grammar.
    • Construction of LL(1) parsing table.
  6. Bottom-up parsing and LR(k) Grammars.
    • General notion of reduction process, including use of handles.
    • LR grammars:
      • Is a grammar an LR(0), LR(1), etc. grammar?
      • Is a grammar not LL(1) but LR(1)?
      • Relation between right-most derivation and bottom-up parse (including moves and stack contents).
    • LR parsing:
      • LR parsing (shift-reduce) algorithm.
      • Conflicts in parse table (shift-reduce, reduce-reduce) and how to correct them.
      • Construction of SLR parsing tables:
        • Constructing sets of LR(0) items.
        • Relation between sets of LR(0) items and DFA used for the parse.
        • Constructing the parse table from the sets of items
      • Constructing LR(1) parsing tables:
      • What is different from SLR method?
      • What problem does this solve in SLR? How does it solve the problem?
      • Can a grammar be parsed using LR method but not SLR?
      • Constructing the parse table from the sets of items.
    • LALR parsing:
      • Constructing item sets for LALR(1).
      • Difference between LALR and SLR, LR(1).
      • Constructing the parse table from the sets of items.

Sample Papers