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.
Setup
The following instructions assume that you are using a Debian-based Linux system such as the Ubuntu MATE virtual machine.
Input
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:
‘(program
((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:
Program
[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.
Processing
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.
Output
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:.
- traversing the AST
- generating new registers and labels.
- generating pseudo-assembly
- producing correct output on selected subsets of Figure 15.2 ( attached )
- producing correct output for the entire GCD program in Figure 15.2 (attached )
- programming in a purely functional style
figure 15.2 ( attached )