Special bonus features (at no additional cost!): Here is an elaboration of the answer to question 2 below: A program to read binary trees as a sequence of characters, using the syntax for binary trees given in question 2. The program then converts the tree to internal tree format. Finally, the program writes the tree as the same sequence of characters using the same format. (The lower-case letters at the nodes are converted to upper-case, just to prove that something is happening.)

• Binary tree conversion in C.
• Binary tree conversion in Java.

Here is the C program elaborated into two programs. The first reads lowercase letters and uses them to build a binary search tree. This tree is written out using the above format. The second program reads in the binary search tree, and does an inorder traversal to print the letters in alphabetic order. Finally, the listing illustrates using a Unix pipe between the two processes, where a binary tree is fed from the first process (standard output) into the second process (standard input):

• Program to pipe a binary tree from one process to another.

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 #

   
                                           P
                                      +----+-----+
                                      E          |
                                      |          |
                                      T          |
             +------------------------+----+     |
             T                        |    |     |
             |                        |    |     |
             S                        |    |     |
             |                        |    |     |
             F                        |    |     |
   +---------+-------------------+    |    |     |
   |         E                   |    |    |     |
   |    +----+---------+         |    |    |     |
   |    E    |         T         |    |    |     |
   |    |    |         |         |    |    |     |
   |    T    |         S         |    |    |     |
   |    |    |    +----+----+    |    |    |     |
   |    S    |    |    |    S    |    |    S     |
   |    |    |    |    |    |    |    |    |     |
   |    F    |    F    |    F    |    |    F     |
   |    |    |    |    |    |    |    |    |     |
   (    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))) #
                                       a
                                      / \
                                     /   \
                                    /     \
                                   b       c
                                  / \     / \
                                 /   0   /   \
                                d       e     f
                               / \     / \   / \
                              0   0   0   0 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    --->  '0'  |  '('  letter  tree  tree  ')'
      letter  --->  'a'  |  'b'  |  'c'  |  ...
      
      

   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.)

   
   void bintree(void) {
      scan();
      tree();
      if (next != '#') error(1);
      else printf("Successful parse\n");
   }
   
   void tree(void) {
      if (next == '0')
         scan();
      else {
         if (next == '(')
            scan();
         else error(2);
         if (isalpha(next))
            scan();
         else error(3);
         tree();
         tree();
         if (next == ')')
            scan();
         else error(4);
      }
   }
   
   void scan(void) {
      while (isspace(next = getchar()))
         ;
   }
   void error(int n) {
      printf("\n*** ERROR: %i\n", n);
      exit(1);
   }
   

   ---

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 if-then-else (no MIPS code needed here)
      # Start of code to evaluate an expression E
         ...
      # Result left in a temporary memory location 144 bytes past
      #   the start of the memory array M.
      # INSERT EXTRA LABEL(S) AND/OR INSTRUCTION(S) HERE
              lw      $t1,    172($s1)
              beq     $t1,    $zero,  ThenEnd4
      # Start of code to evaluate the first portion { S }
         ...
      # INSERT EXTRA LABEL(S) AND/OR INSTRUCTION(S) HERE
              j       ElseEnd4
      ThenEnd4:
      # Start of code to evaluate the second portion {S}
         ...
      # INSERT EXTRA LABEL(S) AND/OR INSTRUCTION(S) HERE
      ElseEnd4:
      
      

      (Note that there must be a unique sequence number, like the 4 above, that will distinguish this if-then-else from any other.)

   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? This value, either in bytes or words, is returned by the E function.

   ---

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.
      The rows are stored in order in sequential locations, so the order is as follows:

      s[0][0], s[0][1], s[0][2], s[0][3], s[1][0], s[1][1], s[1][2], s[1][3], s[2][0], s[2][1], s[2][2], s[2][3], s[3][0], s[3][1], s[3][2], s[3][3], s[4][0], s[4][1], s[4][2], s[4][3].

   2. Explain how C/C++ will access array element s[2][3] in memory, using the declaration in part (a) above. C/C++ must skip over 2 rows, each of length 4, and then go 3 additional locations, so in pointer arithmetic terms, the address of the desired location is: s + 2*4 + 3.

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

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

   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. This is an array of 5 references (pointers), each referencing an array of 4 integers.

   ---

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? A stack for the activation record of a function, including among other things the return address, return value, parameters, local variables and additional pointers. This is very easy to allocate and deallocate.

   2. What two pitfalls or mistakes are possible when using explicit allocation and deallocation in a language like C or C++? A memory leak can occur when a variable is allocated and not deallocated after it is no longer used (after there is no longer an active pointer pointing to it). A dangling pointer pointer to garbage can occur if active storage is deallocated in error, and then an attempt is made to access the storage.

   3. How does Java overcome the pitfalls in part (b) above? Java uses an automated garbage collector, which could also be used in C/C++ but usually is not.

   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? The most important thing is that the allocated storage includes its size at the start, so it is easy to know how much to recover.