Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP4403 - Compilers and Interpreters
Assignment 3

Due date: 15:00 Thursday 25 May 2023

---

This is an individual assignment which involves modifying the assignment 3 compiler for the language PL0 to add named value and reference parameters, with defaults. I'd suggest adding value parameters first, and then default parameter expressions, and then add reference parameters.

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 this version). Note that the symbol table Scope and SymEntry and Type implementations have been extended already to provide support for procedure parameters.

· a3.zip Save this .zip file and follow the instructions for setting up a compiler project in IntelliJ

· Setting up and running PL0 in IntellliJ

· Brief documentation on assignment 3 files

Please pay attention to course Blackboard announcments, and ensure you follow the course discussion board (https://edstem.org/) 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 taking 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 may not include the external libraries. Please check you are not importing external libraries before submitted.

· 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 some Java compilers and all comments should be readable by the person assessing your assignment.

· Your implementation should be in Java 1.8. Set the IntelliJ preferences for the Java compiler to 1.8 (or use the "-source 1.8" option to the Java compiler).

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

Procedures with value and reference parameters

The declaration of a procedure includes a list of formal parameters. The type of each formal parameter is declared and it optionally has a default expression to be used when the parameter is not supplied in the call. Formal reference parameters are preceded by the keyword "var". For example,

  // A procedure fact with

  // a formal value parameter n of type int with a default value of 0 and

  // a formal reference parameter r of type int with no default

  procedure fact( n: int <- 0, var r: int ) =

   begin

    if n = 0 then

      r := 1

    else

     begin

      // The formal parameter n for the recursive call gets the value of the

      // local n minus 1, where the n within n-1 is the value of the formal

      // parameter n for this (calling) instance of fact.

      // The parameter r of the call is the formal parameter r of this

      // (calling) instance of fact.

      call fact( n <- n-1, r <- r);

      r := n * r

     end

   end // fact

The above procedure returns the value of factorial n via r, e.g., the call

    call fact( r<-f, n<-4 )

assigns f the value of factorial 4, i.e., 4*3*2*1 = 24. Note that as the parameters must be explicitly named in the call, they can be in any order. The following uses the default value for n, i.e. 0.

    call fact( r<-f )

It assigns f the value of factorial 0, i.e. 1.

Syntax Changes

The following lexical tokens have been added to the scanner module of PL0 already.

COMMA	→	","
GETS	→	"<-"

A procedure may have any number of formal value and reference parameters (zero or more). Each formal parameter has a type and an optional default expression. The syntax for a procedure declaration follows. It is given in Extended BNF, but you won't be able to use the EBNF directly in the parser generator Java-CUP (see below).

ProcedureDef → ProcedureHead '=' Block ';'
ProcedureHead → 'procedure' IDENTIFIER '(' [ FormalParams ] ')'
FormalParams → FormalParam { ',' FormalParam }
FormalParam → IDENTIFIER ':' TypeIdentifier [ '<-' Condition ]
FormalParam → 'var' IDENTIFIER ':' TypeIdentifier [ '<-' LValue ]

A procedure call has a list of actual parameters, each of which assigns an expression (Condition really (to allow for boolean expressions)) to a formal parameter.

Statement → 'call' IDENTIFIER '(' [ ActualParams ] ')'
ActualParams → ActualParam { ',' ActualParam }
ActualParam → IDENTIFIER '<-' Condition

Note that all actual parameter expressions are Conditions in order to allow for boolean value parameters. Type checking in the static checker is used to determine whether the parameter expression is valid, in particular for a reference parameter.

You are expected to provide some syntax error recovery using Java CUP's "error" symbol, in particular for formal and actual parameters. 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. Your handling of syntax errors does not have to exactly match that used for the sample solutions.

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 (using run configuration "Run CUP") 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. 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

First some terminology. Note that there are three different scopes to consider.

· formal parameter: the declared parameter in the procedure header

· actual parameter: the parameter in the call

· declaration scope: the (outer) scope in which the procedure is declared

· local scope: the (inner) scope containing the formal parameters and local variables of a procedure

· calling scope: the scope in which the procedure call occurs

The name of a procedure must be distinct from all constants, variables, types, and other procedures declared in the declaration scope (as already).

The names of all the formal parameters of a procedure must be distinct. For the formal parameter declarations, the formal parameters are treated as local to the procedure, but the type identifiers and default expressions used in the parameter declarations are treated as being from the declaration scope of the procedure (because the type and expression need to be shared with the calling context). To achieve this the type identifiers and expressions in the formal parameter declarations should be interpreted in the (outer) declaration scope of the procedure but the formal parameters should be defined within the (inner) local scope.

A formal parameter name x, may be the same as the name of a variable (or constant or type or procedure) declared non-locally; within the procedure, x refers to the formal parameter and any non-local x (a variable or other construct) is no longer accessible. Names declared locally within the body of a procedure p cannot have the same name as a formal parameter of p (unless they are within the local scope of a procedure nested within p), i.e., formal parameters are in the same scope as local variables of the procedure.

For a procedure call on p, the value of each formal parameter may be specified at most once using an actual parameter of the form id <- exp, where id is the name of a formal parameter of p and exp is an expression. If id is a formal value parameter of type T, exp must be assignment compatible with T. If id is a formal reference parameter of type T, exp must be of type ref(T). If a formal parameter to p does not have a corresponding actual parameter in the call, the default expression for the formal parameter is used; if there is neither an actual parameter nor a default expression for the parameter, that is an error. The default expression is defined in the declaration scope of the procedure and must satisfy the same typing rules as an actual parameter.

Dynamic Semantics

For a procedure call, it is as if fresh local variables corresponding to all the formal value parameters are allocated. All the value parameters are given the values of the corresponding actual parameter expressions (or default expressions if there is no actual parameter) and the statements in the body of the called procedure are executed. The actual parameter expressions are evaluated once at call time. The actual parameter expressions are evaluated with respect to the calling scope.

During execution of the body of a procedure any references to a formal value parameter treat it as a local variable of the procedure, and any access (read or write) to a formal reference parameter will (indirectly) access the corresponding actual parameter for that call each time.

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.

The Stack Machine provides features to help implement procedure calls.

· The CALL instruction assumes that the top of the stack contains the address of the procedure to be called and the second top of stack been set up with the static link for the call. It pops and remembers the address of the procedure (but leaves the static link on the stack where it is -- it becomes the first word of the new stack frame). It then pushes the frame pointer onto the stack to form the dynamic link, and sets the frame pointer to the address of the (already set up) static link. Finally it pushes the return address (location of the instruction after the call) onto the stack and branches to the (saved) address of the procedure.

· The RETURN instruction exits from a procedure. It automatically deallocates all the local variables (not parameters), pops the return address into the program instruction counter (pc), restores the frame pointer (fp) from the dynamic link, removes the dynamic and static links, and branches to the return address.

· The ALLOC_STACK instruction is used to allocate locations on the run-time stack. It pops an argument from the top of the stack which is the number of words to allocate for local variables on the stack (not parameters).

· The DEALLOC_STACK instruction is used to deallocate words from the run-time stack. It pops an argument from the top of the stack which is the number of words to deallocate from the stack (used for parameters).

The usual way to implement parameters in a procedure call is that the values of the actual parameter expressions are loaded onto the stack before the call is made. Because all the parameters are placed on the stack prior to the stack frame being set up for the procedure, all of the parameters are at negative offsets from the frame pointer for the called procedure.

It is suggested that you implement a procedure call as follows. Your generated code should:

· For each parameter (in reverse order of their declaration), load the value of the corresponding actual parameter expression onto the stack.

· Note that these parameters on the stack can be directly accessed from within the procedure by using negative offsets from the frame pointer. If you load the first parameter on to the stack last, it will end up having the least (negative) offset from the frame pointer (e.g., -1 for an integer).

· For reference parameters the actual parameter should evaluate to an absolute address.

· Set up the static link -- this is already done in the current code for parameterless procedures.

· Call the procedure (genCall may be of use for both the previous step and this step).

· Within the procedure, references to the formal parameters may be accomplished by using negative offsets from the current frame pointer.

· Within the procedure, formal value parameters look just like local variables (hint, hint) - the only difference is that their addresses have negative offsets).

