DOC PREVIEW
U of I CS 421 - Abstract Syntax Trees

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

U of I CS 421 - Abstract Syntax Trees

Documents in this Course
Lecture 2

Lecture 2

12 pages

Exams

Exams

20 pages

Lecture

Lecture

32 pages

Lecture

Lecture

21 pages

Lecture

Lecture

15 pages

Lecture

Lecture

4 pages

Lecture

Lecture

68 pages

Lecture

Lecture

68 pages

Lecture

Lecture

84 pages

s

s

32 pages

Parsing

Parsing

52 pages

Lecture 2

Lecture 2

45 pages

Midterm

Midterm

13 pages

LECTURE

LECTURE

10 pages

Lecture

Lecture

5 pages

Lecture

Lecture

39 pages

Load more
Download Abstract Syntax Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Abstract Syntax Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Abstract Syntax Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?