Exam Information

CS536-S24 Intro to PLs and Compilers

On this page: Midterm Exam 1 | Midterm Exam 2 | Final Exam

There are two midterm exams and one final exam worth a total of 60% of your grade. Midterm exam 1 is worth 18% of your grade, midterm exam 2 is worth 16% of your grade, and the final exam is worth 26% of your grade.

Exams are closed-book and consist of multiple-choice, short-answer,and written questions. The final will be cumulative but with the majority of the exam on the topics covered since the second midterm. You are responsible for material covered in the lectures, readings, and assignments. Note that some details may be covered in the readings but not in the lecture and vice versa.

Conflicts: Any exam conflicts must be brought to the instructor's attention during the three weeks of class (or as soon as you find out about it) by filling out this CS 536 Alternate Exam Request Form.

You MUST bring your student ID to identify yourself.

Midterm Exam 1

Thursday, February 29, 7:30 - 9 pm, S429 Chemistry

Topics

• Scanning
  • General: what does a scanner do; how does it fit into the design of a compiler?
  • Underlying model: finite-state machines (FSMs); deterministic vs. non-deterministics FSMs; translating regular expressions to NFAs, translating NFAs to DFAs
  • Specification of a scanner: regular expressions; JLex specifications (you do NOT need to know all of JLex's special characters)
  
  
• Context-Free Grammars: Specification of a language's syntax via a context-free grammar (CFG)
  • derivations (leftmost, rightmost)
  • parse trees
  • expression grammars (precedence, associativity)
  • list grammars
  • ambiguous grammars
  • recursive grammar (left recursive, right recursive)
  
  
• Syntax-Directed Translation: "plain" translations
  • writing rules of the form "S1.trans = ..."
  • being able to define translations of any types (integer, AST nodes, ...)
  
  
• You should be able to do the following:
  • Given an English description of a language, write the appropriate finite-state machine (FSM), regular expression (RE), or context-free grammar (CFG). For an expression language, the CFG's parse trees should correctly reflect the precedences and associativities of the operators.
  • Given an English definition of a language and a faulty FSM, RE, or CFG, find and fix the problems.
  • Given a CFG and a syntax-directed translation goal, define the translation rules. Given an input string, draw the parse tree and annotate each nonterminal in the tree with its translation.

Covers material from

Additional information

Midterm Exam 2

Thursday, March 21, 7:30 - 9 pm, S429 Chemistry

Topics

Covers material from

Additional information

Final Exam

Sunday, May 5, 2:45 - 4:45 pm, B102 Van Vleck

Topics

• Basic ideas of scanning and parsing
  • including, e.g., writing finite-state machines and/or regular expressions for tokens and writing a CFG for a language, but not including LL(1) parsing or CYK algorithm
  
  
• Symbol-Table Management
  • static scoping
    • scoping rules for Java vs base vs C/C++
    • identifying multiply declared names
    • matching uses to corresponding declarations
    • implementation: list of hashtables
      how the approach works, efficiency concerns, extending the approach to handle new language constructs
    
    
  • dynamic scoping
    • matching uses to corresponding declarations
  
  
• Type Checking
  • type checking base constructs
  • extensions to handle new constructs
  
  
• Runtime Storage Management

  • general storage layout (stack, heap, static data area)

  • activation records
    • what is in an activation record and why
    • manipulation of activation records on:
      • method call
      • method entry
      • method return
    
    
  • access to variables at runtime
    • for parameters, locals, globals
    • access links and displays to access non-local variables at runtime for languages with nested subprograms
  
  
• Parameter-Passing Modes
  • call-by-value
  • call-by-reference
  • call-by-value-result
  • call-by-name

  both from a language-design point of view, a programmer's point of view, and a compiler-writer's point of view

• Code Generation
  • generating code for base constructs
  • extensions to handle new constructs
  
  
• Optimization
  • goals (safety and profitability)
  • peephole optimizations
  • copy propagation
  • loop optimizations
    • moving loop-invariant computations out of the loop
    • strength reduction in for loops

Additional information