Interp - an Interpreted Programming Language Pt.6 - Math ‘n’ parsing

6 minute read

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.

Next Up

Click for Pt. 7 or click here for all parts.

Updated: