February 2024 1 SCC312 Compilers Coursework 23/24
SCC312 Compilers Coursework 2023/24:
Recursive Descent Recogniser
1. General Instructions
Section 3 describes a grammar for a simple programming language rather like Ada. The task is to implement a
syntax analyser (SA) for this language using a recursive descent parser. The analyser’s sole function is make sure a
user’s source program is syntactically correct, and the SA should generate appropriate and helpful error messages
where required. The SA should terminate on encountering and reporting the first error. To be more precise, you
are expected to build a Syntax Recogniser with its purpose to recognise its input as a valid sentence in the
language specified by the grammar.
The coursework task is to implement part of a compiler for this language using a recursive descent parser.
1.1. Java Classes Provided
You are provided with the following Java classes:
(a) Token in a file Token.java, to represent a token returned by the lexical analyser stage. This has:
• a set of integer constants (becomesSymbol, beginSymbol, identifier, leftParenthesis, and so on)
representing the possible types of token in this language
• three public attributes (symbol, an int, which is one of the constants declared above; text, a String,
the characters making up the token; lineNumber, an int, the number of the line containing the
token)
• two constructors, and a static method getName to return the name (a String) of a token provided
as the single int argument
(b) CompilationException in a file CompilationException.java (see below)
(c) LexicalAnalyser in a file LexicalAnalyser.java, which is the lexical analyser for this programming language.
This has:
• a constructor with one String argument, the name of the file from which the tokens are to be read
• a method getNextToken (with no arguments), to return the next token read from the source text
• a main method, with which the operation of the lexical analyser can be tried out on a suitable file
(using a toString method supplied in the Token class)
(d) AbstractGenerate in a file AbstractGenerate.java. This is the abstract class you need to make concrete in
the Generate class you have to provide.
(e) AbstractSyntaxAnalyser in a file AbstractSyntaxAnalyser.java. This is the abstract class you need to make
concrete in the SyntaxAnalyser class you have to provide.
(f) Compile in a file Compile.java. This is the driver program for the whole coursework. This driver program
calls the parse method of the SyntaxAnalyser class for each file with a name of the form "programn"
(integer n ³ 0) (these files are in the coursework pack).
These classes can be found in the coursework pack ZIP folder that this document came along with. To help you
build and run your work, as well as generate this ZIP file to submit, some shell scripts have been included:
February 2024 2 SCC312 Compilers Coursework 23/24
1.2 Building the Code
For Windows Users:
Running ‘compile.bat’ will compile all java source files
Running ‘execute.bat’ will run the compiler against all supplied test programs
For Mac/Linux Users:
A makefile has been included which has the following functions (where ‘$>’ is your terminal prompt:
$> make
Compile all required java sources
$> make run
Run the compiler against all supplied test programs
$> make package
Build a submission .zip file - this is a ‘beta’ feature, check your submission file
has been created successfully before actually submitting it!
Note; The makefile requires a working install of the following: zip, java, javac, and make to work
correctly.
1.3 Java Classes To Be Implemented
1.3.1 SyntaxAnalyser
Write a Java class SyntaxAnalyser. Your SyntaxAnalyser class must include at an appropriate place a comment
line which includes the string "author" and your name.
The AbstractSyntaxAnalyser class contains the following methods :
abstract void _statementPart_()
throws IOException, CompilationException
abstract void acceptTerminal(int symbol)
throws IOException, CompilationException
public void parse(PrintStream ps)
throws IOException
You have to extend the above class as appropriate. Please note that the parse method is provided for you.
1.3.2. Generate
The parser must make use of the Generate class, which you must also supply by extending the AbstractGenerate
class. The AbstractGenerate class contains the following methods:
public void insertTerminal(Token token);
public void commenceNonterminal(String nonTerminalName);
public void finishNonterminal(String nonTerminalName);
public void reportSuccess();
public abstract void reportError(Token token, String explanatoryMessage)
throws CompilationException;
February 2024 3 SCC312 Compilers Coursework 23/24
The parser must demonstrate its operation by calling the Generate class methods as follows:
● insertTerminal(Token token) when it has correctly read a terminal.
● commenceNonterminal(String nonTerminalName) and finishNonterminal(String nonTerminalName) when it
respectively starts and finishes reading a non-terminal. For non-terminals specified in the grammar below, the
String nonTerminalName should be that specified in the grammar (for example "<procedure list>" or
"<assignment statement>"). For new non-terminals introduced by you, the String nonTerminalName should be
of the form "<new SOMETHING>".
● the void method reportSuccess() when it has successfully parsed the file.
Use these methods in a class Generate to display a trace (using System.out.println) of the operation of the
parser.
Error recovery is not required for this parser. Instead parse should report at the first syntax error encountered,
by calling reportError(Token tokenRead, String explanatoryMessage) in the Generate class. Implement a
suitable version of this method to indicate what the next erroneous token is, what the parser is trying to
recognise at this point, and the line number where the error is recognised. The method should finish by throwing
the exception CompilationException, which should eventually be caught by the parse method in the
SyntaxAnalyser class. As the exception reaches each of your parse methods, you should use it as an opportunity
to report where in the parse tree the error occurred. Hint: Look at the constructor for CompilationException.
The parse method should return in the normal way after processing a file, whether it reports success or failure, so
that it can then be called to start to process the next file (if any).
You may include in your Generate class either or both the constructor methods Generate() and Generate(String),
but no other methods than those specified in AbstractGenerate.
You should strive to make your error messages as helpful and as accurate as possible. You should consider how
the structure of the program can be used to get context for errors. We are deliberately not providing sample
error messages res.txt file but you should consider what a programmer of the language would need. When using
if statements, if you have more than 2 branches, please use a switch statement instead.
1.4 Marking criteria
Marks will be allocated according to the following criteria. The percentages are provided to guide you as to where
to dedicate your time and should be considered indicative only.
- SyntaxAnalyser (structure, design and implementation) 50%
- Generate (methods used, implemented and extension) 10%
- For the programs in the test set: 10%
- Success on syntactically correct programs: -
- Errors on syntactically incorrect programs:
- Detailed (correct) error messages 10%
- Recursive errors (stack traces) 10%
- Code quality and comments 10%
The coursework will be checked using a two step process; first automatically using a testing framework against
our provided classes and then manually to review the quality of your error messages, code commenting and other
criteria, and then finally marked according to letter grades.
February 2024 4 SCC312 Compilers Coursework 23/24
1.5 Test Data
The source texts to be analysed can be found in the “Programs Folder” provided. The output from “program0” is
provided as a guide as to what is expected in the way of output, so there is no need to include the results of
recognizing “program0”. To make it easier to see where sections start and end, I have indented the output for
program0, but note that you are not required to do the same in your output. Note: we will not be answering
questions about which programs should throw errors or fail to compile. Feel free to create your own sample
testing programs to test partial solutions while you are developing things.
2. Submission of Work
You should submit:
Listings of the code you have written (the classes SyntaxAnalyser and Generate, suitably laid out and
commented), and all the output from running your code over test files, both output.txt and res.txt should be
submitted. If you are using Mac or Linux, the makefile will help you do this.
Please note we have provided sample output from our worked solution on “program0”; you should use this as a
guideline for the output your recogniser produces, and as a check for the results of your recogniser on
“program0”.
Deadline: 16:00 (4pm), Friday, Week 19
WARNING : You *must not* change any of the pre-supplied Java classes. The 2 classes you submit will be
compiled and tested with the pre-supplied classes. If they fail to compile or run because they depend on some
alteration you have made to the pre-supplied classes, you will receive a mark of zero. Please ensure that you test
on the SCC lab machines with the version of Java installed there.
3. Grammar Rules for part of a Simple Programming Language
<statement part> ::= begin <statement list> end
<statement list> ::= <statement> |
<statement list> ; <statement>
<statement> ::= <assignment statement> |
<if statement> |
<while statement> |
<procedure statement> |
<until statement> |
<for statement>
<assignment statement> ::= identifier := <expression> |
identifier := stringConstant
<if statement> ::= if <condition> then <statement list> end if |
if <condition> then <statement list> else <statement list> end if
<while statement> ::= while <condition> loop <statement list> end loop
<procedure statement> ::= call identifier ( <argument list> )
<until statement> ::= do <statement list> until <condition>
February 2024 5 SCC312 Compilers Coursework 23/24
<for statement> ::= for ( <assignment statement> ; <condition> ; <assignment
statement> ) do <statement list> end loop
<argument list> ::= identifier |
 <argument list> , identifier
<condition> ::= identifier <conditional operator> identifier |
identifier <conditional operator> numberConstant |
identifier <conditional operator> stringConstant
<conditional operator> ::= > | >= | = | /= | < | <=
<expression> ::= <term> |
<expression> + <term> |
<expression> - <term>
<term> ::= <factor> | <term> * <factor> | <term> / <factor>
<factor> ::= identifier | numberConstant | ( <expression> )
An "identifier" is a sequence of one or more letters (a to z, A to Z) and digits (0 to 9), starting with a letter, and
excluding all the reserved words shown in bold above (procedure, is, integer, etc). Have a look at the
initialiseScanner method in LexicalAnalyser.java.
A "numberConstant" is a sequence of one or more digits (in which case it is of type "integer"), perhaps followed
by a decimal point and one or more digits (in which case it is of type "float"). A "stringConstant" is a sequence of
one or more printable characters (except ") with a " character at each end. Comments start with the symbol --
and terminate at the end of the line.
The distinguished symbol is <statement part>.
This simple language has no boolean or character data types; no arrays or records; no functions; the actual
parameters of all procedures must be identifiers, and are called by reference; only simple boolean expressions
(no not, and or or); only simple numerical expressions (no unary minus).
The grammar as written is not LL(1); it has left-recursive rules of the form:
<X list> ::= <X> | <X list> separator <X>
and rules of the form:
<something> ::= a X b | a Y g
where a, b and g are strings of terminals and/or non-terminals (a non-null) and X and Y are different
请加QQ：99515681  邮箱：99515681@qq.com   WX：codehelp