kaon/compiler/
parser.rs

1use std::rc::Rc;
2
3use crate::{
4    common::{Span, Spanned},
5    compiler::{
6        ASTNode, BinExpr, Class, Constructor, Expr, FunAccess, Ident, Op, ScriptFun, Stmt, Token,
7        TokenType, TypePath, AST,
8    },
9    error::{Error, Item},
10    Source,
11};
12
13use super::{
14    ast::{Signature, Trait, TraitMethod},
15    token::{Delimiter, Keyword, Literal, Symbol, Comment},
16    Lexer,
17};
18
19/// Recursive descent parser for the Kaon language.
20/// Takes a stream of [Token]s created by the [Lexer] and generates an [AST] from it.
21///
22/// # Errors
23/// If the input has any syntactic errors, the parser will return them.
24pub struct Parser {
25    tokens: Spanned<Vec<Token>>,
26    current: Token,
27    pos: usize,
28}
29
30impl Parser {
31    pub fn new(tokens: Spanned<Vec<Token>>) -> Parser {
32        Parser {
33            tokens,
34            current: (TokenType::eof(), Span::empty()),
35            pos: 0,
36        }
37    }
38
39    pub fn parse_source(source: Rc<Source>) -> Result<AST, Error> {
40        let token_stream = Lexer::new(source).tokenize()?;
41        let mut parser = Parser::new(token_stream);
42
43        Ok(parser.parse()?)
44    }
45
46    /// Consume the next token.
47    fn consume(&mut self, token_type: TokenType) -> Result<Span, Error> {
48        match token_type {
49            token_type if token_type == self.current.0 => {
50                self.pos += 1;
51                let old_token =
52                    std::mem::replace(&mut self.current, self.tokens.node[self.pos].clone());
53                Ok(old_token.1)
54            }
55            _ if self.current.0 == TokenType::Delimiter(Delimiter::Newline) => {
56                self.expect_delimiter(Delimiter::Newline)?;
57                self.consume(token_type)
58            }
59            _ => Err(self.error()),
60        }
61    }
62
63    /// Consume a delimiter.
64    fn expect_delimiter(&mut self, delimiter: Delimiter) -> Result<Span, Error> {
65        self.consume(TokenType::Delimiter(delimiter))
66    }
67
68    /// Consume a keyword.
69    fn expect_keyword(&mut self, keyword: Keyword) -> Result<Span, Error> {
70        self.consume(TokenType::Keyword(keyword))
71    }
72
73    /// Consume a symbol.
74    fn symbol(&mut self, symbol: Symbol) -> Result<Span, Error> {
75        self.consume(TokenType::Symbol(symbol))
76    }
77
78    fn _expect(&mut self, token_type: TokenType) -> Result<Span, Error> {
79        match token_type {
80            token_type if token_type == self.current.0 => {
81                self.pos += 1;
82                let old_token =
83                    std::mem::replace(&mut self.current, self.tokens.node[self.pos].clone());
84                Ok(old_token.1)
85            }
86            TokenType::Delimiter(Delimiter::Eof) => Err(Error::UnexpectedEOF(Item::new(
87                "<eof>",
88                self.current.1.clone(),
89            ))),
90            _ => Err(Error::ExpectedToken(
91                Item::new(&self.current.0.to_string(), self.current.1.clone()),
92                Item::new(&self.current.0.to_string(), self.current.1.clone()),
93            )),
94        }
95    }
96
97    fn last(&self) -> &Token {
98        &self.tokens.node[self.pos - 1]
99    }
100
101    /// Return an unexpected token error.
102    fn error(&self) -> Error {
103        Error::UnexpectedToken(Item::new(
104            &self.current.0.to_string(),
105            self.current.1.clone(),
106        ))
107    }
108
109    /// Get the next token without checking it.
110    fn next(&mut self) {
111        self.pos += 1;
112        self.current = self.tokens.node[self.pos].clone();
113    }
114
115    /// Parse a compound statement.
116    fn compound_statement(&mut self) -> Result<Stmt, Error> {
117        match &self.current.0 {
118            TokenType::Keyword(Keyword::If) => self.if_statement(),
119            TokenType::Keyword(Keyword::Loop) => self.loop_statement(),
120            TokenType::Keyword(Keyword::While) => self.while_statement(),
121            TokenType::Keyword(Keyword::Class) => self.class(),
122            TokenType::Keyword(Keyword::Trait) => self.parse_trait(),
123            TokenType::Keyword(Keyword::Fun) => self.fun(),
124            TokenType::Keyword(Keyword::Public) => self.modifier(),
125            TokenType::Delimiter(Delimiter::OpenBrace) => self.block(),
126            _ => self.statement(),
127        }
128    }
129
130    /// Parse a statement and consume a delimiter.
131    fn statement(&mut self) -> Result<Stmt, Error> {
132        let node = self.simple_statement();
133
134        match &self.current.0 {
135            TokenType::Delimiter(Delimiter::Newline) => {
136                self.expect_delimiter(Delimiter::Newline)?;
137                node
138            }
139            TokenType::Symbol(Symbol::SemiColon) => {
140                self.symbol(Symbol::SemiColon)?;
141                node
142            }
143            TokenType::Delimiter(Delimiter::Eof) | TokenType::Delimiter(Delimiter::CloseBrace) => {
144                node
145            }
146            node => Err(Error::ExpectedNewline(Item::new(
147                &node.to_string(),
148                self.current.1.clone(),
149            ))),
150        }
151    }
152
153    /// Parse a statement.
154    fn simple_statement(&mut self) -> Result<Stmt, Error> {
155        match &self.current.0 {
156            TokenType::Keyword(Keyword::Var) => self.var_decl(),
157            TokenType::Keyword(Keyword::Final) => self.const_decl(),
158            TokenType::Keyword(Keyword::Break) => self.break_stmt(),
159            TokenType::Keyword(Keyword::Continue) => self.continue_stmt(),
160            TokenType::Keyword(Keyword::Return) => self.return_stmt(),
161            TokenType::Keyword(Keyword::Import) => self.import_stmt(),
162            TokenType::Keyword(Keyword::Trait) => self.parse_trait(),
163            _ => Ok(self.assignment_stmt()?),
164        }
165    }
166
167    /// Parse a block.
168    fn block(&mut self) -> Result<Stmt, Error> {
169        self.expect_delimiter(Delimiter::OpenBrace)?;
170        let mut nodes = vec![];
171        loop {
172            match &self.current.0 {
173                TokenType::Delimiter(Delimiter::CloseBrace) => {
174                    self.expect_delimiter(Delimiter::CloseBrace)?;
175                    break;
176                }
177                TokenType::Delimiter(Delimiter::Newline) => {
178                    self.expect_delimiter(Delimiter::Newline)?;
179                    continue;
180                }
181                TokenType::Delimiter(Delimiter::Eof) => {
182                    return Err(Error::UnexpectedEOF(Item::new(
183                        "<eof>",
184                        self.current.1.clone(),
185                    )));
186                }
187                TokenType::Comment(_) => {
188                    self.comment()?;
189                    continue;
190                }
191                _ => {
192                    nodes.push(self.compound_statement()?);
193                }
194            }
195        }
196
197        Ok(Stmt::Block(Box::new(nodes), self.tokens.source.clone()))
198    }
199
200    fn loop_statement(&mut self) -> Result<Stmt, Error> {
201        self.expect_keyword(Keyword::Loop)?;
202        Ok(Stmt::LoopStatement(
203            Box::new(self.block()?),
204            self.current.1.clone(),
205        ))
206    }
207
208    fn while_statement(&mut self) -> Result<Stmt, Error> {
209        self.expect_keyword(Keyword::While)?;
210        Ok(Stmt::WhileStatement(
211            self.disjunction()?,
212            Box::new(self.block()?),
213            self.current.1.clone(),
214        ))
215    }
216
217    fn break_stmt(&mut self) -> Result<Stmt, Error> {
218        let start = self.expect_keyword(Keyword::Break)?;
219        Ok(Stmt::Break(start))
220    }
221
222    fn continue_stmt(&mut self) -> Result<Stmt, Error> {
223        let start = self.expect_keyword(Keyword::Continue)?;
224        Ok(Stmt::Continue(start))
225    }
226
227    fn if_statement(&mut self) -> Result<Stmt, Error> {
228        self.expect_keyword(Keyword::If)?;
229
230        let condition = self.disjunction()?;
231
232        let block = self.block()?;
233        let alternate = match &self.current.0 {
234            TokenType::Keyword(Keyword::Else) => Some(self.parse_else_block()?),
235            _ => None,
236        };
237
238        Ok(Stmt::IfStatement(
239            condition,
240            Box::new((block, alternate)),
241            self.current.1.clone(),
242        ))
243    }
244
245    fn parse_else_block(&mut self) -> Result<Stmt, Error> {
246        self.expect_keyword(Keyword::Else)?;
247
248        if let TokenType::Keyword(Keyword::If) = self.current.0 {
249            self.if_statement()
250        } else {
251            self.block()
252        }
253    }
254
255    fn modifier(&mut self) -> Result<Stmt, Error> {
256        self.expect_keyword(Keyword::Public)?;
257
258        match &self.current.0 {
259            TokenType::Keyword(Keyword::Fun) => {
260                let mut fun = self.fun_()?;
261                fun.0.access = FunAccess::Public;
262
263                Ok(Stmt::Function(Box::new(fun.0), fun.1))
264            }
265            _ => Err(self.error()),
266        }
267    }
268
269    fn class(&mut self) -> Result<Stmt, Error> {
270        let start = self.expect_keyword(Keyword::Class)?;
271
272        let name = self.identifier()?;
273
274        let mut fields: Vec<Stmt> = vec![];
275        let mut methods: Vec<Stmt> = vec![];
276        let mut constructors: Vec<Stmt> = vec![];
277
278        self.consume(TokenType::delimiter("{"))?;
279
280        loop {
281            match &self.current.0 {
282                TokenType::Delimiter(Delimiter::CloseBrace) => {
283                    break;
284                }
285                TokenType::Keyword(keyword) => match keyword {
286                    Keyword::Create => {
287                        constructors.push(self.constructor(&name.name)?);
288                    }
289                    Keyword::Fun => {
290                        methods.push(self.fun()?);
291                    }
292                    Keyword::Var => {
293                        fields.push(self.var_decl()?);
294                    }
295                    _ => return Err(self.error()),
296                },
297                TokenType::Delimiter(Delimiter::Newline) => {
298                    self.expect_delimiter(Delimiter::Newline)?;
299                    continue;
300                }
301                TokenType::Comment(_) => {
302                    self.next();
303                    continue;
304                }
305                TokenType::Delimiter(Delimiter::Eof) => {
306                    return Err(Error::UnexpectedEOF(Item::new(
307                        "<eof>",
308                        self.current.1.clone(),
309                    )));
310                }
311                _ => return Err(self.error()),
312            }
313        }
314
315        let end = self.consume(TokenType::delimiter("}"))?;
316        let class = Class::new(name, None, fields, methods, constructors);
317
318        Ok(Stmt::Class(class, Span::combine(&start, &end)))
319    }
320
321    fn parse_trait(&mut self) -> Result<Stmt, Error> {
322        self.expect_keyword(Keyword::Trait)?;
323
324        let name = self.identifier()?;
325
326        match &self.current.0 {
327            TokenType::Symbol(Symbol::Colon) => self.trait_sum(name),
328            TokenType::Delimiter(Delimiter::OpenBrace) => self.trait_decl(name),
329            token => Err(Error::UnexpectedToken(Item::new(
330                &token.to_string(),
331                self.current.1.clone(),
332            ))),
333        }
334    }
335
336    fn trait_decl(&mut self, name: Ident) -> Result<Stmt, Error> {
337        self.expect_delimiter(Delimiter::OpenBrace)?;
338
339        let mut methods = Vec::new();
340
341        while self.current.0 != TokenType::Delimiter(Delimiter::CloseBrace) {
342            match &self.current.0 {
343                TokenType::Delimiter(Delimiter::Newline) => {
344                    self.next();
345                    continue;
346                }
347                TokenType::Keyword(Keyword::Fun) => {
348                    methods.push(self.trait_method()?);
349                }
350                token => {
351                    return Err(Error::UnexpectedToken(Item::new(
352                        &token.to_string(),
353                        self.current.1.clone(),
354                    )))
355                }
356            };
357        }
358
359        let end = self.expect_delimiter(Delimiter::CloseBrace)?;
360        let span = Span::combine(&name.span, &end);
361
362        let trait_ = Trait { methods, span };
363
364        Ok(Stmt::Trait(trait_))
365    }
366
367    fn trait_method(&mut self) -> Result<TraitMethod, Error> {
368        let sig = self.fun_signature()?;
369        let start = &sig.span.clone();
370
371        let mut default = None;
372
373        if let TokenType::Delimiter(Delimiter::OpenBrace) = self.current.0 {
374            default = Some(self.block()?);
375        }
376
377        Ok(TraitMethod {
378            sig,
379            default,
380            span: Span::combine(start, &self.last().1),
381        })
382    }
383
384    fn fun_signature(&mut self) -> Result<Signature, Error> {
385        let start = self.expect_keyword(Keyword::Fun)?;
386
387        let name = self.identifier()?;
388        let params = self.params()?;
389        let return_typ = self.type_spec()?;
390
391        let end = self.current.1.clone();
392
393        Ok(Signature {
394            name,
395            params,
396            return_typ,
397            span: Span::combine(&start, &end),
398        })
399    }
400
401    fn trait_sum(&mut self, _name: Ident) -> Result<Stmt, Error> {
402        todo!()
403    }
404
405    fn constructor(&mut self, class: &str) -> Result<Stmt, Error> {
406        let start = &self.consume(TokenType::keyword("create"))?;
407        let name = self.identifier()?;
408        let params = self.params()?;
409        let body = self.block()?;
410        let end = &body.span();
411
412        let constructor = Constructor::new(name, params.0, body, class.to_string());
413
414        Ok(Stmt::Constructor(
415            Box::new(constructor),
416            Span::combine(start, end),
417        ))
418    }
419
420    fn fun(&mut self) -> Result<Stmt, Error> {
421        let fun = self.fun_()?;
422        Ok(Stmt::Function(Box::new(fun.0), fun.1))
423    }
424
425    fn fun_(&mut self) -> Result<(ScriptFun, Span), Error> {
426        let start = self.consume(TokenType::keyword("fun"))?;
427
428        let name = self.identifier()?;
429        let (params, types) = self.params()?;
430        let return_typ = self.type_spec()?;
431        let body = self.block()?;
432
433        let end = &body.span();
434
435        let access = FunAccess::Private;
436
437        let fun = ScriptFun::new(name, params, body, types, return_typ, access);
438
439        Ok((fun, Span::combine(&start, end)))
440    }
441
442    fn params(&mut self) -> Result<(Vec<Ident>, Vec<Option<Expr>>), Error> {
443        self.expect_delimiter(Delimiter::OpenParen)?;
444        let mut params = vec![];
445        let mut typs = vec![];
446
447        if TokenType::Delimiter(Delimiter::CloseParen) != self.current.0 {
448            params.push(self.identifier()?);
449            typs.push(self.type_spec()?);
450        }
451
452        loop {
453            match &self.current.0 {
454                TokenType::Symbol(Symbol::Comma) => {
455                    self.consume(TokenType::symbol(","))?;
456                    params.push(self.identifier()?);
457                    typs.push(self.type_spec()?);
458                }
459                TokenType::Delimiter(Delimiter::CloseParen) => {
460                    break;
461                }
462                _ => return Err(self.error()),
463            }
464        }
465
466        self.expect_delimiter(Delimiter::CloseParen)?;
467        Ok((params, typs))
468    }
469
470    fn return_stmt(&mut self) -> Result<Stmt, Error> {
471        let start = &self.consume(TokenType::keyword("return"))?;
472
473        let expr = if let TokenType::Delimiter(_) = self.current.0 {
474            None
475        } else {
476            Some(self.disjunction()?)
477        };
478
479        let end = if let Some(expr) = &expr {
480            expr.span()
481        } else {
482            start.clone()
483        };
484
485        let stmt = Stmt::Return(expr, Span::combine(start, &end));
486
487        Ok(stmt)
488    }
489
490    fn import_stmt(&mut self) -> Result<Stmt, Error> {
491        // import ...
492        let start = &self.consume(TokenType::keyword("import"))?;
493
494        // import name ...
495        let import_name = self.dot_expr()?;
496
497        let end = &import_name.span();
498
499        Ok(Stmt::ImportStatement(
500            import_name,
501            Span::combine(start, end),
502        ))
503    }
504
505    fn var_decl(&mut self) -> Result<Stmt, Error> {
506        let start = &self.current.1.clone();
507
508        self.consume(TokenType::keyword("var"))?;
509        let id = self.identifier()?;
510
511        let end = &id.span();
512
513        let typ = self.type_spec()?;
514
515        let init = if let TokenType::Symbol(Symbol::Equal) = self.current.0 {
516            self.consume(TokenType::symbol("="))?;
517            Some(self.disjunction()?)
518        } else {
519            None
520        };
521
522        Ok(Stmt::VarDeclaration(
523            id,
524            init,
525            typ,
526            Span::combine(start, end),
527        ))
528    }
529
530    fn const_decl(&mut self) -> Result<Stmt, Error> {
531        let start = &self.current.1.clone();
532
533        self.consume(TokenType::keyword("con"))?;
534        let id = self.identifier()?;
535
536        let typ = self.type_spec()?;
537
538        self.consume(TokenType::symbol("="))?;
539        let init = self.disjunction()?;
540
541        let end = &init.span();
542
543        Ok(Stmt::ConDeclaration(
544            id,
545            init,
546            typ,
547            Span::combine(start, end),
548        ))
549    }
550
551    fn type_spec(&mut self) -> Result<Option<Expr>, Error> {
552        if let TokenType::Symbol(Symbol::Colon) = self.current.0 {
553            self.consume(TokenType::symbol(":"))?;
554
555            let start = self.current.1.clone();
556            let typ_path = self.type_path()?;
557
558            Ok(Some(Expr::Type(typ_path, start)))
559        } else {
560            Ok(None)
561        }
562    }
563
564    fn type_path(&mut self) -> Result<TypePath, Error> {
565        let ident = self.identifier()?;
566
567        let arguments = match &self.current.0 {
568            TokenType::Symbol(Symbol::LeftAngleBracket) => {
569                self.consume(TokenType::symbol("<"))?;
570                let argument = Some(Box::new(self.type_path()?));
571                self._expect(TokenType::symbol(">"))?;
572                argument
573            }
574            _ => None,
575        };
576
577        Ok(TypePath { ident, arguments })
578    }
579
580    fn args(&mut self) -> Result<Vec<Expr>, Error> {
581        self.expect_delimiter(Delimiter::OpenParen)?;
582
583        let mut args = vec![];
584
585        if self.current.0 != TokenType::delimiter(")") {
586            args.push(self.disjunction()?);
587        }
588
589        loop {
590            match &self.current.0 {
591                TokenType::Delimiter(Delimiter::CloseParen) => {
592                    break;
593                }
594                TokenType::Symbol(Symbol::Comma) => {
595                    self.consume(TokenType::symbol(","))?;
596                    args.push(self.disjunction()?);
597                }
598                _ => break,
599            }
600        }
601
602        self.expect_delimiter(Delimiter::CloseParen)?;
603
604        Ok(args)
605    }
606
607    fn assignment_stmt(&mut self) -> Result<Stmt, Error> {
608        let node = self.expression()?;
609        let start = &node.span();
610
611        if let TokenType::Symbol(Symbol::Equal) = &self.current.0 {
612            self.consume(TokenType::symbol("="))?;
613
614            let id = match node {
615                Stmt::Expr(expr) => expr,
616                _ => {
617                    return Err(Error::ExpectedToken(
618                        Item::new("identifer", self.current.1.clone()),
619                        Item::new(&self.current.0.to_string(), self.current.1.clone()),
620                    ))
621                }
622            };
623
624            let val = self.disjunction()?;
625            let end = &val.span();
626
627            let node = Stmt::AssignStatement(id, val, Span::combine(start, end));
628            return Ok(node);
629        }
630
631        Ok(node)
632    }
633
634    fn expression(&mut self) -> Result<Stmt, Error> {
635        Ok(Stmt::Expr(self.disjunction()?))
636    }
637
638    fn disjunction(&mut self) -> Result<Expr, Error> {
639        let mut node = self.conjunction()?;
640        let start = &node.span();
641        while let TokenType::Keyword(Keyword::Or) = &self.current.0 {
642            self.consume(TokenType::keyword("or"))?;
643            node = Expr::Or(
644                Box::new(node),
645                Box::new(self.conjunction()?),
646                Span::combine(start, &self.current.1),
647            );
648        }
649
650        Ok(node)
651    }
652
653    fn conjunction(&mut self) -> Result<Expr, Error> {
654        let mut node = self.bitwise_or()?;
655        let start = &node.span();
656        loop {
657            if let TokenType::Keyword(Keyword::And) = &self.current.0 {
658                self.consume(TokenType::keyword("and"))?;
659                node = Expr::And(
660                    Box::new(node),
661                    Box::new(self.bitwise_or()?),
662                    Span::combine(start, &self.current.1),
663                );
664            } else {
665                break;
666            }
667        }
668        Ok(node)
669    }
670
671    fn bitwise_or(&mut self) -> Result<Expr, Error> {
672        let mut node = self.bitwise_xor()?;
673
674        loop {
675            if let TokenType::Symbol(Symbol::Or) = &self.current.0 {
676                self.next();
677                let start = &node.span();
678
679                node = Expr::BinExpr(
680                    Box::new(BinExpr::new(Op::BitwiseOr, node, self.bitwise_xor()?)),
681                    Span::combine(start, &self.current.1),
682                );
683            } else {
684                break;
685            }
686        }
687
688        Ok(node)
689    }
690
691    fn bitwise_xor(&mut self) -> Result<Expr, Error> {
692        let mut node = self.bitwise_and()?;
693
694        loop {
695            if let TokenType::Symbol(Symbol::Xor) = &self.current.0 {
696                self.next();
697                let start = &node.span();
698
699                node = Expr::BinExpr(
700                    Box::new(BinExpr::new(Op::BitwiseXor, node, self.bitwise_and()?)),
701                    Span::combine(start, &self.current.1),
702                );
703            } else {
704                break;
705            }
706        }
707
708        Ok(node)
709    }
710
711    fn bitwise_and(&mut self) -> Result<Expr, Error> {
712        let mut node = self.comparison()?;
713
714        loop {
715            if let TokenType::Symbol(Symbol::And) = &self.current.0 {
716                self.next();
717                let start = &node.span();
718
719                node = Expr::BinExpr(
720                    Box::new(BinExpr::new(Op::BitwiseAnd, node, self.comparison()?)),
721                    Span::combine(start, &self.current.1),
722                );
723            } else {
724                break;
725            }
726        }
727
728        Ok(node)
729    }
730
731    fn comparison(&mut self) -> Result<Expr, Error> {
732        let mut node = self.parse_sum()?;
733        let start = &node.span();
734
735        loop {
736            match &self.current.0 {
737                TokenType::Symbol(Symbol::EqualsEquals) => {
738                    self.consume(TokenType::symbol("=="))?;
739                    node = Expr::BinExpr(
740                        Box::new(BinExpr::new(Op::EqualTo, node, self.parse_sum()?)),
741                        Span::combine(start, &self.current.1),
742                    );
743                }
744                TokenType::Symbol(Symbol::NotEqual) => {
745                    self.consume(TokenType::symbol("!="))?;
746                    node = Expr::BinExpr(
747                        Box::new(BinExpr::new(Op::NotEqual, node, self.parse_sum()?)),
748                        Span::combine(start, &self.current.1),
749                    );
750                }
751                TokenType::Symbol(Symbol::GreaterThanEqual) => {
752                    self.consume(TokenType::symbol(">="))?;
753                    node = Expr::BinExpr(
754                        Box::new(BinExpr::new(Op::GreaterThanEquals, node, self.parse_sum()?)),
755                        Span::combine(start, &self.current.1),
756                    );
757                }
758                TokenType::Symbol(Symbol::LessThanEqual) => {
759                    self.consume(TokenType::symbol("<="))?;
760                    node = Expr::BinExpr(
761                        Box::new(BinExpr::new(Op::LessThanEquals, node, self.parse_sum()?)),
762                        Span::combine(start, &self.current.1),
763                    );
764                }
765                TokenType::Symbol(Symbol::RightAngleBracket) => {
766                    self.consume(TokenType::symbol(">"))?;
767                    node = Expr::BinExpr(
768                        Box::new(BinExpr::new(Op::GreaterThan, node, self.parse_sum()?)),
769                        Span::combine(start, &self.current.1),
770                    );
771                }
772                TokenType::Symbol(Symbol::LeftAngleBracket) => {
773                    self.consume(TokenType::symbol("<"))?;
774                    node = Expr::BinExpr(
775                        Box::new(BinExpr::new(Op::LessThan, node, self.parse_sum()?)),
776                        Span::combine(start, &self.current.1),
777                    );
778                }
779                _ => break,
780            }
781        }
782        Ok(node)
783    }
784
785    /// Parse bitwise `and`, `or` operators.
786    fn _bitwise_and_or(&mut self) -> Result<Expr, Error> {
787        let node = self.parse_sum()?;
788
789        Ok(node)
790    }
791
792    fn parse_sum(&mut self) -> Result<Expr, Error> {
793        let mut node = self.parse_term()?;
794        let start = &node.span();
795        loop {
796            match &self.current.0 {
797                TokenType::Symbol(Symbol::Plus) => {
798                    self.consume(TokenType::symbol("+"))?;
799                    node = Expr::BinExpr(
800                        Box::new(BinExpr::new(Op::Add, node, self.parse_term()?)),
801                        Span::combine(start, &self.current.1),
802                    );
803                }
804                TokenType::Symbol(Symbol::Hypen) => {
805                    self.consume(TokenType::symbol("-"))?;
806                    node = Expr::BinExpr(
807                        Box::new(BinExpr::new(Op::Subtract, node, self.parse_term()?)),
808                        Span::combine(start, &self.current.1),
809                    );
810                }
811                _ => {
812                    break;
813                }
814            }
815        }
816        Ok(node)
817    }
818
819    fn parse_term(&mut self) -> Result<Expr, Error> {
820        let mut node = self.member_expr()?;
821        let start = &node.span();
822        loop {
823            match &self.current.0 {
824                TokenType::Symbol(Symbol::Star) => {
825                    self.consume(TokenType::symbol("*"))?;
826                    node = Expr::BinExpr(
827                        Box::new(BinExpr::new(Op::Multiply, node, self.member_expr()?)),
828                        Span::combine(start, &self.current.1),
829                    );
830                }
831                TokenType::Symbol(Symbol::Slash) => {
832                    self.consume(TokenType::symbol("/"))?;
833                    node = Expr::BinExpr(
834                        Box::new(BinExpr::new(Op::Divide, node, self.member_expr()?)),
835                        Span::combine(start, &self.current.1),
836                    );
837                }
838                TokenType::Symbol(Symbol::Modulo) => {
839                    self.consume(TokenType::symbol("%"))?;
840                    node = Expr::BinExpr(
841                        Box::new(BinExpr::new(Op::Remainder, node, self.member_expr()?)),
842                        Span::combine(start, &self.current.1),
843                    );
844                }
845                _ => {
846                    break;
847                }
848            }
849        }
850        Ok(node)
851    }
852
853    fn member_expr(&mut self) -> Result<Expr, Error> {
854        let mut node = self.dot_expr()?;
855        let start = node.span();
856
857        loop {
858            match self.current.0.clone() {
859                TokenType::Delimiter(Delimiter::OpenBracket) => {
860                    self.expect_delimiter(Delimiter::OpenBracket)?;
861                    node = Expr::Index(
862                        Box::new(node),
863                        Box::new(self.disjunction()?),
864                        Span::combine(&start, &self.current.1.clone()),
865                    );
866                    self.expect_delimiter(Delimiter::CloseBracket)?;
867                }
868                TokenType::Delimiter(Delimiter::OpenParen) => {
869                    node = Expr::FunCall(
870                        Box::new(node),
871                        Box::new(self.args()?),
872                        Span::combine(&start, &self.current.1.clone()),
873                    );
874                }
875                TokenType::Comment(typ) => {
876                    self.consume(TokenType::Comment(typ))?;
877                    continue;
878                }
879                _ => break,
880            }
881        }
882
883        Ok(node)
884    }
885
886    fn dot_expr(&mut self) -> Result<Expr, Error> {
887        let mut node = self.paren_expr()?;
888        let start = node.span();
889
890        loop {
891            match &self.current.0 {
892                TokenType::Symbol(Symbol::Dot) => {
893                    self.consume(TokenType::symbol("."))?;
894
895                    node = Expr::MemberExpr(
896                        Box::new(node),
897                        Box::new(self.paren_expr()?),
898                        Span::combine(&start, &self.current.1.clone()),
899                    );
900                }
901                TokenType::Symbol(Symbol::Colon) => {
902                    self.consume(TokenType::symbol(":"))?;
903
904                    node = Expr::AssocExpr(
905                        Box::new(node),
906                        Box::new(self.paren_expr()?),
907                        Span::combine(&start, &self.current.1),
908                    );
909                }
910                TokenType::Comment(_) => {
911                    self.comment()?;
912                    continue;
913                }
914                _ => break,
915            }
916        }
917
918        Ok(node)
919    }
920
921    fn paren_expr(&mut self) -> Result<Expr, Error> {
922        if let TokenType::Delimiter(Delimiter::OpenParen) = self.current.0 {
923            let start = &self.expect_delimiter(Delimiter::OpenParen)?;
924            let node = self.disjunction()?;
925
926            if let TokenType::Symbol(Symbol::Comma) = self.current.0 {
927                todo!()
928            }
929
930            let end = &self.expect_delimiter(Delimiter::CloseParen)?;
931            return Ok(Expr::ParenExpr(Box::new(node), Span::combine(start, end)));
932        }
933
934        self.factor()
935    }
936
937    fn factor(&mut self) -> Result<Expr, Error> {
938        let node;
939        match &self.current.0 {
940            TokenType::Literal(literal) => match literal {
941                Literal::NumberLiteral(number) => {
942                    node = Expr::Number(number.parse::<f64>().unwrap(), self.current.1.clone());
943                    self.next();
944                }
945                Literal::StringLiteral(string) => {
946                    node = Expr::String(string.to_owned(), self.current.1.clone());
947                    self.next();
948                }
949                Literal::CharLiteral(_) => {
950                    unimplemented!()
951                }
952                Literal::False => {
953                    node = Expr::Boolean(false, self.current.1.clone());
954                    self.next();
955                }
956                Literal::True => {
957                    node = Expr::Boolean(true, self.current.1.clone());
958                    self.next();
959                }
960                Literal::Nil => {
961                    node = Expr::Nil(self.current.1.clone());
962                    self.next();
963                }
964                Literal::Id(_) => {
965                    node = Expr::Identifier(self.identifier()?);
966                }
967            },
968            TokenType::Symbol(sym) => match sym {
969                Symbol::Plus => {
970                    self.consume(TokenType::symbol("+"))?;
971                    node = Expr::UnaryExpr(
972                        Op::Add,
973                        Box::new(self.paren_expr()?),
974                        self.current.1.clone(),
975                    );
976                }
977                Symbol::Hypen => {
978                    self.consume(TokenType::symbol("-"))?;
979                    node = Expr::UnaryExpr(
980                        Op::Subtract,
981                        Box::new(self.paren_expr()?),
982                        self.current.1.clone(),
983                    );
984                }
985                Symbol::Bang => {
986                    self.consume(TokenType::symbol("!"))?;
987                    node = Expr::UnaryExpr(
988                        Op::Bang,
989                        Box::new(self.paren_expr()?),
990                        self.current.1.clone(),
991                    );
992                }
993                sym => {
994                    return Err(Error::UnexpectedToken(Item::new(
995                        &sym.to_string(),
996                        self.current.1.clone(),
997                    )))
998                }
999            },
1000            TokenType::Delimiter(delimiter) => match delimiter {
1001                Delimiter::OpenParen => node = self.tuple()?,
1002                Delimiter::OpenBracket => node = self.list()?,
1003                Delimiter::OpenBrace => node = self.map()?,
1004                Delimiter::Newline => {
1005                    self.next();
1006                    node = self.factor()?;
1007                }
1008                sym => {
1009                    return Err(Error::UnexpectedToken(Item::new(
1010                        &sym.to_string(),
1011                        self.current.1.clone(),
1012                    )))
1013                }
1014            },
1015            TokenType::Keyword(Keyword::Self_) => {
1016                node = Expr::SelfExpr(self.current.1.clone());
1017                self.next();
1018            }
1019            TokenType::Comment(Comment::BlockComment) => {
1020                self.next();
1021
1022                node = self.factor()?;
1023            }
1024            _ => {
1025                return Err(Error::UnexpectedToken(Item::new(
1026                    &self.current.0.to_string(),
1027                    self.current.1.clone(),
1028                )))
1029            }
1030        }
1031        Ok(node)
1032    }
1033
1034    fn list(&mut self) -> Result<Expr, Error> {
1035        self.expect_delimiter(Delimiter::OpenBracket)?;
1036
1037        let mut nodes = vec![];
1038
1039        loop {
1040            match &self.current.0 {
1041                TokenType::Symbol(Symbol::Comma) => {
1042                    self.next();
1043                }
1044                TokenType::Delimiter(Delimiter::CloseBracket) => {
1045                    break;
1046                }
1047                _ => nodes.push(self.disjunction()?),
1048            }
1049        }
1050
1051        self.expect_delimiter(Delimiter::CloseBracket)?;
1052
1053        Ok(Expr::List(Box::new(nodes), self.current.1.clone()))
1054    }
1055
1056    fn tuple(&mut self) -> Result<Expr, Error> {
1057        let start = self.expect_delimiter(Delimiter::OpenParen)?;
1058
1059        let mut tuple = Vec::new();
1060        let node = self.disjunction()?;
1061
1062        if let TokenType::Delimiter(Delimiter::CloseParen) = self.current.0 {
1063            self.expect_delimiter(Delimiter::CloseParen)?;
1064            return Ok(node);
1065        }
1066
1067        tuple.push(node);
1068
1069        while let TokenType::Symbol(Symbol::Comma) = &self.current.0 {
1070            self.consume(TokenType::symbol(","))?;
1071            tuple.push(self.disjunction()?);
1072        }
1073
1074        let end = &self.expect_delimiter(Delimiter::CloseParen)?;
1075
1076        Ok(Expr::Tuple(Box::new(tuple), Span::combine(&start, end)))
1077    }
1078
1079    fn map(&mut self) -> Result<Expr, Error> {
1080        let start = &self.expect_delimiter(Delimiter::OpenBrace)?;
1081
1082        if let TokenType::Delimiter(Delimiter::CloseBrace) = self.current.0 {
1083            let end = &self.expect_delimiter(Delimiter::CloseBrace)?;
1084
1085            return Ok(Expr::Map(Box::new(vec![]), Span::combine(start, end)));
1086        }
1087
1088        let mut map = vec![];
1089        loop {
1090            let key = self.factor()?;
1091            self.consume(TokenType::symbol(":"))?;
1092            let value = self.disjunction()?;
1093
1094            map.push((key, value));
1095
1096            match &self.current.0 {
1097                TokenType::Delimiter(Delimiter::CloseBrace) => break,
1098                _ => {
1099                    self.consume(TokenType::symbol(","))?;
1100                    continue;
1101                }
1102            }
1103        }
1104
1105        let end = &self.expect_delimiter(Delimiter::CloseBrace)?;
1106
1107        Ok(Expr::Map(Box::new(map), Span::combine(start, end)))
1108    }
1109
1110    /// Consumes an identifier from the token stream and returns an [`Ident`].
1111    fn identifier(&mut self) -> Result<Ident, Error> {
1112        let name = self.current.0.to_string();
1113        let span = self.current.1.clone();
1114        self.consume(TokenType::Literal(Literal::Id(name.clone())))?;
1115        Ok(Ident { name, span })
1116    }
1117
1118    fn comment(&mut self) -> Result<(), Error> {
1119        self.next();
1120
1121        Ok(())
1122    }
1123
1124    pub fn parse_file(&mut self) -> Result<AST, Error> {
1125        let mut nodes = vec![];
1126
1127        loop {
1128            match &self.current.0 {
1129                TokenType::Delimiter(Delimiter::Eof) => break,
1130                TokenType::Delimiter(Delimiter::Newline) => {
1131                    self.expect_delimiter(Delimiter::Newline)?;
1132                    continue;
1133                }
1134                TokenType::Comment(_) => {
1135                    self.comment()?;
1136                    continue;
1137                }
1138                _ => nodes.push(ASTNode::from(self.compound_statement()?)),
1139            }
1140        }
1141
1142        Ok(AST::new(nodes, self.tokens.source.clone()))
1143    }
1144
1145    pub fn parse(&mut self) -> Result<AST, Error> {
1146        self.current = self.tokens.node[self.pos].clone();
1147
1148        let ast = self.parse_file()?;
1149
1150        Ok(ast)
1151    }
1152}
kaon/compiler/parser.rs

kaon/compiler/
parser.rs
