1use nom::branch::*;
2use nom::bytes::complete::take;
3use nom::combinator::{map, verify, opt};
4use nom::multi::many0;
5use nom::sequence::{preceded, delimited, pair, terminated};
6use nom::*;
7use nom::Err;
8use nom::error::{Error as NomError, ErrorKind};
9
10pub mod ast;
11
12use crate::{
13 lexer::{
14 Lexer,
15 token::{Token, Tokens},
16 },
17 parser::ast::{Expr, Error as ExcelError, Literal, Prefix, Infix, Precedence},
18 errors::Error
19};
20
21macro_rules! tag_token (
22 ($func_name:ident, $tag: expr) => (
23 fn $func_name(tokens: Tokens) -> IResult<Tokens, Tokens> {
24 verify(take(1usize), |t: &Tokens| t.tok[0] == $tag)(tokens)
25 }
26 )
27);
28
29tag_token!(comma_tag, Token::Comma);
30tag_token!(plus_tag, Token::Plus);
31tag_token!(minus_tag, Token::Minus);
32tag_token!(divide_tag, Token::Divide);
33tag_token!(multiply_tag, Token::Multiply);
34tag_token!(exponent_tag, Token::Exponent);
35tag_token!(ampersand_tag, Token::Ampersand);
36tag_token!(equal_tag, Token::Equal);
37tag_token!(semicolon_tag, Token::SemiColon);
38tag_token!(langle_tag, Token::LAngle);
39tag_token!(rangle_tag, Token::RAngle);
40tag_token!(lparen_tag, Token::LParen);
41tag_token!(rparen_tag, Token::RParen);
42tag_token!(lbrace_tag, Token::LBrace);
43tag_token!(rbrace_tag, Token::RBrace);
44tag_token!(eof_tag, Token::EOF);
45
46fn parse_literal(input: Tokens) -> IResult<Tokens, Literal> {
47 let (i1, t1) = take(1usize)(input)?;
48 if t1.tok.is_empty() {
49 Err(Err::Error(NomError::new(input, ErrorKind::Tag)))
50 } else {
51 match t1.tok[0].clone() {
52 Token::Integer(x) => Ok((i1, Literal::Number(x as f64))),
53 Token::Float(x) => Ok((i1, Literal::Number(x))),
54 Token::Text(s) => Ok((i1, Literal::Text(s))),
55 Token::Boolean(b) => Ok((i1, Literal::Boolean(b))),
56 _ => Err(Err::Error(NomError::new(input, ErrorKind::Tag))),
57 }
58 }
59}
60
61fn parse_literal_expr(input: Tokens) -> IResult<Tokens, Expr> {
62 map(parse_literal, Expr::Literal)(input)
63}
64
65fn parse_error(input: Tokens) -> IResult<Tokens, ExcelError> {
66 let (i1, t1) = take(1usize)(input)?;
67 if t1.tok.is_empty() {
68 Err(Err::Error(NomError::new(input, ErrorKind::Tag)))
69 } else {
70 match t1.tok[0].clone() {
71 Token::Null => Ok((i1, ExcelError::Null)),
72 Token::Div => Ok((i1, ExcelError::Div)),
73 Token::Value => Ok((i1, ExcelError::Value)),
74 Token::Ref => Ok((i1, ExcelError::Ref)),
75 Token::Name => Ok((i1, ExcelError::Name)),
76 Token::Num => Ok((i1, ExcelError::Num)),
77 Token::NA => Ok((i1, ExcelError::NA)),
78 Token::GettingData => Ok((i1, ExcelError::GettingData)),
79 _ => Err(Err::Error(NomError::new(input, ErrorKind::Tag)))
80 }
81 }
82}
83
84fn parse_error_expr(input: Tokens) -> IResult<Tokens, Expr> {
85 map(parse_error, Expr::Error)(input)
86}
87
88fn parse_ident(input: Tokens) -> IResult<Tokens, Token> {
89 let (i1, t1) = take(1usize)(input)?;
90 if t1.tok.is_empty() {
91 Err(Err::Error(NomError::new(input, ErrorKind::Tag)))
92 } else if matches!(t1.tok[0], Token::Ident(_)) {
93 Ok((i1, t1.tok[0].clone()))
94 } else {
95 Err(Err::Error(NomError::new(input, ErrorKind::Tag)))
96 }
97}
98
99fn parse_func_expr(input: Tokens) -> IResult<Tokens, Expr> {
100 map(
101 pair(
102 parse_ident,
103 delimited(
104 lparen_tag,
105 alt((parse_exprs, empty_boxed_vec)),
106 rparen_tag,
107 )
108 ),
109 |(ident, exprs)| {
110 Expr::Func { name: format!("{}", ident), args: exprs }
111 }
112 )(input)
113}
114
115fn parse_prefix_expr(input: Tokens) -> IResult<Tokens, Expr> {
116 map(
117 pair(alt((plus_tag, minus_tag)), parse_atom_expr),
118 |(pre, expr)| {
119 let prefix = match &pre.tok[0] {
120 Token::Plus => Prefix::Plus,
121 Token::Minus => Prefix::Minus,
122 _ => unreachable!()
123 };
124 let box_expr = Box::new(expr);
125 Expr::Prefix(prefix, box_expr)
126 }
127 )(input)
128}
129
130
131fn parse_comma_exprs(input: Tokens) -> IResult<Tokens, Expr> {
132 map(
133 preceded(alt((comma_tag, semicolon_tag)), parse_expr),
134 |expr| {
135 expr
136 }
137 )(input)
138}
139
140fn parse_exprs(input: Tokens) -> IResult<Tokens, Vec<Expr>> {
141 map(
142 pair(parse_expr, many0(parse_comma_exprs)),
143 |(first, second)| {
144 [&vec![first][..], &second[..]].concat()
145 }
146 )(input)
147}
148
149fn empty_boxed_vec(input: Tokens) -> IResult<Tokens, Vec<Expr>> {
150 Ok((input, vec![]))
151}
152
153fn parse_array_expr(input: Tokens) -> IResult<Tokens, Expr> {
154 map(
155 delimited(
156 lbrace_tag,
157 alt((parse_exprs, empty_boxed_vec)),
158 rbrace_tag,
159 ),
160 |exprs| {
161 Expr::Array(exprs)
162 }
163 )(input)
164}
165
166fn parse_sheet_or_multisheet(input: Tokens) -> IResult<Tokens, Token> {
167 let (i1, t1) = take(1usize)(input)?;
168 if t1.tok.is_empty() {
169 Err(Err::Error(NomError::new(input, ErrorKind::Tag)))
170 } else {
171 match &t1.tok[0] {
172 Token::MultiSheet(s) => Ok((i1, Token::MultiSheet(s.to_string()))),
173 Token::Sheet(s) => Ok((i1, Token::Sheet(s.to_string()))),
174 _ => Err(Err::Error(NomError::new(input, ErrorKind::Tag)))
175 }
176 }
177}
178
179fn parse_cell_or_range(input: Tokens) -> IResult<Tokens, Token> {
180 let (i1, t1) = take(1usize)(input)?;
181 if t1.tok.is_empty() {
182 Err(Err::Error(NomError::new(input, ErrorKind::Tag)))
183 } else {
184 match &t1.tok[0] {
185 Token::Range(s) => Ok((i1, Token::Range(s.to_string()))),
186 Token::Cell(s) => Ok((i1, Token::Cell(s.to_string()))),
187 Token::VRange(s) => Ok((i1, Token::VRange(s.to_string()))),
188 Token::HRange(s) => Ok((i1, Token::HRange(s.to_string()))),
189 _ => Err(Err::Error(NomError::new(input, ErrorKind::Tag)))
190 }
191 }
192}
193
194fn parse_reference_expr(input: Tokens) -> IResult<Tokens, Expr> {
195 map(
196 pair(
197 opt(parse_sheet_or_multisheet), parse_cell_or_range
198 ),
199 |(sheet, range)| {
200 let sheet : Option<String> = sheet.map(|x| format!("{}", x));
201 Expr::Reference {
202 sheet, reference: format!("{}", range)
203 }
204 }
205 )(input)
206}
207
208
209fn parse_paren_expr(input: Tokens) -> IResult<Tokens, Expr> {
210 delimited(lparen_tag, parse_expr, rparen_tag)(input)
211}
212
213
214fn infix_precedence(infix: Infix) -> Precedence {
215 match infix {
216 Infix::Equal
217 | Infix::NotEqual
218 | Infix::LessThan
219 | Infix::LessThanEqual
220 | Infix::GreaterThan
221 | Infix::GreaterThanEqual => Precedence::Comparison,
222 Infix::Ampersand => Precedence::Concat,
223 Infix::Plus | Infix::Minus => Precedence::PlusMinus,
224 Infix::Multiply | Infix::Divide => Precedence::MultDiv,
225 Infix::Exponent => Precedence::Exponent,
226 }
227}
228
229fn parse_infix_tags(input: Tokens) -> IResult<Tokens, Infix> {
230 alt((
231 map(plus_tag, |_| Infix::Plus),
232 map(minus_tag, |_| Infix::Minus),
233 map(divide_tag, |_| Infix::Divide),
234 map(multiply_tag, |_| Infix::Multiply),
235 map(equal_tag, |_| Infix::Equal),
236 map(pair(langle_tag, rangle_tag), |(_, _)| Infix::NotEqual),
237 map(pair(langle_tag, equal_tag), |(_, _)| Infix::LessThanEqual),
238 map(pair(rangle_tag, equal_tag), |(_, _)| Infix::GreaterThanEqual),
239 map(rangle_tag, |_| Infix::GreaterThan),
240 map(langle_tag, |_| Infix::LessThan),
241 map(exponent_tag, |_| Infix::Exponent),
242 map(ampersand_tag, |_| Infix::Ampersand),
243 ))(input)
244}
245
246fn parse_pratt(input: Tokens, precedence: Precedence) -> IResult<Tokens, Expr> {
247 let (i1, left) = parse_atom_expr(input)?;
248 go_parse_pratt(i1, left, precedence)
249}
250
251fn go_parse_pratt(input: Tokens, lhs: Expr, precedence: Precedence) -> IResult<Tokens, Expr> {
252 let (i1, t1) = take(1usize)(input)?;
253 if t1.tok.is_empty() {
254 Ok((i1, lhs))
255 } else {
256 match t1.tok[0] {
257 Token::EOF => Ok((input, lhs)),
258 _ => {
259 match parse_infix_tags(input) {
260 Ok((_, infix)) => {
261 let p = infix_precedence(infix);
262 if precedence < p {
263 let (i2, lhs2) = parse_infix(input, lhs)?;
264 go_parse_pratt(i2, lhs2, precedence)
265 } else {
266 Ok((input, lhs))
267 }
268 },
269 _ => Ok((input, lhs))
270 }
271 }
272 }
273 }
274}
275
276fn parse_infix(input: Tokens, lhs: Expr) -> IResult<Tokens, Expr> {
277 let (_i1, t1) = take(1usize)(input)?;
278 if t1.tok.is_empty() {
279 Err(Err::Error(error_position!(input, ErrorKind::Tag)))
280 } else {
281 let (i2, infix) = parse_infix_tags(input)?;
282 let p = infix_precedence(infix.clone());
283 let (i3, rhs) = parse_pratt(i2, p)?;
284 Ok((i3, Expr::Infix(infix, Box::new(lhs), Box::new(rhs))))
285 }
286}
287
288fn parse_infix_expr(input: Tokens) -> IResult<Tokens, Expr> {
289 parse_pratt(input, Precedence::Lowest)
290}
291
292fn parse_atom_expr(input: Tokens) -> IResult<Tokens, Expr> {
293 alt((
294 parse_prefix_expr,
295 parse_paren_expr,
296 parse_error_expr,
297 parse_func_expr,
298 parse_array_expr,
299 parse_reference_expr,
300 parse_literal_expr,
301 ))(input)
302}
303
304fn parse_expr(input: Tokens) -> IResult<Tokens, Expr> {
305 alt((
306 parse_infix_expr,
307 parse_atom_expr,
308 ))(input)
309}
310
311pub fn parse(input: Tokens) -> IResult<Tokens, Expr> {
312 terminated(parse_expr, eof_tag)(input)
313}
314
315pub fn parse_str(s: &str) -> Result<Expr, Error> {
316 let t = Lexer::lex_tokens(s.as_bytes())?;
317 let tokens = Tokens::new(&t);
318 match parse(tokens) {
319 Ok((_, expr)) => Ok(expr),
320 _ => Err(Error::UnableToParse(s.to_owned()))
321 }
322}
323
324#[cfg(test)]
325mod tests {
326 use crate::parser::parse_str;
327 use crate::parser::ast::{Expr, Error as ExcelError, Prefix, Infix};
328 use crate::errors::Error;
329
330 #[test]
331 fn test_literal() -> Result<(), Error> {
332 assert_eq!(parse_str("123")?, Expr::from(123.0));
333 assert_eq!(parse_str("1")?, Expr::from(1.0));
334 assert_eq!(parse_str("123.12")?, Expr::from(123.12));
335 assert_eq!(parse_str("123.123")?, Expr::from(123.123));
336 assert_eq!(parse_str("\"Test\"")?, Expr::from("Test"));
337 assert_eq!(parse_str("TRUE")?, Expr::from(true));
338 Ok(())
339 }
340
341 #[test]
342 fn test_errors() -> Result<(), Error> {
343 assert_eq!(parse_str("#NULL!")?, Expr::Error(ExcelError::Null));
344 assert_eq!(parse_str("#DIV/0!")?, Expr::Error(ExcelError::Div));
345 assert_eq!(parse_str("#VALUE!")?, Expr::Error(ExcelError::Value));
346 assert_eq!(parse_str("#REF!")?, Expr::Error(ExcelError::Ref));
347 assert_eq!(parse_str("#NAME!")?, Expr::Error(ExcelError::Name));
348 assert_eq!(parse_str("#NUM!")?, Expr::Error(ExcelError::Num));
349 assert_eq!(parse_str("#N/A!")?, Expr::Error(ExcelError::NA));
350 assert_eq!(parse_str("#GETTING_DATA")?, Expr::Error(ExcelError::GettingData));
351 Ok(())
352 }
353
354 #[test]
355 fn test_function() -> Result<(), Error> {
356 assert_eq!(parse_str("test(\"a\", \"b\")")?, Expr::Func {name: String::from("test"), args: vec![Expr::from("a"), Expr::from("b")]});
357 Ok(())
358 }
359
360 #[test]
361 fn test_reference() -> Result<(), Error> {
362 assert_eq!(parse_str("test!A1")?, Expr::Reference { sheet: Some("test".to_string()), reference: "A1".to_string()});
363 assert_eq!(parse_str("test!A1:B2")?, Expr::Reference { sheet: Some("test".to_string()), reference: "A1:B2".to_string()});
364 Ok(())
365 }
366
367 #[test]
368 fn test_array() -> Result<(), Error> {
369 assert_eq!(parse_str("{1, 2, 3, 4}")?, Expr::Array(vec![Expr::from(1.0), Expr::from(2.0), Expr::from(3.0), Expr::from(4.0)]));
370 assert_eq!(parse_str("{(1+2), 2, 3, 4}")?, Expr::Array(vec![
371 Expr::Infix(
372 Infix::Plus,
373 Box::new(Expr::from(1.0)),
374 Box::new(Expr::from(2.0))
375 ),
376 Expr::from(2.0),
377 Expr::from(3.0),
378 Expr::from(4.0)
379 ]));
380 Ok(())
381 }
382
383 #[test]
384 fn test_prefix() -> Result<(), Error>{
385 assert_eq!(parse_str("+1")?, Expr::Prefix(Prefix::Plus, Box::new(Expr::from(1.0))));
386 Ok(())
387 }
388
389 #[test]
390 fn test_infix() -> Result<(), Error> {
391 assert_eq!(parse_str("1+1")?, Expr::Infix(Infix::Plus, Box::new(Expr::from(1.0)), Box::new(Expr::from(1.0))));
392 assert_eq!(parse_str("(1+1)")?, Expr::Infix(Infix::Plus, Box::new(Expr::from(1.0)), Box::new(Expr::from(1.0))));
393 assert_eq!(parse_str("1 - 1")?, Expr::Infix(Infix::Minus, Box::new(Expr::from(1.0)), Box::new(Expr::from(1.0))));
394 assert_eq!(parse_str("1 / 1")?, Expr::Infix(Infix::Divide, Box::new(Expr::from(1.0)), Box::new(Expr::from(1.0))));
395 assert_eq!(parse_str("1 ^ 1")?, Expr::Infix(Infix::Exponent, Box::new(Expr::from(1.0)), Box::new(Expr::from(1.0))));
396 assert_eq!(parse_str("1 * 1")?, Expr::Infix(Infix::Multiply, Box::new(Expr::from(1.0)), Box::new(Expr::from(1.0))));
397 assert_eq!(parse_str("1 = 1")?, Expr::Infix(Infix::Equal, Box::new(Expr::from(1.0)), Box::new(Expr::from(1.0))));
398 assert_eq!(parse_str("1 < 1")?, Expr::Infix(Infix::LessThan, Box::new(Expr::from(1.0)), Box::new(Expr::from(1.0))));
399 assert_eq!(parse_str("1 <= 1")?, Expr::Infix(Infix::LessThanEqual, Box::new(Expr::from(1.0)), Box::new(Expr::from(1.0))));
400 assert_eq!(parse_str("1 > 1")?, Expr::Infix(Infix::GreaterThan, Box::new(Expr::from(1.0)), Box::new(Expr::from(1.0))));
401 assert_eq!(parse_str("1 >= 1")?, Expr::Infix(Infix::GreaterThanEqual, Box::new(Expr::from(1.0)), Box::new(Expr::from(1.0))));
402 assert_eq!(parse_str("1 <> 1")?, Expr::Infix(Infix::NotEqual, Box::new(Expr::from(1.0)), Box::new(Expr::from(1.0))));
403 assert_eq!(parse_str("1 <> 1")?, Expr::Infix(Infix::NotEqual, Box::new(Expr::from(1.0)), Box::new(Expr::from(1.0))));
404 assert_eq!(parse_str("(1+2)*(3+5)")?, Expr::Infix(
405 Infix::Multiply,
406 Box::new(Expr::Infix(
407 Infix::Plus,
408 Box::new(Expr::from(1.0)),
409 Box::new(Expr::from(2.0))
410 )),
411 Box::new(Expr::Infix(
412 Infix::Plus,
413 Box::new(Expr::from(3.0)),
414 Box::new(Expr::from(5.0))
415 ))
416 ));
417 assert_eq!(parse_str("(1+(2*1))")?, Expr::Infix(
418 Infix::Plus,
419 Box::new(Expr::from(1.0)),
420 Box::new(
421 Expr::Infix(
422 Infix::Multiply,
423 Box::new(Expr::from(2.0)),
424 Box::new(Expr::from(1.0))
425 )
426 )));
427 Ok(())
428 }
429
430 #[test]
431 fn test_reference_formula() -> Result<(), Error> {
432 assert_eq!(parse_str("SUM(Sheet1!A1:A10)")?, Expr::Func { name: "SUM".to_string(), args: vec![Expr::Reference { sheet: Some("Sheet1".to_string()), reference: "A1:A10".to_string() }] });
433 Ok(())
434 }
435
436 #[test]
437 fn test_floor() -> Result<(), Error> {
438 assert_eq!(parse_str("FLOOR(3.7, 1)")?, Expr::Func {
439 name: "FLOOR".to_string(),
440 args: vec![
441 Expr::from(3.7),
442 Expr::from(1.0)
443 ]
444 });
445 Ok(())
446 }
447
448 #[test]
449 fn test_infix_precedence() -> Result<(), Error> {
450 assert_eq!(parse_str("-(1+1)-2")?, Expr::Infix(
451 Infix::Minus,
452 Box::new(Expr::Prefix(
453 Prefix::Minus,
454 Box::new(Expr::Infix(
455 Infix::Plus,
456 Box::new(Expr::from(1.0)),
457 Box::new(Expr::from(1.0))
458 ))
459 )),
460 Box::new(Expr::from(2.0))
461 ));
462 Ok(())
463 }
464
465 #[test]
466 fn test_complex() -> Result<(), Error> {
467 assert_eq!(parse_str("1*1*1*1")?,
468 Expr::Infix(
469 Infix::Multiply,
470 Box::new(
471 Expr::Infix(
472 Infix::Multiply,
473 Box::new(
474 Expr::Infix(
475 Infix::Multiply,
476 Box::new(Expr::from(1.0)),
477 Box::new(Expr::from(1.0))
478 )
479 ),
480 Box::new(Expr::from(1.0))
481 )
482 ),
483 Box::new(Expr::from(1.0))
484 )
485 );
486 Ok(())
487 }
488}