CSCI 5220
Spring 2002
Answers to exam 2 questions

1. How would a live variable analysis be useful in generating good quality executable code? A: It can help to avoid generating instructions to store some values from registers into memory. Note: Live variable analysis cannot allow more registers to be used, since it does not increase the number of registers. It does not obviate the need for control flow analysis, and it is not the right kind of dataflow analysis for detecting uses of uninitialized variables.

2. Which of the following would be least likely to be stored in the symbol table of a compiler? A: the type of a complex expression. All of the others (the type of an identifier, the location where an identifier will be stored, the number of bytes required for a particular named type) are typically stored in a symbol table. They are characteristics of the things referred to by names.

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: A: often differs substantially from a parse tree.

   Note. A parse tree is purely syntactic. If there is a comma in the program, that comma will be part of the parse tree. A syntax tree is intermediate between syntax and semantics. It describes the relevant details about a program. Sometimes, a syntax tree can differ from a parse tree. For example, a for-loop might be described by the program that it abbreviates; the form of the for-loop is not present in the syntax tree. Syntax trees are powerful and commonly used.

4. Inherited attributes are difficult to use in a bottom-up parser because: A: The parser only makes one bottom-up pass over the parse tree.

5. In a Pascal compiler, types of expressions can be inferred: A: as synthesized attributes of expression nonterminals. The type information flows up the tree.

6. A basic block is a useful concept for code generation because: The compiler can generate code for a basic block as a sequence of instructions without concern for branching. Basic blocks are a convenience, not a necessity. They allow the compiler to treat sections of code as straight-line instructions. The compiler has flexibility in rearranging the instructions in a basic block.

\item 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.

    M_FETCH_GLOBAL_INTEGER
    1
    M_FETCH_GLOBAL_INTEGER
    2
    M_INTEGER_ADD
    M_FETCH_GLOBAL_INTEGER
    2
    M_INTEGER_ADD
  

7. A programming language has a kind of expression called a booleanExpression. The following productions describe them.

       booleanExpression} -> identifier > identifier
       booleanExpression} -> not booleanExpression
       booleanExpression} -> booleanExpression or booleanExpression
     

   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.

   Production	Semantic actions
   booleanExpression -> identifier1 > identifier2	booleanExpression.code =  emit(M_FETCH_GLOBAL_INTEGER) +  emit(get_var_offset(identifier1.name) +  emit(M_FETCH_GLOBAL_INTEGER) +  emit(get_var_offset(identifier2.name) +  emit(M_GOTO_IF_NOT_POSITIVE) +  emit(booleanExpression.false) +  emit(M_GOTO) +  emit(booleanExpression.true)
   booleanExpression} -> not booleanExpression1	booleanExpression1.true = booleanExpression.true booleanExpression1.false = booleanExpression.false booleanExpression.code = booleanExpression1.code
   booleanExpression -> booleanExpression1 or booleanExpression2	L = newlabel() booleanExpression1.true = booleanExpression.true booleanExpression1.false = L booleanExpression2.true = booleanExpression.true booleanExpression2.false = booleanExpression.false booleanExpression.code =  booleanExpression1.code +  emit(M_LABEL) +  emit(L) +  booleanExpression2.code

8. You are given the following grammar for variable declarations.

       declaration    -> var identifierList : type ;
       identifierList -> identifier
       identifierList -> identifierList identifier
     

   for example, declaration

       var x,y,z: integer;
     

   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.)

   The problem is to get the type to the places where it needs to be used. But that can be done by passing the type down the tree as an inherited attritute.

       declaration    -> var declarationRest
                               {}
   
       declarationRest -> identifier : type ;
                               {insert($1, $3);
                                $$ = $3;
                               }
   
       declarationRest -> identifier , declarationRest
                               {insert($1, $3);
                                $$ = $3;
                               }