USE SCHEME LANGUAGE ONLY NO C++

use a functional language to traverse an Abstract Syntax Tree and generate pseudo-assembly code.

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)))))

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.

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).

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: