1. What makes a grammar ambiguous?

  2. What is the difference between operator precedence and operator associativity?

  3. Can the following grammar be parsed by a top-down parser? Why or why not?
    G -> S $$
    S -> A M | A
    M -> S
    A -> a E | b A A | a
    E -> a B | B A
    B -> b E | a B B | b 
    
  4. For the following grammar, list the a) non-terminal symbols, and b) terminal symbols.

  5. Using the table format shown in the class notes, trace out a parse for the following input program:
    foo : record
          a : char;
          b : array 1..2 of real;
    end;
    
    Your table format should look as follows:
    input                stack                 action
    id : record ...      1                     first action 
    ...
    
    To save room you only have to list the next several tokens of input.

    Use the grammar from the previous exercise and the following parse table for your parse:

    Stateidintrealchararrayconst..ofrecordend;:$$decl_listdecltype
    1s4errerrerrerrerrerrerrerrerrerrerrerrs2s3err
    2s4errerrerrerrerrerrerrerrerrerrerraccerrs5err
    3errerrerrerrerrerrerrerrerrerrs6errerrerrerrerr
    4errerrerrerrerrerrerrerrerrerrerrs7errerrerrerr
    5errerrerrerrerrerrerrerrerrerrs8errerrerrerrerr
    6r3(2)errerrerrerrerrerrerrerrr3(2)errerrr3(2)errerrerr
    7errs10s11s12s13errerrerrs14errerrerrerrerrerrs9
    8r2(3)errerrerrerrerrerrerrerrr2(3)errerrr2(3)errerrerr
    9errerrerrerrerrerrerrerrerrerrr4(3)errerrerrerrerr
    10errerrerrerrerrerrerrerrerrerrr5(1)errerrerrerrerr
    11errerrerrerrerrerrerrerrerrerrr6(1)errerrerrerrerr
    12errerrerrerrerrerrerrerrerrerrr7(1)errerrerrerrerr
    13errerrerrerrerrs15errerrerrerrerrerrerrerrerrerr
    14s4errerrerrerrerrerrerrerrerrerrerrerrs16s3err
    15errerrerrerrerrerrs17errerrerrerrerrerrerrerrerr
    16s4errerrerrerrerrerrerrerrs18errerrerrerrs5err
    17errerrerrerrerrs19errerrerrerrerrerrerrerrerrerr
    18errerrerrerrerrerrerrerrerrerrr9(3)errerrerrerrerr
    19errerrerrerrerrerrerrs20errerrerrerrerrerrerrerr
    20errs10s11s12s13s14errerrerrerrerrerrerrerrerrs21
    21errerrerrerrerrerrerrerrerrerrr8(6)errerrerrerrerr

  6. Extend the prefix expression tree parser that you wrote in the previous assignment so that it builds expression trees for each of the expressions input by the user. You should use the expression tree classes that either you or I wrote in previous assignments to construct your expression trees.

    You should still use an interactive interpreter that reads lines one at a time. Instead of having your code parse the input it should now call your JCUP parser to parse the input. Your JCUP parser should build an expression tree as it recognizes productions and then store the expression tree in an appropriate instance variable in your expression tree class. Unfortunately JCUP's parser returns a Symbol object so you cannot return an expression tree from JCUP.

    You will need to create a new instance of your parser for each line of input since the parser wants to read to the end of the input in order to fully recognize a string. To get the parser and lexer to read from your string instead of from stdin you will need to pass an instance of a StringReader class to your lexer. You should look up the StringReader class in the java documentation to see how it works.

    When you have completed this exercise your code should be much simpler than it was when you hand-parsed each statement.