COSC4307                              Final Exam                                         Summer 2007

 

 

Name___________________________________________________________

 

PART-A.         Multiple-Choice                                                          (72 points)

 

Answer 18 questions in this PART.

Choose the one BEST answer in each question you answer by writing down a BIG Letter (in Capital).

 

For the first four questions, consider the following Boolean expression and the corresponding sequence

of quadruples that can be generated:

 

                        ((A+B*C)  AND  (NOT D)  AND  E)

 

                        10:       =,         #1,`      0,         T4

                        11:       *,         B,         C,         T5

                        12:       +,         A,        T5,       T6

                        13:      BB,       T6,       X1,      X2

                        14:      BB,       D,        X3,      X4

                        15:      BB,       E,         X5,      X6

                        16:       =,         #0,       0,         T4

                        17:   BEQ,        T4,       #0,       ??

 

You must assume the usual operator precedence:  That is, NOT, AND, and OR in that order.

 

 1.        The values of X1 and X2 are, respectively,

            a.         14 and 16.                   b.         16 and 14.       c.         17 and 14.      

d.         None. 

 

 2.        The values of X3 and X4 are, respectively,

            a.         17 and 15                    b.         16 and 15.       c.         16 and 15

            d.         None.  

 

 3.        Which two values are the same?

            a.         X4 and X6                   b.         X2 and X4                   c.         Both.                            d.         Neither

 

4.        Which two values are the same?

a.         X1 and X3                   b.         X1 and X4                   c.         X4 and X6.

            d.         None.

 

Next three questions are about the following sequence of quadruples generated for a boolean expression:

 

                        20:                   =          #1        0          T4

                        21:                   BB       A         22        24

                        22:                   BB       B          24        23

                        23:                   BB       C          25        24

                        24:                   =          #0        0          T5

                        25:                   BEQ     T4        #0        ???

 

5.         The boolean expression is

            a.         A AND B AND C

            b.         A AND (NOT B) AND C

            c.         A AND B OR C

            d.         None above.

 

6.         Which call(s) to Merge() was made during the generation of these codes?

            a.         Merge (-21,22)

            b.         Merge (-21,-23)                                   c.         both.                            d.         neither.

 

7.         Exactly before quad #24 was about to be generated, which Fillin() call was made?

            a.         Fillin (-21)

            b.         Fillin (-23)

            c.         Fillin ( 23)

            d.         none above.

 

For the next four questions, consider the following array declaration:

                        Integer AA[1:10, 1:20, 1:30]

 

Assume that the Row-major sequence is used and that the first array element, AA[1,1,1], is stored at location 10000 and that each array element occupies exactly one memory location for the sake of simplicity.

 

 8.        The modified first address of this array is

            a.         10000  -  (1+30+600+6000)

            b.         10000  + (1+30+600)               c.  Neither

 

 9.        The VarPart (offset(AA(Z,Y,X))) is

            a.  X+30*Y+600*Z

            b.  6000*Z+600*Y+30*X                   c.  Neither

 

 10.      Which array element has a smaller VarPart of its offset when the Row-major sequence

            is used than when the Column-major sequence is used?

            a.         AA [10,10,1]  

            b.         AA [1,10,30]               c.  Both.                       d.  Neither

 

11.      The difference in memory locations between AA[M, L-2,K] and AA[M,L,K] where L>1

a.         1200                            b.         60                                c.         30

d.         None above.                E.         Cannot tell

 

For the next four questions, refer to the following CFG for generating Boolean expressions:

                        Bool     ->   BE

                        BE       ->   BE  OR  BT   |   BE AND BT   |   BT

                        BT       ->   BF   |   NOT  BE

                        BF        ->   id     |   ( BE )                    

 

12.                   NOT A OR B

            According to the grammar, above has to be unambiguously equivalent to

            a.         (NOT A) OR B

            b.         NOT (A OR B)                                    c.  Both.                       d.   Neither.

 

