CSE 401 Final Exam

December 18, 2002

Name: ___________________________________________________

PLEASE READ THIS. IT'S IMPORTANT! I'M NOT KIDDING!

All questions have only ONE valid answer.

Sometimes the wrong answers might be formulated in an attractive manner. Be confident on your knowledge and choose the answers that make the most sense according to what we talked in class.

If two answers are basically correct but one is more precise and detailed than the other, choose the more precise and detailed one. For example:

Q: What is a horse?

(a) A horse is an entity

(b) A horse is a mammal

you should choose (b) because it is the most precise, although (a) is valid as well.

All questions are closed book, closed notes, open mind. Use the back side of the page for scratch paper, if necessary. If you feel there are points you want to make to justify your answers, do so in writing.

There are 50 questions total, each worth 1 point. The duration of the exam is 110 minutes. This means you should spend 2.2 minutes for every question. Please budget your time carefully!

What is the purpose of generating machine-independent intermediate code before generating machine code for the target machine?

(a) Make the task of generating machine code easier

(b) Make the code generator and the optimizer portable across several processors

How many temporary variables can the intermediate code generator create?

(a) As many as there are registers in the target processor

(b) A number that's arbitrarily chosen, but fixed

What is the format of intermediate code?

(a) Tree-structured: mimics the AST of the source program because it was generated from it.

(b) Linear list of instructions

What is the most accurate definition of an l-value?

(a) An expression referring to an entity that has an address in memory.

(b) A variable name

(d) A function call

In an optimized interpreter, could the activation record for procedures be merged with the symbol table of that procedure?

(a) No

(b) Yes, if the language disallows recursive calls

(d) Yes, but only for procedures that don't define local variables

When accessing variables defined in the enclosing scope in a compiled PL/0 program, what can you say about the runtime access speed?

(a) Constant

(b) Linear in the depth of scoping; the deeper the nesting, the longer the access time

(d) Linear in the length of the identifier name

When calling a function in a given language, the order of pushing the arguments onto the stack (left-to-right versus right-to-left) is decided by:

(a) The complexity of the expressions that form the actual arguments

(b) Whether the function has a fixed or variable number of arguments

(d) The language and the implementor

Alignment issues are caused by:

(a) Different widths of the Internal and external processor bus

(b) The quirks of transferring data between cache and main memory

(d) The Virtual Memory Manager (VMM)

Under what circumstances could an implementation of the C++ programming language store a variable of type bool in a single bit?

(a) That variable is a compile-time constant, i.e., it is initialized with a constant and then never written

(b) The address of that variable is never taken

(d) That variable is defined with the register qualifier

Consider the following C++ code:

void Fun()
{
    char* p = new char[sizeof(int) + 1];
    int* pInt1 = (int*)p;
    ++p;
    int* pInt2 = (int*)p;
    *pInt1 = 1;
    *pInt2 = 2;
}

(a) The code likely has an alignment issue, and it depends on the system whether a run-time error/crash will occur

(b) The code does not have an alignment issue

(d) The code has an alignment issue and a buffer overrun issue

(e) The code only has a buffer overrun issue

In C and C++, can a type require more alignment than its own size?

(a) Yes; the typical example is float numbers. Although they might be only 4 bytes in size, they sometimes need 8 bytes of alignment due to the way some floating-point units work.

(b) No, because that would mean you can't compute the position of data in an array by multiplying the index with sizeof(element), and this is how array offsets are supposed to be computed

(c) Yes, because for example floating point numbers can internally (in the processor registers) hold more bits of precision than exposed externally

(d) No, because the type couldn't be stored properly in structures and classes

Which matrix format storage is better, row-major or column-major?

(a) Depends on the style of iteration that's most commonly used

(b) Column major because most scientific computations scan arrays columnwise

(c) Given that both styles of iteration are common, row-major has an edge because it allows the type system to naturally implement multidimensional arrays as arrays of arrays of arrays...

(d) Given that both styles of iterations are common, column-major has an edge because it allows the type system to naturally implement multidimensional arrays as arrays of arrays of arrays...

What disadvantages have fixed-size arrays?

(a) Make static checking of program harder

(b) Impose bounds checking at each access in the array

(c) Make writing reusable code harder, because the length of the array is part of the type; therefore functions written for arrays of size 1024 won't simply work with arrays of other sizes

What does “static allocation” mean for a variable?

(a) It has statically-known size and is allocated on the program stack

(b) It is allocated in the static data area of the executable program

(d) It is invisible outside the function where it is defined

Consider the following C++ function:

void Fun(int a, int b)
{
    if (a == b)
    {
        double d1 = a / 4;
    }
    double d2 = b / 4;
}

What can you say about the addresses of d1 and d2?

(a) They could be allocated at the same address, because their lifetimes are not overlapping

(b) They cannot be allocated at the same address

(c) They can be allocated at the same address because double is a primitive type. If in the code above you replace double with a class type that has constructors and destructor, then d1 and d2 cannot possibly be allocated at the same address.

When accessing variables defined in the enclosing scope in a compiled C or C++ program, what can you say about the runtime access speed?

(a) Constant because in C and C++ there is only the global scope and the local scope

(b) Linear in the depth of scoping; the deeper the nesting, the longer the access time

(d) Linear in the length of the identifier name

What inherent limitations imposes stack allocation on language power?

(a) Stack variables cannot have their address taken

(b) Stack variables cannot escape their context, and therefore supporting first-class functions is difficult

(d) Stack variables make variable lookup rules overly complicated because of nested scopes

In PL/0, the dynamic link is conceptually needed:

(a) Solely for knowing where to return when the function exits (the dynamic link is practically the return address)

(b) For the purpose mentioned at (a), plus to access variables defined in caller's scope

In class we discussed a non-standard C library function called alloca bearing the following prototype:

void* alloca(size_t size);

What does alloca do? Select the answer that best describes alloca.

(a) Allocates memory on the stack of the executing function. To free that memory, you need to call the pair function dealloca.

(b) Allocates memory on the stack of the caller of the executing function. The memory will last after the current function returns, but will be automatically reclaimed when the caller returns.

(c) Allocates memory on the stack of the executing function. When the executing function returns, memory will be automatically reclaimed.

(d) Allows the programmer to control local variable allocation

(e) Allows functions to return arrays by value

In our PL/0 implementation, the static link is conceptually needed:

(a) For accessing variables defined in caller's scope

(b) For for knowing where to return when the function exits

What can you say about the relationship between the stack pointer and the frame pointer in a PL/0 implementation in which the stack grows downward?

(a) FP is always greater than SP

(b) FP is always smaller than SP

Consider the following program written in pseudo-C:

int a[] = { 1, 2, 3, 4, 5 };
int i = 0;

int Fun(int x)
{
    x += a[0];
    i += 2;
    x += a[0];
    return x;
}

int main()
{
    cout << Fun(a[i]);
}

We said pseudo-C because we can tweak the calling convention used by this language. Under which calling convention will the program print the largest number?

(a) Call-by-value

(b) Call-by-reference

What is a closure as discussed in class?

(a) The set of variables accessible at a given point in a program

(b) The set of variables local to a given function

(d) The act of closing a deal with a used car salesman

What can be said about the stack space needed to execute a function?

(a) It is statically known, unless the function uses tricks such as alloca

(b) It can't be known statically because the exact stack space needed depends on the control flow, recursion etc.

What is the quintessential advantage of a compiler over an interpreter?

(a) Better type checking

(b) Faster execution

(d) Adherence to binary standards

In our PL/0 implementation, where are constants' values held?

(a) In the symbol table

(b) In the activation record

(d) In the AST after parsing

In a compiled C++ program, is the symbol table loaded at runtime?

(a) Yes, because C++ allows definition of local classes which can define functions

(b) Only in programs that use non-local control flow, such as exceptions.

What is the structure of the symbol table of a program?

(a) Singly-linked list

(b) Doubly-linked list

(d) Tree with a different topology than the AST of the program

(e) Array

Consider the types int and double as the archetypal integer and floating point types. If you were to establish a relationship between these types, what would you say?

(a) int could inherit double

(b) double could inherit int

