COMP 261- Assignment 4

COMP 261- Assignment 4
code.zip
data.zip
Marking guide
NB! The submission link can be found on the left.
Important: Part of this assignment will be auto marked. Please do not modify the template code's file names or
class names. In particular, DO NOT modify the World.java file.
Goal
The goal of this assignment is to design and implement a parser and interpreter for a simple programming
language to control simple robots.
To Submit
The Java sources of the entire program, including your parser (your Parser.java file, along with any additional
files required by your parser) and the robot simulation code.
Your report.txt file. See end of handout for details of what this should include.
Introduction
A variety of applications allow the user to "script" the application, or otherwise specify domain-specific programs
to control, modify, or extend the application. Many advanced computer games have this facility, as do many
sophisticated editors. All these applications provide some kind of domain-specific language for specifying the
scripts/programs, and must therefore also have a parser and interpreter to parse and execute the scripts.
In this assignment, your task will be to design and implement a parser and interpreter for a simple programming
language that can be used to control robots for a simple robot game. The RoboGame program is written already;
your task is to add the parser and interpreter.
We will provide a set of programs for testing each stage of your language interpreter.
Although it is not part of the assignment, you may wish to publish any robot programs you write on the forum so
that other students can try running their robot programs against yours.
RoboGame
RoboGame is a program for a simple game involving two robots moving in a 2D grid based world that contains
barrels of fuel. The goal of the "game" is survival - the winner is the robot that still has fuel when the other one has
run out.
The robots start in opposite corners of the grid, and can move around the world. At each step, a robot may move
forward one step, turn left, right or completely around, or remain where it is.
The robots require fuel, and use some up on every step. Their fuel level is displayed by a coloured arc that gets
shorter as the fuel runs down. When the fuel level in one of the robots reaches zero, the robot stops and the game
ends.
Barrels of fuel appear at random places in the world. A robot that is on top of a barrel can take fuel from the barrel.
A robot can also steal fuel from the other robot, if it is next to and facing the other, and the other robot doesn't
have its shield up. Using the shield costs extra fuel.
Each robot is controlled by a program which determines its behaviour. The program may be provided by the user --
- if no program is provided the robot performs a built-in default procedure, which constantly chases the closest
barrel. So the real aim of the game is to write a robot program that will beat any other robot program.
The game has buttons for starting the game, and resetting the game to the start state. It also has a menu for
loading user programs into the robots.
The Robot Language
The robot language has commands directing the robot to perform various basic actions (move, turnL, etc) and
test various sensors (fuelLeft, wallDist, etc). It also includes control structures (loops and conditionals) and
operators for calculating and comparing. A grammar for the full language is given below.
Note: In this grammar (and later ones): Uppercase terms are NON-TERMINALS, terminals are enclosed in double
quotes, [...] means optional, * means zero or more occurrences of the preceding item, + means one or more
occurrences of the preceding item, | is used to separate alternatives, ::= separates the left and right hand sides of a
definition, and VAR and NUM are defined by regular expressions.
PROG ::= STMT*
STMT ::= ACT ";" | LOOP | IF | WHILE | ASSGN ";"
LOOP ::= "loop" BLOCK
IF ::= "if" "(" COND ")" BLOCK [ "elif" "(" COND ")" BLOCK ]* [ "else" BLOCK
]
WHILE ::= "while" "(" COND ")" BLOCK
ASSGN ::= VAR "=" EXP
BLOCK ::= "{" STMT+ "}"
ACT ::= "move" [ "(" EXP ")" ] | "turnL" | "turnR" | "turnAround" |
 "shieldOn" | "shieldOff" | "takeFuel" | "wait" [ "(" EXP ")" ]
EXP ::= NUM | SEN | VAR | OP "(" EXP "," EXP ")"
SEN ::= "fuelLeft" | "oppLR" | "oppFB" | "numBarrels" |
 "barrelLR" [ "(" EXP ")" ] | "barrelFB" [ "(" EXP ")" ] | "wallDist"
