COMP 261 – Assignment 4 RoboGame solved

Description

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:

 

 

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.

 

What to 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):

 

 

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.

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.

 

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().

 

 

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 "(" SEN "," NUM ")
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!

 

What to 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.