Crate csc_7b_fc 

CSC 123/252 Assignment: compiling simple expression trees.

Abstract Machine AM16 is a 16-bit instruction set architecture that can compute arithmetic expressions as defined by the enum Expr AST type in this module (see source code). The abstract machine has the following general purpose registers: ax, bx, cx.

And the following instructions

   push src
   pop dst
   add src dst
   sub src dst
   mult src dst
   div src dst

In each instruction, the dst (destination) operand must name one of the three registers, while the src (source) operand can be register or immediate (constant). The semantics of an ALU instruction such as sub ax bx is bx -= ax. In addition, the div (divide) instruction has a special semantics: it calculates both the quotient and the remainder. The quotient is stored in the dst register while the remainder is always stored in register cx. If the dst register is also cx, then the quotient is discarded. For example, if ax contains value 9 and bx contains value 2 then executing div bx ax will store 4 in ax and 1 in cx.

The following sample program computes 5-3:

  push 3
  push 5
  pop ax
  pop bx
  sub bx ax
  push ax

The last instruction should always push the result on the stack: this protocol is essential in order to compute compound expressions such as 2+3*4, which compiles to:

  push 4
  push 3
  pop ax
  pop bx
  mult ax bx
  push bx
  push 2
  pop ax
  pop bx
  add ax bx
  push bx

At the end of a successful computation, the top of the stack always contains the result.

Your assignment is to write a compiler for simple arithmetic expressions. It should print the sequence of instructions, which can be captured into a file and executed on “vm16”, a virtual machine implementation of AM16 written in C++.

To compile the program, execute a POSTORDER traveral on the expression tree. The leaves of the tree contain constants of the form Val(n) in abstract syntax. For such a leaf, just println!("push {}",n); For a non-leaf node such as Plus(a,b), you need to recursively compile a and b first (postorder) then add instructions to calculate the sum, then push the final result on top of the stack. I’ve written a skeleton with the case for Neg(a) and you just need to finish the other cases.

---

This assignment’s base program is hosted on github. The assignment is designed to be a gentle introduction to Rust because you’re mostly just going to println!. Do the following to set up a Rust “cargo” project, assuming you’ve rust already installed.

1. git clone https://github.com/chuckcscccl/csc_7b_fc.git

   If you don’t have git, goto the github link and “get” it manually. Periodically, I will update this repository and you will need to do a git pull inside the folder to upgrade.

2. cargo new myfirstcrate

   This creates a cargo project folder. Make sure this folder is in the same folder as csc_7b_fc. Inside src/main.rs there’s a main that prints hello world. You will replace this main. If you submit a project that prints hello world you will lose one million points.

3. Go into the myfirstcrate folder and edit Cargo.toml. Add the following under [dependencies]:

     [dependencies]
     csc_7b_fc = { path = "../csc_7b_fc/" }

   Change the path if that’s not where the base crate is located.

4. cargo build : this compiles the program and its dependencies.

5. cargo run : this runs the program

6. Go into the folder csc_7b_fc/vm16/ and read the README. Compile and test the vm16 program. You can then move the vm16 executable into your project’s folder so it’s more accessible.

7. Rewrite the main.rs in myfirstcrate/src/. I’ve written a skeleton for you that you can edit/follow. Make sure this main is in YOUR crate. Do not change my crate (csc_7b_fc). Test it by compiling expressions such as 3*20-9%2. Run it on vm16.

8. Submit only the main.rs of your project.

There are additional helpful commands you can run with cargo:

1. cargo fmt : this will format your code to be nicely spaced and properly indented.
2. cargo doc : generate documentation from certain types of comments written in markdown (see source code for example). Documentation should be provided for all pub items. The docs are viewable in /target/doc/myfirstcrate/index.html
3. cargo clipply : runs addtional static analysis on your code, provides suggestions such as how to improve performance.

What follows is the documentation on the different elements of this crate, generated from comments.

---

Modules

avlmap

CSC 7B/FC Rust Assignment 2

avlnavigator

AVL Tree Navigator Module.

avltree

AVL Binary Search Tree in Rust, 2024 version

bijectivemap

Skeleton module for the bijective hashmap assignment.

bimap

CSC 123/252 Assignment

circularqueue

eytzinger

hmap

This module contains the implementation of a closed hashmap from scratch. Because the interior of the implementation is exposed, one can use it to implement a biject hashmap without resorting to Copy, Clone, Rc or anything unsafe.

redblack

twoway

Rust Assignment 2. Instructions are in the documentation for the TwowayMap struct.

Enums

Expr

Abstract Syntax (AST) type for arithmetic expressions. Smart pointer Box is required to define recursive structures. One drawback of Rust is that Box blocks nested pattern matching, so sometimes nested match expressions are required.

Functions

eval

Eval function evaluates to an Option type. Further demonstrates monadic error handling, which is the only form of error handling in Rust.

eval_interactive

Function that prompts user for expression, parses and evaluates it.

lex

Simple String Tokenizer. Takes a string slice and generates a Vector of tokens such as Sym("+"), Val(3), etc.

parse

This function takes a vector of tokens produced by the lex function and returns an Expr inside an Option: Some(AST) or None if parsing failed. The function is defined using “slice patterns”. Also note the while loop: recursion is generally discouraged in Rust. However, in dealing with recursive Expr trees it is OK because these trees will not be large.

proper

checks if expr is a proper AST expression, and not just a token pre-parsing. This function is not equivalent to !.is_token because Val(_) is both a token and a proper expression.