This is intended to give you a sense of what I think is important from the course so far, and what I will be thinking of when creating the exam.
I hate disclaimers, but here are some anyway. This is not a contract. I may have inadvertently left something off this list that ends up in an exam question. I make no guarantees that the exam will be 100% limited to items listed below. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some subset of it.
You are permitted one 8.5 x 11 sheet of paper with notes (both sides) for use as a reference during the exam.
Here are the specifics.
Regarding the interpreter project: Be able to answer questions about what we did at each stage, and why we did it. Be able to write variations of aspects of the project by writing C code, modifying provided C code, or describing what your technique might be. Specifically, be able to do the above regarding questions about and/or variations on:
Be able to motivate what purpose BNF serves. Be able to precisely produce BNF to describe a language that I describe in words and/or examples, as well as use derivations in order to show if a particular "sentence" is valid in a particular language. Be able to draw parse trees, and be able to demonstrate whether or not a particular grammar is ambiguous. Be able to discuss the merits of different parse trees that describe the same sentence from the perspective of which is more desirable for a compiler or interpreter to work with.
Be able to explain what an LL(1) grammar is. For a simple grammar, assess whether or not it is LL(1). Distinguish recursive descent parsing from the kind of parsing that we did for our Racket interpreter.Be able to produce FIRST, FOLLOW, and PREDICT sets for a particular grammar. Be able to demonstrate how this information would be used in coding a parser.
Explain and answer questions regarding how to manage free memory; specifically, buddy system techniques such as binary and fibonacci.
Define, explain, compare, and contrast dangling pointer strategies such as tombstones and locks-and-keys; and garbage collection techniques, such as reference counters, mark and sweep (including tri-color marking), stop and copy, and generational approaches.
Be able to distinguish static, stack, and heap memory storage. For a known language (Racket, Python, C), be able to identify whether a particular language characteristic relates to data stored statically, in a stack, or in a heap.
Be able to distinguish between static and dynamic scoping, and be able to evaluate trade-offs. Similarly, be able to distinguish between shallow and deep binding.
Evaluate the results of pseudocode using different parameter passing methods, including pass by value, by reference, by sharing, by value-result, and by name. Be able to explain how they are implemented underneath, and be able to answer questions that demonstrate knowledge of this.
Be able to identify, describe, and/or define various forms of polymorphism, and use or interpret appropriately. (This will be covered in class either on Friday or on Monday.) Types of polymorphism include: