Example Questions For Final Exam


From Midterm!

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

Other Questions

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.