辅导案例-COMP4403/COMP7402-Assignment 1
Last updated: Mon 23 Mar 2020 10:20:57 AEST. COMP4403/COMP7402 - Compilers and Interpreters Assignment 1 Due date: 15:00 Thursday 9th April, 2020 Modify the recursive descent compiler for the language PL0 (provided on the course web page with this assignment) to add a skip statement, a multiple assignment statement, and an extended version of a loop statement. Assignment Compiler Files All sources for the assignment PL0 compiler are available as a1.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). a1.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 1 files Please ensure you follow the course Piazza bulletin 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 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 the Java compiler used to test your assignment and all comments should be readable by the person assessing your assignment. Your implementation should be in Java 1.8 and Project language level 8. Set the IntelliJ preferences for the Java compiler to 1.8 (or use the "-source 1.8" option to the command line 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/Eclipse) so that your files will print sensibly. Read all the fine print below in detail before you start! And, most important, when you have finished implementing the assignment, come back and re-read the fine print again. Overview The multiple assignment statement allows a list of variables to be simultaneously assigned the values of a list of expressions. The trick is that all the expressions are evaluated before any of the assignments takes place, for example, the following multiple assignment swaps the values of x and y: x,y := y,x The following assignment rotates the values of x, y and z: x,y,z := y,z,x A do statement chooses a branch with a true guard and executes it; if the chosen branch ends with exit, the do statement terminates, otherwise it repeats from the beginning. The following do statement calculates the greatest common divisor of positive integers x and y using Euclid's algorithm. // requires 0 < x && 0 < y do x < y then y := y - x [] x = y then gcd := x exit [] y < x then x := x - y od The GCD program above repeatedly executes either the first or third branches until x equals y, at which point it executes the middle branch, which assigns to gcd and terminates the do statement. Syntax Changes The following lexical tokens have been added to the scanner module of PL0 already. SEPARATOR → ">@" KW_OD → "od" KW_EXIT → "exit" KW_SKIP → "skip" Keywords are case sensitive. The non-terminal Statement in the grammar for PL0 is modified to the following Extended Backus-Naur Form (EBNF) grammar rules. Statement → WhileStatement | IfStatement | CallStatement | Assignment | ReadStatement | WriteStatement | CompoundStatement | SkipStatement | DoStatement where SkipStatement → KW_SKIP Assignment → LValueList ASSIGN ConditionList LValueList → LValue { COMMA LValue } ConditionList → Condition { COMMA Condition } DoStatement → KW_DO DoBranch { SEPARATOR DoBranch } KW_OD DoBranch → Condition KW_THEN StatementList > KW_EXIT @ Note that the branches of the do statement contain statement lists rather than just a single statement, and the do statement is terminated by the keyword od. The addition of a skip statement allows one to write if x < 0 then x := -x else skip to assign x its absolute value. Equivalently one can use the following: do x < 0 then x := -x exit [] 0 <= x then skip exit od Static Semantic Restrictions Skip statement There are not any static semantic restrictions on the skip statement, that is, it is well formed for any symbol table context. syms ⊢ WFStatement(skip) Multiple assignment The lists of left values and right values must be the same length. All of the variables on the left side of a multiple assignment must be distinct. The type of each condition (expression) must be assignment compatible (coercible) to the type of the corresponding variable to which it is assigned. n = m ∀ i, j ∈ >1..n@ • i ≠ j ⇒ v ≠ v ∀ i ∈ >1..n@ • (syms ⊢ v : ref(T )) && (syms ⊢ e : T ) syms ⊢ WFStatement(v , v , ... , v := e , e , ... , e ) Do statement A branch of a do statement is well formed if its condition c is of type boolean (it could be a variable of type ref(boolean) or even a subrange of boolean or ...) and its body ss (a statement list) is well formed. syms ⊢ c : boolean i j i i i i 1 2 n 1 2 m syms ⊢ WFStatement(list(ss)) syms ⊢ WFDoBranch(c then ss) The do branch with a exit is similar. syms ⊢ c : boolean syms ⊢ WFStatement(list(ss)) syms ⊢ WFDoBranch(c then ss exit) A do statement is well formed if all its branches are well formed. ∀ j ∈ >1..n@ • (syms ⊢ WFDoBranch(b )) syms ⊢ WFStatement(do b >@ b >@ ... >@ b od) Dynamic Semantics Skip statement The skip statement does nothing. The less it does the better. Multiple assignment For a multiple assignment, all the expressions in all the assignments are evaluated before any of the variables are assigned, and then all of the assignments take place. Note that it does not matter in what order the simple assignments are done because the left sides are all distinct and the expressions have all been evaluated using the values of the variables before any assignments take place (and expression evaluation does not have any side effects in PL0). Do statement The do statement selects a branch for which the condition is true and executes the corresponding statement list. If more than one condition is true, any one (but only one) of the corresponding statement lists may be executed. That is, the branch selected does not have to be the first with a true guard, but it may be. When the selected branch has finished execution, if the branch ends in the keyword exit, the whole do statement terminates, otherwise the do statement is repeated from the beginning. For example, the following calculates the maximum of x and y. Because both branches exit, this particular statement is more like a multiple branch if statement. do x <= y then max := y exit [] y <= x then max := x exit j 1 2 n od Note that if x equals y then both guards are true and either branch may be executed (and the same value is assigned to max via either branch in this example). In your implementation you are free to choose a particular order in which to evaluate the conditions. A do statement that does not have any branch with an exit will loop forever. That is the intended semantics. If all the conditions in a do statement evaluate to false, this is considered a runtime error and the interpreter is terminated by a call to method runtime with an error message "No branch of do loop has a true guard". Interpreter The PL0 compiler for this assignment uses an interpreter (rather than generate code). A description of the interpreter is available in Interpreter.pdf. The interpretation is done in class Interpreter, which uses class Frame for its runtime stack and class Value for the runtime representation of values. Each kind of expression/statement node in the PL0 abstract syntax tree has a "visit" method that interprets (evaluates/executes) the corresponding expression/statement. The interpreter for the skip statement is trivial. The interpreter for the multiple assignment has to be careful to evaluate all expressions before doing any assignments. The interpreter for the do statement needs to handle multiple branches and either breaking out of the loop or repeating it. For the do statement, you can determine in what order to evaluate the conditions (but keep it simple). 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, including the bulletin board or emailing to other students. If you need that sort of help consult the lecturer and/or tutor. Note that Piazza 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 A penalty of 5% of the maximum mark for an assignment will be deducted for each day or part thereof late up to a limit of 7 days, after which time assignments will not be accepted for assessment unless you have been granted an extension. As we plan to hand back assignments a week or two after submission, requests for an extension will not be accepted more than one week late, unless there are exceptional circumstances. Requests for extensions should be accompanied by suitable documentation (see the course profile for details). Personal hardware or computer failures are not grounds for extension. Assignments must be backed up on the university system. 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. Do not forget to remove any code generating debugging output and any 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 any other form of archive file) for evaluation and marking. Note that file names are case-sensitive. You must only modify the files Interpreter.java Parser.java StatementNode.java StatementVisitor.java StaticChecker.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 20 marks. Marks will be allocated as follows: 8 - Syntax analysis including syntax error recovery and tree building 7 - Static semantics checking 5 - Interpreter Marks will be awarded for the correctness of the changes to each category. Readability, modular structure, and structural and computational complexity are also 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 especially 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(n ) 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 10/20. The program submitted will not correctly handle any test case with the new facilities: Maximum 13/20. 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. 2