Example Questions For Final Exam
Show how an operator precedence parser would parse the string (ex. A-(B/C-D)/E+F)
- Show the contents of the stacks at each step; produce a tree as output
Give one advantage and disadvantage of hashing as a method of symbol table organization
Consider the regular expression (a|b)b+b. What is the simplest regular expression that denotes the same language?
Give the allowable form of productions for a Regular grammar.
Consider the following grammar :
- S -> a S
- S -> S b
- S -> b
- What kind of grammar is this in the Chomsky hierarchy?
- What kind of language does it denote?
- Is there a simpler kind of grammar that denotes the same language? If so, give the grammar, if not, explain why not.
Briefly and clearly define the following terms : vocab
A robot moves on a square grid. The robot can go forward, turn left or turn right. Give a grammar to describe the language of all sequences of moves that leave the robot pointing in the same direction as when it started
What kind of grammar is the above(in the Chomsky hierarchy)?
Describe a kind of local optimization
Describe what it means for a subexpression to be (a) available (b) busy (c) killed
Describe sources of extra run-time overhead in (a) time and (b)space in an OOP language
Draw boxes around the following code to show the basic blocks:
n := k*2;
if n < j then write(‘less’) else begin k := k - 1; write(‘more’) end;
- Number the blocks and draw a flow graph; give the matrix form of the flow graph and its transitive closure
Give an advantage and a disadvantage for (a) call by reference (b) call by value
What are the most important things to optimize in a scientific program? Why?
Give three examples of computer architecture innovations that require compiler innovations to be effective
Briefly and clearly define the following terms: … 20 terms chosen from the vocabulary list on the study guide
Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools
UT Austin CS375: Compilers by G.Novak.