SCC312代做、代写Java编程语言

日期：2024-03-07 09:49

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 terminal

symbols.