Computer Science 5220
Spring 2002
Exam 2

Instructions. Answer all of the questions. For the multiple-choice questions, circle the letter of the best answer, even if no answer is ideal.

1. How would a live variable analysis be useful in generating good quality executable code?
   1. It can help to avoid generating instructions to store some values from registers into memory.
   2. It allows you to use more registers to hold temporary values.
   3. A live variable analysis makes it unnecessary to perform a control flow analysis.
   4. A live variable analysis is useful in finding places where variables might be used before they are defined.

2. Which of the following would be least likely to be stored in the symbol table of a compiler?
   1. The type of an identifier.
   2. The location where an identifier will be stored.
   3. The type of a complex expression.
   4. The number of bytes required for a particular, named type.

3. Some compilers work by building data structures called syntax trees that describe relevant information about a component of a program, such as an expression or statement. A syntax tree
   1. is almost always identical in structure to a parse tree.
   2. often differs substantially from a parse tree.
   3. is not stored explicitly in the memory, but is traversed implicitly during the parsing process.
   4. is usually considered an inefficient way to perform translations, and should be avoided.

4. Inherited attributes are difficult to use in a bottom-up parser because
   1. The parser cannot handle ambiguous grammars.
   2. The parser does not build an explicit parse tree.
   3. The parser only makes one bottom-up pass over the parse tree.
   4. The parser only makes one top-down pass over the parse tree.

5. In a Pascal compiler, types of expressions can be inferred
   1. as a synthesized attribute of expression nonterminal.
   2. as an inherited attribute of expression nonterminals.
   3. by looking in the symbol table, without using attributes.
   4. by asking the lexer to determine type information.

6. A basic block is a useful concept for code generation because
   1. Basic blocks are required for dataflow analysis.
   2. Basic blocks are required for control flow analysis.
   3. The compiler would not be able to assign registers without using basic blocks.
   4. The compiler can generate code for a basic block as a sequence of instructions without concern for branching.

7. Assume that $a$ and $b$ are global variables of type integer, where $a$ is at offset 1 and $b$ is at offset 2. Write a translation of expression $a + b + b$ into code for the abstract machine used in your Pascal compiler project. The code should compute the value of this expression and store the result onto the stack. Only show the code that might be generated by your compiler. It is not important that you use the exact correct names of instructions, but use names that make the intended instruction clear.

8. A programming language has a kind of expression called a booleanExpression. The following productions describe them.
   $$\begin{eqnarray*} {\rm booleanExpression} &\to& {\bf identifier} > {\bf identif... ...to& {\rm booleanExpression~} {\bf or} {\rm ~booleanExpression} \end{eqnarray*}$$
   
   
   
   
   
   A booleanExpression has two inherited attributes, called true and false, where $e$.true is a label number where the program should jump if $e$ is true, and $e$.false is the label where the program should jump if $e$ is false.

   Write semantic actions to compile boolean expressions into the byte code that you used for your Pascal compiler. Just write the semantic actions in a clear form, being sure to define the inherited attributes where necessary. Assume that all variables are global variables of type integer. Function get_var_offset(x) tells the offset where global variable x is stored.

9. You are given the following grammar for variable declarations in a programming language.
   $$\begin{eqnarray*} {\rm declaration} &\to& {\bf var} {\rm ~identifierList~} {\b... ... identifierList} &\to& {\rm identifierList~} {\bf ,~identifier} \end{eqnarray*}$$
   
   
   
   
   
   for example, declaration
   
   declares $x$, $y$ and $z$ to have type integer. The lexical analyzer produces the name of an identifier (a string) for an identifier, and the parser produces a data structure that describes a type as the attribute of a type. A function insert(name,type) is available that makes an entry in the symbol table indicating that the type of variable name is type, where name is a string and type is the same kind of thing that is produced as the attribute of the type nonterminal.

   You would like to make entries into the symbol table that are called for by a given declaration. Modify the grammar (without changing the language) so that only synthesized attributes are needed. Write the grammar with semantic actions in Bison syntax so that the necessary symbol table entries get done. Your new nonterminals can have attributes. Do not use any global variables. (Hint: think about what the parse tree should look like so that information only needs to flow up the tree.)