SLP11 Exam Topics

The oral exam of the SLP course (in its 2011 edition) is concerned with topics as described below.

Overall the exam is ideally structured as follows:

  • One 3rd of the time is spent on the discussion of your assignment solutions.
  • Another 3rd is concerned with conceptual questions; see the topics below.
  • The final 3rd is concerned with program comprehension; see indications below.

The following topics were extracted from the individual lectures.

Some topics are tagged with VIP to mean that Very Interested Persons (with a view on a top grade) must handle these topics.

  • Architectural model of a classical compiler
  • Reasons for separating lexer and parser
  • Key concepts: token, lexeme, regular language definition
  • Riddle: What is the computational complexity of a lexer? (VIP)
  • Basic, possibly non-deterministic stack-based top-down and bottom-up parsing
  • Grammar classes of LL(1), LL(k), LL(*), LL with backtracking with examples
  • First(1)/Follow(1) sets and their use for grammar-class restrictions
  • Elimination of left recursion (VIP)
  • Scheme of deriving recursive descent procedures from a grammar
  • Basic definition of attribute grammars (AG): attributes, semantic rules, …
  • Conversion of binary numbers to decimal numbers with AGs
  • Synthesized AGs including the application to the above-mentioned example
  • Informal description of a general, dynamic attribute evaluation algorithm (VIP)
  • Attribute grammar extensions: reference attributes, collection attributes
  • Simple program comprehension exercises with JastAdd examples
  • Pros and Cons of AGs vs. rewriting; see also Kiama (VIP)
  • Meaning and purpose of traversal primitives and strategies (as in Kiama, Stratego, etc.)
  • Classification of transformations (see Visser) including examples or scenarios
  • Pros and Cons of DSLs vs. GPPLs
  • Basic classification of DSLs (in particular: intern and extern)
  • API-based implementation of DSLs (in particular: chaining and fluency)
  • Key concepts of multi-stage programming: brackets, escape.
  • Illustrative examples of multi-stage programming (see exponentiation example)
  • Conversion of an interpreter into a partial evaluator; see this tutorial.
  • TXL approach to grammar programming (see redefines)
  • The notion of island grammars (VIP)
  • Local-to-global transformation (see, for example, TXL)
  • Global-to-local transformation (see, for example, TXL)
  • Goto elimination (TXL)
  • Backward slicing (TXL)
  • Intermediate code generation by translation to three-address code
  • Derivation of control-flow graph with basic blocks
  • Simple code generation with simple register allocation (VIP)