Introductory remarks

I have been asked, how about a list of (typical) exam questions? I always said, the list of possible questions is basically known, as for every concept or definition in the pensum, there could be a question. So since there is one or a couple of slides about ambiguity, so there could be a question "what's ambiguity?" or "tell me about ambiguity!". I call that here a bland question. For every concept (like ambiguity) covered in the lecture, there could be a bland question ``what's XXX/tell me about XXX'' or similar. There can be also not so bland questions in connection with that, like ``is an ambiguous grammar LR-parsable?'' ``why are ambiguous grammars not good for parsing'', etc.

I always had a list of questions, basically for myself, making the exam more smooth or structured. Of course, in principle I know basically all topics, but it may take time to remember all aspects that has been discussed, so in a concrete exam situation, I should not waste time to collect my thoughts (maybe while listening to an answer) to figure out what to ask next.

What this list is not!

This is meant to give an impression of possible questions. Most importantly it's not complete, i.e. just because a question (or a topic) is not listed here does not mean it's not pensum or cannot be asked.

Then of course the questions as listed here are "unnaturally sterile" and "isolated", or bland as I called it. In a concrete exam, (depending on the candidate), it's mostly a dialogue, with follow-ups etc. While some of the questions may be asked in bland form What is a context-free grammar?, there are many different ways to shape an answer (give the definition, give an example, explain why it's context free and what role they play for parsing etc.) Depending on the reaction and the response to the bland question, there would be a follow up question, but typically it might not be just picking up a random bland question from the same section of the material, but reacting on the given response. So questions can range from a bland what is BNF? ``can you say a bit more about the example you are given'' (if for instance an example is offered by the candidate but without much words, and one likes to check if the example is just learned by heart, or understood).

Of course I will not include situational questions like "can you explain your example in more detail" in the list of possible questions here, though they might be common.

The bland questions, as I called them, is basically the list of concepts. As mentioned, I (as examiner) use them basically as aide-m¨¦moire during the exam, it's basically nothing more as a list of keywords, or in index of concepts from the lecture or script.

Variations

The list of questions is (and cannot) be complete for all (non-bland) variations that could be asked. I cannot think of all variations (some are maybe situational), but if there is a concept like "liveness", then variations of that concept are

Many concepts can have such variations (or more), they are in that sense generic. However, specific concepts may have variations that only make sense for that. For instance, maybe for some concepts (like first and follow sets), we have not discussed variations (as for liveness). Related to that, some "variation" or follow-ups to some concept make sense only for that concept. For liveness we could ask "liveness analysis: is it a backward or forward analysis". There exists also analyses for which that would make sense to ask it, but we did not discuss or presented that in the lecture. In the list of questions sometimes there are those follow ups as concrete questions, but also there, the possibility of variations is endless, so it's not complete also in that respect (even if all topics were at least touched upon).

General (in particular intro chapter)

Warm-up and intro

• What's a compiler?

• front-end back end? explain

