Directions: Use your own paper for this exam.

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'  |  'd'  |  '(' E ')'
   

   1. List all the terminal symbols, then all the non-terminal symbols, and finally all the metasymbols.
   2. Is this grammar ambiguous? (Yes or No)
   3. Is this grammar suitable for a recursive descent parser? (Yes or No)
   4. What is the associativity of the operator ^? If we wanted to reverse its associativity, how would we change the grammar?
   5. Construct the parse tree for the sentence: a ^ ( b + c * d ) $

   ---

2. Consider the following grammar:

   
           S ---> b M b              ("S" is the start symbol)
           M ---> ( L
           M ---> a
           L ---> M a )
   

   Use the following shift-reduce table for this grammar:

   
              |  b  |  a  |  (  |  )  |  $   |
         -----+-----+-----+-----+-----+------+
           S  |     |     |     |     |  acc |     
           M  |  s  |  s  |     |     |      |
           L  |  r  |  r  |     |     |      |     
           b  |     |  s  |  s  |     |  r   |
           a  |  r  |  r  |     |  s  |      |     
           (  |  s  |  s  |  s  |     |      |
           )  |  r  |  r  |     |     |      |
   

   1. Carry out the shift-reduce parse of the following sentence, showing the stack, current symbol, remaining symbols, and next action to take at each stage. (This sentence has the extra artificial symbol $ stuck in at the beginning and the end.)

      
           $ b ( ( a a ) a ) b $
      

      (Remember that you should initially shift the starting $ and then shift the next symbol.)

   ---

3. Consider the grammar rule for an assignment statement, as it was presented for the class compiler project:

   
      A  --->  lower-case  '='  E  ';' 
   

   1. Give the function A used in your recursive descent parser to handle this rule. (Give it in as complete a detail as you can, using the language that you used for your programming.)

   2. How does the parser know to call A, rather than some other function that is part of the recursive descent parser? (How does the parser decide to call A?)

   3. In as much detail as possible, give the actual code that you used for the final version of the function A, so that it will generate the proper MIPS code. (If necessary, put in pseudo-code or slur over details, but you may lose some credit in this case.)

   ---

4. Consider the recitation that involved translating while and if-then-else statements. As part of the translation process, labels would be inserted into the assembly code. In order to handle nested and repeated instances of these constructs, what trick was needed (or if you like, how did you manage to translate these so that the constructs could be nested or repeated)?

   ---

5. This is a question about run-time storage management:
   1. What is stack-based storage mainly used for?

   2. Describe the pitfall that we discussed in the use of stack-based storage in C or C++ (the dangle example)? Why is this pitfall impossible to encounter in Java?

   3. What is a memory leak? What will be the bad effects of a memory leak?

   ---

6. Consider the attached Java program (Paren.java), along with sample output.
   1. What is this program doing?

   2. Say roughly how it is working.

   3. If it puts in extra parentheses, then why doesn't it put extra parentheses into the input ( ( a + b ) * c ) $? (Be as specific in your answer as possible.)

   4. Given the input ( ( ( ( a ) ) ) ) $, what will the output be?