NEW MEXICO STATE UNIVERSITY
Department of Computer Science

Compilers Qualifying Examination
January 12th, 1999 -- 12-14pm

1. (40%) Consider the following languages:
$L_1 = \{ a^n b^n c ~\vert~ n \geq 1 \} \cup \{ a^n b^{2n} d ~\vert~ n \geq 1 \}$
$L_2 = \{ a^n c b^n ~\vert~ n \geq 1 \} \cup \{ a^n d b^{2n} ~\vert~ n \geq 1 \}$
$L_3 = \{ c a^n b^n ~\vert~ n \geq 1 \} \cup \{ d a^n b^{2n} ~\vert~ n \geq 1 \}$

(a) Is L₁ suitable for top-down parsing?
(b) Is L₁ suitable for bottom-up parsing?
(c) Is L₂ suitable for top-down parsing?
(d) Is L₂ suitable for bottom-up parsing?
(e) Is L₃ suitable for top-down parsing?
(f) Is L₃ suitable for bottom-up parsing?

Briefly (informally) justify your answers.

2. (30%) Consider the programming language C. We define the `comment' token as a sequence of characters beginning with /* and ending with */. Comments cannot be nested. Give a regular expression for the `comment' token. You can give the expression in LEX.

3. (30%) Consider the following program fragment:

   while (!(x == y))
      if (x > y) {
         x = x-y; 
         if (x== y*5) {
            break; 
            y=x+6;
         }
      }
      else {
         if (y==x*5) {
            continue; 
         } 
         y = y-x;
      }
   return x;

Suppose we want to generate intermediate code for the above program. What are the basic blocks? What intermediate code is in each basic block?

Note: You do not have to apply optimization to the code in each basic block.