\documentstyle[11pt,html,abstract]{article}

\def\hwno{1}  % Homework No
\def\hwtit{Syntax, Parsing, Abstract Syntax} % title of homework
\def\hwdue{12:00 noon, Wednesday, September 10, 2008}

\title{C311 -- Program~\hwno: \hwtit}
\author{Corky Cartwright}
\date{Produced:~\today --- Due:~\hwdue}

\begin{document}

\maketitle

\noindent{\Large \bf Overview}

\bigskip
\noindent
{\bf Preparation:} 
We suggest that you download and install the latest
version of the Java 6 SE JDK and the latest version of DrJava
for your preferred computing platform.
On Windows and Linux, the best Java 6 SE JDK is provided by
Sun Microsystems.  The latest version of the various Sun Java 6 SE JDK
systems can be obtained at 
\url{http://java.sun.com/javase/downloads/index.jsp}.
We recommend downloading and installing only the JDK, not the JDK with NetBeans
(which greatly increases the size of the download).
The latest version of DrJava can be obtained from \url{http://drjava.org}.

We will try to maintain the latest versions of the Java 6 SE JDK
and DrJava on OwlNet, but OwlNet is under the control of Rice IT,
which gives a very limited ability to configure what
software is available.  We recommend using OwlNet only to submit
your programs.  On OwlNet, we provide a {\tt turnin311} script,
which submits your program to our repository and tests that it
passes the trivial unit testing suite that we provide as
supporting software to help you debug your program.

On OwlNet, try running the {\tt register} command for {\tt comp311}, which
will make a recent version of drjava available as a commands in your OwlNet environment.
A Java 6 SE JDK should already be installed.

DrJava is distributed as a Java .jar file at the web site
\htmladdnormallink{
\verb|drjava.org|.}
{http://drjava.org}
You can
run DrJava on a Unix system (with Java JDK 5.0 or 6.0 installed)
by typing 
\begin{quote}
\verb|java -jar drjava.jar|
\end{quote}
assuming that \verb|drjava.jar| is located in the current directory.
On Windows machines (with Java JDK 5.0/6.0 installed), you can
run the \verb|drjava.jar| file simply by clicking on the
icon.
Documentation for DrJava is available at \htmladdnormallink{
\verb|drjava.info|.} {http://drjava.org}
In addition, if you have questions about
DrJava, send email to 
\begin{quote}
\htmladdnormallink{
\verb|javaplt@rice.edu|.}
{mailto:javaplt@rice.edu}
\end{quote}

A good article on the use of Generic Java in conjunction with unit
testing is available the IBM DeveloperWorks website:
\begin{verbatim}
    www-106.ibm.com/developerworks/java/library/j-diag0625.html?dwzone=java
\end{verbatim}
Every student should create
a {\tt comp311} directory in his or her home directory.  Each programming
team should submit their solution under the userid one team member.
We recommend creating a 
a {\tt programs/1} directory within the directory {\tt comp311}.
All of your files for this assignment should be stored in
the {\tt programs/1} subdirectory.

\bigskip
\noindent
{\bf TeamWork:} You are strongly encouraged to do this assignment and
all other assignments in this course in teams of two.  When you submit
your assignment, indicate the composition of your team (names, student
id's, and email addresses) and to what extent you followed the
pair-programming model in your {\tt README} file.

If you cannot find a partner and would like one, send 
Cherif Salama (cherif@rice.edu)
email and he will try to find one for you.
Teams of more than two members are {\em not}
permitted.  

\bigskip
\noindent
{\bf Testing:} You are expected to write unit tests for all of your 
non-trivial methods or functions, depending on whether you write your
assignments in Java or Scheme.  DrJava provides integrated support for
JUnit which makes this task easy.  Activating the ``Test'' button
(or ``Test Project'' button if in project mode) will run all of the
JUnit tests (which are classes extending {\tt junit.framework.TestCase})
that are open (listed in the Navigation pane) in DrJava.

\bigskip
\noindent
{\bf Task:} Your task is to write a parser in Generic Java or Scheme
that recognizes expressions in the
illustrative language {\sf Jam}, which will be defined subsequently. 
The course staff has provided lexers in both Scheme and Java
for this assignment.
These lexers return a larger
set of symbols than what appears in the {\sf Jam} definition.
These extra symbols anticipate future extensions to {\sf Jam}.
At this point, your parser should simply reject any program containing
one of these extra symbols as ill-formed, just like it would for any
other syntax error.

To make this programming assignment more tractable and to ensure common
interfaces within your parsers that we can easily test, we are supplying
you with a Java library, stored in a single file called
{\tt lexer.java}, that includes both a lexer (scanner) and
a collection of AST (abstract syntax tree) classes.
In our Java library, the parser's input token stream is provided by
a {\tt Lexer} object supporting the parameterless method 
{\tt readToken()}.  The {\tt readToken()} method
produces a stream of {\tt Token} objects
belonging to various subclasses of the {\tt Token} interface.
The {\tt Lexer} class supports two constructors: a zero-ary
constructor that converts standard input to a {\tt Lexer}
and a unary constructor {\tt Lexer(String fileName)} that converts
the specified file to a {\tt Lexer}.  The file {\tt lexer.java}
contains the definition of the Lexer class and the collection
of classes representing tokens (the Java interface {\tt Token})
and abstract syntax trees (the java interface {\tt AST}).

Your parser should be expressed
as a class {\tt Parser} with constructors
{\tt Parser(Reader stream)} and
{\tt Parser(String filename)}
which create parsers reading the specified stream or file.
The provided {\tt Lexer} class includes two similar constructors
{\tt Lexer(Reader stream)} and
{\tt Lexer(String filename)}.  The {\tt Reader} form of these
constructors is very convenient when you are testing your parser
from the DrJava read-eval-print loop or from unit test methods.

The {\tt Parser} class should contain a {\tt public} method {\tt AST parse()}
that returns the abstract syntax tree for the Jam expression
in the input stream.  
Our grading program will print the output using
the method {\tt System.out.println}, which invokes the 
{\tt toString} method on its argument.  All of the requisite abstract
syntax classes including {\tt toString} methods are defined in the
file {\tt lexer.java}.
This library files are available on the web in the directory
\begin{verbatim}
    www.cs.rice.edu/~javaplt/311/Assignments/1/java.
\end{verbatim}

If your parser encounters an erroneous input, simply print an
explanation of the syntax error and abort parsing the file (using the
{\tt error} primitive Scheme and the throwing of a {\tt
ParseException} in Java.  Recovering from a syntax error to
continue parsing is a complex problem
with many special cases.  It is not a realistic goal for this
assignment.
\bigskip
\noindent

\section*{Input Language Specification:}
The following paragraphs define the parser's input language and
the subset that your parser is supposed to recognize a legal
{\sf Jam} program. 

\bigskip
\noindent{\bf The Input Language} The
parser's input language is {\tt <input>} where: 
\begin{quote}
{\small 
\begin{verbatim}
%% A phrase P enclosed in braces { P } is optional
%% A phrase P followed by a * is iterated zero or more times, e.g. <def>+ means
%%   the concatenation of zero or more <def> phrases
%% A phrase P followed by a + is iterated one or more times, e.g. <def>+ means
%%   the concatenation of one or more <def> phrases
%% If a phrase P enclosed in brackets { P } is followed by a * or +, the braces are
%%   simply denote grouping: the enclosed phrase is iterated as specified by the
%%   * or + symbol

  <input> ::= <token>*

  <token> ::= <alpha/other> <alpha/other/numeric>* | <delimiter> | <operator>

%% Adjacent tokens must be separated by whitespace (a non-empty sequence of 
%% spaces, tabs, and newlines) unless one of the tokens is a delimiter or 
%% operator.
%% In identifying operators, the lexer chooses the longest possible match.  
%% Hence, "<=" is %% interpreted as a single token rather than "<" followed by "="

  <alpha/other/numeric> ::=  <alpha/other> | <digit> 

  <alpha/other> ::= <lower> | <upper> | <other> 

  <lower> ::= a | b | c | d | ... | z

  <upper> ::= A | B | C | D | ... | Z

  <other>  ::= ? | _ 

  <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

  <delimiter> ::= ( | ) | [ | ] | , | ; | 
  %% In subsequent assignments, "{" and "}" will be added to this list

  <operator> ::= "+" | - | ~ | "*" | / | = | != | < | > | <= | >= | & | 
                 "|" | := 

%% The operators "ref", "<-",  and "!" will be added in subsequent assignments, 
%% but they do not exist in Assignment 1

\end{verbatim}}
\end{quote}

\noindent{\bf Jam} The set of legitimate {\sf Jam} phrases is 
the subset of the potential inputs consisting
the expressions {\tt <exp> } defined by the following grammar:
\begin{quote}
{\small 
\begin{verbatim}
%% Expressions:
  <exp> ::= <term> { <binop> <exp> }
	  | if <exp> then <exp> else <exp>
	  | let <def>+ in <exp>
	  | map <id-list> to <exp>

  <term> ::= <unop> <term>
	   | <factor> { ( <exp-list> ) }
	   | <null> 
	   | <int>
	   | <bool>

  <factor> ::= ( <exp> )  |  <prim>  | <id>

  <exp-list>      ::= { <prop-exp-list> }
  <prop-exp-list> ::= <exp>   | <exp> , <prop-exp-list> 
  <id-list>       ::= { <prop-id-list> }
  <prop-id-list>  ::= <id>    | <id> , <prop-id-list> 

%% Definitions:
  <def> ::= <id> := <exp> ;

%% Primitive Constants, Operators, and Operations: 
  <null>  ::= null
  <bool>  ::= true | false 

  <unop>  ::= <sign> | ~ 
  <sign>  ::= "+" | -
  <binop> ::= <sign> | "*" | / | = | != | < | > | <= | >= | & | "|"
  <prim>  ::= number? | function? | list? | null? | cons? | cons
            | first | rest | arity
  %% In subsequent assignments ref? will be added to <prim>

%% Identifiers:
  <id>  ::= <alpha/other> {<alpha/other> | <digit>}*
            %% except for <prim> and the keywords if, then, else,
            %%   map, to, let, in, null, true, false 
            %% In subsequent assignments ref will be added to this list

  <alpha/other> ::= <alpha> | <other>  %% <other> as defined above
  <alpha> ::= <upper> | <lower>        %% <upper> and <lower> as defined above


%% Numbers:
   <int>  ::= <digit>+ 
\end{verbatim}}
\end{quote}

\bigskip
The lexer recognizes keywords, delimiters (parentheses, commas, semicolons),
primitive operations, identifiers, and numbers.  

The preceding grammar requires one symbol lookahead in a few
situations.
Our Java lexer includes a method {\tt Token peek()} that
behaves exactly like the method
{\tt Token readToken()} except for the fact that it leaves the
the scanned token at the front of the input stream (in contrast
{\tt readToken()} removes the scanned token from the input stream).

\noindent{\bf Abstract Syntax Trees} As mentioned above, the
Scheme library {\tt lexer.ss} defines the set of constructors used
to build abstract syntax trees in Scheme.  There is one constructor
for each different form of expression in the definition of {\sf Jam} syntax 
given above.  In addition, there is one abstract syntax
form for {\sf Jam} definitions, which can easily express both concrete
forms given above.

For example, suppose the Jam program under
consideration is 
\begin{verbatim}
                   f(x) + (x * 12))
\end{verbatim}

The abstract syntax representation for this
program phrase is:
\begin{quote}
\begin{verbatim}
(make-biop-exp '+
  (make-app-exp (make-id-exp 'f) (list (make-id-exp 'x)))
  (make-biop-exp '* (make-id-exp 'x) (make-num-exp 12)))
\end{verbatim}
\end{quote}
in the context of the following data descriptor definitions:
\begin{quote}
\begin{verbatim}
(define-struct biop-exp (rator rand1 rand2))
(define-struct app-exp (rator l-of-rands))
(define-struct id-exp (arg))
(define-struct num-exp (arg))
\end{verbatim}
\end{quote}

The Java file {\tt lexer.java} defines all of the abstract syntax
classes required to represent Jam programs.
There is one constructor
for each different form of expression in the definition of {\sf Jam} syntax 
given above.  Some primitive (non-recursive) abstract syntax classes
are the same the corresponding token classes.
There is one abstract syntax
form for {\sf Jam} definitions, which can easily express both concrete
forms given above.

\section*{Testing and Submitting Your Program}

The file 
\begin{verbatim}
    www.cs.rice.edu/~javaplt/311/Assignments/1/java.
\end{verbatim}
contains
a sample input program.
Create a README file in the your directory {\tt program/1} that
\begin{itemize}
\item
gives the names and userids of {\em both} team members, 
\item
outlines the
organization of your program, and 
\item 
specifies
what testing process you used to confirm the 
correctness of your program.  
\end{itemize}
Your test data
files should be stored in the {\tt programs/1} directory.

Each procedure or method in your program should include
a short comment stating precisely what it does.  For
routines that parse a particular form of program phrase,
give a grammar rule(s) describing that form.

To submit your program, make sure that everything that
you want to submit is located
in the directory {\tt programs/1} and type the command
{\tt turnin311 1}.  The command will inform you whether
or not your submission succeeded. {\em Only submit one
copy of your program per team.  If you need to resubmit
an improved version your program, submit it from the
same account as the original so that the old version is
replaced.}

\bigskip
\noindent
{\bf Implementation Hints}
Use an ``unparser'' to print a concrete representation
for an abstract syntax tree.  Then you can directly compare test
input strings and output strings (up to differences
in whitespace and parentheses using for grouping).
\end{document}

