Directions: Please write your answers on this exam.

1. Consider the formal Grammar in the comment at the start of the attached program.
   1. Is this grammar ambiguous? (Yes or No)
   2. What is the associativity of the operator ^?
   3. If we wanted to reverse its associativity, how would we change the grammar?

       

   4. Construct the parse tree for the sentence: 1 * ( 2 + 3^4 )

    

    

    

    

   ---

2. This question has to do with finite state machines (FSM).
   1. In class we talked about a FSM being equivalent to a language construct that you have seen elsewhere. What is this construct?

   2. What is the definition of a language, when the terminal symbols (called the alphabet) consists of the three letters a, b, and c?

       

   3. Convert the following FSM to the notation of the other language construct.

      

       

       

   4. In both cases these methods are describing or recognizing a language. Describe this language in ordinary English.

    

    

   ---

3. Consider the following code. It is my parse function for one of the grammar rules in the Tiny® language. (Your code ought to have been similar. The name of this function has been replaced by a letter X.)

   
      private void X() {
         // 1: start of code to parse the statement
   
   
   
         if (next == '{') {
            scan();
            // 2: start of code to parse next portion
   
   
   
            E();
         }
         else error();
         // 3: start of code to parse next portion
   
   
   
         if (next == '?') {
            scan();
            while (next != '}') {
               S();
               // 4: location for code inside loop
   
   
         }
         else error();
         if (next == '}') scan();
         else error();
         // 5: end of code for statement
   
   
   
      }
   

   1. Which language construct it this code for?

   2. Give the grammar rule for this construct.

   3. There are numbered locations labeled 1, 2, 3, 4, and 5 in comments. Following each of these locations there may be none, or one, or more than one parts of MIPS code (including possibly labels) that need to be output at this point. Give the MIPS code as well as you can. Show what is done with the value returned by the call to the function E.

   4. There is an extra integer counter value that is used inside this function. What is this counter value for?

    

   ---

4. This is a question about run-time storage management, specifically, support for function call/return.
   1. What kind of object is used to support function call/return?

   2. Does this support recursive functions? (Yes or No).

   3. What kind of information is usually placed in this object during a function call? What form does the information have?

       

       

       

       

   4. Given a function that looks like the following (C/C++ notation):

      
      int F(int x, char y) {
         int a[4] = {1, 2, 3, 4};
         return a[2];
      }
      

      what additional information will be placed in the object?

       

       

   5. What happens when the program returns from the function F above?

    

    

    

    

    

    

    

   ---

5. Consider the attached Java program Paren.java along with sample output. (The separate class GetNext.java just has a method getNextChar() that fetches the next input char.)
   1. What kind of parser is being used in this program?

   2. Briefly say what this program is doing.

       

       

   3. Briefly say roughly how it is working.

       

       

   4. Given the input 7 $, what will the output be?

   5. Given the input ( ( ( ( 7 + ((4)) ) ) ) ) $, what will the output be?

       

   6. Alter the program so that it outputs Lisp expressions, that is, Lisp S-expressions, which have the form of a parenthesized expression with the operator first, followed by the two operands, separated by at least one blank. The operands have this same structure. Here is what the output should look like. (The column on the right shows the actual Lisp interpreter processing the output.) You can give your answer by marking up the attached sheet with the Paren.java program on it.

      % java ParenLisp 1 + 2 * 3 $ (+ 1 (* 2 3)) % java ParenLisp (1 + (2 * 3)) $ (+ 1 (* 2 3)) % java ParenLisp 1*(2+3)$ (* 1 (+ 2 3))

      % lisp > (+ 1 (* 2 3)) 7 > (* 1 (+ 2 3)) 5 > (quit) %