\documentstyle[12pt,fullpage,simplemargins]{article}

\setleftmargin{0.75in}
\setrightmargin{0.75in}
\settopmargin{0.75in}
\setbottommargin{0.75in}

\begin{document}
6.035 - Fall 1999 - TA: Daniel Barkalow \hspace{3in} le04
\begin{center} 
{\bf Parser project}
\end{center}

\section{Introducing le04}
    Chris Laas (golem)\\
    Mike Phillips (mpp)\\
    Jim Waldrop (jlwfnord)\\


\section{Division of Labor}

Since this was a small project, we were not able to simply cut the project
into thirds and assign a piece to each person. Instead we hacked on it 
together, taking turns adding to the grammar, tidying up debugging output, 
and generating test cases. The only real design discussion we needed was
to think about how to do error recovery.

\section{Clarifications, Assumptions, Additions}

None.


\section{Overview}

Starting with a working scanner and the Decaf language description, our
primary task was simply to hammer out the grammar. We also needed to 
deal with assigning precedence to our operators to avoid amigutity and
providing useful error messages. We modified Chris's scanner to use Longs
instead of Integers to store numbers to deal with the case of $-(MAXINT+1)$
and to provide a token number to string description mapping. 


\section{Implementation Issues and Insights}

Most of our time was spent in frustration with CUP's ``Symbol
recycling'' bug, producing better error messages, and playing with
error recovery. The error messages include the line number of the
error and the token that caused the error. In the case of tokens with
values (IDs, literals), the actual value is displayed instead of the
token name. When a missing right brace or semi-colon is detected,
error recovery is attempted so that later syntax errors can also be
reported.

\newpage
\section{Grammar}

\begin{verbatim}
parser code {:
  Yylex lexer;
  ParseErrorStream error_stream;
  boolean debug;

  public Parser(java.io.InputStream s, ParseErrorStream es, boolean d) {
    this();
    if (s == null)
      throw new Error("Error: Bad input stream initializer.");

    lexer = new Yylex(s, es);
    error_stream = es;
    debug = d;
  }

  public Parser(java.io.InputStream s, ParseErrorStream es) {
    this(s, es, false);
  }

  public java_cup.runtime.Symbol parse() throws Exception {
    if (debug)
      return super.debug_parse();
    else
      return super.parse();
  }

  public void syntax_error(java_cup.runtime.Symbol current) {
    error_stream.error(((Token)current).line,
                       "Syntax error at " + ((Token)current));
  }

  public void report_error(String message, Object current) {
    error_stream.error(((Token)current).line,
                       "Syntax error at " + ((Token)current) + ": " + message);
  }
:};

action code {:
  public void print_production(String prodstring) {
    if (parser.debug)
      System.out.println(prodstring);
  }
:};

scan with {: return lexer.nextToken(); :};


terminal           LBRACE, RBRACE, LBRACKET, RBRACKET, LPAREN, RPAREN,
                   COMMA, SEMICOLON, PLUS, MINUS, TIMES, LSHIFT, RSHIFT,
                   LE, GE, LT, GT, EQ, NE, ASSIGN, AND, OR, DOT, UMINUS,
                   BOOLEAN, CALLOUT, CLASS, ELSE, EXTENDS, FALSE, IF,
                   INT, NEW, NULL, RETURN, THIS, TRUE, VOID, WHILE;
terminal Integer   INT_LITERAL;
terminal Character CHAR_LITERAL;
terminal String    STRING_LITERAL, ID;

/* Non terminals */
nonterminal
           program, field_decl_list, field_decl,
           field_decl_id_list, field_decl_id,
           method_decl_list, method_decl,
           method_param_spec, method_param_list, block,
           var_decl_list, var_decl, var_decl_id_list, type,
           statement_list, statement, else_clause,
           method_call, expr_list, callout_arg_list,
           method_name, location, expr, callout_arg,
           bin_op, arith_op, rel_op, cond_op, literal,
           bool_literal, eq_op, semi, r_brace;

/* Precedences. */

precedence left OR;
precedence left AND;
precedence left EQ, NE;
precedence left LE, GE, LT, GT;
precedence left LSHIFT, RSHIFT;
precedence left PLUS, MINUS;
precedence left TIMES;
precedence left UMINUS;

/* The grammar. */

program            ::= CLASS ID LBRACE field_decl_list method_decl_list r_brace
                       {: print_production(PRODSTRING); :}
                   |   CLASS ID LBRACE field_decl_list r_brace
                       {: print_production(PRODSTRING); :}
                   ;

field_decl_list    ::= field_decl_list field_decl
                       {: print_production(PRODSTRING); :}
                   |
                       {: print_production(PRODSTRING); :}
                   ;

field_decl         ::= type field_decl_id_list semi
                       {: print_production(PRODSTRING); :}
                   ;

field_decl_id_list ::= field_decl_id_list COMMA field_decl_id
                       {: print_production(PRODSTRING); :}
                   |   field_decl_id
                       {: print_production(PRODSTRING); :}
                   ;

field_decl_id      ::= ID
                       {: print_production(PRODSTRING); :}
                   |   ID LBRACKET INT_LITERAL RBRACKET
                       {: print_production(PRODSTRING); :}
                   ;

method_decl_list   ::= method_decl_list method_decl
                       {: print_production(PRODSTRING); :}
                   |   method_decl
                       {: print_production(PRODSTRING); :}
                   ;

method_decl        ::= type ID LPAREN method_param_spec RPAREN block
                       {: print_production(PRODSTRING); :}
                   |   VOID ID LPAREN method_param_spec RPAREN block
                       {: print_production(PRODSTRING); :}
                   ;

method_param_spec  ::= method_param_list
                       {: print_production(PRODSTRING); :}
                   |
                       {: print_production(PRODSTRING); :}
                   ;

method_param_list  ::= method_param_list COMMA type ID
                       {: print_production(PRODSTRING); :}
                   |   type ID
                       {: print_production(PRODSTRING); :}
                   ;

block              ::= LBRACE var_decl_list statement_list r_brace
                       {: print_production(PRODSTRING); :}
                   ;

var_decl_list      ::= var_decl_list var_decl
                       {: print_production(PRODSTRING); :}
                   |
                       {: print_production(PRODSTRING); :}
                   ;

var_decl           ::= type var_decl_id_list semi
                       {: print_production(PRODSTRING); :}
                   ;

var_decl_id_list   ::= var_decl_id_list COMMA ID
                       {: print_production(PRODSTRING); :}
                   |   ID
                       {: print_production(PRODSTRING); :}
                   ;

type               ::= INT
                       {: print_production(PRODSTRING); :}
                   |   BOOLEAN
                       {: print_production(PRODSTRING); :}
                   ;

statement_list     ::= statement_list statement
                       {: print_production(PRODSTRING); :}
                   |
                       {: print_production(PRODSTRING); :}
                   ;

statement          ::= location ASSIGN expr semi
                       {: print_production(PRODSTRING); :}
                   |   method_call semi
                       {: print_production(PRODSTRING); :}
                   |   IF LPAREN expr RPAREN LBRACE statement_list r_brace 
                          else_clause
                       {: print_production(PRODSTRING); :}
                   |   WHILE LPAREN expr RPAREN LBRACE statement_list r_brace
                       {: print_production(PRODSTRING); :}
                   |   RETURN semi
                       {: print_production(PRODSTRING); :}
                   |   RETURN expr semi
                       {: print_production(PRODSTRING); :}
                   ;

else_clause        ::= ELSE LBRACE statement_list r_brace
                       {: print_production(PRODSTRING); :}
                   |
                       {: print_production(PRODSTRING); :}
                   ;

