COMP4403 - Compilers and Interpreters
Compilers and Interpreters
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP4403 - Compilers and Interpreters
Assignment
This is an individual assignment which involves modifying the LALR assignment 3 compiler for the PL0
language to add to add exceptions and exception handling.
Assignment Compiler Files
All sources for the assignment PL0 compiler are available as a3.zip (below). Please be sure to use the
version for this assignment and not the one used for the tutorials or another assignment. There are
differences (like the lexical tokens you need for this assignment are only defined in the assignment
version).
a3.zipSun 5 May 2024 12:52:23 AEST Save this .zip file and follow the instructions for setting up
a compiler project in IntelliJ
Setting up and running PL0 in IntelliJThu 21 May 2020 16:46:06 AEST
Brief documentation on assignment 3 filesSun 5 May 2024 11:50:12 AEST
Here is the documentation for
Java CUP [HTML]
JFlex [HTML]
For the most part you will not need these.
Please pay attention to course Blackboard announcments, and ensure you follow the course
discussion board for any updates and further information on the assignment.
Do not use imports for external packages other than those in java.util.*. Note that IntelliJ may
offer the option of importing an external package to resolve an issue; please avoid accepting
this option because it will often add an erroneous import that you will not need. Such imports
lead to the compilation failing in the environment in which your compiler will be assessed
because that environment does not include the external libraries. Please check you are not
importing external libraries before submitting.
You must only modify the files that must be submitted (see below).
You must not modify any other files because we will be testing your implementation using the
existing other files with your submitted files.
Please do not reformat the files because we would like to just print the differences between the
originals and the versions you hand in.
Please keep the length of lines in your files below 100 characters, so that we can print them
sensibly.
Please avoid using non-standard characters, e.g. Chinese characters, including in the
comments. Non-standard characters are not accepted by the Java compiler used to test your
assignment and all comments should be readable by the person assessing your assignment.
Please remove any debugging output before your assignment is submitted because
debugging output will cause your program to fail our automated testing of your assignment.
Either avoid using tabs or set your tabs stops to 4 spaces (this is the default for IntelliJ/Eclipse)
so that your files will print sensibly.
Read the fine print in detail before you start! And, most important, when you have finished
implementing the assignment, come back and reread the fine print again.
Overview
An exception e is declared in a declaration of the form
exception e;
Exceptions may be declared within the main program or local to a procedure. An exception e can be
thrown by a throw statement of the form
throw e
To handle an exception one uses a try statement, that consists of a statement list to be "tried", an
exception to be caught, and a statement list to be executed when the exception is caught. For
example, the following declares and uses an exception e.
var x : int;
procedure test() =
exception e;
begin // test
try
write x;
if x = 0 then
throw e
else
write 10/x
catch e
write -1
end // try-catch
end; // test
begin // main
x := 5;
call test();
x := 0;
call test()
end // main
Procedure test enters the "tried" statement where it writes out the value of x and then if x is zero
throws an exception or otherwise it writes out the value of 10/x. If the exception e is thrown, the
statement within the catch part is executed, which writes out -1. If the exception is not thrown, the
catch part is skipped and the procedure returns normally.
The catching of exceptions is dynamic in the sense that when an exception e is thrown, it is the most
recently entered (but not exited) try statement for e that catches the exception. The throw statement
can be within the execution of a called procedure. For example,
var
x : int;
y : int;
exception e;
procedure p() =
exception f;
begin //p
try
if x = 102 then
x := 101
else
throw f // caught within procedure p
catch f
y := 100;
throw e // caught in main program
end // try-catch
end; // p
begin // main
x := 102;
try
write x;
call p();
write x;
call p()
catch e
write y
end // try-catch
end // main
As a different example, if the "throw f" within procedure p was replaced by "throw e" then exception e
would not be caught by the catch (f) block in the procedure but it would be caught by the catch (e)
block in the main program. If the "throw e" within the "catch" part within procedure p is replaced by
"throw f", that throw will not be caught in either p or the main program and will become an uncaught
exception to be caught by the default exception handler (associated with the main program).
Syntax Changes
The new lexical tokens required for this assignment are the keywords "exception", "throw", "try" and
"catch" and the comma symbol ",". The keywords are in lowercase. These tokens have already been
added to PL0.flex and the terminals section of PL0.cup as KW_EXCEPTION, KW_THROW, KW_TRY,
KW_CATCH and COMMA.
A Declaration has a new alternative for declaring a list of one or more exception names.
Declaration → ... | "exception" ExceptionList ";"
ExceptionList → { IDENTIFIER "," } IDENTIFIER
The production for ExceptionList is given in Extended BNF, although you will not be able to use
Extended BNF with the Java-CUP parser generator.
The syntax of the throw statement and the try statement are as follows.
Statement → "throw" IDENTIFIER
Statement → "try" StatementList "catch" IDENTIFIER StatementList "end"
You need to add these productions and their associated actions to build the symbol table entries and
abstract syntax trees to PL0.cup.
You are expected to provide some syntax error recovery using Java CUP's "error" symbol, in particular
for exception declarations. Note that you must handle semantic errors appropriately, including
handling the situation when there is a syntax error, i.e., your compiler should not crash because of a
syntax error.
The Parser Generator Java-CUP
The parser specification for the compiler is specified in the file PL0.cup. You will need to add
productions (and their associated actions) to the specification and then run the parser generator Java-
CUP (manually or automatically) to generate the files CUPParser.java and CUPToken.java. Do not
modify these two Java files directly (even if you think you understand them (do you really?)) - remake
them from PL0.cup. You should make the compiler before you change anything just to see what forms
of messages to expect. When you make the compiler (before you modify it) there will be some
warning messages about the terminal symbols like ILLEGAL being declared but never used; these are
to be expected at this stage. Any new warning/error messages will be significant. Beware that if there
are Java-CUP errors reported, the Java files for the parser will not be generated, so check for Java-CUP
errors first. There is HTML documentation for Java-CUP available from the class web page (with the
assignment).
The Scanner Generator JFlex
All the lexical tokens for this version of the compiler have already been added to the lexical analyser.
The file Lexer.java is automatically generated by the scanner generator JFlex from PL0.flex; again, do
not modify Lexer.java - remake Lexer.java from PL0.flex.
Both Java-CUP and JFlex are available with the assignment files on the course web page, with
instructions on how to run them in IntelliJ. Java archives for Java-CUP and JFlex are part of the IntelliJ
project for the assignment.
Static Semantic Restrictions
An exception acts like any other identifier in terms of its scope. Exceptions may not be assigned or
compared.
The identifier named in a throw statement or a "catch" clause of a try statement must be an
exception and must be in scope. The statement lists in the try statement must be well formed.
Dynamic Semantics
When an exception e is thrown, the most recently entered (but not exited) try statement for e is
found (if it exists) and control is transferred to the corresponding catch statement. If no such try
statement exists, the default exception handler is used.
Note that a "tried" statement may call a procedure and within the execution of that procedure (or a
nested call on a further procedure and so on) an exception e may be thrown. If there have been no
intervening try statements catching exception e, then execution will transfer to the catch statement
list for e. This means that all the nested calls of procedures between the try statement and the throw
statement are exited. This effectively restores the execution context of the try statement before the
catch part is executed. (See below for ideas on how to achieve this.) In particular, if exception e also
happens to be thrown within the catch part, e is not caught by that catch part but some dynamically
enclosing try statement for e (if one exists). (This avoids an infinite loop if the exception e is thrown
within the catch statement for exception e - a common programming technique).
Within execution of a "tried" statement for an exception e, there may be another nested try statement
for exception e. The inner try statement will handle an occurrence of exception e within its "tried"
statement, and the outer try will handle any other occurrence within the outer try statement
execution, including an exception e thrown within the catch part of the inner try statement.
If an exception e is thrown when there is no currently active try statement for that exception then the
default exception handler is executed: it stops the program (using the STOP instruction with a code of
StackMachine.EXCEPTION_NOT_CAUGHT).
Implementation
The implementation scheme to be used for exceptions makes use of a list of exception frames for all
the currently active exceptions. The head of the list corresponds to the most recently entered (but not
exited) try statement, and the last element in the list corresponds to the default exception handler.
When an exception e is thrown, control is transferred to the catch part for the exception at the head
of the list, and the head of the list is removed. Before executing the statement within the catch part, it
checks to see if the thrown exception is the one handled by the catch part. If it is, the catch part
statement list is executed, but if not, the exception e is effectively thrown to the next catch part on
the active list (which has already had its head element removed); this effectively repeats the process
described in this paragraph.
The default exception handler handles all exceptions and hence doesn't bother checking the
exception code; it just stops the machine.
Parts of the implementation of exceptions have already been done.
ExceptionEntry has been added to SymEntry.java -- it records an exception code (an integer).
Each exception declaration throughout the whole program gets a unique exception code.
Class Scope has methods for adding and looking up an exception identifier.
You will need to implement the following.
Extend StatementNode.java (and StatementTransform.java and StatementVisitor.java) with
additional suitable abstract syntax tree representations.
Extend PL0.cup to recognise the new syntax for exceptions and to perform appropriate actions
to build the abstract syntax tree and symbol table.
Extend StaticChecker.java to handle declarations of exceptions and type checking of exceptions.
Extend CodeGenerator.java to implement the code generation for exceptions (see next section).
Object Code
The PL0 compiler generates code for the Stack Machine. A description of the stack machine is
available in StackMachineHandout.pdf. See also the file StackMachine.java (near the end) for details of
the instruction set.
Stack Machine modifications
To allow implementation of exceptions the stack machine has been extended with two additional
"registers":
1. the catch pointer (CP); and
2. the thrown exception code (TE).
TE holds the exception code of the thrown exception during the processing of a throw. CP holds the
address of the head of the list of exception frames. Each exception frame is dynamically created on
the stack when the corresponding try statement is entered. An exception frame consists of the
following three words (in this order):
1. the address of the previous exception frame (i.e., the next in the list);
2. the value of the frame pointer when the try statement was entered; and
3. the address of the code for the catch part.
When an exception e is thrown, control is transferred to the most recently entered (but not exited)
catch part. As well as a transfer of control this involves (effectively) exiting any procedure calls
between the throw and the catch part. Such a combined exit and transfer requires both the program
counter and the frame pointer to be updated. This can be accomplished with the help of the RETURN
instruction. The RETURN instruction is also used to implement a return from a procedure. The
RETURN instruction expects the (stack machine's) frame pointer to index a location in the stack that
contains:
the static or previous exception link (its contents are ignored by RETURN);
the dynamic link or frame link to which the frame pointer is set; and
the return or transfer address.
For use in implementing exceptions, RETURN instruction expects the frame pointer to address the
head catch frame; it sets the frame pointer to the frame link, sets the program counter to transfer
address. The stack pointer is then set back to the position it was before the try statement was
entered, i.e., it points to the (now deallocated) exception frame.