PLI Assignment 2

Due date

Week 13: 4pm Monday 28 May 2007

Weight

30%

Task

Your solutions must be written in C unless you have explicit permission of the convenor. Any supporting files will only be provided in C.

The two tasks are described below.

Task 1

Implement a semantic analyser for J-, the language whose structure was defined in Assignment 1. The semantic properties of J- are provided separately.

Please report any errors or ambiguities or unclarities of these semantic properties to the teaching team or on the discussion forum as soon as possible.

Your semantic analyser should (a) recognise whether or not a syntactically correct J- compilation unit satisfies the semantic condtions and (b) report all semantic conditions that it violates. Your solution should be based on traversal of the parse tree constructed in Assignment 1. Error reports should clearly identify the locations of each error or warning.

The following are three key questions for you to think about.

• What attributes need to be stored at nodes of the syntax tree? Different attributes may be required at different types of nodes. Do not rely on the generic extrainfo for these attributes.
• What information needs to be stored in the symbol table, and how should it be organised, specially given nested ranges?
• How should the syntax tree be traversed to evaluate attributes and check the various conditions? (Do not try hard to use a single pass algorithm, it's OK to traverse the syntax tree multiple times. That's one reason it's there.)

It may be helpful to adapt and extend the files provided for the TINY compiler in the text, but don't do so unthinkingly. We will give advice on how to adapt and extend these files.

Test your solution thoroughly on both correct and incorrect J- programs. Test that a wide range of possible semantic errors are detected and reported. Roughly speaking, you should provide at least one test case for each condition in the semantic specification.

Task 2

Implement a translator from J- to C where J- is the language whose structure was defined in Assignment 1.

This is a more open-ended but probably more interesting assignment. A grade of credit will be awarded for a solution that correctly translates J- source files into C in the simplest possible way, i.e., translating J- expressions into C expressions, translating J- method calls into C function calls, translating J- object constructor actions into calls of the C function malloc(), and so on.

Additional credit will be awarded for solutions that store J- local variables on an explicitly managed stack, that translate J- method calls into sequences of C statements that push argument values and bookkeeping information onto the stack and implement method calls and returns by goto statements, that explicitly manage a heap as a C data structure and allocate newly constructed J- objects from this heap, and so on.

I don't expect you to implement the standard J- library. This may make it impossible to actually run your translated J- programs. That's OK. But your translated J- programs must compile with gcc on dwarf.

The following are key questions for you to think about.

• How should each J- data type be represented in C? Recall that all J- data types are objects, even numbers.
• In particular, how should J- class instances be represented? What additional runtime information about class methods is required?

For this task you may assume that the source J- programs are syntactically and semantically correct,

Test your solution thoroughly on a wide range of J- programs. Roughly speaking, you should test that both simple and complex examples of each syntactic construct are tested.

Sample solution for Assignment 1

A sample solution for Assignment 1 may be provided if there is sufficient demand.

Advice

Start work on the assignment now! Do not leave it until the last week!!

Make sure you understand the lecture notes on the relevant topic, the TINY compiler in the text, and the J- language, before starting to design and implement your solution.

Design, implement and test your solution incrementally. By that, I mean think ahead, but only implement and test one new semantic property at a time.

Documentation

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:

• Describe how to compile and use your solution.
• Describe the design and implementation of your solution.
• Describe what was and what wasn't implemented and why.
• Describe what testing you performed.
• State which solution of Assignment 1 you used and why?
• Carefully describe the contribution of each member of your pair. You may do this separately if you can't agree. Be honest.
• Provide any addition usage notes or comments.

Assessment criteria and submission

Assessment of Assignment 2 will be based on functionality, implementation, testing, documentation, overall quality, and submission.

The general breakdown of marks is 25 for product (20 for functionality, 5 for structure) and 5 for documentation.

Solutions must be submitted as a set of source files (including a "makefile" and test files), and must compile and run on dwarf. Requests for exceptions may be made to the course convenor.

We require the organisation and English of your documentation to be of high quality.

We require your source code to be well structured and well commented, and to conform to accepted software standards.

See these additionalsubmission instructions.

Other information

• Plagiarism will be detected and dealt with severely according to standard University policy.
• All use of work done by others must be properly cited.
• Extensions will not be granted except for medical or other similar reasons.