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)
page revision: 4, last edited: 29 Jul 2011 23:01