Introduction. This task is about parsing. You will write a parser for a fragment of the simple programming language given here.

Task. Write a parser for the language specified by the CFG below.

 INT → ... 
 BLOCK → { ENE }
 ENE → E | E; ENE
 E →  INT | BLOCK | skip

The starting symbol is BLOCK. Your parser will take as input a token list, using the definition of tokens from Task 2 (given here). Your parser should return a suitable AST (i.e. an instance of the class Block), provided the input adheres to the syntax given above. Otherwise it should throw a SyntaxException given below. As the parser takes a token list as input, it might be helpful to see the grammar in a form where terminal symbols are token names. Since the grammar above does not parse the full language, not all valid tokens are used for valid programs, e.g. T_Then .

 BLOCK → T_LeftCurlyBracket ENE T_RightCurlyBracket
 ENE → E | E T_Semicolon ENE
 E →  T_Integer | BLOCK | T_Skip

Note that you are not asked to write a parser for the full language given here, only for the fragment above. You are free to write the parser in any form you want, whether 'by hand' or with a parser generator like CUPS, Yacc etc. As the grammar fragment is so simple, I recommend writing a top-down parser 'by hand'. As explained in the lectures, a top-down parser is naturally written using recursion rather than loops. If you find yourself using loop constructs, I recommend to rethink your approach (note: it is possible to write parsers with loops, I just personally find this much more cumbersome). If you use a parser generator to handle this task, I strongly recommend submitting the generator's source files too. I am unable to comprehend and comment on auto-generated parsers without source files: the auto-generated code is too complicated/weird for humans to comprehend directly.

Your parser has to implement the interface Parser given next.

interface Parser {
    public Block parse ( List < Token > input ) throws SyntaxException, 
                                                       Task3Exception; }

    class SyntaxException extends Exception {
    public String msg;
    public SyntaxException ( String _msg ) { msg = _msg; } }

class Task3Exception extends Exception {
    public String msg;
    public Task3Exception ( String _msg ) { msg = _msg; } }

Here List<...> is the list class imported from java.util.List. The AST class Block is given here. You need to use those classes and not modify them at all. The class SyntaxException should be thrown whenever input is encountered that does not adhere to the syntactic specification. Do not use this exception to indicate any other form of error -- use Task3Exception for any other error. Errors should be reported by exception only.

You will also have to implement a method create that, when called, returns an instance of the interface Parser. For this please use the following fragment, replacing ... with the appropriate code.

class Task3 {
    public static Parser create () { ... } }

For your convenience, here are the remaining definitions in one file.

The necessary Java files for all three tasks can be found for convenient download here:

• Zip archieve
• Github repo

Warning. Your code needs to compile against the signatures given to you here. Do not change them. You are welcome to add new classes. For your convenience you can find a file tester-skeleton3.java here that you can use to check if your submission compiles properly. Just download it, added to the directory containing all the files you want to submit, and run javac *.java. Note that tester-skeleton3.java does not test if you code has the right functionality. You will have to create and run your own tests to do that.