Assignment 3. CS330 Programming Languages,

Summer 2005 (due July 4)

Parsing Combinators and Datatypes (10% of grade)

Assignment Description

PLEASE READ CAREFULLY - MISSING
LITTLE DETAILS MIGHT COST YOU


  Things that you will learn by doing this assignment:
  1. Parsing combinators: a top-down approach to building lexical analyzers and parsers based on the use of higher-order functions
  2. The use of records and datatypes to represent structured information 
  3. Comprehending and extending existing code in SML

Formal languages are the basis of describing the syntax of programming languages and structured file formats such as HTML or XML. They are typically defined by a a grammar which is a set of production rules for each syntactic category. The task of parsing is to reverse the process of applying production rules i.e to take a string and discover how it could have been generated by the production rules for a syntactic category. Typically the output is a parse tree i.e.  a tree whose structure represents
the input in a format convenient for the particular task. In SML parse trees can
be represented elegantly as recursive datatypes.

For example, The following grammar can be used to parse binary expressions
in infix notation with precedence and parentheses: 
expr  -> expr + term | term
term  -> term * factor | factor 
factor -> (expr) | number
For example a datatype for representing circuits as parse trees would be: 
datatype circuit = CRES of real
                 | VRES of string 
                 | SER of circuit * circuit
                 | PAR of circuit * circuit

Parsing is the task of converting a string such as 
hello - 0.5 | 0.8

to a value of the datatype (the parse tree): 
val cir = PAR(SER(VRES("hello"),CRES(0.5)), CRES(0.8))

Introduction - Overview

The production rules suggest a very simple way of going about parsing
using a series of mutually recursive functions (1 for each rule in the grammar). The idea is to have a function for each syntactic category, and a recursive structure that reflects exactly the mutual recursion found in the grammar itseft. For example the procedure for parsing factor will recursively call the procedure for parsing
expr which may in turn call the procedure for parsing pterm again. Such
a style of programming is natural in a language like SML where recursion is the primary control mechanism.

In our ML implementation, we suppose that we have some input list of objects of arbitrary type 'a for the parser to consume. These might be simply characters
when doing lexical analysis or tokens. We avoid commiting ourselves to any particular type. Similary, the parser is allwed to construct objects of arbitrary type
'b from it's input. These might be for example be parse trees as members of a recursive datatype, or might be simply number if the parser is to take an expression and evaluate it. Now in general, parser might not consume all it's input, so we also make it ouput the remaining tokens therefore a parser will have type:

                         'a list -> b * 'a list

For example, when given the input characters (5 + 3) * 2 the function factor should process the characters (5+3) and leave the remaining characters *  2. It might return a parse tree for the p]rocessed expression using our earlier recursive type,
and hence we would have:
factor("(5 + 3) * 2") = (SUM(NUM(5),NUM(3)), "* 2")

So basically every function will consume as much input as it needs
to and then return the result followed by the remaining tokens as a tuple.


Parsing combinators are a technique for plugging parsers together
to form more complicated parsers. By giving them infix status,
we can make the ML parser program look quite similar in
structure to the original grammar defining the language. Exceptions
are used to handle control flow when a parser fails. The following operators
are defined: infix ++ that applies two parsers in sequence, pairing up their results,
and an infix || that tries first one parser, then the other. We then define
a many-fold version of ++ that repeats a parser as far as possible, putting the results into a  list. Finally, the infix >> is used to modify the results of a parser according to a function. we want ++ to be the strongest, followed by >> and || being the weakest.

Here is the ML code for parser combinators: 
(* Parser combinators *) 
infix 5 ++
infix 4 ||
infix 3 >> 

exception Noparse;

fun (parser1 ++ parser2) input = let val (result1, rest1) = parser1 input 
                                     val (result2, rest2) = parser2 rest1 
			         in
				     ((result1, result2), rest2)
			         end

fun (parser1 || parser2) input = parser1 input handle Noparse => parser2 input 


fun (parser >> transform) input = let val (result,rest) = parser input
				  in 
				      (transform(result),rest)
				  end

fun empty input = ([],input)

fun many parser input = ((parser ++ many parser >> (op::))
				|| empty) input handle Noparse=>([],input);
				      
fun some p [] = raise Noparse
  | some p (x::xs) = if p(x) then (x,xs) else raise Noparse

fun several p = many (some p) 

fun finished input = if input = [] then (0,input) else raise Noparse;


Here is some example code that shows how they
can be used to do simple lexical analysis and parsing (This code
is just a sketch. You will have to modify and extend the code
accordingly for this assignment). 
(* Lexical analysis - incomplete *) 

datatype token = Name of string | Num of string | Other of string 

val lex  = let fun K x y = x 
	       fun collect(h,rest) = Char.toString(h) ^ implode(rest)
	       fun upper_alpha c = #"A" <= c andalso c <= #"Z" 
	       fun lower_alpha c = #"a" <= c andalso c <= #"z" 
	       fun digit c = #"0" <= c andalso c <= #"9"
	       fun letter c = lower_alpha c orelse upper_alpha c 
	       fun alpha c = letter c orelse c = #"_" orelse c = #"'" 
	       fun alphanum c = alpha c orelse digit c 
	       fun space c = c = #" " orelse c = #"\n" orelse c = #"\t"
	       val rawname = (some alpha ++ several digit) >> (Name o collect) 
	       val rawnumeral = (some digit ++ several digit) >> (Num o collect)
	       val rawother = some (K true) >> (Other o Char.toString)
	       fun fst(x,y) = x
	       fun snd(x,y) = y
	       val token = (rawname || rawnumeral || rawother) ++ several space >> fst 
	       val tokens = (several space ++ many token) >> snd 
	       val alltokens = (tokens ++ finished) >> fst 
	   in
	       fst o alltokens o explode
	   end;


