Assignment 2

210: Compiler Design
Fall 2014
Assignment 2a, 2b and 2c
Due dates:
Part 2a: October 16th, 2014, 10:15 a.m.
Part 2b + 2c: October 31st, 2014, 10:15 a.m.
30 Points
1
Introduction
The objective of this assignment is to construct a lexer (lexical analyzer) and a parser (syntax analyzer) for the
complete Javali programming language. Please refer to the Javali language specification for the syntax and the
rules for identifiers, constants, etc. The updated Javali language specification is available on the course web
page.
You may notice that the Javali syntax includes a few features that will not be handled by the compiler later
on (at least not by the bare-bones compiler that you are asked to develop). For example, the syntax allows nested
method definitions, but our code generator is not expected to deal with them. Further, the Javali syntax accepts
certain incorrect constructs, such as this[0], that will be rejected by the semantic analyzer later on. You are
not required to parse constructs that you will not support (e.g., nested methods) or constructs that are not correct
(e.g., this[0]). If you would prefer, however, to parse such constructs, you are permitted to do so, so long as
in Assignment 3 your semantic analyzer rejects them. Note that if you accept a different set of programs from
the reference solution, it may be necessary to modify the .ref files to avoid unit test failures.
The lexer and parser are to be constructed using the ANTLR parser generator tool. ANTLRWorks is a
convenient IDE for ANTLR that we highly recommend for this assignment. We provide the ANTLRWorks jar
file in the fragment’s lib directory. Information about ANTLR and ANTLRWorks is available online, however,
a detailed introduction will be given in class.
2
Task
To construct the lexer and parser for Javali, you need to complete the two files src/cd/parser/Javali.g
and src/cd/parser/JavaliWalker.g. The file src/cd/parser/Javali.g defines an ANTLR
parser grammar. A parser grammar specifies both the lexical rules and parser rules for the Javali language.
In addition, the parser grammar contains tree construction rules (rewriting rules) to build an intermediate AST.
This AST is only internal to ANTLR. The file src/cd/parser/JavaliWalker.g defines an ANTLR tree
grammar. A tree grammar specifies a visitor to visit the intermediate AST generated by the parser grammar.
A tree grammar may contain Java action code that is executed while visiting the intermediate AST. In this assignment, you are asked to incorporate appropriate action code to map the ANTLR intermediate AST to the
framework’s AST. This can be done by instantiating the appropriate subclasses of src/cd/ir/Ast in the
action code.
1
Part 2a: lexer and parser rules
In the first part of this assignment you are asked to construct the lexer and the parser for Javali. The input to the
lexer is a series of characters representing the Javali program, and the output is a sequence of tokens. The input
to the parser is the sequence of tokens produced by the lexer. Both lexer and parser rules ought to be specified
in the file src/cd/parser/Javali.g.
We have given a first due date for the first part of the assignment. This due date is mandatory and you are
required to turn in the parser grammar separately from the rest of the assignment. We will provide a sample
solution for the first part such that you can complete the assignment if you encountered problems. If you are
confident of the correctness of your parser grammar we highly recommend that you try to start working on the
next parts of the assignment immediately after completing the first part (2a).
Part 2b: rewriting rules (ANTLR AST generation)
Once you have completed the lexer and parser rules, you are asked to extend your parser grammar with rewriting
rules. A rewriting rule tells ANTLR how to hierarchically structure the sequence of tokens the parser receives
from the lexer. The output of a rewriting rule is an intermediate ANTLR AST.
Part 2c: walker (Javali AST generation)
Once you have completed the rewriting rules and have constructed the intermediate ANTLR AST, you are asked
to visit this intermediate AST and generate a proper AST, using the framework’s AST classes src/cd/ir/Ast.
For this purpose, you must define an ANTLR tree grammar (file src/cd/parser/JavaliWalker.g) and
include appropriate Java action code. The input to the tree grammar is the intermediate ANTLR AST, its output
is a list of class declarations (List<ClassDecl>).
3
Framework
We have included the necessary ANTLR jar files in the framework. Also, there exist appropriate targets in the
Ant build file to allow the framework interface with ANTLR. The target antlr-parser-source generates
the corresponding Java lexer, parser, and walker from your parser grammar and tree grammar files. Note that in
Eclipse you should press F5 to refresh the view of the directory after executing antlr-parser-source, so
that Eclipse knows that new files have been generated, and/or that existing files have changed. Otherwise,
the generated files will not be (re)compiled. To complete this assignment, you only need to edit the files
src/cd/parser/Javali.g and src/cd/parser/JavaliWalker.g. As always, we provide a few
simple test programs but you are required to add some of your own!
4
Debugging your parser grammar and tree grammar
Unlike other assignments, in this assignment you cannot use the framework’s unit test functionality right from
the start. Only once you have completed your parser and tree grammar, the corresponding Java lexer, parser, and
walker files can be generated (using antlr-parser-source) and you can unit test your implementation as
usual. Before getting there, you can use ANTLRWorks debugging facility to test your parser grammar and tree
grammar.
How to use the ANTLRWorks debugging facility:
• Preliminaries: In ANTLRWorks, menu File-Preferences-Compiler-Custom Classpath,
set the path to your compiler’s bin directory.
2
• Debugging your parser grammar: Open Run/Debug in ANTLRWorks. Either type in a sample
Javali program into the text area or select a Javali program from the file system. Run the program (either
step-by-step or at once) and consult the generated parse tree and ANTLR AST.
• Debugging your tree grammar: Open Eclipse and delete any generated ANTLR parser or walker files
(Ant clean-antlr-parser target). Execute the Ant target antrl-debug-parser-source.
Edit the class test/cd/test/TestSamplerPrograms.java to run only one file and execute it.
You will notice that JUnit blocks. Switch to ANTLRWorks. Open Run-Debug Remote. Change the
port number, if necessary (see below), and connect.
Depending on your platform, you may have to change the port number ANTLRWorks uses for debugging purposes. For changing the local debugging port number (debugging of parser grammar), open File Preferences and change the port number in the Debugger tab. For changing the remote debugging port
number (debugging of tree grammar), override the port number in the constructor of the generated
src/cd/parser/JavaliWalker.java file.
5
Assignment submission
Please ensure that your final submission is checked into Subversion by the deadline(s). To submit Part 2a please
create a copy of src/cd/parser/Javali.g and rename it as src/cd/parser/JavaliTeam.g. We
will submit the sample solution named as src/cd/parser/JavaliReference.g, please rename it accordingly. In addition to the parser and tree grammar files please include any test cases you created. To make it
easier for us to locate these test cases, place them in a subdirectory of javali_tests named A2_team. In
addition, it is very helpful if you include a comment at the top of the test file indicating what you are trying to
test. Finally, if there are any comments you should have on your solution, please provide a README file in the
CD1 A2 directory of your team’s Subversion directory.
3

Download Report