\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
run the OwlNet {\tt register} command for {\tt comp311}, which
will make the latest versions of drscheme and drjava available
as commands in your OwlNet environment.

For more information about DrScheme, read the documentation in 
\begin{quote}
\htmladdnormallink{
\verb|http://www.drscheme.org/tour/|}
{http://www.drscheme.org/tour/}
\end{quote}
and the DrScheme Help menu.  You can download DrScheme Version
205 from \htmladdnormallink{
\verb|drscheme.org|.}{http://drscheme.org}
DrScheme supports a variety of different Scheme dialects.
For this class, please use the "Pretty Big" dialect of Scheme under
Professional Languages.

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 
James Sasitorn (camus@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.  DrScheme Version 205 supports a similar unit
testing system for Scheme called (surprise!) SchemeUnit.  It is available for 
download from 
\begin{verbatim}
    http://sourceforge.net/projects/schematics/
\end{verbatim}
under the name {\tt schemeunit} in the list of file releases.  The downloadable
file is a "plt" file that you open using DrScheme.  When you open it, DrScheme
adds the library to the collection of libraries maintained by DrScheme.
Documentation for SchemeUnit is available at 
\begin{verbatim}
    http://schematics.sourceforge.net/schemeunit/schemeunit.html
\end{verbatim}
Chapter 2 entitled "Quick Start" (a single page!) provides enough information
to write unit tests for this assignment.

Note that unit testing conflicts in some cases with
the name hiding recommendations given for writing Scheme code in Comp 210
because lexically nested function definitions cannot be tested. In
your Scheme programs all non-trivial functions must be accessible
at the top-level.

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

\bigskip
\noindent
{\bf Scheme Version:}

In Scheme, the parser's input language is a stream of tokens
implemented as a parameterless ``read'' procedure {\tt p} that encodes
a token stream.  Given the procedure
{\tt p}, the application {\tt (p)} returns the next
token in the encoded stream, which is either a Scheme symbol, a Scheme integer,
or a special end-of-file object that is recognized by
the predicate \verb|eof-object?|.  

The Scheme library file {\tt lexer.ss} implements a scanner
(lexical analyzer) that converts either a file or a string
to a corresponding token stream.  Given a string {\tt s} specifying 
a file name, the application {\tt (make-file-lexer s)} returns
the corresponding token stream.  Given a string {\tt s}
consisting of program text, the application {\tt (make-string-lexer s)}
returns the corresponding token stream.

The parser's output language is {\sf Jam} abstract syntax,
which is defined in the library file {\tt abs.ss}.
If the parser determines that some
given input does {\em not\/} represent a legal {\sf Jam} program, it
should print an appropriate error message and terminate the parsing
process.  In Java, you can abort the computation by throwing
a {\tt ParseException} for which there is no {\tt catch} handler.

Note that {\tt lexer.ss} and {\tt abs.ss} are {\it Teachpack} (library) files
and should be loaded into DrScheme using the {\tt AddTeachpack} command
on the {\tt Language} menu.  You can load
both libraries
into DrScheme as a single
TeachPack library by placing both library files in your program directory
and designating the file {\tt lexer.ss} as the TeachPack to be loaded.
The module {\tt lexer.ss} requires the module {\tt abs.ss}, which forces
it to be loaded.
These library files are available on the web in the directory
\begin{verbatim}
    www.cs.rice.edu/\~javaplt/311/Assignments/1/scheme.
\end{verbatim}

Your parser should be expressed as a function {\tt parse} that takes a
string specifying a file name as its only argument and returns an
abstract syntax tree for the Jam expression in the specified file.
Your Scheme program should be stored in the file {\tt parser.ss},
which will be recognized by the {\tt turnin311} command and our
grading program.

\bigskip
\noindent
{\bf Java (GJ) Version:}

In Java, 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

{\bf Choice of Language:}
Generic Java and Scheme are the only languages permitted for this
assignment.

\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.
The Scheme lexer in the file {\tt lexer.ss} supports a peek
operation precisely for this purpose.  Given a token stream {\tt p}, 
an application of the
form {\tt (p $x$)} where $x$ is any argument ({\em e.g.}, the symbol
{\tt 'peek}) returns a copy of the next token in {\tt p} without removing
it from (or otherwise changing) {\tt p}. 

In the Java lexer, the method {\tt Token peek()} 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}

