1use std::fmt::Display;
6
7use crate::ast;
8use crate::input::{HasSpan, Span};
9use crate::lex::{self, Token, TokenKind};
10
11#[derive(Debug)]
12pub enum Error {
13 Lex(lex::Error),
14 UnexpectedEndOfInput(Span),
15 UnexpectedToken(Token, Option<String>),
16}
17
18impl From<lex::Error> for Error {
19 fn from(e: lex::Error) -> Self {
20 Error::Lex(e)
21 }
22}
23
24impl HasSpan for Error {
25 fn span(&self) -> Span {
26 match self {
27 Error::Lex(err) => err.span(),
28 Error::UnexpectedEndOfInput(span) => *span,
29 Error::UnexpectedToken(tok, _) => tok.span,
30 }
31 }
32}
33
34impl Display for Error {
35 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
36 match self {
37 Error::Lex(err) => err.fmt(f),
38 Error::UnexpectedEndOfInput(_) => {
39 write!(f, "Unexpected end of input")
40 }
41 Error::UnexpectedToken(tok, expected) => {
42 write!(f, "Unexpected token: {:?}", tok.kind)?;
43 if let Some(expected) = expected {
44 write!(f, " (expected {})", expected)?;
45 }
46 Ok(())
47 }
48 }
49 }
50}
51
52pub type Result<T> = std::result::Result<T, Error>;
53
54pub fn parse_line<I>(chars: I) -> Result<ast::Item>
56where
57 I: IntoIterator<Item = char>,
58 I::IntoIter: Clone,
59{
60 let tokens = lex::tokenize(chars).in_band();
61 Parser::new(tokens).parse_item()
62}
63
64#[derive(Debug, Clone)]
65pub struct Parser<T> {
66 tokens: T,
67 last_span: Span,
68}
69
70impl<T> Parser<T> {
71 pub fn new(tokens: T) -> Parser<T> {
72 Parser {
73 tokens,
74 last_span: (0, 0),
75 }
76 }
77}
78
79impl<T> Parser<T>
80where
81 T: Iterator<Item = lex::Result<Token>> + Clone,
82{
83 fn expect_kind(&mut self, kind: TokenKind) -> Result<Span> {
84 let tok = self.next_token()?;
85 if let Some(tok) = tok {
86 if tok.kind == kind {
87 Ok(tok.span)
88 } else {
89 Err(Error::UnexpectedToken(tok, Some(format!("{:?}", kind))))
90 }
91 } else {
92 let span = (self.last_span.1, self.last_span.1 + 2);
93 Err(Error::UnexpectedEndOfInput(span))
94 }
95 }
96}
97
98impl<T> Parser<T>
99where
100 T: Iterator<Item = lex::Result<Token>> + Clone,
101{
102 fn first_token(&self) -> lex::Result<Option<Token>> {
103 self.tokens.clone().next().transpose()
104 }
105
106 fn bump_token(&mut self) {
107 self.next_token().unwrap();
108 }
109
110 fn next_token(&mut self) -> Result<Option<Token>> {
111 let tok = self.tokens.next().transpose()?;
112 if let Some(tok) = &tok {
113 self.last_span = tok.span;
114 }
115 Ok(tok)
116 }
117
118 fn parse_item(&mut self) -> Result<ast::Item> {
119 let mut cl_toks = self.tokens.clone();
120 let tok1 = cl_toks.next().transpose()?;
121 let item = match tok1 {
122 Some(Token {
123 kind: TokenKind::Symbol(sym),
124 span,
125 }) => {
126 let tok2 = cl_toks.next().transpose()?;
127 if let Some(Token {
128 kind: TokenKind::Equal,
129 ..
130 }) = tok2
131 {
132 self.bump_token(); self.bump_token(); let expr = self.parse_expr()?;
135 let span = (span.0, expr.span.1);
136 Ok(ast::Item {
137 kind: ast::ItemKind::Assign(sym, expr),
138 span,
139 })
140 } else {
141 let expr = self.parse_expr()?;
142 let span = expr.span;
143 Ok(ast::Item {
144 kind: ast::ItemKind::Expr(expr),
145 span,
146 })
147 }
148 }
149 Some(..) => {
150 let expr = self.parse_expr()?;
151 let span = expr.span;
152 Ok(ast::Item {
153 kind: ast::ItemKind::Expr(expr),
154 span,
155 })
156 }
157 None => Err(Error::UnexpectedEndOfInput(self.last_span)),
158 };
159 let tok = self.next_token()?;
160 if let Some(tok) = tok {
161 return Err(Error::UnexpectedToken(
162 tok,
163 Some("NewLine or Operator".to_string()),
164 ));
165 }
166 item
167 }
168
169 fn parse_expr(&mut self) -> Result<ast::Expr> {
170 self.parse_add_expr()
171 }
172
173 fn parse_add_expr(&mut self) -> Result<ast::Expr> {
174 let mut lhs = self.parse_mul_expr()?;
175 loop {
176 let tok = self.first_token()?;
177 match tok {
178 Some(Token { kind, .. }) if is_add_op(&kind) => {
179 self.bump_token();
180 let rhs = self.parse_mul_expr()?;
181 let expr = ast::Expr {
182 span: (lhs.span.0, rhs.span.1),
183 kind: ast::ExprKind::BinOp(bin_op(&kind), Box::new(lhs), Box::new(rhs)),
184 };
185 lhs = expr;
186 }
187 _ => return Ok(lhs),
188 }
189 }
190 }
191
192 fn parse_mul_expr(&mut self) -> Result<ast::Expr> {
193 let mut lhs = self.parse_unary_expr()?;
194 loop {
195 let tok = self.first_token()?;
196 match tok {
197 Some(Token { kind, .. }) if is_mul_op(&kind) => {
198 self.bump_token();
199 let rhs = self.parse_unary_expr()?;
200 let expr = ast::Expr {
201 span: (lhs.span.0, rhs.span.1),
202 kind: ast::ExprKind::BinOp(bin_op(&kind), Box::new(lhs), Box::new(rhs)),
203 };
204 lhs = expr;
205 }
206 _ => return Ok(lhs),
207 }
208 }
209 }
210
211 fn parse_unary_expr(&mut self) -> Result<ast::Expr> {
212 let tok = self.first_token()?;
213 match tok {
214 Some(Token { kind, span }) if is_un_op(&kind) => {
215 self.bump_token();
216 let expr = self.parse_pow_expr()?;
217 let span = (span.0, expr.span.1);
218 Ok(ast::Expr {
219 kind: ast::ExprKind::UnOp(un_op(&kind), Box::new(expr)),
220 span,
221 })
222 }
223 _ => Ok(self.parse_pow_expr()?),
224 }
225 }
226
227 fn parse_pow_expr(&mut self) -> Result<ast::Expr> {
228 let lhs = self.parse_primary()?;
229 let tok = self.first_token()?;
230 match tok {
231 Some(Token {
232 kind: TokenKind::Hat,
233 ..
234 }) => {
235 self.bump_token();
236 let rhs = self.parse_pow_expr()?;
237 let span = (lhs.span.0, rhs.span.1);
238 Ok(ast::Expr {
239 kind: ast::ExprKind::BinOp(ast::BinOp::Pow, Box::new(lhs), Box::new(rhs)),
240 span,
241 })
242 }
243 _ => Ok(lhs),
244 }
245 }
246
247 fn parse_primary(&mut self) -> Result<ast::Expr> {
248 let tok = self.next_token()?;
249 match tok {
250 Some(Token {
251 kind: TokenKind::Num(val),
252 span,
253 }) => Ok(ast::Expr {
254 kind: ast::ExprKind::Num(val),
255 span,
256 }),
257 Some(Token {
258 kind: TokenKind::OpenPar,
259 span,
260 }) => {
261 let expr = self.parse_expr()?;
262 let endspan = self.expect_kind(TokenKind::ClosePar)?;
263 let span = (span.0, endspan.1);
264 Ok(ast::Expr {
265 kind: expr.kind,
266 span,
267 })
268 }
269 Some(Token {
270 kind: TokenKind::Symbol(name),
271 span: name_span,
272 }) => {
273 let next = self.first_token()?;
274 match next {
275 Some(Token {
276 kind: TokenKind::OpenPar,
277 ..
278 }) => {
279 self.bump_token();
280 let args = self.parse_arg_list()?;
281 let closespan = self.expect_kind(TokenKind::ClosePar)?;
282 let span = (name_span.0, closespan.1);
283 Ok(ast::Expr {
284 kind: ast::ExprKind::Call {
285 name_span,
286 name,
287 args,
288 },
289 span,
290 })
291 }
292 _ => Ok(ast::Expr {
293 kind: ast::ExprKind::Var(name),
294 span: name_span,
295 }),
296 }
297 }
298 Some(tok) => Err(Error::UnexpectedToken(tok, None)),
299 None => Err(Error::UnexpectedEndOfInput(self.last_span)),
300 }
301 }
302
303 fn parse_arg_list(&mut self) -> Result<Vec<ast::Expr>> {
304 let mut args = Vec::new();
305 loop {
306 let tok = self.first_token()?;
307 match tok {
308 Some(Token {
309 kind: TokenKind::ClosePar,
310 ..
311 }) => {
312 break;
313 }
314 Some(Token {
315 kind: TokenKind::Comma,
316 ..
317 }) => continue,
318 Some(..) => {
319 args.push(self.parse_expr()?);
320 }
321 None => return Err(Error::UnexpectedEndOfInput(self.eoi_span())),
322 }
323 }
324 Ok(args)
325 }
326
327 fn eoi_span(&self) -> Span {
328 (self.last_span.1, self.last_span.1 + 1)
329 }
330}
331
332fn is_add_op(kind: &TokenKind) -> bool {
333 matches!(kind, TokenKind::Plus | TokenKind::Minus)
334}
335
336fn is_mul_op(kind: &TokenKind) -> bool {
337 matches!(
338 kind,
339 TokenKind::Star | TokenKind::Slash | TokenKind::Percent
340 )
341}
342
343fn is_un_op(kind: &TokenKind) -> bool {
344 matches!(kind, TokenKind::Plus | TokenKind::Minus)
345}
346
347fn bin_op(kind: &TokenKind) -> ast::BinOp {
348 match kind {
349 TokenKind::Plus => ast::BinOp::Add,
350 TokenKind::Minus => ast::BinOp::Sub,
351 TokenKind::Star => ast::BinOp::Mul,
352 TokenKind::Slash => ast::BinOp::Div,
353 TokenKind::Percent => ast::BinOp::Mod,
354 _ => unreachable!(),
355 }
356}
357
358fn un_op(kind: &TokenKind) -> ast::UnOp {
359 match kind {
360 TokenKind::Plus => ast::UnOp::Plus,
361 TokenKind::Minus => ast::UnOp::Minus,
362 _ => unreachable!(),
363 }
364}
365
366#[test]
367fn test_parse_assignment() {
368 let item: ast::Item = parse_line("x = 2".chars()).unwrap();
369
370 assert_eq!(
371 item,
372 ast::Item {
373 span: (0, 5),
374 kind: ast::ItemKind::Assign(
375 "x".to_string(),
376 ast::Expr {
377 span: (4, 5),
378 kind: ast::ExprKind::Num(2.0),
379 }
380 )
381 }
382 )
383}
384
385#[test]
386fn test_parse_add() {
387 let item: ast::Item = parse_line("1 + 2".chars()).unwrap();
388
389 assert_eq!(
390 item,
391 ast::Item {
392 span: (0, 5),
393 kind: ast::ItemKind::Expr(ast::Expr {
394 span: (0, 5),
395 kind: ast::ExprKind::BinOp(
396 ast::BinOp::Add,
397 Box::new(ast::Expr {
398 span: (0, 1),
399 kind: ast::ExprKind::Num(1.0),
400 }),
401 Box::new(ast::Expr {
402 span: (4, 5),
403 kind: ast::ExprKind::Num(2.0),
404 })
405 )
406 })
407 }
408 )
409}
410
411#[test]
412fn test_parse_mul() {
413 let item: ast::Item = parse_line("2 * 3".chars()).unwrap();
414
415 assert_eq!(
416 item,
417 ast::Item {
418 span: (0, 5),
419 kind: ast::ItemKind::Expr(ast::Expr {
420 span: (0, 5),
421 kind: ast::ExprKind::BinOp(
422 ast::BinOp::Mul,
423 Box::new(ast::Expr {
424 span: (0, 1),
425 kind: ast::ExprKind::Num(2.0),
426 }),
427 Box::new(ast::Expr {
428 span: (4, 5),
429 kind: ast::ExprKind::Num(3.0),
430 })
431 )
432 })
433 }
434 )
435}
436
437#[test]
438fn test_parse_unary() {
439 let item: ast::Item = parse_line("-3".chars()).unwrap();
440
441 assert_eq!(
442 item,
443 ast::Item {
444 span: (0, 2),
445 kind: ast::ItemKind::Expr(ast::Expr {
446 span: (0, 2),
447 kind: ast::ExprKind::UnOp(
448 ast::UnOp::Minus,
449 Box::new(ast::Expr {
450 span: (1, 2),
451 kind: ast::ExprKind::Num(3.0),
452 }),
453 )
454 })
455 }
456 )
457}
458
459#[test]
460fn test_parse_2nd_order() {
461 let item: ast::Item = parse_line("y = 3*x^2 + 4".chars()).unwrap();
462
463 assert_eq!(
464 item,
465 ast::Item {
466 span: (0, 13),
467 kind: ast::ItemKind::Assign(
468 "y".to_string(),
469 ast::Expr {
470 span: (4, 13),
471 kind: ast::ExprKind::BinOp(
472 ast::BinOp::Add,
473 Box::new(ast::Expr {
474 span: (4, 9),
475 kind: ast::ExprKind::BinOp(
476 ast::BinOp::Mul,
477 Box::new(ast::Expr {
478 span: (4, 5),
479 kind: ast::ExprKind::Num(3.0),
480 }),
481 Box::new(ast::Expr {
482 span: (6, 9),
483 kind: ast::ExprKind::BinOp(
484 ast::BinOp::Pow,
485 Box::new(ast::Expr {
486 span: (6, 7),
487 kind: ast::ExprKind::Var("x".to_string()),
488 }),
489 Box::new(ast::Expr {
490 span: (8, 9),
491 kind: ast::ExprKind::Num(2.0),
492 }),
493 ),
494 }),
495 )
496 }),
497 Box::new(ast::Expr {
498 span: (12, 13),
499 kind: ast::ExprKind::Num(4.0),
500 })
501 ),
502 },
503 )
504 }
505 )
506}
507
508#[test]
509fn test_parse_add_mul() {
510 let items: ast::Item = parse_line("1 + 2 * 3".chars()).unwrap();
511
512 assert_eq!(
513 items,
514 ast::Item {
515 span: (0, 9),
516 kind: ast::ItemKind::Expr(ast::Expr {
517 span: (0, 9),
518 kind: ast::ExprKind::BinOp(
519 ast::BinOp::Add,
520 Box::new(ast::Expr {
521 span: (0, 1),
522 kind: ast::ExprKind::Num(1.0),
523 }),
524 Box::new(ast::Expr {
525 span: (4, 9),
526 kind: ast::ExprKind::BinOp(
527 ast::BinOp::Mul,
528 Box::new(ast::Expr {
529 span: (4, 5),
530 kind: ast::ExprKind::Num(2.0),
531 }),
532 Box::new(ast::Expr {
533 span: (8, 9),
534 kind: ast::ExprKind::Num(3.0),
535 })
536 ),
537 })
538 )
539 })
540 }
541 )
542}
543
544#[test]
545fn test_parse_mul_add() {
546 let items: ast::Item = parse_line("1 * 2 + 3".chars()).unwrap();
547
548 assert_eq!(
549 items,
550 ast::Item {
551 span: (0, 9),
552 kind: ast::ItemKind::Expr(ast::Expr {
553 span: (0, 9),
554 kind: ast::ExprKind::BinOp(
555 ast::BinOp::Add,
556 Box::new(ast::Expr {
557 span: (0, 5),
558 kind: ast::ExprKind::BinOp(
559 ast::BinOp::Mul,
560 Box::new(ast::Expr {
561 span: (0, 1),
562 kind: ast::ExprKind::Num(1.0),
563 }),
564 Box::new(ast::Expr {
565 span: (4, 5),
566 kind: ast::ExprKind::Num(2.0),
567 })
568 ),
569 }),
570 Box::new(ast::Expr {
571 span: (8, 9),
572 kind: ast::ExprKind::Num(3.0),
573 })
574 )
575 })
576 }
577 )
578}
579
580#[test]
581fn test_parse_mul_add_parentheses() {
582 let items: ast::Item = parse_line("1 * (2 + 3)".chars()).unwrap();
583
584 assert_eq!(
585 items,
586 ast::Item {
587 span: (0, 11),
588 kind: ast::ItemKind::Expr(ast::Expr {
589 span: (0, 11),
590 kind: ast::ExprKind::BinOp(
591 ast::BinOp::Mul,
592 Box::new(ast::Expr {
593 span: (0, 1),
594 kind: ast::ExprKind::Num(1.0),
595 }),
596 Box::new(ast::Expr {
597 span: (4, 11),
598 kind: ast::ExprKind::BinOp(
599 ast::BinOp::Add,
600 Box::new(ast::Expr {
601 span: (5, 6),
602 kind: ast::ExprKind::Num(2.0),
603 }),
604 Box::new(ast::Expr {
605 span: (9, 10),
606 kind: ast::ExprKind::Num(3.0),
607 })
608 )
609 })
610 )
611 })
612 }
613 )
614}
615
616#[test]
617fn test_sin_pi() {
618 let item: ast::Item = parse_line("sin(pi)".chars()).unwrap();
619
620 assert_eq!(
621 item,
622 ast::Item {
623 span: (0, 7),
624 kind: ast::ItemKind::Expr(ast::Expr {
625 span: (0, 7),
626 kind: ast::ExprKind::Call {
627 name_span: (0, 3),
628 name: "sin".to_string(),
629 args: vec![ast::Expr {
630 span: (4, 6),
631 kind: ast::ExprKind::Var("pi".to_string(),)
632 }]
633 }
634 })
635 }
636 )
637}
638
639#[test]
640fn fail_test_14_eq_12() {
641 assert!(parse_line("14 = 12".chars()).is_err());
642}
643
644#[test]
645fn test_parse_add_add() {
646 let item: ast::Item = parse_line("1 + 2 + 3".chars()).unwrap();
647
648 assert_eq!(
649 item,
650 ast::Item {
651 span: (0, 9),
652 kind: ast::ItemKind::Expr(ast::Expr {
653 span: (0, 9),
654 kind: ast::ExprKind::BinOp(
655 ast::BinOp::Add,
656 Box::new(ast::Expr {
657 span: (0, 5),
658 kind: ast::ExprKind::BinOp(
659 ast::BinOp::Add,
660 Box::new(ast::Expr {
661 span: (0, 1),
662 kind: ast::ExprKind::Num(1.0),
663 }),
664 Box::new(ast::Expr {
665 span: (4, 5),
666 kind: ast::ExprKind::Num(2.0),
667 })
668 )
669 }),
670 Box::new(ast::Expr {
671 span: (8, 9),
672 kind: ast::ExprKind::Num(3.0),
673 })
674 )
675 })
676 }
677 )
678}
679
680#[test]
681fn test_parse_minus_minus() {
682 let item: ast::Item = parse_line("1 - 2 - 3".chars()).unwrap();
683
684 assert_eq!(
685 item,
686 ast::Item {
687 span: (0, 9),
688 kind: ast::ItemKind::Expr(ast::Expr {
689 span: (0, 9),
690 kind: ast::ExprKind::BinOp(
691 ast::BinOp::Sub,
692 Box::new(ast::Expr {
693 span: (0, 5),
694 kind: ast::ExprKind::BinOp(
695 ast::BinOp::Sub,
696 Box::new(ast::Expr {
697 span: (0, 1),
698 kind: ast::ExprKind::Num(1.0),
699 }),
700 Box::new(ast::Expr {
701 span: (4, 5),
702 kind: ast::ExprKind::Num(2.0),
703 })
704 )
705 }),
706 Box::new(ast::Expr {
707 span: (8, 9),
708 kind: ast::ExprKind::Num(3.0),
709 })
710 )
711 })
712 }
713 )
714}
715
716#[test]
717fn test_parse_mul_mul() {
718 let item: ast::Item = parse_line("1 * 2 * 3".chars()).unwrap();
719
720 assert_eq!(
721 item,
722 ast::Item {
723 span: (0, 9),
724 kind: ast::ItemKind::Expr(ast::Expr {
725 span: (0, 9),
726 kind: ast::ExprKind::BinOp(
727 ast::BinOp::Mul,
728 Box::new(ast::Expr {
729 span: (0, 5),
730 kind: ast::ExprKind::BinOp(
731 ast::BinOp::Mul,
732 Box::new(ast::Expr {
733 span: (0, 1),
734 kind: ast::ExprKind::Num(1.0),
735 }),
736 Box::new(ast::Expr {
737 span: (4, 5),
738 kind: ast::ExprKind::Num(2.0),
739 })
740 ),
741 }),
742 Box::new(ast::Expr {
743 span: (8, 9),
744 kind: ast::ExprKind::Num(3.0),
745 }),
746 )
747 })
748 }
749 );
750}
751
752#[test]
753fn test_parse_div_div() {
754 let item: ast::Item = parse_line("1 / 2 / 3".chars()).unwrap();
755
756 assert_eq!(
757 item,
758 ast::Item {
759 span: (0, 9),
760 kind: ast::ItemKind::Expr(ast::Expr {
761 span: (0, 9),
762 kind: ast::ExprKind::BinOp(
763 ast::BinOp::Div,
764 Box::new(ast::Expr {
765 span: (0, 5),
766 kind: ast::ExprKind::BinOp(
767 ast::BinOp::Div,
768 Box::new(ast::Expr {
769 span: (0, 1),
770 kind: ast::ExprKind::Num(1.0),
771 }),
772 Box::new(ast::Expr {
773 span: (4, 5),
774 kind: ast::ExprKind::Num(2.0),
775 })
776 ),
777 }),
778 Box::new(ast::Expr {
779 span: (8, 9),
780 kind: ast::ExprKind::Num(3.0),
781 }),
782 )
783 })
784 }
785 );
786}