12-Week Exam Study Guide

Review Session

A review session will be held on Thursday evening, November 3, at 7:15pm in MI 223. This will be an undirected review, meaning that you should come prepared with what topics or problems you are unsure about.

Policies

The exam will be open-book. This includes not only the textbook but also any course notes, returned work, posted slides, or other printed materials. However, the use of any electronic device is prohibited.

New rule: Any study materials that are shared between multiple students must also be shared with the instructor.

Coverage

This exam is not cumulative (although the final will be). Coverage will be the material of Classes 11-17 and Labs 5-8.

For this exam, you should be able to:

Determine whether a grammar is SLR(0).
Draw a parse tree and AST for a given program in a specified language, with specified associativity and precedence rules.
Trace the execution of a program in a simple programming language, using any scoping and variable-passing rules we have discussed.
Scoping rules you might see are
- Dynamic
- Lexical (a.k.a. static)
Variable passing rules you might see are
- By value
- By reference
- By value/result
Besides the actual program behavior, the trace may also include:
- The function call stack (a.k.a. activation records).
- Global symbol table, Central reference table, or Lexical frames, as appropriate.
- A scope tree. (This isn't technically part of a trace, but anyway you should be able to draw one for a given program.)
Solve simple problems and create example programs to demonstrate your understanding of the scoping, allocation, and parameter-passing rules above.

You should also have a good understanding of:

The differences between parse trees and ASTs.
The trade-offs involved in dynamic versus lexical scoping.
The trade-offs involved in giving 1st/2nd/3rd class privileges to functions
The differences between all four parameter-passing modes (including pass by sharing).
How memory is allocated for local and global variables in different scoping/parameter passing/function privileges scenarios.
When declaration order is important for implementing scoping rules.
What overloading and subtype polymorphism are, what they require from the compiler/interpreter, and why they might be useful.

Finally, you should know the meaning of these terms, and be able to use them correctly in a meaningful discussion:

1st/2nd/3rd-class
Abstract Syntax Tree
Activation record
Allocation
Binding
Call site
Central Reference Table
Closure
Compile-time
Declaration order
Deep binding
Dynamic
Dynamic link
Forward declaration
Function call stack
Global
Heap (memory allocation)
LALR
Lexical frame
Lifetime
Local
Mutual recursion
Name
Name resolution
Nested function
Nested scope
Non-local reference
Overloading
Parse Tree
Polymorphism
Referencing environment
Run-time
Scope
Shallow binding
SLR
Stack (memory allocation)
Static
Static link
Symbol table
Syntactic sugar