程序代写代做代考 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 Success extends Result {
public final AST ast;
public final List remaining;
public Success ( 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 Success with the Minus of the AST it returned
case Success ( ( ast, rest2 ) ) => Success ( ( Minus ( ast ), rest2 ) )
}
}

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

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

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

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

case _ => {
Failure
}
}
}