程序代写代做代考 Java Tutorial Week 5 (Solutions)

Tutorial Week 5 (Solutions)

Task 1. You were asked the remove left recursion from the following grammar.
E ::= E+E | E*E | -E | (E) | E/E | 0 | 1 | 2 | …
Here is one way of doing this.
E ::= -E | 0E’ | 1E’ | 2E’ | …
E’ ::= +E | *E | /E | ε
Task 2. You were asked the produce a top-down parser for the non-left-recursive grammar you produced in Task 1. Here is one possible solution using pseudo-code. Many others are possible.
abstract class Result {}

class Failure extends Result {}

class Successful extends Result {
public final AST ast;
public final List remaining;
public Successful ( AST ast, List remaining ) {
this.ast = ast;
this.remaining = remaining; } }

Result parse ( List tl ) {
tl match {

// if tl contains a T_Minus and a rest…
case T_Minus () :: rest => {
// try to parse the rest, and…
parse ( rest ) match {
// if that fails, everything fails
case Failure => Failure
// if it succeeds, return Successful with the Minus of the AST it returned
case Successful ( ( ast, rest2 ) ) => Successful ( ( Minus ( ast ), rest2 ) ) } }

case T_Int ( n ) :: T_Plus () :: rest => {
parse ( rest ) match {
case Failure => Failure
case Successful ( ( ast, rest2 ) ) => Successful ( ( Plus ( Integer ( n ), ast ), rest2 ) ) } }

case T_Int ( n ) :: T_Times () :: rest => {
parse ( rest ) match {
case Failure => Failure
case Successful ( ( ast, rest2 ) ) => Successful ( ( Times ( Integer ( n ), ast ), rest2 ) ) } }

case T_Int ( n ) :: T_Division () :: rest => {
parse ( rest ) match {
case Failure => Failure
case Successful ( ( ast, rest2 ) ) => Successful ( ( Div ( Integer ( n ), ast ), rest2 ) ) } }

case T_Int ( n ) :: rest => {
Successful ( ( Integer ( n ), rest ) ) }

case _ => {
Failure } } }
In practise it’s probably easiest to use java.util.Optional, see here.