(* Parsing Notes - Incomplete  *) 

fun name (Name s::rest) = (s,rest) 
  | name _ = raise Noparse

fun numeral (Num s::rest) = (s,rest) 
  | numeral _ = raise Noparse

fun other (Other s::rest) = (s,rest) 
  | other _ = raise Noparse



(* To define mutually recursive functions in ML use the 
keyword and. Here is a sketch of the recursive descent 
parser *) 

(* 

fun expr input   = 
and term input   = 
and factor input = 

*)

Part 1 (Binary resistance circuits using parser combinators - 6 pts)

Your task is to implement lexical analysis and parsing for assignment 1 (binary resistance circuits) using parser combinators. Write one lexical analyzer (1pt)
and 3 parsers. The first parser (1pt) will accept circuits in prefix form
with no variables and compute the directly the total resistance.
The second parser will accept circuits in prefix form with variables
and construct a parse tree represented as a recursive datatype.
The third parser (2pt) will accept circuits in infix notation with the
series operator - having higher precedence than the parallel operator |.
That means that the experssion: 0.5 |  0.2 - 0.3 will be interpreted
as 0.5 | (0.2 - 0.3) rather than (0.5 | 0.2) - 0.3. The grammar for arithmetic
expression provided above will help you with this task.


Part 3 (Bibtex file parsing - 4 pts)


This part of the assignment is based on parsing a simple
subset of the bibtex file format for storing bibliographic references.
The task is to build a parser for a simplified version of the bibtex
format and represent the file using datatypes and records.

Here is an example bib file: example.bib

As you can see there are two type of entries. The ones
starting with @Article are journal articles and the ones
starting with @InProceedings are conference articles.
As you can see there are no pages for the conference
articles. (this is a simplified version of the actual bibtex format).
You can assume that each field (Authors, Title etc) will be
provided in the order of the example bib file. Journal articles
and conference articles can be mixed arbitrarily.

Use the following datypes/types to represent the bibliography
file: 

type name = {fnm:string, lnm:string};  (* first name, last name *) 

type inproc_info = {title:string, 
		    authors:name list, 
		    conf:string, 
		    year:int,
		    id:string};

type journal_info = {title:string, 
		     authors:name list, 
		     year:int,
		     journal:string,
		     pages: string,
		     id:string};


datatype BibEntry = INPROC of inproc_info
		  | JOURNAL of journal_info 

type Bibliography = BibEntry list;

Your task is to build a lexical analyzer, parser and
printer for bibliographies. Here is the top
level bibparse function (you will need to
write the lex and parse parts using parser combinators) : 

fun bibparse fname = let val lin = TextIO.inputAll(TextIO.openIn fname)
			 val pin = lex(lin)
			 val res = parse(pin)
		     in
			 res:Bibliography
		     end;


For example: 

bibparse("example.bib");
val it =
  [JOURNAL
     {authors=[{fnm=#,lnm=#},{fnm=#,lnm=#}],id="TC02",
      journal="IEEE Transactions on Speech and Audio Processing",
      pages="100-115",title="Musical Genre Classification",year=2002},
   JOURNAL
     {authors=[{fnm=#,lnm=#},{fnm=#,lnm=#}],id="TC00",
      journal="Organized Sound",pages="15-23",
      title="Marsyas a framework for Audio Analysis",year=2000},
   INPROC
     {authors=[{fnm=#,lnm=#},{fnm=#,lnm=#},{fnm=#,lnm=#}],
      conf="Proceeding of the International Conference on Music Information Retrie#",
      id="KBG04",title="Query-by-Beat-Boxing Music Retrieval for the DJ",
      year=2004}] : Bibliography
In addition implement a function print_bib that outputs
the bibliography in a more readable format. For example:
(Notice: the In before the booktitle in the conference article
and the abbreviation of the first names). 
print_bib("example.bib");
Musical Genre Classification
G. Tzanetakis, P. Cook
IEEE Transactions on Speech and Audio Processing
100-115 2002

Marsyas a framework for Audio Analysis
G. Tzanetakis, P. Cook
Organized Sound
15-23 2000

Query-by-Beat-Boxing Music Retrieval for the DJ
A. Kapur, M. Benning, G. Tzanetakis
In Proceeding of the International Conference on Music Information Retrieval
2004


I hope you find this assignment a good learning experience
and enjoyable.

EXTRA CREDIT

  1. (1pt) Implement the bibtex lexical analyzer and parser using ML-Lex and ML-Yacc. You will have to find the documentation and learn about these tools by yourself (that's why it's extra credit)
  2. (1 pt) Produce html output that use CSS (Cascading Style Sheets) to control the appearance of the bibliographic elements. Generate nice looking html bibliographies
  3. (1 pt) Make the parser independent of the order in which the fields of each bibliographical entry appear.
  4. (2 pt) Support the full syntax of bibtex files. 

Practical matters 

You must submit the full source code (including the functions I provide) in
a single .sml file. Please don't use any archiving/compressing software (such as winzip, rar, tar, gzip etc).

Check the course web page for submission instructions (should be
similar to the web submission system you have used for
other courses) and if you run into problems email me and we will figure it out.

Late assignment policy:  If the assignment is submitted
within three days from when it was due, you will get half the grade you
would get if you had submitted on time. You will not be able
to submit after three days. (exceptions to this rule only
if you have a VERY important reason).

IMPORTANT: The careful design and documentation (i.e comments) of
your code will be important factors in your grade. If there is a bug
it's better to report it than hide it. Be honest, precise and clear and
you shall be rewarded. NEVER (at least in this class) sacrifice
clarity for efficiency of execution.