1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
//! Parser for plaintext math.
use std::collections::VecDeque;
use crate::ast::{BinaryOp, Fixity, Symbol, SymbolBinaryOp, UnaryOp, AST};
use crate::delimiter::{self, DelimDir, Delimiter};
use crate::operators::Op;
use crate::parsers::token::Token;
use super::token::Tokenizer;
/// Represents an error while parsing input expressions.
#[derive(Debug, Clone)]
pub enum ParseError {
/// Indicates that parentheses are mismatched.
MismatchedParentheses,
/// Indicates that operators are missing operators.
MissingOperands,
/// Indicates an empty expression.
EmptyExpr,
}
/// Parses the list of tokens into postfix.
pub fn parse_into_postfix(inputs: Vec<Token>) -> Result<VecDeque<Token>, ParseError> {
// implements the shunting-yard algorithm
// embarrassingly, my reference is Wikipedia
// https://www.wikiwand.com/en/Shunting-yard_algorithm
// use as a stack
let mut operators = VecDeque::new();
// use as a queue
let mut output = VecDeque::new();
for token in inputs.into_iter() {
// println!("Before token {:#?}", token.clone());
// println!("Operators: {:#?}", operators.clone());
// println!("Output: {:#?}", output.clone());
match token {
Token::Operand(_) => output.push_back(token),
Token::Operator(Op {
sym: ref _sym1,
l_prec: l_prec1,
r_prec: _r_prec1,
}) => {
while let Some(op2) = operators.front() {
match op2 {
Token::Delim(Delimiter {
dir: delimiter::DelimDir::Left,
kind: _,
}) => {
// we can't bind things from beyond a left delimiter: at the + in
// 2 * (3 + 4), we only bind the 3
break;
}
// Because we're extending to the left from op1's position, we use op1's
// left precedence and op2's right precedence. If we're at the second ^ in
// 2 ^ 2 ^ 3, we don't bind the first ^, because ^ binds more strongly on
// the right than on the left.
// this < could be nonstrict, and nothing should change: if two precedences
// are equal, that should mean that they're completely interchangeable.
Token::Operator(Op {
sym: _sym,
l_prec: _l_prec,
r_prec,
}) => {
let does_bind = match (l_prec1, r_prec) {
// If both exist, see if rp is lower, meaning more precedent
(Some(lp), Some(rp)) => rp < &lp,
// The only standard example of an operator with None on the right
// side is ! (factorial). So here an example might be 2! * 3: no
// matter what *'s precedence is, the postfix becomes 2 ! 3 *, with
// ! pushed first.
(Some(_lp), None) => true,
// An example of an operator with no left precedence is -. If we
// consider the example 2 + -3, here no matter what + is the correct
// postfix is 2 3 - +, with the + not being inserted first.
(None, Some(_rp)) => false,
// This should never happen in valid math: an example of what this
// would look like is 2! sin 3 if sin were an operator.
(None, None) => return Err(ParseError::MissingOperands),
};
if does_bind {
output.push_back(operators.pop_front().unwrap());
} else {
break;
}
}
Token::Function(_) => {
// functions never bind through operators without parentheses: sin 2 + x
// should convert to 2 sin x +, because if people mean sin (2 + x) they
// should write it with parentheses
output.push_back(operators.pop_front().unwrap());
}
_ => {
// this should never happen, because the operator stack should only
// contain left delimiters, operators, and functions.
panic!("Unknown token on operator stack: {:?}", op2);
}
}
}
operators.push_front(token);
}
Token::Function(_) => operators.push_front(token),
Token::Delim(Delimiter { dir, kind: lkind }) => match dir {
DelimDir::Left => operators.push_front(token),
DelimDir::Right => {
while let Some(op2) = operators.front() {
if let Token::Delim(Delimiter {
dir: DelimDir::Left,
kind,
}) = op2
{
if kind == &lkind {
// found matching pair
// get rid of left paren, it did its duty
operators.pop_front();
// if function, pop onto output
if let Some(Token::Function(_)) = operators.front() {
output.push_back(operators.pop_front().unwrap())
}
} else {
// something like (1 + [2 + 3)] happened and parens are mismatched
return Err(ParseError::MismatchedParentheses);
}
} else {
// otherwise, push onto output
output.push_back(operators.pop_front().unwrap());
}
}
}
},
Token::End => {
break;
}
}
}
output.append(&mut operators);
return Ok(output);
}
/// Given an AST, unpacks all outer , operators into a list.
fn comma_sep_to_list(tree: AST) -> Vec<AST> {
match tree {
AST::BinaryExpr(BinaryOp::Generic(SymbolBinaryOp { op, .. }), arg1, arg2)
if op.sym == crate::symbols::COMMA.clone() =>
{
let mut args1 = comma_sep_to_list(*arg1);
let mut args2 = comma_sep_to_list(*arg2);
args1.append(&mut args2);
args1
}
_ => {
vec![tree]
}
}
}
/// Turns a postfix-ordered list of tokens into an AST.
pub fn parse_into_tree(tokens: VecDeque<Token>) -> Result<AST, ParseError> {
let mut exprs = VecDeque::new();
for token in tokens.into_iter() {
match token {
Token::Operand(sym) => exprs.push_front(AST::Sym(sym)),
Token::Operator(op) => {
// TODO integrate this into type system so it isn't hacky, by adding arity to
// operators themselves
if crate::operators::UNARY_OPS.contains(&op) {
let new_expr = match exprs.pop_front() {
Some(tree) => AST::UnaryExpr(UnaryOp::Generic(op.sym), Box::new(tree)),
None => return Err(ParseError::MissingOperands),
};
exprs.push_front(new_expr);
} else {
let new_expr = match (exprs.pop_front(), exprs.pop_front()) {
(Some(arg2), Some(arg1)) => {
// special-case special binary operations
if op == crate::operators::POWER.clone() {
AST::BinaryExpr(BinaryOp::Power, Box::new(arg1), Box::new(arg2))
} else if op == crate::operators::DIV.clone() {
AST::BinaryExpr(BinaryOp::Frac, Box::new(arg1), Box::new(arg2))
} else {
AST::BinaryExpr(
BinaryOp::Generic(SymbolBinaryOp {
op,
fixity: Fixity::Infix,
}),
Box::new(arg1),
Box::new(arg2),
)
}
}
_ => return Err(ParseError::MissingOperands),
};
exprs.push_front(new_expr);
}
}
Token::Function(func) => match exprs.pop_front() {
Some(tree) => exprs.push_front(AST::Function(func, comma_sep_to_list(tree))),
None => return Err(ParseError::MissingOperands),
},
// if there's a delimiter here, it must be a left delimiter that never got cleaned up by
// its associated right pair, so parens are mismatched
Token::Delim(_) => return Err(ParseError::MismatchedParentheses),
Token::End => {
break;
}
}
}
// now we have one or many expressions to concatenate together
let output = exprs
.into_iter()
.rev()
.reduce(|acc, new| AST::BinaryExpr(BinaryOp::Concat, Box::new(acc), Box::new(new)));
match output {
None => Err(ParseError::EmptyExpr),
Some(tree) => Ok(tree),
}
}
/// A parser for ASCII.
#[derive(Debug, Clone, Default)]
pub struct AsciiParser {
/// The tokenizer to use.
tokenizer: Tokenizer,
}
impl<T> super::ASTParser<T> for AsciiParser
where
T: ToString,
{
type ParseError = ParseError;
fn parse(&self, input: &T) -> Result<AST, Self::ParseError> {
let input = input.to_string();
let tokens = self.tokenizer.tokenize(&input);
let postfix = parse_into_postfix(tokens)?;
dbg!(
"{}",
postfix
.clone()
.into_iter()
.map(|x| x.to_string())
.collect::<Vec<String>>()
.join(" ")
);
dbg!(
"{:#?}",
parse_into_tree(postfix.clone()).unwrap_or(AST::Sym(Symbol::from("oops")))
);
parse_into_tree(postfix)
}
}
#[cfg(test)]
mod tests {
use crate::parsers::token::Tokenizer;
use super::*;
// #[test]
// fn test_basic() {
// let tokens = Tokenizer::default().tokenize("2 + 3");
// assert_eq!(parse_into_postfix(tokens).unwrap(), vec![]);
// }
#[test]
fn test_simple_frac() {
let tokens = Tokenizer::default().tokenize("1 + (2 * 3)");
println!("{:#?}", parse_into_postfix(tokens).unwrap());
assert_eq!(0, 0);
}
}