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<Token> remaining; public Successful ( AST ast, List<Token> remaining ) { this.ast = ast; this.remaining = remaining; } } Result parse ( List<Token> 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.