OP ::= "add" | "sub" | "mul" | "div"
COND ::= RELOP "(" EXP "," EXP ")" | and ( COND, COND ) | or ( COND, COND ) |
not ( COND )
RELOP ::= "lt" | "gt" | "eq"
VAR ::= "\\$[A-Za-z][A-Za-z0-9]*"
NUM ::= "-?[0-9]+"
Notes:
None of the actions require arguments, but move and wait can take an optional argument.
The conditions in if and while statements can involve comparisons of integer valued expressions, or logical
combinations of them using and, or and not.
Expressions specifying values (EXP) can be sensor values, actual numbers, variables, or arithmetic expressions
using add, sub, mul, or div.
Expressions are written in a prefix/functional form (e.g. eq(barrelFB, 0) or add(5,1)) for ease of parsing.
This will be replaced by infix expressions in the last part of the assignment.
Variable names must start with a $, and variables can have numeric values assigned to them. The specification is a
Java regular expression that matches variable names.
Numbers are integers, with an optional -ve sign. The specification is Java regular expression that matches
numbers.
The sensors oppLR, oppFB, barrelLR, and barrelFB return the position of the opponent robot or the closest
barrel, relative to the current position and direction of the robot. LR means the distance to the left (-ve) or right
(+ve) , FB means the distance in front (+ve) or behind (-ve). If there are no barrels at present, barrelLR and
barrellFB will return a very large integer.
The sensors barrelLR, and barrelFB both take an optional argument, as in barrelLR(n) or
barrelFB(n), in which case they refer to the nth closest barrel.
Any amount of white space (blanks, newlines and tabs) may occur between two adjacent terminals.
Here is a program in this language, along with some comments:
01 while (gt(fuelLeft, 0)) { // loop as long as fuel left is > 0
02 if (eq(numBarrels, 0)) { // if there are no barrels, then wait
03 wait;
04 } elif ( lt(add(oppFB,oppLR), 3) ) { // if opponent is close
05 move(oppFB); // (actually a wrong calculation!)
06 } else {
07 $lr = barrelLR; // put the relative position of
08 $fb = barrelFB; // closest barrel into variables
09 if (and(eq($lr, 0), eq($fb, 0))) { // if robot is on top of a barrel
10 takeFuel; // take the fuel
11 } else {
12 if (eq($fb, 0)) { // otherwise, turn and move
13 if (lt($lr, 0)) { // towards the closest barrel
14 turnL;
15 } else{
16 turnR;
17 }
18 } else {
19 if (gt($fb, 0)) {
20 move;
21 } else {
22 turnAround;
23 }
24 }
25 }
26 }
27 }
The RoboGame program
The RoboGame program consists of the following files:
RoboGame.java has a main method which constructs the user interface.
WorldComponent.java manages the display of the state of the game.
World.java contains code for simulating the world.
Robot.java contains code for the individual robot objects. Your interpreter will call methods from the Robot
class.
RobotProgramNode.java defines the type for nodes in the abstract syntax tree your parser will construct. Each
RobotProgramNode will have an execute method that takes a robot, and executes the program in the node on
that robot.
Parser.java will contain your parser and interpreter. The very top level of the parser is already provided. The file
also contains a main method that will help you test your parser quickly without having to run the whole
RoboGame program.
ParserFailureException and RobotInterruptedException declare exceptions used by the parser and
robot simulator.
Whatto do?
Your task is to write a parser and interpreter which can read and parse a robot program from a file, and then
execute it.
More specifically, you are to complete Parser.java by writing all the parse methods, and to define classes for
the different types of AST node, along with the methods in those classes (e.g. execute) that define the
interpreter.
The assignment lays out a sequence of increasing subsets of the language which you should implement one at a
time. You should not attempt to build the parser for the whole language at once!
Stage 0: Getting started (40%)
For stage 0, you are to write a parser that can parse and execute a small subset of the language that has actions
and loops without conditions, given by the follow grammar:
PROG ::= STMT*
STMT ::= ACT ";" | LOOP
ACT ::= "move" | "turnL" | "turnR" | "takeFuel" | "wait"
LOOP ::= "loop" BLOCK
BLOCK ::= "{" STMT+ "}"
The following is an example program for this stage:
move; move; move; turnL ;
wait;
loop{
 move; move; turnR;
 move; move; turnR;
 move; turnR;
 move; move; turnR;
 takeFuel;
}
You will need to define a node class for each of the non-terminals. It is also sensible to define a node class for each
of the actions (or perhaps use an enum). Each node class should have an execute(Robot robot) method. The
execute method for an action node will call the relevant method from the Robot class on the given robot. For
example, for the TurnLNode class, it might be:
Note that the method name in the Robot class is not necessarily the same name as the command in the robot
language.
The execute method for LoopNode will not call methods on the robot directly, but will repeatedly call the
execute method of the BlockNode that it contains. Similarly, the BlockNode will need to call the execute
method of each of its components in turn.
The node classes should also have a toString method which returns a textual representation of the node. The
nodes corresponding to the PROG, STMT, LOOP and BLOCK rules will need to construct the string out of their
components. For example, the LoopNode class might have the following method (assuming that block is a field
containing the BlockNode that is contained in the LoopNode):
1 public void execute(Robot robot) {
2 robot.turnLeft();
3 }
1 public String toString() {
2 return "loop" + this.block;
You will also need to create a parse... method for each of the rules, which takes the scanner, and returns a
RobotProgramNode.
Hint: There will be a lot of node classes. You can put each of them in a separate file, or you can include them all in
the Parser.java file as non-public classes, since they are only accessed by the parser itself. It depends on your
IDE which option is easier to handle.
Test your parser on the example program above and the other test programs that we will provide.
Run the main method of the Parser class to check whether the parser parses programs correctly.
Once they parse correctly, run the RoboGame and load the programs into the robots to see whether the programs
are executed correctly.
Write some test programs of your own to test different parts of the language and the behaviour of the robot.
Stage 1 Basic language (up to 60%)
For stage 1, you should extend your parser to handle the robot sensors, and IF and WHILE statements, as shown
in the following grammar. The conditions in IF and WHILE statements can be restricted to simple comparisons of a
sensor value with a number, e.g. lt(fuelLeft, 20) to determine whether there are less than 20 units of fuel left
(the robot starts with 100 units).
PROG ::= STMT*
STMT ::= ACT ";" | LOOP | IF | WHILE
ACT ::= "move" | "turnL" | "turnR" | "turnAround" | "shieldOn" |
 "shieldOff" | "takeFuel" | "wait"
LOOP ::= "loop" BLOCK
IF ::= "if" "(" COND ")" BLOCK
WHILE ::= "while" "(" COND ")" BLOCK
BLOCK ::= "{" STMT+ "}"
COND ::= RELOP "(" SEN "," NUM ")
RELOP ::= "lt" | "gt" | "eq"
SEN ::= "fuelLeft" | "oppLR" | "oppFB" | "numBarrels" |
 "barrelLR" | "barrelFB" | "wallDist"
NUM ::= "-?[0-9]+"
Here is an example program for this stage:
while ( gt(barrelFB, 0) ) { move; }
if (eq(barrelLR, 0)) {
 takeFuel;
}
if (lt(barrelLR, 0)) {
 turnL;
 while ( gt(barrelFB,0) ){ move;}
 takeFuel;
}
if (gt(barrelLR, 0)) {
 turnR;
 while ( gt(barrelFB,0) ){ move;}
 takeFuel;
}
wait;
loop {
 if ( gt(fuelLeft, 0) ) {
 move;
 turnL;
 }
}
You will need additional node classes and parse methods for the IF, WHILE, COND, and SEN rules. It is sensible to
have a class for each of the comparisons (less than, greater than, and equal) and for each of the sensors (fuelLeft,
etc) --- again, an alternative would be to use enums for these. The execute methods for the IfNode and
WhileNode will need to perform the logic of testing the value of the condition in the node, and then executing the
block in the node.
Note that the condition nodes (Cond, LessThan, etc) are a different type from RobotProgramNode since they do
not need an execute method, but instead need an evaluate method which takes a robot as an argument and
returns a boolean value. You will need to define an interface type for this category of node.
The Sensor nodes are different again. Like the condition nodes, they need an evaluate method, but their
evaluate method will return an int not a boolean. Their evaluate methods will need to call the
appropriate methods on the robot: getFuel(), getOpponentLR(), getOpponentFB(), numBarrels(),
getClosestBarrelLR() or getClosestBarrelFB().
3 }
Stage 2: Arguments, Else, and Expressions (up to 75%)
For this stage, you should extend your parser to handle:
actions with optional arguments: move and wait can take an argument specifying how many move or wait steps
to take.
if statements with optional else clauses
arithmetic expressions that compute values with sensors and numbers.
more complex conditions with logical operators and expressions; comparisons between any expressions, not just a
sensor and a number.
more restrictive form of integer constant, which does not allow leading zeroes.
The grammar for stage 2 is:
PROG ::= STMT*
STMT ::= ACT ";" | LOOP | IF | WHILE
ACT ::= "move" [ "(" EXP ")" ] | "turnL" | "turnR" | "turnAround" |
 "shieldOn" | "shieldOff" | "takeFuel" | "wait" [ "(" EXP ")" ]
