File TakeHomeFinal.html    Authors McKeeman    Copyright © 2007

Take Home Final for 10-Lecture Course

X

  1. Where does the basic design for X come from?
  2. Write and run a short X program to compute the average of two real numbers.
  3. Write and run another short X program to test the first program.
  4. What are the primitive concepts of X?
  5. What common programming language primitives are omitted?
  6. Describe the X subprogram call.

Grammars

  1. Define the term Context-free Grammar.
  2. Write a CFG to describe exact change for a dime.
  3. Repeat the problem, using a different grammar notation
  4. Repeat the problem, using a different grammar notation
  5. Define the term Finite Automaton in terms of a CFG.
  6. Write a FA grammar for change for a dime.
  7. Describe briefly how a CFG determines order of expression evaluation.

Lexing

  1. Describe the concept of a lexeme.
  2. Describe the concept of a token.
  3. There is an argument that implies doing all the lexing before using any of the tokens is efficient. What is the argument?

Parsing

  1. What are the roles of the CFG and IOG in parser construction?
  2. Describe the process of deriving the IOG from the CFG.
  3. The bottom-up parser does not need the IOG. Why?
  4. What is the output of the parser?

Trees

  1. How is the tree built?
  2. Describe the difference between a syntax tree and an AST.
  3. Using X.cfg, write down a syntax tree for "x:=1"
  4. Using X.cfg, write down an AST for "x:=a*2-2/b"
  5. The trees in xcom are read-only. Why might one like them to be writable?

Symbols

  1. What is the purpose of the compiler symbol table?
  2. What are the methods of the symbol table object?
  3. What is the relation between the symbol table and run-time frame?
  4. What error will the X program "x:=y" give?
  5. What error will the X program "x:=rand+1" give?

Generator

  1. What is the purpose of the generator?
  2. How does it work?

Emitter

  1. What is the purpose of the emitter?

Assembler

  1. What is the purpose of the assembler?
  2. Using the mnemonics of xcom, describe the following instructions as a state change on the CPU.
    1. addRR EAX,ECX
    2. faddp
    3. movMR x,EAX
    4. movRM EAX,y
    5. bge n

Emulator

  1. What is the purpose of the emulator?
  2. The emulator can step ahead and back any number of steps. How is this done?

Optimization

  1. What is the "as if" rule?
  2. Give an example of constant folding.
  3. Give an example common subexpression elimination.
  4. Give an example of hoisting.
  5. Why is the X code i := r2i(z); j := i+1; likely to lead to a successful peephole optimization?

Runtime

  1. What is the purpose of the runtime?
  2. Describe the run-time frame:
    1. as a place to keep three types of X variables
    2. in relation to input and output
    3. in relation to subprogram linkage