Description
The goal of this assignment is to modify your Parser implementation for HW-3 to generate an abstract syntax tree (AST). To complete the assignment, finish the following steps. Note that you should get started on this assignment early to give yourself enough time to ask questions (and receive a response) before the due date. If you wait until the last minute and have issues, you will likely have to turn your homework in with the late penalty. If you have questions, please ask them over Piazza or else via office hours with the instructor or graders. 1. Download the HW-4 Starter Code. Use the link provided in Piazza to accept the GitHub Classroom assignment for HW-4. When accepting the assignment, please be sure to link your account to your name in the roster (if you haven’t done so already). Accepting the assignment will create a copy of the starter code and place it in a hw-4 repository for you. You will then need to clone this repository to your local machine. As always, be sure to frequently add, commit, and push your changes. 2. Add your previous files HW to your repository. You will need to copy your header and cpp files from HW-3 into your HW-4 repository (and working directory). These files are required to compile and build the hw4 executable. 3. Extend your Parser (in parser.h) to build the corresponding AST objects (defined in ast.h). Please see the discussion and notes from class for more details. As a guide, use the basic MyPL AST diagram below. Note that you may need to modify your recursive descent functions from HW-3 as you instrument your code to build the AST objects. A set of basic test files are also provided in the test subdirectory. As you work on your implementation, you will want to use these files as well as develop additional tests to check your work. Note that you must also provide a robust set of tests for the assignment, and the graders will be using additional tests as well. 4. Implement the Printer AST visitor to “pretty print” the original source code based on the AST generated by the Parser. When writing your “pretty printer”, you must use the following MyPL code styling rules (also see the test cases provided separately). (a) Indent all statements within a block by three spaces. (b) Each statement should be on a separate line without blank lines before or after the statement. The exceptions to this rule are user-defined type and function declarations. (c) Format variable declarations without explicit types using one space between var and the identifier, and one space before and after the assignment symbol, e.g., var id = expr. 1 (d) Format variable declarations with explicit types the same as for implicit types, but with a colon directly after the variable name (no extra space), followed by a space, followed by the type, followed by a space, e.g., var id: type = expr. (e) Format variable assignments with one space between the identifier and the assignment symbol, e.g., id = expr. (f) Format type declarations such that the reserved word type and the type name appears on one line, with one space between the two, each variable declaration indented (two spaces from the start of type) and on a separate line (with no blanks between), and end on the next immediate line after the last variable declaration and aligned with type. There should be one blank line after a type declaration. Here is an example: type Person var age = 0 var name = “” var mother: Person = nil var father: Person = nil end (g) Format function declarations such that fun, the return type, the function name, and the parameter list are all on the same line, the body of the function is indendented appropriately, and the end is on a separate line, immediately following the last body statement, aligned with the fun reserved word. There should be one space between fun and the type, one space between the type and the function name, and so on. There should be one blank line after each function declaration. Here is an example: fun int add(x: int, y: int) sum = x + y return sum end (h) Format while statements such that while and do occur on the same line, there is one space between the start and end of the Boolean expression, the body of the while loop is appropriately indendented, and end is aligned with while and occurs on the line immediately after the last statement of the body. (i) Format for statements such that for and do occur on the same line, each part of the loop specification is separated by a single space, the body of the for loop is appropriately indendented, and end is aligned with for and occurs on the line immediately after the last statement of the body. (j) Format if-elseif-else statements similar to while statements such that the body of each section is indented, elseif and else statements appear on seperate lines (with no blank lines before or after), then appears on the same line as its corresponding if or elseif, and end statements appear on separate lines with no preceding blank lines. 2 (k) Format simple expressions without any extra spaces. Path expressions should not contain spaces between corresponding dots (e.g., x.y.z). (l) Format complex expressions with spaces between their corresponding parts and fully enclose them in parentheses (regardless of whether there were parentheses in the original source code). For example, if the original was written as 3+4+5 the pretty-printed version should be written as (3 + (4 + 5)). (m) Boolean expressions should follow the same rules as for complex expressions. For example, not (x>1) and (y>1) should print as not ((x > 1) and (y > 1)). (n) Format structured type object creation such that there is one space between new and the struct type name. (o) Format function calls such that the function name is immediately followed by an opening parenthesis, followed by a comma-sparated list of expressions, followed by a closing parenthesis. There should be one space after each comma. Note that because we are not going to be implementing proper associativity and precedence of operators, some MyPL expressions can end up with some strange looking parenthesizations. Thus, associativity and precendence will need to be explicitly stated by a programmer via explicit use of parentheses. 5. Testing your implementation. In addition to the test files, you will also want to test cases that represent invalid MyPL syntax. Again, this can be done using additional test files, from the comand line, or using standard in from hw4. The graders will also be testing your code for error cases. 6. Submit your code. Be sure you have submitted all of your source code to your GitHub repo for the assignment (again, you should get into the habit of frequently adding, committing, and pushing your code). In addition to your source code, you must also submit each of your extended and any additional test files you used for testing. For error cases, submit a file that contains the error cases you tried (or else a script with the error cases themselves). Note that all necessary files to compile and build your program must be checked in to your repository. If your homework doesn’t compile, the graders won’t be able to test it for correctness or completeness. Homework Submission. All homework must be submitted through GitHub Classroom. A link for each assignment will be posted on Piazza when the homework is assigned. Be sure all of your code is pushed by the due date (which you can double check for your repository using the GitHub website). Each programming assignment is worth 35 points. The points are allocated based on the following. • Correct and Complete (25 points). Your code must correctly and completely do the requested tasks using the requested techniques. Note that for most assignments you will be 3 provided a partial set of test cases to help you determine a minimal level of correctness. If your program fails any of the provided test cases you will only receive partial credit. Note that passing the given test cases does not mean your work is complete nor correct. Your assignment will also be graded with additional test cases (not provided to you) that will help the graders determine the extent of your solution and your final score. Note that for C++ code, correctness also implies properly handling the creation and deletion of dynamic memory (i.e., the absence of memory leaks). • Evidence and Quality of Testing (5 points). As part of your homework assignments you must develop additional test cases beyond those given to you to ensure your program is correct and complete. These test cases must be turned in with your assignment. You will be graded on the scope and quality of the additional test cases you provide. • Formatting and Comments (5 points). Your code must be formatted consistently and appropriately for the language used. For C++, you must follow the provided style guide (see the course webpage). You must also comment your code and test cases, which at a minimum must include a file heading (see examples provided), function comments, and meaningfully selected variable, class, and function names. 4 ASTNode (interface) Decl (interface) isa Program decls : list<Decl*> Stmt (interface) isa ExprTerm (interface) isa isa Expr negated : bool first : ExprTerm* op : Token* rest : Expr* isa RValue (interface) isa SimpleTerm rvalue : RValue* isa ComplexTerm expr : Expr* isa VarDeclStmt id : Token type : Token* expr : Expr* isa AssignStmt lvalue_list : list expr : Expr* isa TypeDecl id : Token isa vdecls : list<VarDeclStmt*> FunDecl return_type : Token id : Token params : list stmts : list<Stmt*> isa FunParam id : Token type : Token ReturnStmt expr : Expr* isa WhileStmt expr : Expr* isa stmts : list<Stmt*> ForStmt var_id : Token start : Expr* end : Expr* stmts : list<Stmt*> isa IfStmt if_part : BasicIf* else_ifs : list<BasicIf*> else_stmts: list<Stmt*> isa BasicIf expr : Expr* stmts : list<Stmt*> SimpleRValue value : Token isa NewRValue type_id : Token isa CallExpr function_id : Token arg_list : list<Expr*> isa isa IDRValue path : list isa NegatedRValue expr : Expr* isa 5