CSE 401

Fall 2001

Robert Henry

MIdterm (with terms updated for 2014)

  1. 10pt What is the difference between compile time and run time?
  2. 10pt What is the difference between the analysis part of the compiler and the synthesis part of the compiler?
  3. 15pt What are some features a compiler should have if it is to be used to compile programs that control a nuclear reactor?
  4. 10pt Randy and Kurt are on a programming team for the MJ project.  They choose not to use a source control system (git, svn, cvs, mercurial, …) to manage their software, but instead have separate copies of their development work, and promise to merge the software sometime later  What kinds of problems might they encounter as the quarter progresses?
  5. 10pt What are the advantages and disadvantages of encoding restrictions on language use into the syntactic structure of the grammar?
  6. 10pt Consider the standard recursive descent parser implementation of the standard EBNF specification of this expression grammar:
  1. 15pt Consider the following productions in a grammar where S, A, B, D, E are non terminals, and a, b, x, y are terminals. What is the signature set for the two productions for A, assuming we are using an LL(2) parser?  (Hint: generalize the signature set to map productions to sets of strings of length 2)
  1. 10pt Describe the role that an itemset has in the construction step of an LR parser.
  2. 10pt Write a context free grammar, expressed either in EBNF or in BNF, that describes Lisp S-expressions  To refresh your memory, there are no keywords in Lisp, merely tokens and matching parentheses.  Here are some examples: ()  (a b c (q r s)) (foobar ()) (if (eq a b) (set q 14) (list w x))
  3. 10pt What benefits might an algorithm that makes decisions as late as possible (lazily) have over a different algorithm for the same problem that chooses to make decisions early on?
  4. 10pt What is the difference between an inherited attributed and a synthesized attribute?
  5. 10pt Describe some of the problems a compiler writer might have when the programming language she is implementing is specified informally using English and examples.
  6. 15pt The main implementer of LEX (the intellectual antecedent to jflex) once told me that while LEX was an interesting and useful tool, any good computer scientist should not use LEX and should instead write a scanner by hand in the implementation language of choice.  Construct an argument that supports what he said.  Then construct a counter argument to what he said.
  7. 20pt  Suppose we change mini-Java so that identifiers and integer constants can have spaces (Or space equivalents) in the identifier or constant.  (Some people believe this enhances readability.) Keywords can not have spaces in them.  For example, a statement might be written as: return 17 000 * some variable which should be interpreted as: return 17000 * somevariable  Describe the modifications you would make to the existing MiniJava compiler to support this change.
  8. (specific to the 2001 project, not relevant in 2011)