Interp - an Interpreted Programming Language Pt.6 - Math ‘n’ parsing
In Pt. 6 we dive deeper into the world of parsing.
Preparation
First, let’s add the Debug trait to our structs. Implement the Debug trait, add the following line before the Line, LineType, Expr, ExprData, and Loc structs.
src/parser/*.rs:
#[derive(Debug)] // Add this line
pub struct ...
If we want to see our parse tree, we must modify main like so.
src/main.rs:
...
let parsed_line = parser::parse_line(&line_str, &filename, line_nr);
println!("{:?}", parsed_line); // Add this
match parsed_line {
...
Now we can see our parsed structs.
$ echo "Print(\"Hello, world\"\\n)" > hello.interp
$ interp hello.interp
Ok(Line { type_: Expr(Expr { type_: Call(Expr { type_: Variable("Print"), loc: Loc { filename: "<stdin>", line_nr: 0, index: 0 } }, [Expr { type_: String("\"Hello, world!\""), loc: Loc { filename: "<stdin>", line_nr: 0, index: 6 } }]), loc: Loc { filename: "<stdin>", line_nr: 0, index: 0 } }), loc: Loc { filename: "<stdin>", line_nr: 0, index: 0 } })
Hello, world!
You can remove the “println!” line any time you like.
Parsing
Expr
Add these ExprTypes.
/src/parser/expr.rs:
pub enum ExprType {
...
Float(String),
Int(String),
Neg(Box<Expr>),
Add(Box<Expr>, Box<Expr>),
Sub(Box<Expr>, Box<Expr>),
Mul(Box<Expr>, Box<Expr>),
Div(Box<Expr>, Box<Expr>),
Mod(Box<Expr>, Box<Expr>),
Pow(Box<Expr>, Box<Expr>),
Concat(Box<Expr>, Box<Expr>),
...
}
Grammar
Le’ts add more grammar. Add these tokens and rules.
src/parser/grammar.lalrpop:
match {
...
r#"[0-9]*\.[0-9]+"# => Float,
r#"[0-9]+"# => Int,
"+",
"-",
"*",
"/",
"%",
"^",
"<>",
...
}
...
expr0: Expr = {
"(" <expr> ")",
string,
int,
float,
variable,
function_call,
}
// ex. "hello"
string: Expr = {
<l:@L> <a:String> => Expr { type_: ExprType::String(a.to_owned()), loc: Loc { filename: filename.to_owned(), line_nr, index: l } }
}
// ex. 1.234
float: Expr = {
<l:@L> <a:Float> => Expr { type_: ExprType::Float(a.to_owned()), loc: Loc { filename: filename.to_owned(), line_nr, index: l } }
}
// ex. 1234
int: Expr = {
<l:@L> <a:Int> => Expr { type_: ExprType::Int(a.to_owned()), loc: Loc { filename: filename.to_owned(), line_nr, index: l } }
}
// ex. Print
variable: Expr = {
<l:@L> <a:Identifier> => Expr { type_: ExprType::Variable(a.to_owned()), loc: Loc { filename: filename.to_owned(), line_nr, index: l } }
}
// ex. Print("Hello, world!")
function_call: Expr = {
<l:@L> <a:expr0> "(" <b:expr_list> ")" => Expr { type_: ExprType::Call(Box::new(a), b), loc: Loc { filename: filename.to_owned(), line_nr, index: l } },
}
expr1: Expr = {
expr0,
<l:@L> <a:expr1> "^" <b:expr0> => Expr { type_: ExprType::Pow(Box::new(a), Box::new(b)), loc: Loc { filename: filename.to_owned(), line_nr, index: l } },
}
// ex. -4
expr2: Expr = {
expr1,
<l:@L> "-" <a:expr1> => Expr { type_: ExprType::Neg(Box::new(a)), loc: Loc { filename: filename.to_owned(), line_nr, index: l } }
}
// ex. -1 * 2
expr3: Expr = {
expr2,
<l:@L> <a:expr3> "*" <b:expr2> => Expr { type_: ExprType::Mul(Box::new(a), Box::new(b)), loc: Loc { filename: filename.to_owned(), line_nr, index: l } },
<l:@L> <a:expr3> "/" <b:expr2> => Expr { type_: ExprType::Div(Box::new(a), Box::new(b)), loc: Loc { filename: filename.to_owned(), line_nr, index: l } },
<l:@L> <a:expr3> "%" <b:expr2> => Expr { type_: ExprType::Mod(Box::new(a), Box::new(b)), loc: Loc { filename: filename.to_owned(), line_nr, index: l } },
}
// ex. 3 + 4 * 5
expr4: Expr = {
expr3,
<l:@L> <a:expr4> "+" <b:expr3> => Expr { type_: ExprType::Add(Box::new(a), Box::new(b)), loc: Loc { filename: filename.to_owned(), line_nr, index: l } },
<l:@L> <a:expr4> "-" <b:expr3> => Expr { type_: ExprType::Sub(Box::new(a), Box::new(b)), loc: Loc { filename: filename.to_owned(), line_nr, index: l } },
<l:@L> <a:expr4> "<>" <b:expr3> => Expr { type_: ExprType::Concat(Box::new(a), Box::new(b)), loc: Loc { filename: filename.to_owned(), line_nr, index: l } },
}
expr: Expr = {
expr4
}
It’s simpler than it looks. expr0 defines our basic atoms like strings, numbers, and variables. expr1 defines the negation operator since it has bigger precedence than the other operators. expr2 defines the mul, div, and mod operators. Lastly, expr3 defines the addition and subtraction operators. This is how we define precedence. We must also define the expression types.
VM
Value
Let’s add the Int and Float value.
src/vm/value.rs:
pub enum Value {
Void,
String(String),
Int(i64), // We add these
Float(f64),
PrintBuiltin,
}
Operator Evaluation
Next, let’s create a file for arithmetic. Don’t forget to declare the module in src/vm/mod.rs. Your job is to make the sub, mul, and mod_ (mod is a keyword) functions.
src/vm/mod.rs:
mod value;
mod arithmetic;
src/vm/arithmetic.rs:
use crate::vm::value::Value;
use crate::err;
use crate::parser::loc::Loc;
pub fn neg(x: Value, x_loc: &Loc) -> Value {
match x {
Value::Float(a) => Value::Float(-a),
Value::Int(a) => Value::Int(-a),
_ => {
err::throw_loc(err::Err::TokenExpected { expected: "number".to_owned() }, x_loc);
Value::Void
}
}
}
pub fn add(x: Value, y: Value, x_loc: &Loc) -> Value {
match (x, y) {
(Value::Float(a), Value::Float(b)) => Value::Float(a + b),
(Value::Int(a), Value::Float(b)) => Value::Float((a as f64) + b),
(Value::Float(a), Value::Int(b)) => Value::Float(a + (b as f64)),
(Value::Int(a), Value::Int(b)) => Value::Int(a + b),
_ => {
err::throw_loc(err::Err::TokenExpected { expected: "numbers".to_owned() }, x_loc);
Value::Void
}
}
}
... // Implement sub, mul
pub fn div(x: Value, y: Value, x_loc: &Loc, y_loc: &Loc) -> Value {
if let Value::Float(num) = y {
if num == 0.0 {
err::throw_loc(err::Err::DivByZero, y_loc);
return Value::Void;
}
} else if let Value::Int(0) = y {
err::throw_loc(err::Err::DivByZero, y_loc);
return Value::Void;
}
match (x, y) {
(Value::Float(a), Value::Float(b)) => Value::Float(a / b),
(Value::Int(a), Value::Float(b)) => Value::Float((a as f64) / b),
(Value::Float(a), Value::Int(b)) => Value::Float(a / (b as f64)),
(Value::Int(a), Value::Int(b)) => Value::Int(a / b),
_ => {
err::throw_loc(err::Err::TokenExpected { expected: "numbers".to_owned() }, x_loc);
Value::Void
}
}
}
... // Implement mod_ (mod is a keyword)
pub fn pow(x: Value, y: Value, x_loc: &Loc) -> Value {
match (x, y) {
(Value::Float(a), Value::Float(b)) => Value::Float(a.powf(b)),
(Value::Int(a), Value::Float(b)) => Value::Float(a.pow(b as u32) as f64),
(Value::Float(a), Value::Int(b)) => Value::Float(a.powi(b as i32) as f64),
(Value::Int(a), Value::Int(b)) => Value::Int(a.pow(b as u32)),
_ => {
err::throw_loc(err::Err::TokenExpected { expected: "numbers".to_owned() }, x_loc);
Value::Void
}
}
}
pub fn concat(x: Value, y: Value) -> Value {
Value::String(crate::vm::value_repr(x) + &crate::vm::value_repr(y))
}
expr_to_value
Now let’s add the match cases.
src/vm/mod.rs:
fn expr_to_value(vm: &mut VM, expr: &Expr) -> value::Value {
match &expr.type_ {
...
ExprType::Float(str) => value::Value::Float(str.parse().unwrap()),
ExprType::Int(str) => value::Value::Int(str.parse().unwrap()),
...
ExprType::Neg(expr) => {
let value = expr_to_value(vm, expr);
arithmetic::neg(value, &expr.loc)
}
ExprType::Add(x_expr, y_expr) => {
let x = expr_to_value(vm, x_expr);
let y = expr_to_value(vm, y_expr);
arithmetic::add(x, y, &x_expr.loc)
}
... // Implement Sub, Mul, Mod, Pow
ExprType::Div(x_expr, y_expr) => {
let x = expr_to_value(vm, x_expr);
let y = expr_to_value(vm, y_expr);
arithmetic::div(x, y, &x_expr.loc, &y_expr.loc)
}
... // Implement Mod
ExprType::Concat(x_expr, y_expr) => {
let x = expr_to_value(vm, x_expr);
let y = expr_to_value(vm, y_expr);
arithmetic::concat(x, y)
}
value_repr
Finally, value_repr must be updated.
src/vm/mod.rs
fn value_repr(val: value::Value) -> String {
match val {
...
value::Value::Float(float) => float.to_string(),
// Define Int here
...
}
}
DivByZero Error
Define the DivByZero error.
src/err.rs:
pub enum Err {
...
DivByZero,
}
pub fn throw(err: Err) {
match err {
...
Err::DivByZero => eprintln!("can't divide by zero"),
}
}
Wrapping it up
We now have a functioning calculator.
$ echo "Print(1+2)" > calc.interp
$ interp calc.interp
Ok(Line { type_: Expr(Expr { type_: Call(Expr { type_: Variable("Print"), loc: Loc { filename: "<stdin>", line_nr: 1, index: 0 } }, [Expr { type_: Add(Expr { type_: Int("1"), loc: Loc { filename: "<stdin>", line_nr: 1, index: 6 } }, Expr { type_: Int("2"), loc: Loc { filename: "<stdin>", line_nr: 1, index: 8 } }), loc: Loc { filename: "<stdin>", line_nr: 1, index: 6 } }]), loc: Loc { filename: "<stdin>", line_nr: 1, index: 0 } }), loc: Loc { filename: "<stdin>", line_nr: 1, index: 0 } })
3
In the next one we will implement variables.
Source Code
Source code for this part can be found here.