Skip to content

Mt1 rs

General Instructions

  • This is a take-home, open book exam.
  • You must do this exam by yourself (i.e., no collaboration with anyone).
  • You must type all solutions.
  • If you used any resources (e.g., online, books, lectures), you need to explicitly say so.
  • Solutions will be graded on correctness and clarity. Each problem has a relatively simple and straightforward solution. We might deduct points if your solution is far more complicated than necessary. Partial solutions will be graded for partial credit.

Preparation

  • To prepare for the exam, you on focus on reading the notes and reviewing the review sets.

  • Some Topics that I can think of (not a complete list):

    • General Things about Compilers
      • Compiler Stages
      • Inputs and outputs for each stage, how the outputs of one stage becomes the input of the other. Note that for most stages, the inputs are not just simply those from another stage. For example, the inputs to parsing is the output of the lexer (e.g., file.cl-lex), and the output of the Parser Generator (e.g., OcamlYacc), whose input is the CFG (e.g., file.mly). The inputs to the Static analyzer, in addition, to the AST, would be things like type inferrence rules.
    • RE, Automaton, CFG
      • RE and DFA
      • Relationships between DFA, NFA, CFG, AST
      • Know why DFA is not enough and we need CFG. Able to show some lagnuages that are not recognized by RE but with CFG.
      • Ambiguous grammar, what it is, how to fix, parse trees
      • Recursive Descent: how it works, its limitations
      • Left Recursion: what it is, how to fix