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