Sample midterm questions
The midterm format will be best 4 out of 5 questions, a mix of coding and essay/discussion
style questions, with an assumption that you spend roughly 20 minutes on each question.
There are 10 sample questions below, though they are still a bit unpolished.
While the actual midterm questions might vary quite a bit in terms of specific material,
these should give a good idea of the depth/style of question that's likely to appear.
- Explain how code optimizers are an example of metaprogramming, using one of the
optimizations below to illustrate your point:
- loop unwinding
- tail recursion optimisation (stack reuse)
- inlining function calls
- dead code elimination
- (i) Many code profilers work by inserting instructions to count how
often functions are called and from where. Explain how this does or does not constitute
metaprogramming.
(ii) Many web browsers allow you to examine a page's source code. Explain how this
does or does not constitute metaprogramming.
- In your own words, explain the role of the following in tools that analyze source code
(i) tokenizing
(ii) grammars
(iii) parse trees
- Suppose we wanted to add one of the following changes to the C programming language:
- allowing variable names to begin with a digit
- automatically checking array bounds on each element access
Pick one of the two, and discuss possible changes needed in the language's
regular expressions and grfammar rules, and the problems that would need to be
addressed in preprocessing and compilation to apply these changes.
- Update the Ruby code for the IttyBitty
tokenizer (original version appended to the exam)
to support all of the following changes:
- identifiers can now be alphanumeric with underscores, but the first character cannot be a digit
- post-increment (e.g. x++) and post-decrement (e.g. x--) will now be supported
- Update the Ruby code for the IttyBitty parser (original version appended to the exam)
to support the changes from question 5 above.
- Update the Ruby code for the IttyBitty translator (original version appended to the exam)
to support the changes from question 5 above.
- (i) Provide C macro(s) to enable the use of
aprint(arrayname, i, j, formatstr)
which prints array positions i through j (inclusive) using the format string provided, e.g.
aprint(arr, 3, 12, "%d")
(ii) Provide a constexpr C++ function quadroot(a,b,c)
to compute (-b + sqrt(b*b + 4*a*c))/(2*a), including a test for
divide by zero.
(EDIT: assume a constexpr sqrt function exists)
(iii) Provide a variadic C++ function checkBounds that takes lower and upper bounds as
its first two arguments, and returns true if all the remaining arguments fall within those
bounds (inclusive). Sample calls might be:
checkBounds('e', 'k', val1, val2, val3)
checkBounds(4.5, 23.7, x)
checkBounds(M, N, 1, 2, 3, 4, 5, 6, 7)
- The immediately-relevant C grammar rules for array indexing can be paraphrased as
POSTFIX --> POSTFIX '[' EXPRESSION ']'
POSTFIX --> PRIMARY
PRIMARY --> IDENTIFIER
PRIMARY --> STRINGLITERAL
PRIMARY --> CONSTANT
PRIMARY --> '(' EXPRESSION ')'
Under those rules alone, would the following appear to be legal array accesses?
"hello"[3.1*17.4]
(25*16-3.5)[3]
In practice, the compiler generates type errors for each (because of the non-integer
index in the first, and the double[int] format for the second).
Explain how the idea of "augmented grammar rules" comes into play in processing source code
containing arrays like those shown above.
- Suppose you worked for a compiler developer, working on language FOO,
and they asked you to write software that would automatically generate random valid FOO programs.
Outline how you could use the language grammar rules as a basis for your solution.