Directions: Use this exam sheet for your answers if you can, and otherwise use additional sheets. The answers will be posted.

1. Consider the formal Grammar

   
   P ---> E '#'
   E ---> E '+' T  |  E '-' T  |  T
   T ---> T '*' S  |  T '/' S  |  S
   S ---> F '^' S  |  F
   F ---> 'a'  |  'b'  |  'c'  |  '(' E ')'
   

   1. Is this grammar ambiguous? (Yes or No)
   2. Is this grammar suitable for a recursive descent parser? (Yes or No)
   3. Construct the parse tree for the sentence: (a + b^c)*a #

    

    

   ---

2. Suppose you are working with binary trees that have a single letter at their nodes. You wish to represent these trees as a string of characters. You will use 0 for the null node (empty node). A non-empty node will consist of a left paren, the node value (a letter), the left subtree, the right subtree, and finally a right paren. The top-level tree will have a # at the end. Here are some examples of the representation:
   Null tree: 0 #
   Tree with node a and with null left and right subtrees: (a 0 0) # 
   Tree with node a and with left subtree b and right subtree c: (a (b 0 0) (c 0 0) ) #

   1. Draw a diagram for the tree:

      
      (a (b (d 0 0) 0) (c (e 0 0) (f 0 0))) #
      

       

       

   2. Write a BNF (CF) grammar for these trees. Use non-terminal bintree for the whole tree including the # at the end, and use tree for a tree, so that the first grammar rule might be: bintree ---> tree '#'    Complete the grammar below:

      
      bintree --->  tree  '#'
      tree    ---> 
      
      

   3. Based on the grammar in part b above, write a skeleton recursive-descent parser corresponding to this grammar. (Use any notation and language. Just write the basic functions, starting with a function named bintree(). Assume a scanner named scan() is given that places the next input character into a variable next. Do not include any "helper" or "error" or "debug" functions.)

    

    

    

    

    

   ---

3. Consider the grammar rule for an if-then-else construct, as it was presented in class:

   
      I  --->  '['  E  '?'  { S }  ':'  { S }  ']' 
   

   1. What does { S } stand for in the rule?

   2. Show what additional MIPS instructions must be generated inside the function I in order to implement the if-then-else. More specifically, show exactly what MIPS instruction(s) and/or label(s) (if any) would need to be inserted by the I function at the four places below labeled # INSERT .... (If you don't remember the exact form of the MIPS instructions, just fake it as well as you can.)

      
      # Start of code for an if-then-else
      # INSERT EXTRA LABEL(S) AND/OR INSTRUCTION(S) HERE
      
      
      
      # Start of code to evaluate an expression E
         ...
      # Result left in a temporary memory location 172 bytes past
      #   the start of the memory array M.
      # INSERT EXTRA LABEL(S) AND/OR INSTRUCTION(S) HERE
      
      
      
      # Start of code to evaluate the first portion { S }
         ...
      # INSERT EXTRA LABEL(S) AND/OR INSTRUCTION(S) HERE
      
      
      
      # Start of code to evaluate the second portion {S}
         ...
      # INSERT EXTRA LABEL(S) AND/OR INSTRUCTION(S) HERE
      
      
      
      

   3. How does the function I find out that the result of evaluating E is going to be in a memory location 172 bytes past the start of M?

   ---

4. This is a question about 2-dimensional arrays in C/C++/Java:
   1. Suppose you declare a variable s in C or C++ using int s[5][4];.
      Draw a diagram to show how this is stored in memory.

       

   2. Explain how C/C++ will access array element s[2][3] in memory, using the declaration in part (a) above.

   3. In order to do this accessing, is it essential that C/C++ know the constant 4 (length of a row)?

   4. In order to do this accessing, is it essential that C/C++ know the constant 5 (number of rows)?

   5. Suppose you declare a variable s in Java using int[][] s = new int[5][4];.
      Draw a diagram to show how this is stored in memory.

    

    

   ---

5. This is a question about run-time storage management:
   1. What is used to manage the storage needed by functions when they are called?

   2. What two pitfalls or mistakes are possible when using explicit allocation and deallocation in a language like C or C++?

   3. How does Java overcome the pitfalls in part (b) above?

   4. Consider the heap as maintained in C for malloc and free, using the algorithms in the K&R book. What form does an allocated block of storage have, and how does free know how much storage to deallocate?