代写data留学生编程、c/c++程序设计代做

日期：2021-05-11 09:44

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.