13.                   A OR B AND C

            According to the grammar, above has to be unambiguously equivalent to

            a.         (A OR B) AND C

            b.         A OR (B AND C)                    c.  Both.                       d.   Neither.

 

14.                   A AND B AND C

            According to the grammar, above has to be unambiguously equivalent to

            a.  (A AND B) AND C

            b.  A AND (B  AND C)                                   c.  Both.                       d.   Neither.

 

15.                   BT  ->  NOT   BT

            Suppose that above rule replaced the following rule of this grammar:

BT  ->  NOT   BE

            a.  (NOT A  AND B) is ambiguous in the original grammar before this replacement.

            b. (NOT A   AND B) is ambiguous in the new resulting grammar after this replacement.

            c. Both.                                                d.  Neither.

 

16.                   void BE (int& Tlink, int& Flink)

            As presented in class, above function

            a.  may resolve one or more F-links by itself

            b.  may merge two or more T-links by itself.

            c.  Both.                                   d.  Neither.

 

17.                   void BF (int& Tlink, int& Flink)

            As presented in class, above function

            a.  always sets both its parameters by itself (rather than resolving) regardless of what is being generated.

            b.  may set both its parameters by way of a function call depending upon what is being derived.

            c.  both.                                               d.  neither.

 

18.       Evaluating loop parameters just once before the loop body execution

            a.  is more flexible and more efficient (in speed) than otherwise.

            b.  is safer and less efficient (in speed) than otherwise.

            c.  Both.                                   d.  Neither.        

 

19.       In a top-down error recovery, when a stack symbol is popped at the point of an error detection,

a.                   zero or more tokens are inserted before the current token.

b.                  one or more tokens are inserted after the current token.

c.                   Both.                                                    d.         Neither.

 

20.       Which error processing requires exactly “Parsing the entire program in the face of some errors”?

            a.         error repair

            b.         error recovery

            c.         error detection/report

d.                  none above.

 

21.       As presented in class, the semantic routine that actually generates by itself quadruples for ‘+’ is

a.                   E()

b.                  T()

c.                   Both                                                     d.         Neither.

 

 

 

22.                   *          A         B          T5

                        *          T5        C          T6

                        +          T6        D         T7

            Which will generate above sequence of quadruples?

a.                   A*B*C+D

b.                  (A*B*C)+D

c.                   (A*B)*C+D

d.                  all above                      e.         two above.                               f.          none above.

 

23.                   void  T(int & loc)

            As presented in class, above function always generates

a.                   at least one quadruple for ‘*’ by itself.

b.                  at least one quadruple for ‘+’ by itself.

c.                   Both.                                        d.         neither.

 

24.       As presented in class, the semantic routine that actually generates by itself quadruples for ‘*’ is

a.                   E()

b.                  T()

c.                   F()                                d.         all above.                     e.         two above.

 

PART-B.                     Other Problems                                              (28 points)

 

Do two problems in this PART.

 

   A. Give a semantic routine to translate a variable of the following form:                    Var -> id  |  id [ Elist ]

   1. In the above rule, only "Var" and "Elist" are the nonterminals.

         2. Assume that you have available a routine,

E(int& LOC), that translates an expression and returns a  

memory location to contain the value of the expression.

         3. “Elist” represents a list of one or more numerical expressions

            separated by a comma and each expression is a subscript of an array

      element.

     And, give quadruples to be generated by the above routine for:

A[I,J] = X *  B[I,J]

 

   B. Give a semantic routine to translate the following “WHILE” loop:

                  While E <> E do S

Note that this loop iterates exactly as long as the two given expressions are 

not the same and that it may not iterate even once.

 

      And, give quadruples to be generated for:

 

            while A+B <> C*D  do

                  begin       C = C+1;

                              A = A+C;

                              Print A*C         end

 

   C. Complete the following C++ function that resolves a given link field

      which is the first one of any number of links already merged/linked together.

 

                  Void Fillin (int field) // note that the given field may be negative