|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).