MP 3 – Abstract Syntax TreesCS 421 – Spring 2008Revision 1.2Assigned January 24, 2008Due Monday, January 28, 2008, 11:59 PMExtension 48 hours (penalty 20% of total points possible)1 Change Log1.2 Switch Cases Explanation.1.1 Due Date Correction.1.0 Initial Release.2 Objectives and BackgroundAfter completing this MP, you should better understand:• pattern matching and recursion• user-defined datatypes• abstract syntax trees3 BackgroundOne of the objectives of this course is to provide you with the skills necessary to implement a language. A compilerconsists of two parts, the “front-end” and the “back-end.” The front-end translates the concrete program — thesequence of characters — into an internal format called an abstract syntax tree (AST). The back-end translates theAST to machine language. In OCaml, abstract syntax trees are built from user-defined data types; these types arecalled the abstract syntax of the language.In this MP you will work on abstract syntax trees for a language based on Java. Specifically, you will write afunction to print the source code of a program given its AST, and a function to calculate the “symbol table” of aprogram — the set of variables in scope at each point of the program. You will be given code to support your work,including the abstract syntax and the type definition for symbol tables.4 Given CodeThis semester, we will build a compiler for the language MiniJava. MiniJiva is a simplification of Java. In addition todropping many features, such as exceptions, it has one syntactic difference that you will see immediately: All methodsreturn values; there is no type “void”; and every method ends with a return statement.In this assignment, you will build functions to traverse an abstract syntax tree. The file mp3common.cmo containscompiled code to support your construction of these functions. Its contents are described here.14.1 Abstract syntax of MiniJavaThe abstract syntax for MiniJava is given by the following mutually-recursive Ocaml types (we have interspersedexplanatory comments between the type definitions):type program = Program of (class_decl list)and class_decl = Class of id*id*(var_decl list)*(method_decl list)A program is a list of classes. A class has a name, superclass name (which is the empty string if the class does nothave an extends clause), fields, and methods.A method has a return type, name, argument list, local variable list, and body; in MiniJava, the body is a statementlist and then a return statement with an expression. Variable declarations have a name and type, and optionally thestatic modifier.and method_decl = Method of exp_type*id*((exp_type*id) list)*(var_decl list)*(statement list)*expand var_decl = Var of exp_type*id | StaticVar of exp_type*idStatements make changes in environments but don’t return any value. The following should have obvious meanings,with a couple of exceptions: The Println constructor gives us an easy way to include a print statement, instead ofthe complicated way required by real Java. The switch statement can only handle integer cases, and you can’t havemultiple cases with a single statement list; abstractly, it contains a list of (integer, statement list) pairs (the regularcases), plus one more statement list (the default case).and statement = Block of (statement list)| If of exp*statement*statement| While of exp*statement| Println of exp| Assignment of id*exp| ArrayAssignment of id*exp*exp| Break| Continue| Switch of exp*((int*(statement list)) list) (*cases*)*(statement list) (*default*)The abstract syntax for expressions follows. The constructor NewId creates a zero-argument constructor call (thereare only zero-argument constructors in MiniJava).and exp = Operation of exp*binary_operation*exp| Array of exp*exp| Length of exp| MethodCall of exp*id*(exp list)| Id of id| This| NewArray of exp_type*exp| NewId of id| Not of exp2| Null| True| False| Integer of int| String of string| Float of floatand binary_operation = And | Or | GreaterThan| Plus | Minus | Multiplication | DivisionThe abstract syntax for types and identifiers follows. IdType of id corresponds to a classname used as a type.and exp_type = ArrayType of exp_type | Boolean| IntType | IdType of id | StringType | FloatTypeand id = Identifier of string5 ProblemsNote: In the problems below, you do not have to begin your definitions in a manner identical to the sample code,which is present solely for guiding you better. However, you have to use the indicated name for your functions, andthe functions have to have the same type.Note: In these problems, you may use any library function, including @ (list concatenation) and ˆ (string concatena-tion).1. (15 pts) Write a function pretty print to print out the source code of an AST. It should have typeval pretty print : program -> string = <fun>The concrete syntax of MiniJava is explained in the following webpages. Also, you can find sample MiniJavaprograms.• http://www.cambridge.org/resources/052182060X/MCIIJ2e/grammar.htm• http://www.cambridge.org/resources/052182060X/In general, the concrete syntax for each of our abstract syntax constructors should be clear to you from yourknowledge of Java. There are a couple of exceptions: Methods should begin with the word public; there areonly public methods in MiniJava, but instead of just omitting the public modifier, we want to include it to maintainconsistency with Java. Println e should print as System.out.println(E), where E is the pretty-printedversion of e, again to maintain compatibility with Java. We have included the following features not in the originalMiniJava described in those links, and you’ll have to use Java itself as a guide to how to pretty-print them. Theyare: types string and float, and arbitrary array types; and statements break, continue, and switch.You will need to mutually-recursive functions, one for each of the types in the abstract syntax.The problem has one main part, an extra credit part, and a part that is required only for students enrolled in thecourse for four hours.a. (15 pts — full credit) Pretty-print the entire abstract syntax except switch statements, in such a way that theresulting program could be compiled. That is, you must insert spaces where needed (such as between thekeyword class and the class name), but you are not otherwise obliged to include any whitespace. Further-more, to insure that the result would be parsed correctly, in arithmetic expressions
View Full Document