· Within the procedure, formal reference parameters are absolute addresses of the actual parameters and need to be loaded and stored indirectly.

· After procedure exit, deallocate the space used by the actual parameters by using the DEALLOC_STACK instruction, which expects a value on top of the stack indicating how many top of stack locations to discard, i.e., the size of all the actual parameters.

Student Misconduct

Students are reminded of the University's policy on student misconduct, including plagiarism. See the course profile and the School web page http://www.itee.uq.edu.au/itee-student-misconduct-including-plagiarism

You are expected to protect your files so that they are not readable by other users.

Your assignment is expected to be your own individual work and must not include code copied from other students, current or past. You are also reminded not to post your (partial) solutions to assignments to any place accessible by others (before or after the assignment deadline), including the course discussion board or emailing to other students. If you need that sort of help consult the lecturer and/or tutor. Note that course discussion board allows private posts to the instructors.

This assignment compiler is provided solely for the purposes of doing this assignment and your solutions must never be shared, especially publicly, even after completion of the course. Such publication would be considered both student misconduct and a breach of copyright.

Late Submission

See section 5.3 of the course profile for details.

If there are documented medical or exceptional circumstances that will affect your ability to complete the assignment by the due date, then you can apply for an extension. Extensions to non-exam assignments must be requested via my.UQ. You can find instructions on how to submit your request online.

