| 1 |
use nom::{ |
| 2 |
branch::alt, |
| 3 |
bytes::complete::tag, |
| 4 |
character::complete::{alphanumeric1 as alphanumeric, digit1 as digit}, |
| 5 |
combinator::{map, map_res}, |
| 6 |
multi::separated_list0, |
| 7 |
sequence::delimited, |
| 8 |
IResult, Parser, |
| 9 |
}; |
| 10 |
use nom_language::precedence::{binary_op, precedence, unary_op, Assoc, Operation}; |
| 11 |
|
| 12 |
// Elements of the abstract syntax tree (ast) that represents an expression. |
| 13 |
#[derive(Debug)] |
| 14 |
pub enum Expr { |
| 15 |
// A number literal. |
| 16 |
Num(i64), |
| 17 |
// An identifier. |
| 18 |
Iden(String), |
| 19 |
// Arithmetic operations. Each have a left hand side (lhs) and a right hand side (rhs). |
| 20 |
Add(Box<Expr>, Box<Expr>), |
| 21 |
Sub(Box<Expr>, Box<Expr>), |
| 22 |
Mul(Box<Expr>, Box<Expr>), |
| 23 |
Div(Box<Expr>, Box<Expr>), |
| 24 |
// The function call operation. Left is the expression the function is called on, right is the list of parameters. |
| 25 |
Call(Box<Expr>, Vec<Expr>), |
| 26 |
// The ternary operator, the expressions from left to right are: The condition, the true case, the false case. |
| 27 |
Tern(Box<Expr>, Box<Expr>, Box<Expr>), |
| 28 |
} |
| 29 |
|
| 30 |
// Prefix operators. |
| 31 |
enum PrefixOp { |
| 32 |
Identity, // + |
| 33 |
Negate, // - |
| 34 |
} |
| 35 |
|
| 36 |
// Postfix operators. |
| 37 |
enum PostfixOp { |
| 38 |
// The function call operator. In addition to its own representation "()" it carries additional information that we need to keep here. |
| 39 |
// Specifically the vector of expressions that make up the parameters. |
| 40 |
Call(Vec<Expr>), // () |
| 41 |
} |
| 42 |
|
| 43 |
// Binary operators. |
| 44 |
enum BinaryOp { |
| 45 |
Addition, // + |
| 46 |
Subtraction, // - |
| 47 |
Multiplication, // * |
| 48 |
Division, // / |
| 49 |
// The ternary operator can contain a single expression. |
| 50 |
Ternary(Expr), // ?: |
| 51 |
} |
| 52 |
|
| 53 |
// Parser for function calls. |
| 54 |
fn function_call(i: &str) -> IResult<&str, PostfixOp> { |
| 55 |
map( |
| 56 |
delimited( |
| 57 |
tag("("), |
| 58 |
// Subexpressions are evaluated by recursing back into the expression parser. |
| 59 |
separated_list0(tag(","), expression), |
| 60 |
tag(")"), |
| 61 |
), |
| 62 |
|v: Vec<Expr>| PostfixOp::Call(v), |
| 63 |
) |
| 64 |
.parse(i) |
| 65 |
} |
| 66 |
|
| 67 |
// The ternary operator is actually just a binary operator that contains another expression. So it can be |
| 68 |
// handled similarly to the function call operator except its in a binary position and can only contain |
| 69 |
// a single expression. |
| 70 |
// |
| 71 |
// For example the expression "a<b ? a : b" is handled similarly to the function call operator, the |
| 72 |
// "?" is treated like an opening bracket and the ":" is treated like a closing bracket. |
| 73 |
// |
| 74 |
// For the outer expression the result looks like "a<b ?: b". Where "?:" is a single operator. The |
| 75 |
// subexpression is contained within the operator in the same way that the function call operator |
| 76 |
// contains subexpressions. |
| 77 |
fn ternary_operator(i: &str) -> IResult<&str, BinaryOp> { |
| 78 |
map(delimited(tag("?"), expression, tag(":")), |e: Expr| { |
| 79 |
BinaryOp::Ternary(e) |
| 80 |
}) |
| 81 |
.parse(i) |
| 82 |
} |
| 83 |
|
| 84 |
// The actual expression parser . |
| 85 |
fn expression(i: &str) -> IResult<&str, Expr> { |
| 86 |
precedence( |
| 87 |
alt(( |
| 88 |
unary_op(2, map(tag("+"), |_| PrefixOp::Identity)), |
| 89 |
unary_op(2, map(tag("-"), |_| PrefixOp::Negate)), |
| 90 |
)), |
| 91 |
// Function calls are implemented as postfix unary operators. |
| 92 |
unary_op(1, function_call), |
| 93 |
alt(( |
| 94 |
binary_op( |
| 95 |
3, |
| 96 |
Assoc::Left, |
| 97 |
alt(( |
| 98 |
map(tag("*"), |_| BinaryOp::Multiplication), |
| 99 |
map(tag("/"), |_| BinaryOp::Division), |
| 100 |
)), |
| 101 |
), |
| 102 |
binary_op( |
| 103 |
4, |
| 104 |
Assoc::Left, |
| 105 |
alt(( |
| 106 |
map(tag("+"), |_| BinaryOp::Addition), |
| 107 |
map(tag("-"), |_| BinaryOp::Subtraction), |
| 108 |
)), |
| 109 |
), |
| 110 |
// Ternary operators are just binary operators with a subexpression. |
| 111 |
binary_op(5, Assoc::Right, ternary_operator), |
| 112 |
)), |
| 113 |
alt(( |
| 114 |
map_res(digit, |s: &str| match s.parse::<i64>() { |
| 115 |
Ok(s) => Ok(Expr::Num(s)), |
| 116 |
Err(e) => Err(e), |
| 117 |
}), |
| 118 |
map(alphanumeric, |s: &str| Expr::Iden(s.to_string())), |
| 119 |
delimited(tag("("), expression, tag(")")), |
| 120 |
)), |
| 121 |
|op: Operation<PrefixOp, PostfixOp, BinaryOp, Expr>| -> Result<Expr, ()> { |
| 122 |
use nom_language::precedence::Operation::*; |
| 123 |
use BinaryOp::*; |
| 124 |
use PostfixOp::*; |
| 125 |
use PrefixOp::*; |
| 126 |
match op { |
| 127 |
// The identity operator (prefix +) is ignored. |
| 128 |
Prefix(Identity, e) => Ok(e), |
| 129 |
|
| 130 |
// Unary minus gets evaluated to the same representation as a multiplication with -1. |
| 131 |
Prefix(Negate, e) => Ok(Expr::Mul(Expr::Num(-1).into(), e.into())), |
| 132 |
|
| 133 |
// The list of parameters are taken from the operator and placed into the ast. |
| 134 |
Postfix(e, Call(p)) => Ok(Expr::Call(e.into(), p)), |
| 135 |
|
| 136 |
// Meaning is assigned to the expressions of the ternary operator during evaluation. |
| 137 |
// The lhs becomes the condition, the contained expression is the true case, rhs the false case. |
| 138 |
Binary(lhs, Ternary(e), rhs) => Ok(Expr::Tern(lhs.into(), e.into(), rhs.into())), |
| 139 |
|
| 140 |
// Raw operators get turned into their respective ast nodes. |
| 141 |
Binary(lhs, Multiplication, rhs) => Ok(Expr::Mul(lhs.into(), rhs.into())), |
| 142 |
Binary(lhs, Division, rhs) => Ok(Expr::Div(lhs.into(), rhs.into())), |
| 143 |
Binary(lhs, Addition, rhs) => Ok(Expr::Add(lhs.into(), rhs.into())), |
| 144 |
Binary(lhs, Subtraction, rhs) => Ok(Expr::Sub(lhs.into(), rhs.into())), |
| 145 |
} |
| 146 |
}, |
| 147 |
)(i) |
| 148 |
} |
| 149 |
|
| 150 |
#[test] |
| 151 |
fn expression_test() { |
| 152 |
assert_eq!( |
| 153 |
expression("-2*max(2,3)-2").map(|(i, x)| (i, format!("{:?}", x))), |
| 154 |
Ok(( |
| 155 |
"", |
| 156 |
String::from("Sub(Mul(Mul(Num(-1), Num(2)), Call(Iden(\"max\"), [Num(2), Num(3)])), Num(2))") |
| 157 |
)) |
| 158 |
); |
| 159 |
|
| 160 |
assert_eq!( |
| 161 |
expression("a?2+c:-2*2").map(|(i, x)| (i, format!("{:?}", x))), |
| 162 |
Ok(( |
| 163 |
"", |
| 164 |
String::from( |
| 165 |
"Tern(Iden(\"a\"), Add(Num(2), Iden(\"c\")), Mul(Mul(Num(-1), Num(2)), Num(2)))" |
| 166 |
) |
| 167 |
)) |
| 168 |
); |
| 169 |
} |