Parsing
The 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; you need to add the parser and interpreter. 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. RoboGame
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. 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.
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. 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:
TO DO: complete 4 stages
You need 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.
It 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 1:
you need 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:
The following is an example program for this stage:
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):
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
1.Run the main method of the Parser class to check whether the parser parses programs
correctly. 2.Once they parse correctly, run the RoboGame and load the programs into the robots to see
whether the programs are executed correctly. The goal in stage 1:
Simple actions work. The robot can loop through a block of multiple actions. The parser throws errors on invalid strings. Stage 2:
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).
Here is an example program for this stage :
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(). The goal in stage 2:
The extended list of actions work. Conditions return the correct value. Sensors return the correct value. If and while loops behave as expected. Stage 3:
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 this stage is:
Here is a program for this stage parser:
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. The goal in stage 3:
The move and wait commands can now take an argument
If statements can take an else clause. Arithmetic expressions and boolean conditions work. Stage 4:
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 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 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. The goal in stage 4:
Variables and assignments work. Conditionals can have any number of elifs. The barrel sensors can take an argument.