Consider two types: Point (having as members two coordinates) and ColoredPoint (having as members two coordinates and a color). If you were to establish a relationship between these types, what would you say?

(a) Point could inherit ColoredPoint

(b) ColoredPoint could inherit Point

(d) Either of (a), (b)

In our PL/0 implementation, what is the relationship between the hierarchy rooted in Type and that rooted in TypeAST?

(a) TypeAST is the type as parsed, and Type is the type used for typechecking purposes

(b) Type is the type as parsed, and TypeAST is the type as stored in the AST.

(d) TypeAST inherits Type

How does PL/0 solve the dangling else problem?

(a) The if-else statement is defined in a manner that avoids the dangling else altogether

(b) The IfStmt class has a simple hack to take care of that

How is an assignment typechecked in the new (enhanced) PL/0?

(a) The left-hand-side and right-hand-side expressions must be of the same type

(b) The left-hand-side and right-hand-side expressions must be of the same type, and the left-hand-side expression must refer to an lvalue.

(c) The left-hand-side and right-hand-side expressions must be of the same type, and the left-hand-side expression must be a variable name.

(d) The right-hand-side type must be convertible to the left-hand side type, and the left-hand-side expression must refer to an lvalue.

What can you say about downcasts and upcasts in C++?

(a) Downcasts are always safe, upcasts are sometimes unsafe

(b) Upcasts are always safe, downcasts are sometimes unsafe

(d) Both are safe

A grammar is ambiguous when:

(a) A symbol name appears duplicated

(b) Two different textual inputs parse to the same AST

(d) There are valid inputs that cannot be parsed into a valid AST

In a recursive descent parser:

(a) Each terminal is a function

(b) Each nonterminal is a function

(d) Each nonterminal is a class

In an LL(k) grammar, k stands for:

(a) The maximum number of nonterminals that can build a valid production

(b) The maximum number of nonterminals that a parser must look ahead to decide which production to use

For a string µ of terminals and non-terminals, FIRST(µ) is:

(a) The set of terminals that begin strings derived from µ, together with ε, if µ can derive ε.

(b) The first k elements in µ, assuming the grammar is LL(k)

For an LL(1) grammar, the PREDICT function:

(a) Takes a terminal, returns a nonterminal

(b) Takes a nonterminal, returns a terminal

(d) Takes a nonterminal and a terminal, returns a set of productions

(e) Takes a terminal, returns a production

Which part of the build process does yacc automate?

(a) Scanning

(b) Parsing

(d) Code generation

In a compiler with a classic structure, would the code generator need to invoke the scanner?

(a) No

(b) Yes, but only when macro preprocessing is involved

Consider the following routine for scanning integers in our compiler:

Token* Scanner::GetInt()
{
    int integer = 0;
    while (isdigit(CurrentCh)) 
    {
        integer += CurrentCh - '0';
        integer *= 10;
        GetCh();
    }
    return new IntegerToken(integer);
}

This routine has a bug, can you spot it?

(a) The subtraction of '0' from CurrentCh is not needed

(b) The integer must be multiplied by CurrentCh – '0' and must be added 10

How would be class inheritance most accurately described?

(a) “Is-a”

(b) “Is substitutable for”

(d) “Extends”

When scanning a program, the scanner finding an integer will:

(a) Emit the same token for all integers

(b) Emit a distinct token for each integer

An “undefined identifier” error might be caught during:

(a) Scanning

(b) Parsing

(d) Space allocation

In C and C++, typedef introduces:

(a) A brand new type with the same behavior as the original type

(b) A type that's structurally equivalent with the original type

When calling a function, the responsibility for clearing up the arguments off the stack after the callee has returned falls on:

(a) The caller

(b) The callee

Can an implementation pass some arguments in registers (as opposed to the stack)?

(a) No, because the registers are destroyed during the issue of the call

(b) No, because that would mess up the stack frame of the function

(d) No, because the compiler lacks information in the case of separate compilation

In a program, in general variables should:

(a) Be as local as possible

(b) Be as global as possible

What is the major problem with passing arguments by reference?

(a) Simple/standard functions are hard to implement

(b) Aliasing