Tutorial Week 5
Task 1. Consider the following grammar, which is ambiguous and left-recursive.
E ::= E+E | E*E | -E | E/E | 0 | 1 | 2 | …
Convert the grammar into a form that is free from left-recursion, but has the same language. It’s fine if your translation makes the language unambiguous.
Task 2. Write a top-down parser accepting the (left-recursing free) language you were asked to produce in Task 1. To simplify matters, assume the input to your parser is a list (=string) of tokens, for example as follows:
interface Token
class T_Plus () implements Token
class T_Times () implements Token
class T_Minus () implements Token
class T_Division () implements Token
class T_Int ( n : Int ) implements Token
Here is a suggestion for the data type of abstract syntax trees in pseudo-code.
interface AST
class Plus ( l : AST, r : AST ) implements AST
class Times ( l : AST, r : AST ) implements AST
class Minus ( arg : AST ) implements AST
class Div ( l : AST, r : AST ) implements AST
class Integer ( n : Int ) implements AST
No need to implement this in Java, pseudo-code is fine. But if you really want to know if you can do it, it’s probably best to test your ideas against a real compiler (and some real tests).