csc_7b_fc/lib.rs
1//! # CSC 123/252 Assignment: compiling simple expression trees.
2//!
3//! Abstract Machine *AM16* is a 16-bit instruction set architecture that
4//! can compute arithmetic expressions as defined by the **enum [Expr]** AST
5//! type in this module (see source code). The abstract machine has
6//! the following general purpose registers:
7//! **ax, bx, cx**.
8//!
9//! And the following instructions
10//! ```
11//! push src
12//! pop dst
13//! add src dst
14//! sub src dst
15//! mult src dst
16//! div src dst
17//! ```
18//! In each instruction, the dst (destination) operand must name one of the
19//! three registers, while the src (source) operand can be register or
20//! immediate (constant). The semantics of an ALU instruction such as
21//! `sub ax bx` is `bx -= ax`. In addition, the div (divide) instruction has
22//! a special semantics: it calculates both the quotient and the remainder.
23//! The quotient is stored in the dst register while the remainder is always
24//! stored in register cx. If the dst register is also cx, then the quotient
25//! is discarded. For example, if ax contains value 9 and bx contains value 2
26//! then executing `div bx ax` will store 4 in ax and 1 in cx.
27//!
28//! The following sample program computes 5-3:
29//! ```
30//! push 3
31//! push 5
32//! pop ax
33//! pop bx
34//! sub bx ax
35//! push ax
36//! ```
37//! The last instruction should always push the result on the stack: this
38//! protocol is essential in order to compute compound expressions such as
39//! 2+3*4, which compiles to:
40//! ```
41//! push 4
42//! push 3
43//! pop ax
44//! pop bx
45//! mult ax bx
46//! push bx
47//! push 2
48//! pop ax
49//! pop bx
50//! add ax bx
51//! push bx
52//! ```
53//! At the end of a successful computation, the top of the stack always
54//! contains the result.
55//!
56//! Your assignment is to write a compiler for simple arithmetic expressions.
57//! It should print the sequence of instructions, which can be captured into
58//! a file and executed on "vm16", a virtual machine implementation of AM16
59//! written in C++.
60//!
61//! To compile the program, execute a POSTORDER traveral on the expression tree.
62//! The leaves of the tree contain constants of the form Val(n) in abstract
63//! syntax. For such a leaf, just `println!("push {}",n);` For a non-leaf
64//! node such as `Plus(a,b)`, you need to recursively compile a and b first
65//! (postorder) then add instructions to calculate the sum, then push the
66//! final result on top of the stack. I've written a [skeleton](https://github.com/chuckcscccl/csc_7b_fc/blob/main/src/main.rs) with the case
67//! for `Neg(a)` and you just need to finish the other cases.
68//!
69//! <p>
70//!
71//! -----------------
72//! This assignment's base program is hosted on **[github](https://github.com/chuckcscccl/csc_7b_fc/)**. The assignment is designed to be a gentle introduction to Rust
73//! because you're mostly just going to [println]!. Do the following to
74//! set up a Rust "cargo" project, assuming you've rust already installed.
75//! 1. `git clone https://github.com/chuckcscccl/csc_7b_fc.git`
76//!
77//! If you don't have git, goto the github link and "get" it manually.
78//! Periodically, I will update this repository and you will need to
79//! do a `git pull` inside the folder to upgrade.
80//!
81//! 2. `cargo new myfirstcrate`
82//!
83//! This creates a cargo project folder. Make sure this
84//! folder is in the same folder as `csc_7b_fc`. Inside `src/main.rs`
85//! there's a main that prints hello world. You will replace this main.
86//! If you submit a project that prints hello world you will lose
87//! one million points.
88//!
89//! 3. Go into the `myfirstcrate` folder and edit `Cargo.toml`. Add the following under `[dependencies]`:
90//! ```
91//! [dependencies]
92//! csc_7b_fc = { path = "../csc_7b_fc/" }
93//! ```
94//! Change the path if that's not where the base crate is located.
95//!
96//! 4. `cargo build` : this compiles the program and its dependencies.
97//!
98//! 5. `cargo run` : this runs the program
99//!
100//! 6. Go into the folder `csc_7b_fc/vm16/` and read the [README](https://github.com/chuckcscccl/csc_7b_fc/tree/main/vm16). Compile and test the `vm16` program. You can then move the vm16 executable into your project's folder so
101//! it's more accessible.
102//!
103//! 7. Rewrite the `main.rs` in `myfirstcrate/src/`. I've written a **[skeleton](https://github.com/chuckcscccl/csc_7b_fc/blob/main/src/main.rs)**
104//! for you that you can edit/follow. Make sure this main is in YOUR crate.
105//! Do not change my crate (`csc_7b_fc`). Test it by compiling expressions
106//! such as 3*20-9%2. Run it on vm16.
107//!
108//! 8. Submit only the main.rs of your project.
109//! <p>
110//!
111//! There are additional helpful commands you can run with [cargo](https://doc.rust-lang.org/cargo/):
112//! 1. `cargo fmt` : this will format your code to be nicely spaced and
113//! properly indented.
114//! 2. `cargo doc` : generate documentation from certain types of comments
115//! written in markdown
116//! (see source code for example). Documentation should be provided for
117//! all `pub` items. The docs are viewable in `/target/doc/myfirstcrate/index.html`
118//! 3. `cargo clipply` : runs addtional static analysis on your code, provides suggestions such as how to [improve performance](https://nnethercote.github.io/perf-book/linting.html).
119//! <p>
120//!
121//! What follows is the documentation on the different elements of this crate,
122//! generated from comments.
123//!
124//! -----------------
125
126#![allow(dead_code)]
127#![allow(non_snake_case)]
128#![allow(unused_variables)]
129#![allow(unused_parens)]
130#![allow(unused_imports)]
131#![allow(non_camel_case_types)]
132use std::fmt::{Display, Formatter, Result};
133use std::io::{self, Read, Write};
134use Expr::*;
135// online calculator in Rust, with shift-reduce parser
136
137/// Abstract Syntax (AST) type for arithmetic expressions. Smart pointer
138/// [Box] is required to define recursive structures. One drawback of
139/// Rust is that Box blocks nested pattern matching, so sometimes
140/// nested `match` expressions are required.
141#[derive(Debug)]
142pub enum Expr {
143 Val(i32), // i32 is type for 32 bit signed ints
144 Plus(Box<Expr>, Box<Expr>), // recursion requires smart pointer
145 Minus(Box<Expr>, Box<Expr>),
146 Times(Box<Expr>, Box<Expr>), // Box is like unique_ptr in C++
147 Divide(Box<Expr>, Box<Expr>),
148 Mod(Box<Expr>, Box<Expr>),
149 Neg(Box<Expr>),
150 Sym(char),
151 EOF,
152 Dummy,
153} // Expr enum
154
155impl Expr {
156 /// alias to [eval] function, but called as a method: `expr1.eval_to()`
157 pub fn eval_to(&self) -> Option<i32> {
158 eval(self)
159 }
160
161 /// determines if expr is a shallow token, produced by the lexical
162 /// tokenizer before parsing.
163 pub fn is_token(&self) -> bool {
164 match self {
165 Val(_) | Sym(_) | EOF | Dummy => true,
166 _ => false,
167 } //match
168 } //is_token
169
170 /// cloning the entire tree is expensive but a token is shallow and can
171 /// be copied. Non-token expressions are cloned to `Dummy`.
172 pub fn clone_token(&self) -> Self {
173 match self {
174 Val(n) => Val(*n),
175 Sym(c) => Sym(*c),
176 EOF => EOF,
177 _ => Dummy, // everything else clones to Dummy
178 } //match
179 } //clone_token
180} // method-style implementations
181
182/// checks if expr is a proper AST expression, and not just a token pre-parsing.
183/// This function is not equivalent to `!.is_token` because `Val(_)` is both a
184/// token and a proper expression.
185pub fn proper(e: &Expr) -> bool {
186 match e {
187 Sym(_) | EOF | Dummy => false,
188 _ => true,
189 }
190} //proper
191
192/// Eval function evaluates to an [Option] type. Further demonstrates
193/// monadic error handling, which is the only form of error handling
194/// in Rust.
195pub fn eval(e: &Expr) -> Option<i32> {
196 match e {
197 Val(x) => Some(*x), // x is a ref so has to be deref'ed
198 Neg(x) => eval(x).map(|a| -1 * a), //& does deref coercion on Box
199 Plus(x, y) => eval(x).zip(eval(y)).map(|(a, b)| a + b),
200 Minus(x, y) => eval(x).zip(eval(y)).map(|(a, b)| a - b),
201 Times(x, y) => eval(x).zip(eval(y)).map(|(a, b)| a * b),
202 Divide(x, y) => eval(y).and_then(|b| if b != 0 { eval(x).map(|a| a / b) } else { None }),
203 Mod(x, y) => eval(y).and_then(|b| if b != 0 { eval(x).map(|a| a % b) } else { None }),
204 _ => None,
205 } //match
206} //eval
207
208/////////// Trait implementations for Expr
209
210impl Default for Expr {
211 fn default() -> Expr {
212 Dummy
213 }
214}
215
216impl Display for Expr {
217 fn fmt(&self, f: &mut Formatter<'_>) -> Result // required by trait
218 {
219 match self {
220 Val(x) => write!(f, "{}", x),
221 Plus(x, y) => write!(f, "({}+{})", x, y),
222 Times(x, y) => write!(f, "{}*{}", x, y),
223 Minus(x, y) => write!(f, "({}-{})", x, y),
224 Divide(x, y) => write!(f, "{}/{}", x, y),
225 Mod(x, y) => write!(f, "{}%{}", x, y),
226 Neg(x) => {
227 if let Neg(y) = &**x {
228 write!(f, "{}", y)
229 } else {
230 write!(f, "-{}", x)
231 }
232 }
233 Sym(s) => write!(f, " {} ", s),
234 EOF => write!(f, " EOF "),
235 Dummy => write!(f, " Dummy "),
236 } //match
237 }
238} // impl Display for Expr
239 // no ability to deep-pattern match inside a Box/Rc
240
241/// Function that prompts user for expression, parses and evaluates it.
242pub fn eval_interactive() // interpreter
243{
244 print!("Enter Expression: ");
245 io::stdout().flush().unwrap();
246 let mut input = String::new();
247 if let Ok(_) = io::stdin().read_line(&mut input) {
248 let tokens = lex(&input[0..input.len() - 1].trim());
249 //println!("tokens: {:?}",&tokens);
250 let exp = parse(&tokens);
251 exp.and_then(|e| {
252 eval(&e).map(|n| {
253 println!("Value of {} = {}", &e, n);
254 })
255 });
256 } // if let Ok(n)
257} // - evals instead of compiles
258
259////////////////////////////////////////////////////////////////////////////
260/// Simple String Tokenizer. Takes a string slice and generates a [Vec]tor
261/// of tokens such as `Sym("+")`, `Val(3)`, etc.
262pub fn lex(inp: &str) -> Vec<Expr> {
263 let input: Vec<char> = inp.chars().collect();
264 let mut tokens: Vec<Expr> = Vec::new();
265 let mut i: usize = 0;
266 while i < input.len() {
267 let mut c = input[i];
268 i += 1; // get one char
269 let mut isnum = false;
270 let mut n = 0;
271 while c.is_digit(10) && i <= input.len() {
272 isnum = true;
273 n = n * 10 + c.to_digit(10).unwrap();
274 if i < input.len() {
275 c = input[i];
276 i += 1;
277 } else {
278 i += 1;
279 }
280 } // while numerical digit
281 if isnum {
282 tokens.push(Val(n as i32));
283 }
284 if !c.is_digit(10) && c != ' ' {
285 tokens.push(Sym(c));
286 }
287 } //while
288 tokens.push(EOF);
289 return tokens;
290} //lexer
291
292/// operator precedence parser
293fn precedence(e: &Expr) -> u32 {
294 match e {
295 Val(_) => 250,
296 Sym('+') => 100,
297 Sym('-') => 100,
298 Sym('*') => 200,
299 Sym('/') => 200,
300 Sym('%') => 200,
301 Sym('u') => 220,
302 Sym('(') => 500,
303 Sym(')') => 10,
304 EOF => 5,
305 _ => 0,
306 }
307}
308fn prec(a: &Expr, b: char) -> bool {
309 precedence(a) <= precedence(&Sym(b))
310}
311// assume universal left-associativity.
312
313fn ateof(e: &Expr) -> bool // at end-of-file predicate
314{
315 match e {
316 EOF => true,
317 _ => false,
318 }
319}
320
321/// This function takes a vector of tokens produced by the [lex] function
322/// and returns an Expr inside an Option: Some(AST) or None if parsing
323/// failed. The function is defined using "slice patterns". Also note
324/// the while loop: recursion is generally discouraged in Rust. However,
325/// in dealing with recursive Expr trees it is OK because these trees will
326/// not be large.
327pub fn parse(tokens: &Vec<Expr>) -> Option<Expr> {
328 let mut stack: Vec<Expr> = Vec::new();
329 let mut ti: usize = 0; // indexes tokens
330 let mut lookahead = &tokens[ti];
331 while !(ateof(lookahead) && stack.len() == 1) {
332 let sl = stack.len();
333 match stack.as_slice() {
334 // match against stack as slice
335 [cdr @ .., Sym('('), e, Sym(')')] if prec(lookahead, '(') => {
336 stack.swap(sl - 2, sl - 3); // move e down stack
337 stack.truncate(sl - 2); // pop last two values
338 }
339 [cdr @ .., e1, Sym('+'), e2] if prec(lookahead, '+') => {
340 let mut tos = stack.split_off(sl - 3);
341 let b = Box::new(tos.remove(2));
342 let a = Box::new(tos.remove(0));
343 stack.push(Plus(a, b));
344 }
345 [cdr @ .., e1, Sym('-'), e2] if prec(lookahead, '-') => {
346 let mut tos = stack.split_off(sl - 3);
347 let b = Box::new(tos.remove(2));
348 let a = Box::new(tos.remove(0));
349 stack.push(Minus(a, b));
350 }
351 [cdr @ .., e1, Sym('*'), e2] if prec(lookahead, '*') => {
352 let mut tos = stack.split_off(sl - 3);
353 let b = Box::new(tos.remove(2));
354 let a = Box::new(tos.remove(0));
355 stack.push(Times(a, b));
356 }
357 [cdr @ .., e1, Sym('/'), e2] if prec(lookahead, '/') => {
358 let mut tos = stack.split_off(sl - 3);
359 let b = Box::new(tos.remove(2));
360 let a = Box::new(tos.remove(0));
361 stack.push(Divide(a, b));
362 }
363 [cdr @ .., e1, Sym('%'), e2] if prec(lookahead, '%') => {
364 let mut tos = stack.split_off(sl - 3);
365 let b = Box::new(tos.remove(2));
366 let a = Box::new(tos.remove(0));
367 stack.push(Mod(a, b));
368 },
369 [cdr @ .., e2, Sym('-'), e1] if !proper(e2) && prec(lookahead, 'u') => {
370 let e = Neg(Box::new(stack.pop().unwrap()));
371 stack[sl - 2] = e; // e moved to stack
372 },
373 [Sym('-'), e1] if prec(lookahead, 'u') => {
374 let e = Neg(Box::new(stack.pop().unwrap()));
375 stack[sl - 2] = e; // e moved to stack
376 },
377 _ if ti + 1 < tokens.len() => {
378 // shift
379 stack.push(lookahead.clone_token());
380 ti += 1;
381 lookahead = &tokens[ti];
382 }
383 _ => {
384 for ex in stack {
385 print!("{:?}::", ex);
386 }
387 eprintln!("\nPARSING ERROR");
388 return None;
389 }
390 } // match
391 } // while
392 return stack.pop();
393} //parse
394
395///////////// bijective map
396pub mod bijectivemap;
397
398///////////// circular queue
399pub mod circularqueue;
400
401//////////// AVL Tree
402pub mod avlmap;
403pub mod avltree;
404pub mod avlnavigator;
405pub mod eytzinger;
406
407pub mod redblack;
408
409pub mod twoway;
410
411pub mod hmap;
412pub mod bimap;