Semester Project

Purpose

To put it all together:

Due dates

You must submit a proposal via electronic mail by 9:00am on Tuesday, October 25. Your submission must be an attachment, and must contain your name(s) and the assignment subject. The attachment must be a PDF file, whose name is of the form ``FirstLast.pdf'' (e.g. ``JohnDoe.pdf''). You should be prepared to discuss your proposal in the lab on Wednesday, October 26. This part of the assignment is worth 10 points.

You must submit a specification of your abstract syntax tree, with a rationale for that tree structure, via electronic mail by 9:00am on Tuesday, November 8. Your submission must be an attachment, and must contain your name(s) and the assignment subject. The attachment must be a zip file, whose name is of the form ``FirstLast.zip'' (e.g. ``JohnDoe.zip''). You should be prepared to demonstrate your abstract syntax tree in the lab on Wednesday, November 9. This part of the assignment is worth 20 points.

You must submit a specification of your source program analyzer, with a discussion of the techniques that you used, via electronic mail by 9:00am on Tuesday, November 22. Your submission must be an attachment, and must contain your name(s) and the assignment subject. The attachment must be a zip file, whose name is of the form ``FirstLast.zip'' (e.g. ``JohnDoe.zip''). You should be prepared to demonstrate your analyzer in the lab on in the lab on Wednesday, November 23. This part of the assignment is worth 20 points.

You must submit your complete specification, with appropriate documentation and test cases, via electronic mail by 7:00pm on Friday, December 9. Your submission must be an attachment, and must contain your name(s) and the assignment subject. The attachment must be a zip file, whose name is of the form ``FirstLast.zip'' (e.g. ``JohnDoe.zip''). This part of the assignment is worth 50 points.

Background

The best way to evaluate the strengths and weaknesses of a tool is to apply that tool to a problem in your own area. When you do that, you are assured that the problem has not been chosen to showcase the tool.

Your problem must, however, be one that is within the general capabilities of the tool. Although we believe that the area of domain-specific languages is very broad (as evidenced by your answers to the first assignment in this course), you may have difficulty finding a suitable project. In that case, we suggest that you select a translator for a language designed for compiler construction courses. See the instructor for suggestions and references.

The remainder of this section gives a number of general criteria for an acceptable project. You may petition for a project that falls outside these guidelines, but you should secure an agreement about such a project from the instructor before you spend too much time on your proposal.

You should consult frequently with your instructor and fellow students during the course of the project. Use class time to bring up questions of strategy and tactics, and use the laboratories to get help with specific issues. Remember that this is a learning experience...

Source-to-source translation

Your project should lie in the general area of source-to-source translation. Homework 3, the expression interpreter, would not satisfy this condition but Homework 4, the course web site generator, would. A translator from a programming language to assembly language is also considered source-to-source in this context.

The source language should be some human-readable language and the target language should be something that can be checked by a computer. We strongly advise you not to use XML as a source language. While it is human-readable (barely) it is quite inconvenient to write and very difficult to parse.

XML is an appropriate target language for a number of applications, and an XML file can be checked against its DTD or fed into an application for which your project is a front end. Thus it satisfies the checkability aspect.

SPIM is an appropriate target language for any translator to assembly code. It is well-documented, and there is a public-domain assembler/interpreter that can be used to run your output. There is also an Eli specification for SPIM that you can use to handle the actual output task.

Name analysis

Analysis of your source language should involve establishing bindings for representations of entities. While the normal representations of such entities are identifiers, denotations may be appropriate representations in some applications.

Unless you have explicit agreement from the instructor, your language constructs must establish several scopes and/or name spaces that affect the binding process.

Structured output

Once you have built and decorated a source language abstract syntax tree, your translator must produce some form of structured output. There are two possibilities:
  1. You may output directly from the tree, either by using PTG directly or by unparsing your tree. (In the latter case your output must require some modification of the standard unparser behavior.)
  2. You may transform the shape of the tree using the tree parser and further attribute the transformed tree. In this case you may use printf, an existing specification (like SPIM), or an unmodified unparser to perform the final output.

Task

The implementation of your processor involves four deliverables:
Proposal
A written document describing the problem that you intend to solve, in enough detail that the knowledgeable reader can understand its complexity and recognize a finished product.

Abstract Syntax Tree
A specification for your AST, including a justification for its structure. It must be possible to generate a program from this specification that will accept any syntactically-correct source language file and construct the corresponding AST. Verification of the correct tree structure will be by examination with the execution monitor.

Analyzer
A specification of the analysis portion of your processor, including information about the strategy you used in carrying out that analysis. It must be possible to generate a program from this specification that will accept any file and either build a correct and completely decorated AST or provide appropriate error reports. Verification of the correct tree structure and decoration will be by examination with the execution monitor; verification of error reporting will be by examination of the reports.

Processor
A complete specification of your processor, including information about the strategy you used in carrying out the translation. It must be possible to generate a program from this specification that will accept any file and either produce the correct output or provide appropriate error reports. Verification of correct programs will be by checking the resulting output mechanically; verification of error reporting will be by examination of the reports.

Instructor
Revision 1.3 (2005/11/14 00:21:53)