LOOP ::= "loop" BLOCK
IF ::= "if" "(" COND ")" BLOCK [ "else" BLOCK ]
WHILE ::= "while" "(" COND ")" BLOCK
BLOCK ::= "{" STMT+ "}"
EXP ::= NUM | SEN | OP "(" EXP "," EXP ")"
SEN ::= "fuelLeft" | "oppLR" | "oppFB" | "numBarrels" |
 "barrelLR" | "barrelFB" | "wallDist"
OP ::= "add" | "sub" | "mul" | "div"
COND ::= "and" "(" COND "," COND ")" | "or" "(" COND "," COND ")" | "not" "("
COND ")" |
 RELOP "(" EXP "," EXP ")
RELOP ::= "lt" | "gt" | "eq"
NUM ::= "-?[1-9][0-9]*|0"
Here is a program for the stage 2 parser:
move(8);
turnL;
loop {
 while ( or(eq(numBarrels, 0),
 lt(add(oppFB, oppLR), add(barrelFB,barrelLR))) ) {
 if (lt(oppFB,0)) { turnAround; }
 else { if (gt(oppFB,0)) { move(add(1, div(oppFB, 2))); }
 else { if (lt(oppLR,0)) { turnL;}
 else { if (gt(oppLR,0)) { turnR;}
 else { if (eq(oppLR,0)) { takeFuel; }}}}}
 }
 if ( and(eq(barrelFB, 0),eq(barrelLR, 0))) { takeFuel; }
 else { if ( lt(barrelFB, 0) ){ turnAround; }
 else { if ( gt(barrelFB, 0) ) { move(barrelFB); }
 else { if ( lt(barrelLR, 0) ) { turnL; }
 else { if ( gt(barrelLR, 0) ) { turnR; }}}}}
}
You will need to:
Add node classes and parse methods to handle the expressions.
Extend your parse methods for if statements to handle an optional else. After parsing the condition and the
"then" block, the method needs to check whether there is an "=else=" to determine whether it needs to parse an
else block or simply return the IfNode without an else block. The execute method also needs to be extended.
Extend your parse methods for the move and wait actions to check for an optional argument. They should check
for a "(" to determine whether there is an argument or not. The execute methods also need to be extended. Note
that the Robot class does not provide a move or idleWait method with an argument - your execute method
needs to call the move or idlewait method the specified number of times.
Stage 3 Variables (up to 85%)
For this stage, you should extend your parser to handle:
variables and assignment statements.
a sequence of elif elements in an if statement.
optional arguments to barrelLR and barrelFB to access the relative position of barrels other than the closest
one.
The grammar for this stage and an example program are given above, under The Robot Language.
Variables are identifiers starting with a $, and can hold integer values. Assignment statements can assign a value to
a variable, and variables can be used inside expressions. Variables do not need to be declared. If a variable is used
in an expression before a value has been assigned to it, it is assumed to have the value 0. The scope of all
variables is the whole program.
Evaluating an expression now needs to be able to access a map containing all the current variables and their
values, and an assignment statement needs to update the value of a variable in the map. If a variable being
accessed which is not in the map should be added and given the value 0.
The Robot class provides four methods for accessing relative barrel position: getClosestBarrelLR(),
getClosestBarrelFB(), getBarrelLR(int n) and getClosestBarrelFB(int n). The last two return
the relative position of the nth closest barrel, allowing the program to identify barrels other than the closest one.
With these, you could write robot programs that determine which barrel to aim for, if the opponent is already closer
to the closest barrel.
Stage 4: Challenge (up to 100%)
For this stage, you should extend your parser and interpreter to:
Allow infix operators and optional parentheses for both arithmetic and logical expressions.
Require variables to be declared before they can be used.
Allow nested scope, so that variables declared inside a block (i) are only accessible within the block, and (ii)
"shadow" any variables of the same name declared in the program or outer blocks.
The grammar for this stage is:
PROG ::= [ DECL ] STMT*
DECL ::= "vars" VAR [ "," VAR ]* ";"
STMT ::= ACT ";" | ASSGN ";" | LOOP | IF | WHILE | BLOCK
ASSGN ::= VAR "=" EXP
LOOP ::= "loop" STMT
IF ::= "if" "(" COND ")" BLOCK [ "elif" "(" COND ")" BLOCK ]* [ "else" BLOCK ]
WHILE ::= "while" "(" COND ")" BLOCK
BLOCK ::= "{" [ DECL ] STMT* "}"
ACT ::= "move" [ "(" EXP ")" ] | "turnL" | "turnR" | "turnAround" |
 "shieldOn" | "shieldOff" | "takeFuel" | "wait" [ "(" EXP ")" ]