• What are phases, name them (best in a structured way and mention short what kind of formats they operate on/use as input and output.

• Which phases did you do in your oblig?

• What's the difference between a (full) compiler and an interpreter?

• optimizations: what is that in a compiler, where can one do "optimization" is there an "optimal" compiler? In which phases is there optimization

• what's a preprocessor?

• what are intermediate representations in general, name a few, place them in a compiler

  ¡­

Not asked, not pensum

• T-diagrams, bootstrapping,

Scanning

Warm up

• what's scanning?

• what's lexing, a lexer

• place it in the phases of a compiler,

• what's scanning? what are "lexical aspects"?

• what's the input and the output of a scanner

• what tool(s) exists / what did you use in the oblig?

-..

Regex

• let's go to reg-languages: for a starts: what's a language in that context?

• what's an alphabet? what's an ordered alphabet? What's the deal with ordered alphabets?

• which aspects of a language are covered by a scanner

• which not?

• on which theory does scanner typically build upon?, what is the theoretical basis?

• can one have nested comments?

• what's the "interface" between a scanner and a parser (data structure)

• what's a lexeme and a token and token value? can you give examples?

• A scanner's task is classification: given a concrete language (like Java): what would be typical "classes" or syntactical categories (or token) for a lexer

Regular expressions/language

• Define RE then, what is it (regular language, regular expressions) what role do they play in a scanner?

• give an example of a language that is not RE?

• Define Regexp, using the words "language, alphabet", what is the alphabet of a typical language like C or Java etc.

• is the language of "regular expressions" a regular language?

• What are the limits of regex? Give an example of a language which is not regular? or tell

• Example: make regular expressions capturing "numbers", "Signed numbers" or identifiers [not so good in Zoom]

Finite state automata questions

• define an FSA? What's the alphabet of an FSA? what is the language of a FSA

• what is the role of an FSA in a compiler?

• determinism (DFA vs NFA)

• how does it relate?

• what's Thompson's algo

• Sketch the steps what to do when one has the following task: given a regular expression -> give a deterministic FSA?

• Motivation for NFA: how would you implement a FSA/DFA?

• What is better to implement, a DFA or an FSA? Why does one bother about FSA at all? [There as slides about: why to introduce FSA at all]

  (because of the transfer from regex -> DFA)

• What are extended reg-exprs? Name some extensions (syntactic sugar

What is Thompson's construction?

• where is it used?

• sketch some cases (or make an example)

• compositionality

Subset construction?

• where is it used, what role does it play

• why does one need it?

• what does it mean for an automaton or similar to be deterministic

• Bonus: can one apply the subset construction also on, let's say, a push-down automaton?

• doing subset, does it get bigger or smaller?

DFA vs. reg?

• what are reg-expressions

• define the syntax of regexps

• what do they mean? what do they represent, their semantics?

• what's the ``language'' of a reg-expression

Do some things from exercise [regexp]

• a (b | c)* or similar

Minimization

• what's a minimal automaton?
• why is that important,
• what's more important, minimization or determinization?
• How did we minimize automata, can you sketch how it works
• here's an automaton, is it minimal?

Grammars

Intro

• what is the purpose of a parser, what is it's place in the compiler, what is the input and output of a parser

• what's terminals/non-terminals, connect that to tokens?

• what's a context free grammar, how does one write them down?

• BNF

• [can you give or sketch a language which is not context free]

• what subclasses of CFGs did we discuss. Explain more

• what's a derivation?

• derivation: left-most, right-most

General: trees

• trees play a big role: which "kind of" trees were mentioned in connection in CFG and parsing?

• difference between a parse tree and an abstract syntax tree.

• how did your group implement ASTs in the oblig, how do you implement ASTs in, say Java.

Grammars

• What's a CFG grammar?

• what's the relationship to regular expressions?

• properties of CFGs

  • ambiguity
  • left-recursive, right-recursive ¡­

• normally, one does not work with CFG in their generality

  • why is that?
  • which kind of restrictions did we discuss?
  • what to do about them?

• Some of the properties are not nice (ambiguity, left-recursion) for parsing: why and which context is that and what do do about it?

• give an example of a grammar for expressions.

• Discuss notions of associativity and precedence on it

First and Follow sets

• What are the first set and the follow set intuitively defined?

• What are they used for? for top-down and bottom up?

• what is nullable?

• we discussed nullable in connection with F&F, why is that relevant

• here is the definition, explain

• here is the definition without nullable symbols, what needs to be changed if we want to deal

Example: expression

• make an grammar [not in zoom]

Ambiguity

Parsers

"defects" in grammars (for

• name a few?

Removing left-recursion

• what's Left-Rec?

• where is it a problem?

• what can one do about it?

• is it always possible to remove it?

• if one removes LR, that may be problematic resp. has unwanted consequences, what are those?

• we discussed that removing LR may change associativity? Is that problematic What can one do about it, what is associativity anyway

left-factoring

• what is a common left factor
• what is the problem with that
• what can one do about that
• common left factors

Top down vs. bottom up parsers

• there are main two flavors of parsers, name them, explain one of them

• why are those to things called top-down and bottom-up parser? sketch the differences? which one is better? for a given look-ahead

• what's a look-ahead? Can one work without look-ahead?

• What's LR(1)/ll(1)

• can you give a grammar which is bottom-up parsable but not top-down (with say LL(1) and LR(1)

• name the different classes of bottom-up parsers we sketched, hierarchy?

• what's a parser table?

• what's a conflict? (in connection with a table)

• what

Top-Down parsing

• what is LL(x)-grammars/LL(1) parsing?
• what's the abbrev, what's the LL(1) parsing principle?
• How can one implement an LL(1) parser?
• what's is a problematic aspects for LL(1)?
• are epsilons/nullable symbols problematic for parsing? no and yes

LR(1) parsing construction

• what's LR parsing, LR(1) parsing?

• what's an LR(0) item, what's the LR(0)-DFA?

• sketch in words the overall construction

• do S -> a S b | eps make the LR(0)-DFA

• what role does the LR(0) (or similar) DFA play for parsing?

• epsilon closure

LR-parser machine

• what the configuration/state of such a machine,

• what determines the state of such a machine

• which steps can such a machine do?

• what determines what steps (shift/ reduce)

• parser table, what's a run

• describe a shift-step, and a reduce step.

• when does an LR-machine accept?

Example: construct the LR(0) DFA

S -> (S) S | eps E -> E + num | num

conflicts in LR(0)

• Look at some print out/example

• how to define/find such conflicts?

• SLR 1 parsing table for that one

  accept?

  LR(1)

Not part of the questions

• syntax diagrams

A-Grammars

• what's an attribute grammar?

• where did we use attribute grammars for, examples

• what's the format of an entry in an attribute grammar, what's a semantic rule (production, semantic rule)

• maybe sketch an attribute grammar for

  • what are attributes, what are synthesized and inherited attributes

  • does an attribute grammar always ``make sense''?

  • What are conditions that make a attribute grammar definition meaninless?

  • What's a dependency graph in the context of Agrammars?, what condition must a dependency graph have.

  • what does it mean to be acyclic?

    • Transfer (but I mentioned in the class and in exercises sheets also shows up in writing): Is it necessary for an AG that the underlying grammar is unambiguous,

  • what is a typical application of attribute grammars in programming language

  • what are typical ``applications'' of synthesized and inherited att's (type declaration and

  • give an example for calculating value of an expression

Symbol tables

• what's a symbol table?

• what's a hash-table

• what's the "interface" for a symbol table, typical "methods"

• what's a scope, what's lexical scope

• how to deal with nested blocks in ST?, we had (sketched) 2 ways

• what are static links, especially in connection with symbol tables

• how are scoping rules/lexical scoping reflected in STs?

• what's a typical way/data structure to implement a symbol table

• what's a hash-table?

• how can hash-tables implement ST?

• we had discussed also an alternative to STs, what is that

• collateral/simultaneous vs sequential declarations?

• what's the "problem" with recursive definitions? "prototypes"

• what's the difference between static vs. dynamic binding, what is more common

• what's binding anyway?

• what's overloading (or maybe ask in connection with types)

• explain the AG for STs

Types

• what's a type?, what are different ``aspects'' of types?

• why did we say early on that types are a central abstraction

• what types are there

• name examples of common basic types and compound types

• what are abstract data types.

• what's encapsulation?

• what are type constructors? examples

• how can one construct new types from old ones

• arrays, records, structs, tuples/product types¡­

• (1, (2, 3)) vs (1, 2, 3)

• Union types: weakness, what has been proposed to improve it`. what's the ultimate purpose of union types and more modern adaptations?

• what types for "alternatives" (like a real or an integer)

• variant records?

• recursive and inductive types? what's pattern matching.

• how are pointers or references represented as types

• what's a function signature

• whats the difference between n-tuple and a list of n elements?

• what role do types and type systems play.

• discuss classes (and or interfaces) as in Java and types

• shadowing

• what's polymorphism

• when are two types equal? discuss alternatives

• what's nominal vs. structural typing?

• equality checking: what's more complex, nominal or structural?, why

• duck typing

• how to represent types in the AST

• what are type aliases

• what is type checking

• explain the AG for type checking/or the type system (derivation rules)

RTE

• what's a run-time environment?

• what's scoping in a language, what especially static scoping? what has it to do with RTE

• how do "features" of a language (like function definitions and scoping) influence the compiler's RTE? Name examples, when does one need a stack and why

  [full static layout -> stack based, fully dynamic RTE

• what is an "activation record" or "stack frame"

• explain: stack pointer, frame pointer, dynamic link/control link, access link/static link

• what's typically stored in an AR, how is it influenced by the language

• what's an AR/stack frame, what's a

• when are activation records allocated on the stack resp. on the heap, explain

• what is the problem of local procedure declarations (and procedure variables)

• what's a closure?

• what's a static link in the context of RTE

• what's a calling sequence? (also calling conventions) sketch some steps.

• what's access chaining

• What are virtual methods, and how can they be represented in the RTE

• what's late binding? overriding, shadowing

• what's a virtual function table.

Parameter passing

• name different parameter passing methods (CBV, CBR, CBN, CBVR)
• what's the scheme in Java or C and similar language
• "we" presented CBN as partly "problematic". Explain, under which circumstances it's not a good idea

Garbage collection

• what's that?
• what is dynamic and static memory
• how can the compiler manage (dynamic) memory

ICode-gen

• what is intermediate code, what IR in general.

• motivation? why not directly code generation?

• what flavors of ic did we have?

• why is it called 3 address code?

• what's characteristic for 3 address code?

• how is control flow dealt with in IC, what's control flow anyway

• what's the difference between IC and code (for instance in our lecture) (platform dependent, symbolic labels)

• what's linear intermediate code? what's characteristic

• how are conditionals and loops translated from ast to intermediate code

• explain code snippets

3AIC

• what are temporaries and labels?
• sketch (not the "algo") the translation of x + (y * z), 2 * a + (b -3) or similar
• labels and pseudo-instructions,
• can you see a connection between the ast and temps?
• how to represent IC instruction (quadruple?)

P-code

• another name for p-code, why

• name typical commands

• explain the difference between sto/stn (store, and store non-destructive) what for

• try to translate x := y * 2 (lda, ldo)

• L-value, R-value

Generating p-code

• can you characterize the generation of p-code as procedure (tree(

Generating 3AIC

• can you characterize the generation of 3AIC as procedure

from p-code to 3AIC and back

• which direction is simpler (or at least we described a version where it was simpler (3AIC to p-code)

• what's macro expansion and static simulation? can you sketch the macro expansion of say t1 := x +3

More complex data type

• we had focused on control flow and single lines, but ignored complications like more complex data types. what's types

• how to do array access (indexed, indirect, maybe scaling)

• what are address modes? , what's indirect?

• IC is platform independent, how to make array access independent from the platform? (sizeof(int))

• array access in 3AIC (2 new instructions, or ``simulate*

• when having address modes, how is that reflected in the code generation?

• access to records, how is that done?

Control statements and logical expressions

• what's the code idea, what needs to be added to code generation (label)

• explain the code

• what's short circuiting?

• what's fall through?

• how to translate if a < b then xxxx else xxx

• sketch the idea to code generation genCode to deal with conditionals and control structures for breaks

Code generation

Intro

• what's the difference(s) between ICode and code, and the "distribution of responsibilities"
• what's one code issue of code generation, concerning efficient code
• what are descriptors resp descriptor table, whats address descriptors and register descriptor tables?
• does one need both
• we discussed book-keeping data structures in code generation, what are those, explain?
• what's a cost model, what
• explain the cost model.
• What are addressing modes

CFG

• what's that
• how to determine the CFG
• ..

Liveness analysis

• what's liveness?
• what's liveness analysis
• we had "extensions" of LA, name them, explain
• where did it play a role?
• how does LA connect to register use
• how is it done?
• what's next-use
• what's a dependence graph, how does it relate to LA? DAG?
• what could a dependence graph be useful?
• what's global LA, what's local
• [SSA]
• how does the local analysis work?
• what complications are in the global one, compared to local?
• sketch the algo for the global one
• explain the global one on a pic
• we treated variables and temps different in local LA, explain
• what does it mean (for the compiler) that a register is free?