Midterm Exam Topics

The exam is open book and open notes and you are free to use a calculator or whatever other computing devices you feel may aid you.

General Programming Languages Questions

• Why there are so many languages
• Why study programming languages
• Imperative vs. Declarative languages
• Interpreted vs. Compiled languages
• Concept of the virtual machine
• Phases of compilation
  • Scanner (lexical analysis)
  • Parser (syntactic analysis)
  • Parser (semantic analysis)
  • Code generation
  • Code improvement
• Role of the symbol table

Syntax

• Expressing grammars using BNF format
  • Construct grammars to represent constructs (e.g. declaring identifiers)
  • Parsing a grammar with a parse tree
• Constructing and reading regular expressions
• How to deal with and fix ambiguous languages
• Lexical, Concrete and Abstract Syntax
  • Differences
  • Parse code using the above, e.g. show parsing a while loop into concrete and the resulting abstract syntax
• Difference between LL and LR grammar
  • LL(1), LL(2), etc.
• Constructing a recursive descent parser

Scoping, Binding, Types

• Activation Records or Stack Frame

  • Creation of local variables
  • Show state of stack when methods are invoked
  • What would be on the stack if parameters passed by reference, or passed by value
• Static vs. Dynamic scoping
• Type checking
  • strong vs. weak. vs static vs. dynamic typing
  • typemap with symbol table
  • type equivalence among structs or classes

Semantics

• Attribute Grammars
  • Be able to write one or follow along on an example to evaluate the attributes
  • Synthesized vs. inherited attributes
• Abstract Syntax
  • Writing the grammar for the abstract syntax of a language
  • Construction of an abstract syntax tree
  • Decorating of the tree or writing code to generate the abstract syntax tree
• Denotational Semantics
  • Be able to calculate the meaning of expressions, statements
  • Write denotational semantics for some new statement or programming language feature

Memory

• Allocating data from the Stack vs. Heap vs. Static memory
• Arrays
  • Layout in memory
  • Differences between C++ and Java
  • Formulas to access the correct element of an array in N dimensions
  • Row vs. Column major order
• Structures
  • Layout in memory
• Concept of pointers and references
• Garbage Collection
• Memory leaks, Dangling Pointer, Orphan, Widow
• Concept of the free list
• Reference counting
  • Show how reference counting works on an example
  • C++ Smart Pointers
  • Problem of circular links
• Mark Sweep
  • How it works
  • What we need to know in order to implement it
  • Advantages/Disadvantages compared to other algorithms
• Copy Collection
• How it works
• What we need to know in order to implement it
• Advantages/Disadvantages compared to other algorithms

  OOP and Dynamic Binding

• Static binding vs. Dynamic binding
• Virtual methods
• vtable to implement virtual methods