method_call        ::= method_name LPAREN expr_list RPAREN
                       {: print_production(PRODSTRING); :}
                   |   method_name LPAREN RPAREN
                       {: print_production(PRODSTRING); :}
                   |   CALLOUT LPAREN STRING_LITERAL RPAREN
                       {: print_production(PRODSTRING); :}
                   |   CALLOUT LPAREN STRING_LITERAL COMMA callout_arg_list
                               RPAREN
                       {: print_production(PRODSTRING); :}
                   ;

expr_list          ::= expr_list COMMA expr
                       {: print_production(PRODSTRING); :}
                   |   expr
                       {: print_production(PRODSTRING); :}
                   ;           

callout_arg_list   ::= callout_arg_list COMMA callout_arg
                       {: print_production(PRODSTRING); :}
                   |   callout_arg
                       {: print_production(PRODSTRING); :}
                   ;

method_name        ::= ID
                       {: print_production(PRODSTRING); :}
                   ;

location           ::= ID
                       {: print_production(PRODSTRING); :}
                   |   ID LBRACKET expr RBRACKET
                       {: print_production(PRODSTRING); :}
                   ;

expr               ::= location  
                       {: print_production(PRODSTRING); :}
                   |   method_call
                       {: print_production(PRODSTRING); :}
                   |   literal
                       {: print_production(PRODSTRING); :}
                   |   expr bin_op expr
                       {: print_production(PRODSTRING); :}
                   |   LPAREN expr RPAREN
                       {: print_production(PRODSTRING); :}
                   |   MINUS expr
                       {: print_production(PRODSTRING); :} %prec UMINUS
                   ;

callout_arg        ::= expr
                       {: print_production(PRODSTRING); :}
                   |   STRING_LITERAL
                       {: print_production(PRODSTRING); :}
                   ;

bin_op             ::= arith_op
                       {: print_production(PRODSTRING); :}
                   |   rel_op
                       {: print_production(PRODSTRING); :}
                   |   eq_op
                       {: print_production(PRODSTRING); :}
                   |   cond_op
                       {: print_production(PRODSTRING); :}
                   ;

arith_op           ::= PLUS
                       {: print_production(PRODSTRING); :}
                   |   MINUS
                       {: print_production(PRODSTRING); :}
                   |   TIMES
                       {: print_production(PRODSTRING); :}
                   |   LSHIFT
                       {: print_production(PRODSTRING); :}
                   |   RSHIFT
                       {: print_production(PRODSTRING); :}
                   ;

rel_op             ::= LT
                       {: print_production(PRODSTRING); :}
                   |   GT
                       {: print_production(PRODSTRING); :}
                   |   LE
                       {: print_production(PRODSTRING); :}
                   |   GE
                       {: print_production(PRODSTRING); :}
                   ;

cond_op            ::= AND
                       {: print_production(PRODSTRING); :}
                   |   OR
                       {: print_production(PRODSTRING); :}
                   ;

literal            ::= INT_LITERAL
                       {: print_production(PRODSTRING); :}
                   |   CHAR_LITERAL
                       {: print_production(PRODSTRING); :}
                   |   bool_literal
                       {: print_production(PRODSTRING); :}
                   ;

bool_literal       ::= TRUE
                       {: print_production(PRODSTRING); :}
                   |   FALSE
                       {: print_production(PRODSTRING); :}
                   ;

eq_op              ::= EQ
                       {: print_production(PRODSTRING); :}
                   |   NE
                       {: print_production(PRODSTRING); :}
                   ;

semi			   ::= SEMICOLON
				   |   error SEMICOLON
				   ;

r_brace			   ::=	RBRACE
				   |	error RBRACE
				   ;
\end{verbatim}

\section{Known Problems and Wish List}

No known problems exist with our Parser. It works fine on the given test
cases as well as on some cases we generated on our own. Ideally, the syntax
error message would include the actual text of the token rather than the
name; e.g. '\{' instead of LBRACE, but we feel this is extremely minor and not
worth dealing with at this time.

\end{document}