If the assignment is submitted after the deadline, without an approved extension, a late penalty will apply. The late penalty shall be 10% of the maximum possible mark for the assessment item will be deducted per calendar day (or part thereof), up to a maximum of seven (7) days. After seven days, no marks will be awarded for the item. A day is considered to be a 24 hour block from the assessment item due time. Negative marks will not be awarded.

Submission

Please keep the length of lines in your files below 100 characters, so that we can print them sensibly. You should avoid using tabs or set your tabs stops to 4 spaces so that when we print them (with tab stops set to 4 spaces) they will print sensibly. Don't forget to remove any code generating debugging output and rogue external imports before submission.

You must submit your completed assignment electronically through the assessment section of the course BlackBoard site (the BlackBoard Assessment page rather than the course web pages).

You need to submit the following list of individual files (not a .zip or other archive file) for evaluation and marking. Note that file names are case-sensitive. You must only modify the files

· PL0.cup

· ExpNode.java

· ExpTransform.java

· StatementNode.java

· StatementTransform.java

· StatementVisitor.java

· StaticChecker.java

· CodeGenerator.java

You can submit your assignment multiple times, but only the last copy submitted will be retained for marking.

Assessment

The assignment is marked out of a total of 15 marks.
Marks will be allocated as follows:

· 4.5 Syntax analysis and tree building

· 6 Static semantics checking

· 4.5 Code generation

Marks will be awarded for the correctness of the changes to each category. Readability and modular structure will also be criteria. For readability, we expect that you follow good software engineering practice, such as appropriate choices of variable names, consistent indentation, appropriate comments where needed, etc. For modularity we expect you introduce new methods where it makes sense to help structure the program and to avoid unnecessary duplication of code. Use of generic Java utility interfaces (like Set, Map, List, Queue, ...) and their implementations (like HashSet, ..., TreeMap, ..., LinkedList, ...) is encouraged. We expect you to produce well structured programs that are not unnecessarily complex, both structurally (e.g. complex control flow that is hard to follow), and in terms of execution time and space requirements, (e.g. an O(n) algorithm is preferred to an O(n2) algorithm, and a O(log n) algorithm is even better).

Your assignment files will be compiled in the context of the remaining assignment files and put through a sequence of tests. The total mark for this assignment will be limited by the overall success of the development in the following way:

· The program submitted does not compile: Maximum 8/15.

· The program submitted will not correctly handle any test case with the new facilities: Maximum 10/15.

You are not required to correct any bugs that may exist in the original compiler. However, we would appreciate being informed of any such bugs that you detect, so that we can correct them, or any improvements to the compiler you might like to suggest.