Solutions to previous exams

TODO (Questions)

• What are dispatch vectors?
• What are right/left-sentinal?
• How do strongly typed and statically typed languages relate?
• In a CFG, what does it mean to dominate?
• What is a partial order?
• What is left factoring and left recursion elimination?
• What is a recursive descent parser?
• What is SLR and LALR(k) and how do they differ from LR(k)?
• What is the meet-over-paths solution of data flow equations?
• What is a interference graph?
• What is a live variable?
• What are L-attributed and S-attributed definitions?

True /False

2010

1. True. LR parsing produces a rightmost derivation, and LL parsing produces a leftmost derivation.
2. TODO: Interfaces (as in Java) specify a dispatch vector layout.
3. True. To be "x" grammar, it must be "x" (unambigously) parseable.
4. False. The regex language in not regular, it needs to be able to count parenthesis.
5. False. Caches.
6. True. The type system may be too strict.
7. False. TAC is an IR.
8. False. Reaching definitions is a forward analysis.
9. True. One must create a parsing table that includes all permutations of the lookahead symbols.
10. TODO: The handle of a right-sentential form is also called a viable prefix.
11. WRONG: Reduce/reduce conflicts can commonly be resolved by adding precedence rules to the parsing scheme.
12. False. One may have run-time strong type checking.
13. TODO: In a control flow graph, the condition of a loop dominates its body.
14. True. The language of context free languages mainly need to support recursion, which is supported by a context free grammar.
15. TODO: Every pair of elements in a partial order must be comparable by the ordering relation.
16. False. There is no automatic cleanup of heap allocation. (But a garbage collector could do something like this.)
17. TODO: Left factoring a grammar reduces the number of lookahead symbols required to parse it predictively.
18. False. It knows what token to expect, not what lexemes.
19. What?: With short-circuit evaluation, binary boolean operators can translate into jumps.
20. True. LALR(k) makes some assumptions that that the general LR(k) does not.

2011

1. False. The type checking may be too strict.
2. False. Not all languages are context free.
3. True. LALR(k) is a simplification of LR(k)
4. TODO: The meet-over-paths solution to a set of dataflow equations is always at least as precise as the maximal fixed point solution
5. False. A connection in an interference graph indicates that they cannot share a register.
6. True. Deterministic finite automatons are a subset of the nondeterministic.
7. True. A token, e.g. digit, may correspond to multiple lexemees, e.g. 0-9.
8. False. Something that is loop-invariant can be moved out without altering the semantics because it does not depend on (is invariant to) the loop.
9. WRONG. Given enough lookahead symbols k, a grammar with left-recursive productions may be LL(k) parsable.
10. False.

2016

1. True. Regular languages are a subset of context-free languages.
2. False. There exists nonambigous grammars with left-recursive productions.
3. WRONG. A top-down parser will always insert the last node of the syntax tree at the end of parsing.
4. False. LALR(0) admits a smaller class of grammars than LR(1) parsing.
5. False. A compiler usually does not ensure semantic correctness (as it is very difficult).
6. False. E.g. C is statically typed but not type-safe.
7. False. A function with side-effects will not necessarily be loop-invariant even if its arguments are.
8. True.
9. False. A live variable may be stored in other places than registers.
10. True.

2017

1. WRONG: All finite languages are regular languages. (Can you not for example construct a finite context-sensitive language?)
2. False. The grammar must be left-factorable.
3. False. A static type system does not ensure type safety (e.g. C)
4. False. TAC assumes infinite registers.
5. TODO: L-attributed definitions admit synthesized attributes (True)
6. True. The LALR(1) parsing table is equal or smaller than the associated LR(1) table.
7. False. A DAG representation of an expression may be tiled in multiple ways. (It is only a partial order?)
8. False. Common subexpression elimination may speed up the run time.
9. False. Two different regexes may match the same language.
10. True. interference graph connects variables which are simultaneously live.

2018

1. True. When the grammar is unambiguous, there only exists one syntax tree which both derivations will find.
2. False. Left-recursiveness is mainly an issue when it comes to LL parsing.
3. WRONG. LL(1) parsers need both a nonterminal and a terminal symbol to select a production
4. True. Function inlining often increases program size.
5. False. Construction of a DFA from NFA often results in redundant states.
6. False?. S-attribution allows
7. False. TAC may have less than 3 operands.
8. TODO: The maximal fixed point (MFP) solution to a data flow equation is at least as precise as the Meet-Over-Paths (MOP) solution
9. True. A->B and A->C. Then B and C have the same immediate dominator (A).
10. False. Compiled languages may have dynamic type checking.

In total: 5 WRONGs and 8 TODOs. (47/60 correct)