In this assignment, you will use a functional language to traverse an Abstract Syntax Tree and generate pseudo-assembly code. You may choose to write the program in Scheme or OCaml.
The following instructions assume that you are using a Debian-based Linux system such as the Ubuntu MATE virtual machine.
Input will be provided as a tree literal for Scheme or Ocaml, as shown on pp. 379-381 of the textbook. The tree will be an AST for a program. For example, the syntax tree for the program in Figure 15.2 on p. 778 could be represented in Scheme as:
((assign (var i int) (call (func getint void int) ()))
(assign (var j int) (call (func getint void int) ()))
(while (neq (var i int) (var j int))
((if (gt (var i int) (var j int))
((assign (var i int) (minus (var i int) (var j int))))
((assign (var j int) (minus (var j int) (var i int)))))))
(call (func putint int void) ((var i int)))))
while in OCaml it could be represented as:
[Assign (Var (“i”, Int), Call (Func (“getint”, [Void], Int), ));
Assign (Var (“j”, Int), Call (Func (“getint”, [Void], Int), ));
While (Neq (Value (Var (“i”, Int)), Value (Var (“j”, Int))),
[If (Gt (Value (Var (“i”, Int)), Value (Var (“j”, Int))),
[Assign (Var (“i”, Int),
Minus (Value (Var (“i”, Int)), Value (Var (“j”, Int))))],
[Assign (Var (“j”, Int),
Minus (Value (Var (“j”, Int)), Value (Var (“i”, Int))))])]);
Expr (Call (Func (“putint”, [Int], Void), [Value (Var (“i”, Int))]))]
Of course, since OCaml is statically typed, the types for the tree must be declared first:
type id = string
and data_type = Int | Void
and var = Var of id * data_type
and arg_types = data_type list
and return_type = data_type
and func = Func of id * arg_types * return_type
and args = expr list
and expr =
| Value of var
| Call of func * args
| Neq of expr * expr
| Gt of expr * expr
| Minus of expr * expr
and stmt =
| Assign of var * expr
| Expr of expr
| While of expr * stmt list
| If of expr * stmt list * stmt list
and program = Program of stmt list ;;
Note the additional Value and Expr type tags in the OCaml version of the AST. These are required to distinguish between the name of a variable and its value, and to allow expressions to be valid statements. In the Scheme version, these distinctions are clear from context, but in OCaml the type checker requires them to be made explicit.
Your program does not need to read the AST from a file; it will be provided with a literal value, as shown above. This is similar to the way that zero-one-even-dfa is provided to the Scheme DFA simulator in Section 11.3 of the textbook and a_b_even_dfa is provided to the OCaml DFA simulator in Section 11.4.
Note also that unlike Figure 15.2, a separate symbol table is not included; type information is provided in-line in var and func nodes of the tree. You may assume that the input AST has already been type-checked.
Using the attribute grammar of Figure 15.6 on pp. 786-787 as a guide, define a function codegen that takes the AST as a parameter. Traverse the AST and generate pseudo-assembly code for the specified program, as shown in Figure 15.7 on p. 789 of the textbook.
Assume an unlimited number of available registers and labels.
Your program should be able to generate pseudo-assembly code for the constructs used in Figure 15.2. Other statements (such as the for loop) or expressions (such as the division operator) used in Figure 15.10 on p. 804 are optional.
The pseudo-assembly code may either be returned as a list of strings or printed directly to the terminal (e.g., with println in Scheme or Printf.printf in OCaml).
You may omit the declaration block at the top of the code (the section beginning — first few lines generated during symbol table traversal) in Figure 15.7. Begin with the label main:.
figure 15.2 ( attached )
Delivering a high-quality product at a reasonable price is not enough anymore.
That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.
You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.Read more
Each paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.Read more
Thanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.Read more
Your email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.Read more
By sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.Read more