Computer Science Department San Francisco State University CSC 413 Spring 2022 Assignment 5 – Debugger Due Date Wednesday, May 18, BEFORE MIDNIGHT No late submissions can be accepted for this assignment! Note that the due date applies to the last commit timestamp into the main branch of your repository. Overview The purpose of this assignment is to continue our work in the large compiler codebase, and implement a Debugger. You will be using your code for the Interpreter class, which must be copied into your github repository when you begin the assignment via this assignment link. Submission Your assignment will be submitted using github. Only the “main” branch of your repository will be graded. Late submission is determined by the last commit time on the “main” branch. You are required to submit a documentation PDF named “documentation.pdf” in a “documentation” folder at the root of your project. Implementation Requirements You may create additional classes as needed to implement the requirements defined here, but must implement at least those classes listed here. If you decide to add additional classes, they must follow object oriented design principles – proper encapsulation and data hiding, and implementing a single responsibility. Project Setup 1. You must be able to execute your program by typing: javac interpreter/debugger/commands/*.java javac interpreter/bytecode/*.java javac interpreter/bytecode/debuggercodes/*.java javac interpreter/Interpreter.java java interpreter.Interpreter Note that the Interpreter may now also be run in debugger mode by providing a switch (-d) and the base file name (instead of the fully qualified bytecode file name): java interpreter.Interpreter -d You may assume that the bytecode programs that are used for testing are generated correctly, and therefore should not contain any errors. Note that the assignment 5 skeleton code provides you with an updated main method in the Interpreter class to handle this switch! 2. Begin by replacing the placeholder classes in the project skeleton with your assignment 4 implementation. The following files should be replaced: a. VirtualMachine.java b. ByteCodeLoader.java c. CodeTable.java d. Program.java e. Any other supporting files you created or that you need(i.e. RuntimeStack). 3. Copy your byte code classes from your assignment 4 implementation into the bytecode package. New Implementation 1. You must add three new byte codes – LINE, FUNCTION, and FORMAL – to the set of byte codes we are implementing. All existing byte codes should continue to function, and may need to add behavior to support debugging. a. The FUNCTION and FORMAL byte codes will be generated as a header for each function declaration. The byte codes generated for each function will begin with: LABEL name1 — branch label for function call LINE n — start of function definition FUNCTION name start end — name of function with source line — number boundaries given by start — and end FORMAL f1 0 — f1 is first formal with offset 0 FORMAL f2 1 — f2 is second formal with offset 1 b. When debugging, we will not need to dump(), so no dump behavior is required for these byte codes. 2. You must implement the FunctionEnvironmentRecord that will be used to track the current function’s state in the debugger. The FunctionEnvironmentRecord consists of a symbol table, a function name, the start and end lines of a function in the original source code file, and the current line number. Note that the current line number must be reset when branching instructions are processed. The symbol table works a lot like the symbol table implementation we saw in constraining, though it is slightly simpler – you may reuse the code from the Table class in the Constrainer, but you will need to make some modifications. The symbol table is modified as follows when the given byte codes are encountered: FORMAL xyz n — enter(“xyz”, n) LIT 0 i — enter(“i”, currentOffset) POP n — delete the last n items entered into the symbol table Note the that class provided in the assignment 5 skeleton code includes a main method to help test your implementation. Compare the output from that main method to the correct output provided in main’s function header. A simulation of the environment stack changes during a debugger execution for the factorial Bytecode Example Description LINE LINE n LINE 5 n is the current source line number; the generated byte codes for line n will follow this code. FUNCTION FUNCTION name start end FUNCTION g 1 20 name is the name of the function, start is the source code line that this function starts on, and end is the source code line that this function ends on. FORMAL FORMAL name offset FORMAL f1 0 name is the name of the formal parameter, offset is the stack offset for the variable. program is provided, with the environment stack shown, in Appendix A. A simulation of symbol table changes during a debugger execution for a simple program is provided in Appendix B. 3. You must provide debugger implementations for each of the byte codes discussed in class (implementations from assignment 4), in addition to three new byte codes that will be introduced to facilitate debugging. Note that byte codes for the debugger do everything they would do for the interpreter, with the addition of some behavior for debugging. a. Debugger byte codes must be placed in the sub package of interpreter.debugger created for this purpose in your assignment 5 skeleton: interpreter.bytecode.debuggercodes. 4. To accommodate these new byte codes, we need a DebuggerCodeTable. The interface for the DebuggerCodeTable is the same as the CodeTable, and only needs to include the new byte codes that are needed by the debugger (i.e. any byte code that requires additional behavior for debugging, and the three new byte codes described below). In the event that a byte code is not found in the DebuggerCodeTable, you will return the result of getting that code from the CodeTable. An implementation is provided for you, but you need to add your debugger byte codes to its initialization method. 5. In the debugger package, you must update the implementation for the Debugger that extends the Interpreter. a. Just after the Interpreter (Debugger) starts, and before the VM executes the first instruction, you should print the source program and then prompt the user for a command. This should be handled by the DebuggerShell object, described below. b. The Debugger will require some additional data structures in order to allow the user to debug a program: i. A Vector of entries where each Entry contains int lineNumber: The line number for this Entry String sourceLine: The source program line i for Vector slot i Boolean isBreakpointLine: Is a breakpoint set for this line Accessors for these fields. ii. A Stack of FunctionEnvironmentRecords. A new record will be pushed when a function is entered, and popped when returning from a function. c. The following commands must be implemented by the debugger: i. Display available commands. Do not display the command list at any other time! Type for help > set list locals source step continue exit Type for help > ii. set (set breakpoint) This command records that a breakpoint has been set for a specific line Type for help > set Enter line number: > 2 Type for help > iii. list (list breakpoints) This command lists all breakpoints currently set with the debugger Type for help > list * 2: int factorial(int n) { Type for help > iv. source (display source) This command displays the source code of the current function, with an indication of where the execution has stopped (if executing), and any breakpoints that have been set: Type for help > source 1: program {boolean j int i -> * 2: int factorial(int n) { 3: if (n < 2) then 4: { return 1 } 5: else 6: {return n*factorial(n-1) } 7: } 8: while (1==1) { 9: i = write(factorial(read())) 10: } 11: } Type for help > v. step This command causes execution to continue for one byte code (essentially the behavior of “step into”). There will be no output, apart from a new prompt (the user can choose to display source if they require output): Type for help > step Type for help > vi. continue This command causes execution to continue. There will be no output, apart from a new prompt (if another break point is encountered). vii. locals This command prints a listing of all symbols in the current frame, with their values: Type for help > locals i: 0 j: 0 Type for help > viii. exit Immediately halts execution of the program: Type for help > exit assignment-5-debugger-spring-2020-jrob8577 git:(master) 6. You must create classes for interaction with the user. Any UI classes must be created in the interpreter.debugger.ui package. a. A class DebuggerShell must be implemented to encapsulate prompting the user for a command. The prompt should be: Type for help > The DebuggerShell class should display the prompt, wait for a user command, validate that the command is allowed, and return an instance of DebuggerCommand to the Debugger. Follow the strategy pattern to implement concrete DebuggerCommands for each of the required commands. b. Whenever the debugger stops, the source code should be displayed, with an indication of: i. Breakpoints (indicated by *) ii. Current line of code that is executing (indicated by ->) 1: program {boolean j int i -> * 2: int factorial(int n) { 3: if (n < 2) then 4: { return 1 } 5: else 6: {return n*factorial(n-1) } 7: } 8: while (1==1) { 9: i = write(factorial(read())) 10: } 11: } 7. In the debugger package, you must provide an implementation for the DebuggerVirtualMachine that extends the VirtualMachine. This extension will add any methods necessary to manage the debugging session. Testing Requirements A test program is provided for you (factorial.x and factorial.x.cod) in the sample_files directory of the assignment 5 project skeleton. Appendix A: Example of Environment Stack changes Note: this is not expected output! This just shows how the function environment stack changes in the debugger during execution. Also, the stack is growing downwards in this example. Bytecode Environment Stack (symbol table, start, end, name, currentLine) < -, -, -, -, - > GOTO start<<1>> LABEL start<<1>> LINE 1 < -, -, -, -, 1 > FUNCTION main 1 11 < (), 1, 11, main, 1 > LIT 0 j < (), 1, 11, main, 1 > LIT 0 i < (, ), 1, 11, main, 1 > GOTO continue<<3>> LABEL continue<<3>> LABEL while<<7>> LINE 8 < (, ), 1, 11, main, 8 > LIT 1 LIT 1 BOP == FALSEBRANCH continue<<6>> LINE 9 < (, ), 1, 11, main, 9 > ARGS 0 CALL Read < (, ), 1, 11, main, 9 > < (), -, -, -, - > LABEL Read LINE -1 < (, ), 1, 11, main, 9 > < (), -, -, -, -1 > FUNCTION Read -1 -1 < (, ), 1, 11, main, 9 > < (), -1, -1, Read, -1 > READ RETURN < (, ), 1, 11, main, 9 > (Return to line 9) ARGS 1 CALL factorial<<2>> < (, ), 1, 11, main, 9 > < (), -, -, -, - > LABEL factorial<<2>> LINE 2 < (, ), 1, 11, main, 9 > < (), -, -, -, 2 > FUNCTION factorial 2 7 < (, ), 1, 11, main, 9 > < (), 2, 7, factorial, 2 > FORMAL n 0 < (, ), 1, 11, main, 9 > < (), 2, 7, factorial, 2 > LINE 3 < (, ), 1, 11, main, 9 > < (), 2, 7, factorial, 3 > LOAD 0 n LIT 2 BOP < FALSEBRANCH else<<4>> LABEL else<<4>> LINE 6 < (, ), 1, 11, main, 9 > < (), 2, 7, factorial, 6 > LOAD 0 n LOAD 0 n LIT 1 BOP – ARGS 1 CALL factorial<<2>> < (, ), 1, 11, main, 9 > < (), 2, 7, factorial, 6 > < (), -, -, -, - > LABEL factorial<<2>> LINE 2 < (, ), 1, 11, main, 9 > < (), 2, 7, factorial, 6 > < (), -, -, -, 2 > FUNCTION factorial 2 7 < (, ), 1, 11, main, 9 > < (), 2, 7, factorial, 6 > < (), 2, 7, factorial, 2 > FORMAL n 0 < (, ), 1, 11, main, 9 > < (), 2, 7, factorial, 6 > < (), 2, 7, factorial, 2 > LINE 3 < (, ), 1, 11, main, 9 > < (), 2, 7, factorial, 6 > < (), 2, 7, factorial, 3 > LOAD 0 n LIT 2 BOP < FALSEBRANCH else<<4>> … etc. Appendix B Consider the following x program snippet: 8. int f() { int j int k 9. { int j j = 1 10. } 11. j = 2 12. } The following is the generated byte codes for this function declaration, along with the state of the symbol table, and the symbol table method called: LABEL f<<2>> create symbol table, beginScope < (), -, -, -, - > LINE 8 < (), -, -, -, 8 > FUNCTION f 8 12 < (), 8, 12, f, 8 > LIT 0 j enter j < (), 8, 12, f, 8 > LIT 0 k enter k < ( ), 8, 12, f, 8 > LINE 9 < ( ), 8, 12, f, 9 > LIT 0 j enter j; symbol table will link to prior entry for j < (- ), 8, 12, f, 9 > LIT 1 STORE 2 POP 1 remove last symbol entered, thereby restoring linked entry of j < ( ), 8, 12, f, 9 > LINE 11 < ( ), 8, 12, f, 11 > LIT 2 STORE 0 POP 2 remove last two symbols < (), 8, 12, f, 11> RETURN f<<2>>