EXP ::= NUM | EXP OP EXP | SEN | VAR | "(" EXP ")"
SEN ::= "fuelLeft" | "oppLR" | "oppFB" | "numBarrels" |
 "barrelLR" [ "(" EXP ")" ] | "barrelFB" [ "(" EXP ")" ] |
 "wallDist"
OP ::= "+" | "-" | "*" | "/"
COND ::= BOOL | COND LOGIC COND | "!" COND |
 EXP COMP EXP | "(" COND ")"
LOGIC ::= "&&" | "||"
COMP ::= "<" | "<=" | ">" | ">=" | "==" | "!="
BOOL ::= "true" | "false"
VAR ::= "\\$[A-Za-z][A-Za-z0-9]*"
NUM ::= "-?[1-9][0-9]*|0"
Implementing some of these extensions will require restructuring of the grammar in ways that have not (yet) been
addressed in the lectures.
To allow infix expressions, you will need to think carefully about how to ensure that the parser is able to choose the
right path.
To handle declarations, you will need to build a set of declared variables when the declaration is parsed, and then
check that any variables used in the program are in this set. You might consider making this set part of the map
used to store values when the program is executed. Note that a block can be now occur anywhere that a
statement can.
To allow declarations to be nested, you need to be able to add variables to the set of declared variables at the start
of a block, and remove them at the end of the block. This also means that you must be able to have more than one
occurrence of a given variable and be able to identify the one with the inner-most scope. You should start by just
implementing top level declarations and get that working before attempting to implement nested declarations!
Whatto hand in: code and report.
Submit:
Your Parser.java file and any additional files you required in your implementation if you chose to place them in
separate files.
A jar file of the complete program so that it can be run by the marker.
If you attempt Stage 4, please submit a separate source file and jar file for marking.
A brief report which lists the parts that you attempted, indicating what worked and what did. Include any of your
own robot programs that you tested your parser on. If your program does not work correctly, give test cases
showing what goes wrong and explaining what you think would be required to fix it.
In a separate document, saved as a PDF, answer the Additional Questions that are given below. Call the document
WrittenAnswers.pdf. Suggestion: your document could be simply hand-written pages photographed with a
phone, as long as the writing is very clear and legible.
Additional Questions (These are Worth up to 10% "bonus".)
NB! The marks you get below are worth up to 10% that can then be used to increase your total mark for A4 but still
have 100% as the overall limit.
In the following, vertical bars take precedence and indicate options. Uppercase variables indicate non-terminals
and lowercase terminals.
1. Suppose you have a lot of files and want to check whether they have valid names or not. A valid name starts
with "file" and ends with ".pdf" but there must be more (but standard) characters (eg: "file-about-stuff.pdf" is
allowed but "file.pdf" is not allowed). Give a regular expression which would check the filenames.
2. draw the (concrete) parse tree generated by a naive top-down recursive parser, for the string "abba" under the
following grammar rules:
A ::= a B
B ::= b B | a
3. describe in one sentence the strings accepted by the regex (ab)+c*
4. draw the Acceptor automaton for the regex (a|b|c)*d(e+)f
5. draw the Acceptor automaton for the regex (axy*z)|(bx+yz)
6. Which ones of the sentences (a) to (g) given below belong to the language defined by the following grammar?
MUD ::= MAD CHOP
CHOP ::= "stop" DOG | DOG "run" | "wet" DOG
MAD ::= [e−z0−9]+ | DOG
DOG ::= (yeh\s)∗(nah\s)∗(bro)+
sentence
(a) yeh nah bro stop bro
(b) bro bro bro bro bro run
(c) yeh bro stop yeh yeh yeh nah nah nah
(d) yeh09 wet bro
(e) ex wet yeh nah
(f) one1 wet bro
(g) 2020 dog run
Consider the following (partial) grammar rules:
T ::= NAMEOF | T "with" T | T "without" T | "(ie." T ")"
NAMEOF ::=
7. Complete the definition of NAMEOF using a regular expression (regex) so that it describes an uppercase letter
followed by one or more lowercase letters.
8. Change the grammar (from question 7) so that it is now LL1 (but still defines the same language).
9. Change the following grammar so that it can be parsed by a naive top-down recursive descent parser:
LIST ::= NUM | LIST "," NUM
NUM ::= [0-9]+
This topic: Courses/COMP261_2021T1 > WebHome > Assignments > Assignment4
Topic revision: