CS 259 Formal Languages

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. The final line only contains the end-of-file character. Every other line either defines a single function or is a single comment, but not both.

1.1 Function definitions

A function definition must comprise exactly 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

For instance the function that returns its argument incremented by 4 can be defined using the following syntax.

DEF ADDFOUR x { x+4 } ;
ADDFOUR is the function name, x is the parameter name and x+4 is the function body.

1.2 Comments

Every comment must begin with /* and end with */, but have no intervening */.

1.3 Additional Conditions

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 every function definition must be followed immediately by the end-of-line character.

3. Function names are non-empty strings of upper-case letters (A-Z) 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 (a-z).

5. The only exception to the rule stated in Section 1.1 is the function with name MAIN. No parameter name is allowed after MAIN, i.e. MAIN must be followed by one space and then the left brace after which the same requirements from Section 1.1 apply.

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. You may assume that numbers do not have leading zeros.

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.

13. A comment can use any ASCII character referenced so far.

14. Each line that has a comment must start with the delimiter /∗. The delimiter ∗/ that ends a comment must be followed by the end-of-line character.

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. Function definitions within comment delimiters are ignored.

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, then 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 LOOP.

• 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.