1    Language Description

PLM (Programming Language of the Moment) is a language that allows users to write code that computes non-negative integers. A PLM program consists of several lines of code, each of which defines a single function (except for the final line; see Additional Condition 2 in the list below). For instance the function that returns its argument incremented by 4 can be defined using the following syntax.

DEF ADDFOUR x { x+4 }  ;

ADDFOUR will be called the function name, x will be called the parameter name and x+4 is the function body.

A function definition must contain the seven elements specified below. They must occur in a single line, exactly in the order listed below, and must be separated from each other by exactly one space character.

• keyword DEF

• function name

• parameter name

• left brace

• function body

• right brace

• semicolon

Additionally, PLM code must satisfy all Additional Conditions described below.

1. The character D from DEF must be the first character on each line with a function definition.

2. The semicolon in the last function definition must be followed immediately by the end-of- line character and then the end-of-file character.

3. Function names are non-empty strings of upper-case letters with one exception. The word DEF is a keyword and a reserved word in the language. Consequently, DEF cannot be used as the name of a function.

4. Parameter names are non-empty strings of lower-case letters.

5. The only exception to the rules is the function name MAIN. No parameter name is allowed after MAIN, i.e. MAIN must be followed by one space and then the left brace.

6. There can be no whitespace inside the function body, but remember that the body must be separated from the enclosing braces by one space on each side.

7. The function body is an arithmetic expression built from non-negative integers, the asso- ciated parameter name as well as function calls.  The only arithmetic operations allowed are addition and multiplication. Parentheses are not allowed, except in function calls (see next point). The function body must be non-empty.

8. Function calls have to refer to functions that have been defined as part of the same program. Function definitions are listed in no particular order. It is possible for a function body to make calls to functions defined later in the program. Functions can also call themselves.

9. Any function different from MAIN can be called.  Function calls are made by mentioning the relevant function name along with an argument enclosed in a pair of parentheses, e.g. ADDFOUR(3+5*6). No Whitespace can occur between the parentheses. The argument must satisfy the same constraints as function bodies. That is, it must be a non-empty arithmetic expression built from addition, multiplication, non-negative integers, the parameter name of the function that is making the call, as well as calls to other functions.

10. Every program must define the MAIN function.

11. No function can be defined twice.

12. No characters other than the specific ASCII characters referenced so far, are allowed. Here are some examples of PLM programs.

1. Example 1

DEF MAIN {  1+ADDFOUR(2+ADDFOUR(3)) } ;

DEF ADDFOUR x { x+4 } ;

2. Example 2

DEF ABCD xyz { BCD(xyz) }  ;

DEF BCD xy { 2*CD(xy) }  ;

DEF CD x { D(x)+EF(x) }  ;

DEF D x { 10 }  ;

DEF EF x { 10*x }  ;

DEF MAIN { ABCD(1) }  ;

3. Example 3

DEF QQ yy { 2*PP(yy)+3*QQ(yy) }  ;

DEF PP xx { QQ(xx)+3 }  ;

DEF MAIN { PP(0)+3 }  ;

Here are some examples of pieces of code that do not constitute a legitimate PLM program.

1. Non-example 1

DIF MAIN {  1+ADDFOUR(2+ADDFOUR(3)) } ;

This is not a PLM program because DIF is used instead of DEF.

2. Non-example 2

DEF P2P xXx { 3*Q()+R(6,Q(5)) };

This is not a PLM program due to any one of the following reasons.

(a) The function name P2P contains a number but function names are only allowed to

contain upper-case letters.

(b) The parameter name xXx contains an upper-case letter, which is not allowed.

(c) The function body contains calls to undefined functions Q and R. Also there are two spaces before }.

(d) The MAIN function is missing.

(e) There is no space between } and ;.

(f) The argument in the call to Q is empty.

(g) The argument in the call to R contains a ‘ , ’ which is not allowed.

2    Tasks

PLM programs can be executed by running the function body of MAIN. This may result in calls to other functions, which may in turn call further functions and so on. When a function call is made, we assume that the argument is always evaluated first and the value is then substituted for all occurrences of the corresponding parameter in the function body.  Sometimes this will produce a result:  the first two examples of PLM programs we saw earlier return 14 and 40 respectively. In cases when there are circular dependencies between functions (eg. Example 3), the program will not terminate. For the purposes of evaluation, we assume that multiplication takes precedence over addition.

2.1    Task one

Implement a parser (along with a lexer) that recognizes PLM programs.

2.2    Task Two

Extend the parser to an interpreter so that it can determine whether the input program returns a result or not.  If the former is the case, the result (a non-negative integer) should be printed out.

3    I/O Specifications

Your parser should read the input from System.in.  System.out should be used for output. Parsing errors should be reported on System.err. You must provide exactly one error message which gives exactly one reason  (out of possibly many reasons) why the input is not a PLM program. More details follow.

• If the input is a valid PLM program, two lines must printed out to System.out: the first line only contains the word PASS and the second line must contain information about the results, as explained in the next sentence.  If the program evaluates to a number, then the number should be printed out on the second line.   Otherwise, the line should read DIVERGENCE.

• If the input is not a PLM program, only a single line with FAIL should be printed out to the standard output stream. Two lines must printed out to System.err: the first line only contains the line number in the input where a violation has been identified and the second line gives an error message clearly describing this violation1 .  When the violation described is a missing MAIN function, then the line number of the violation should be 0. You are not allowed to simply use default javacc messages regarding uncaught exceptions as a reason for the input not being a PLM program.  Consequently,

you are expected to decode the javacc exceptions to provide your own error message. Here is the expected output for the examples given earlier.

Example 1

PASS

14

Example 2

PASS

40

Example 3

PASS

DIVERGENCE

Nonexample 1

FAIL

Nonexample 2

FAIL

Here is a sample of acceptable outputs to the error stream.

Nonexample 1

1

Missing keyword DEF

Nonexample 2

0

Missing MAIN function

4    Further Information

4.1    Submission instructions

Submit a single file named Assignment.jj containing your specification via Tabula.  The file Assignment.jj must cause javacc to generate your parser Assignment.java.   Compilation should work on DCS machines using the commands:

javacc Assignment.jj

javac *.java

1 The error messages will be evaluated manually, so there is no specific format that needs to be followed as long as the violation is clearly described by the error message and line number.

For reading an input file called test.txt, the command

java Assignment <  test.txt

should produce the required output.  The output of the parser should just appear on screen, it should not be sent to another file. To test your solution with the input file test.txt, invoke

java Assignment <  test.txt > output.txt 2>err.txt

and check if the contents of output.txt and err.txt conform to the specifications regarding the standard output and error messages respectively.

4.2    Evaluation policy and constraints

Task One is worth 50% and Task Two is worth 30%.  The remaining 20% is for readable and maintainable code. Comments and indentation improve readability. Moreover, 30% of the Task One score is for correctly determining whether or not the input is a PLM program and the remaining 70% is for accurate error reporting as described in the I/O specifications.

• The evaluation procedure will use JavaCC 7.0.10, so it is your responsibility to make sure that your submission compiles as intended with this version.

• Please base your submission on the template file available on the module page. In partic- ular, the file name and parser name must remain unchanged.

• Any change that must be made to the file name to rectify compilation/execution issues during evaluation will incur a penalty of -20%.

• No changes in your submitted code will be permitted after the coursework deadline has passed. The department’s standard late submission policy applies unless an extension has been granted.

• You may not use JJTree for this coursework.

• You are not allowed to employ StackOverFlowError to detect loops in the input program. Loops must be explicitly detected by your parser/evaluator and the relevant portion of your code appropriately annotated with comments.

• You may work with 32 bit signed integers and you may assume that each input file has at most 50 lines of at most 100 characters each.

5    Suggestions

You may discuss with fellow students the general workings of javacc or parsing, but you are not allowed to collaborate on the solution. The University of Warwick takes plagiarism seriously, and penalties will be incurred if any form of plagiarism is detected.  Copying, or basing your