Week 8: 4pm, Monday 23 April 2007
30%
Your task in this assignment is to implement a simple lexical analyser and parser for an invented language called J-. The syntactic definition of J- is provided separately. Three example J- programs - factorise.jm, queue.jm and dictionary.jm - are provided separately. The detailed semantic definition of J- will be provided later.
Your lexical analyser and parser should (a) recognise whether or not a given input is a syntactically correct J- program, (b) construct a parse tree for the program, and (c) print the resulting parse tree. The parse tree should not contain unnecessary unit productions. Your solution should report lexical and syntactic errors, but is not required to perform error recovery or semantic analysis.
The final compiler must be named jmc. If jmc is run with a command line argument, it must read its input from the file with that name. If it is run with no command line argument, it must read its input from standard input. In each case, it must write the parse tree to a file named listing.
It may be helpful to study the files provided for the TINY compiler in the text as preliminary reading.
You should implement your solution in standard C on dwarf (dwarf.ict.griffith.edu.au). Seek permisssion first if you wish to use any other language. We will test all submissions on dwarf and only on dwarf.
You may either write the lexical analyser and parser by hand, or you may use tools such as lex/flex and yacc/bison.
You must use the parse tree definitions we provide below. (This simplifies your task. And our task.) Parse tree definitions are provided in C only.
In addition, if you implement your parser using yacc/bison, you must also provide an LL(1) grammar for J- together with evidence or an argument that it is LL(1). (A complete proof is not required.) If you implement your parser by hand, presumably as a recursive descent parser, you must also provide an LALR(1) grammar as a yacc/bison specification (without the semantic actions).
Start work on the assignment now!
Make sure you understand the lecture notes up to lexical analysis and parsing, the TINY compiler in the text, the J- language, and the parse tree definitions before starting to design and implement your solution.
Design, implement and test your solution incrementally.
Test your solution thoroughly on a wide range of both correct and incorrect J- programs. Test that a wide range of possible lexical and syntactic errors are detected and reported.
Your submission must consist of a set of (human readable) source files, including a "Makefile", so the markers can compile your solution using "make"; it must also contain separate written documentation; and it and may require a demonstration of your solution. The written documentation must:
Solutions must be submitted as a set of source files (including a "Makefile"), and must compile and run on dwarf. The written documentation must be provided as an HTML document or a PDF file called documentation.html or documentation.pdf.
We require your source code to be well structured and well commented, and to conform to accepted software standards.
We require the organisation and English of your documentation to be of high quality.
See the submission instructions for more details.