parser/
lib.rs

1pub mod ast;
2mod ast_tree_test;
3mod parser_test;
4mod precedences;
5pub mod validation;
6
7pub extern crate lexer;
8
9use crate::ast::*;
10use crate::precedences::{get_token_precedence, Precedence};
11use lexer::token::{Span, Token, TokenKind};
12use lexer::Lexer;
13
14type ParseError = String;
15type ParseErrors = Vec<ParseError>;
16
17pub struct Parser<'a> {
18    lexer: Lexer<'a>,
19    current_token: Token,
20    peek_token: Token,
21    errors: ParseErrors,
22    block_depth: usize,
23}
24
25impl<'a> Parser<'a> {
26    pub fn new(mut lexer: Lexer<'a>) -> Parser<'a> {
27        let cur = lexer.next_token();
28        let next = lexer.next_token();
29        let errors = Vec::new();
30        // in strict sense, rust can be as classic go pattern, but it requires more work
31        // so let's just use pattern matching
32        // ```rust
33        // type PrefixParseFn = fn() -> Result<Expression, ParseError>;
34        // type InfixParseFn = fn(Expression) -> Result<Expression, ParseError>;
35        // let prefix_parse_fns = HashMap::new();
36        // let infix_parse_fns = HashMap::new();
37        // ```
38
39        let p = Parser {
40            lexer,
41            current_token: cur,
42            peek_token: next,
43            errors,
44            block_depth: 0,
45        };
46
47        return p;
48    }
49
50    fn next_token(&mut self) {
51        self.current_token = self.peek_token.clone();
52        self.peek_token = self.lexer.next_token();
53    }
54
55    fn current_token_is(&mut self, token: &TokenKind) -> bool {
56        self.current_token.kind == *token
57    }
58
59    fn peek_token_is(&mut self, token: &TokenKind) -> bool {
60        self.peek_token.kind == *token
61    }
62
63    fn expect_peek(&mut self, token: &TokenKind) -> Result<(), ParseError> {
64        self.next_token();
65        if self.current_token.kind == *token {
66            Ok(())
67        } else {
68            let e = format!("expected token: {} got: {}", token, self.current_token);
69            Err(e)
70        }
71    }
72
73    pub fn parse_program(&mut self) -> Result<Program, ParseErrors> {
74        let mut program = Program::new();
75        while !self.current_token_is(&TokenKind::EOF) {
76            match self.parse_statement() {
77                Ok(stmt) => program.body.push(stmt),
78                Err(e) => self.errors.push(e),
79            }
80            self.next_token();
81        }
82        program.span.end = self.current_token.span.end;
83
84        if self.errors.is_empty() {
85            return Ok(program);
86        } else {
87            return Err(self.errors.clone());
88        }
89    }
90
91    fn parse_statement(&mut self) -> Result<Statement, ParseError> {
92        match self.current_token.kind {
93            TokenKind::LET => self.parse_let_statement(),
94            TokenKind::RETURN => self.parse_return_statement(),
95            TokenKind::CLASS if self.block_depth == 0 => self.parse_class_declaration(),
96            TokenKind::CLASS => Err("class declarations are only allowed at top level".to_string()),
97            _ => self.parse_expression_statement(),
98        }
99    }
100
101    fn parse_let_statement(&mut self) -> Result<Statement, ParseError> {
102        let start = self.current_token.span.start;
103        self.next_token();
104
105        let name = self.current_token.clone();
106        let identifier_name = match &self.current_token.kind {
107            TokenKind::IDENTIFIER {
108                name,
109            } => name.to_string(),
110            _ => return Err(format!("{} not an identifier", self.current_token)),
111        };
112
113        self.expect_peek(&TokenKind::ASSIGN)?;
114        self.next_token();
115
116        let mut value = self.parse_expression(Precedence::LOWEST)?.0;
117        if self.peek_token_is(&TokenKind::ASSIGN) {
118            return Err("property assignment is only allowed as a statement".to_string());
119        }
120        match value {
121            Expression::FUNCTION(ref mut f) => {
122                f.name = identifier_name;
123            }
124            _ => {}
125        }
126
127        if self.peek_token_is(&TokenKind::SEMICOLON) {
128            self.next_token();
129        }
130
131        let end = self.current_token.span.end;
132
133        return Ok(Statement::Let(Let {
134            identifier: name,
135            expr: value,
136            span: Span {
137                start,
138                end,
139            },
140        }));
141    }
142
143    fn parse_return_statement(&mut self) -> Result<Statement, ParseError> {
144        let start = self.current_token.span.start;
145        self.next_token();
146
147        let value = self.parse_expression(Precedence::LOWEST)?.0;
148
149        if self.peek_token_is(&TokenKind::ASSIGN) {
150            return Err("property assignment is only allowed as a statement".to_string());
151        }
152
153        if self.peek_token_is(&TokenKind::SEMICOLON) {
154            self.next_token();
155        }
156        let end = self.current_token.span.end;
157
158        return Ok(Statement::Return(ReturnStatement {
159            argument: value,
160            span: Span {
161                start,
162                end,
163            },
164        }));
165    }
166
167    fn parse_expression_statement(&mut self) -> Result<Statement, ParseError> {
168        let (expr, cover_span) = self.parse_expression(Precedence::LOWEST)?;
169
170        if self.peek_token_is(&TokenKind::ASSIGN) {
171            let property_expression = match expr {
172                Expression::Property(property) => property,
173                _ => return Err("only instance property assignment is supported".to_string()),
174            };
175
176            self.next_token();
177            self.next_token();
178            let (value, value_span) = self.parse_expression(Precedence::LOWEST)?;
179            if self.peek_token_is(&TokenKind::ASSIGN) {
180                return Err("chained property assignment is not supported".to_string());
181            }
182
183            let mut end = value_span.end;
184            if self.peek_token_is(&TokenKind::SEMICOLON) {
185                self.next_token();
186                end = self.current_token.span.end;
187            }
188
189            return Ok(Statement::SetProperty(SetPropertyStatement {
190                object: property_expression.object,
191                property: property_expression.property,
192                value,
193                span: Span {
194                    start: cover_span.start,
195                    end,
196                },
197            }));
198        }
199
200        if self.peek_token_is(&TokenKind::SEMICOLON) {
201            self.next_token();
202        }
203
204        Ok(Statement::Expr(expr))
205    }
206
207    fn parse_expression(
208        &mut self,
209        precedence: Precedence,
210    ) -> Result<(Expression, Span), ParseError> {
211        let (mut left, mut cover_span) = self.parse_prefix_expression()?;
212        while self.peek_token.kind != TokenKind::SEMICOLON
213            && precedence < get_token_precedence(&self.peek_token.kind)
214        {
215            match self.parse_infix_expression(&left, &cover_span) {
216                Some(infix) => {
217                    (left, cover_span) = infix?;
218                }
219                None => {
220                    return Ok((left, cover_span));
221                }
222            }
223        }
224
225        Ok((left, cover_span))
226    }
227
228    fn parse_prefix_expression(&mut self) -> Result<(Expression, Span), ParseError> {
229        // this is prefix fn map :)
230        match &self.current_token.kind {
231            TokenKind::IDENTIFIER {
232                name,
233            } => {
234                let span = self.current_token.span.clone();
235                return Ok((
236                    Expression::IDENTIFIER(IDENTIFIER {
237                        name: name.clone(),
238                        span: span.clone(),
239                    }),
240                    span,
241                ));
242            }
243            TokenKind::INT(i) => {
244                let span = self.current_token.span.clone();
245                return Ok((
246                    Expression::LITERAL(Literal::Integer(Integer {
247                        raw: *i,
248                        span: span.clone(),
249                    })),
250                    span,
251                ));
252            }
253            TokenKind::STRING(s) => {
254                let span = self.current_token.span.clone();
255                return Ok((
256                    Expression::LITERAL(Literal::String(StringType {
257                        raw: s.to_string(),
258                        span: span.clone(),
259                    })),
260                    span,
261                ));
262            }
263            b @ TokenKind::TRUE | b @ TokenKind::FALSE => {
264                let span = self.current_token.span.clone();
265                return Ok((
266                    Expression::LITERAL(Literal::Boolean(Boolean {
267                        raw: *b == TokenKind::TRUE,
268                        span: span.clone(),
269                    })),
270                    span,
271                ));
272            }
273            TokenKind::BANG | TokenKind::MINUS => {
274                let start = self.current_token.span.start;
275                let prefix_op = self.current_token.clone();
276                self.next_token();
277                let (expr, span) = self.parse_expression(Precedence::PREFIX)?;
278                let expression_span = Span {
279                    start,
280                    end: span.end,
281                };
282                return Ok((
283                    Expression::PREFIX(UnaryExpression {
284                        op: prefix_op,
285                        operand: Box::new(expr),
286                        span: expression_span.clone(),
287                    }),
288                    expression_span,
289                ));
290            }
291            TokenKind::LPAREN => {
292                let start = self.current_token.span.start;
293                self.next_token();
294                let expr = self.parse_expression(Precedence::LOWEST)?.0;
295                self.expect_peek(&TokenKind::RPAREN)?;
296                let span = Span {
297                    start,
298                    end: self.current_token.span.end,
299                };
300                return Ok((expr, span));
301            }
302            TokenKind::IF => {
303                let expression = self.parse_if_expression()?;
304                let span = expression.span().clone();
305                Ok((expression, span))
306            }
307            TokenKind::FUNCTION => {
308                let expression = self.parse_fn_expression()?;
309                let span = expression.span().clone();
310                Ok((expression, span))
311            }
312            TokenKind::LBRACKET => {
313                let (elements, span) = self.parse_expression_list(&TokenKind::RBRACKET)?;
314                return Ok((
315                    Expression::LITERAL(Literal::Array(Array {
316                        elements,
317                        span: span.clone(),
318                    })),
319                    span,
320                ));
321            }
322            TokenKind::LBRACE => {
323                let expression = self.parse_hash_expression()?;
324                let span = expression.span().clone();
325                Ok((expression, span))
326            }
327            TokenKind::THIS => {
328                let span = self.current_token.span.clone();
329                Ok((
330                    Expression::This(ThisExpression {
331                        span: span.clone(),
332                    }),
333                    span,
334                ))
335            }
336            TokenKind::NEW => {
337                let expression = self.parse_new_expression()?;
338                let span = expression.span().clone();
339                Ok((expression, span))
340            }
341            _ => Err(format!("no prefix function for token: {}", self.current_token)),
342        }
343    }
344
345    fn parse_infix_expression(
346        &mut self,
347        left: &Expression,
348        left_span: &Span,
349    ) -> Option<Result<(Expression, Span), ParseError>> {
350        match self.peek_token.kind {
351            TokenKind::PLUS
352            | TokenKind::MINUS
353            | TokenKind::ASTERISK
354            | TokenKind::SLASH
355            | TokenKind::EQ
356            | TokenKind::NotEq
357            | TokenKind::LT
358            | TokenKind::GT => {
359                self.next_token();
360                let infix_op = self.current_token.clone();
361                let precedence_value = get_token_precedence(&self.current_token.kind);
362                self.next_token();
363                let result = self
364                    .parse_expression(precedence_value)
365                    .map(|(right, span)| {
366                        let expression_span = Span {
367                            start: left_span.start,
368                            end: span.end,
369                        };
370                        (
371                            Expression::INFIX(BinaryExpression {
372                                op: infix_op,
373                                left: Box::new(left.clone()),
374                                right: Box::new(right),
375                                span: expression_span.clone(),
376                            }),
377                            expression_span,
378                        )
379                    });
380                return Some(result);
381            }
382            TokenKind::LPAREN => {
383                self.next_token();
384                return Some(self.parse_fn_call_expression(left.clone(), left_span.start));
385            }
386            TokenKind::LBRACKET => {
387                self.next_token();
388                return Some(self.parse_index_expression(left.clone(), left_span.start));
389            }
390            TokenKind::DOT => {
391                self.next_token();
392                return Some(self.parse_property_expression(left.clone(), left_span.start));
393            }
394            _ => None,
395        }
396    }
397
398    fn parse_if_expression(&mut self) -> Result<Expression, ParseError> {
399        let start = self.current_token.span.start;
400        self.expect_peek(&TokenKind::LPAREN)?;
401        self.next_token();
402
403        let condition = self.parse_expression(Precedence::LOWEST)?.0;
404        self.expect_peek(&TokenKind::RPAREN)?;
405        self.expect_peek(&TokenKind::LBRACE)?;
406
407        let consequent = self.parse_block_statement()?;
408
409        let alternate = if self.peek_token_is(&TokenKind::ELSE) {
410            self.next_token();
411            self.expect_peek(&TokenKind::LBRACE)?;
412            Some(self.parse_block_statement()?)
413        } else {
414            None
415        };
416
417        let end = self.current_token.span.end;
418
419        return Ok(Expression::IF(IF {
420            condition: Box::new(condition),
421            consequent,
422            alternate,
423            span: Span {
424                start,
425                end,
426            },
427        }));
428    }
429
430    fn parse_block_statement(&mut self) -> Result<BlockStatement, ParseError> {
431        let start = self.current_token.span.start;
432        self.block_depth += 1;
433        self.next_token();
434        let mut block_statement = Vec::new();
435
436        while !self.current_token_is(&TokenKind::RBRACE) && !self.current_token_is(&TokenKind::EOF)
437        {
438            let statement = match self.parse_statement() {
439                Ok(statement) => statement,
440                Err(error) => {
441                    self.block_depth -= 1;
442                    return Err(error);
443                }
444            };
445            block_statement.push(statement);
446
447            self.next_token();
448        }
449
450        self.block_depth -= 1;
451        if self.current_token_is(&TokenKind::EOF) {
452            return Err("expected '}' before end of input".to_string());
453        }
454
455        let end = self.current_token.span.end;
456
457        Ok(BlockStatement {
458            body: block_statement,
459            span: Span {
460                start,
461                end,
462            },
463        })
464    }
465
466    fn parse_fn_expression(&mut self) -> Result<Expression, ParseError> {
467        let start = self.current_token.span.start;
468        self.expect_peek(&TokenKind::LPAREN)?;
469
470        let params = self.parse_fn_parameters()?;
471
472        self.expect_peek(&TokenKind::LBRACE)?;
473
474        let function_body = self.parse_block_statement()?;
475
476        let end = self.current_token.span.end;
477
478        Ok(Expression::FUNCTION(FunctionDeclaration {
479            params,
480            body: function_body,
481            span: Span {
482                start,
483                end,
484            },
485            name: "".to_string(),
486        }))
487    }
488
489    fn parse_fn_parameters(&mut self) -> Result<Vec<IDENTIFIER>, ParseError> {
490        let mut params = Vec::new();
491        if self.peek_token_is(&TokenKind::RPAREN) {
492            self.next_token();
493            return Ok(params);
494        }
495
496        self.next_token();
497
498        match &self.current_token.kind {
499            TokenKind::IDENTIFIER {
500                name,
501            } => params.push(IDENTIFIER {
502                name: name.clone(),
503                span: self.current_token.span.clone(),
504            }),
505            token => {
506                return Err(format!("expected function params  to be an identifier, got {}", token))
507            }
508        }
509
510        while self.peek_token_is(&TokenKind::COMMA) {
511            self.next_token();
512            self.next_token();
513            match &self.current_token.kind {
514                TokenKind::IDENTIFIER {
515                    name,
516                } => params.push(IDENTIFIER {
517                    name: name.clone(),
518                    span: self.current_token.span.clone(),
519                }),
520                token => {
521                    return Err(format!(
522                        "expected function params  to be an identifier, got {}",
523                        token
524                    ))
525                }
526            }
527        }
528
529        self.expect_peek(&TokenKind::RPAREN)?;
530
531        return Ok(params);
532    }
533
534    fn parse_fn_call_expression(
535        &mut self,
536        expr: Expression,
537        start: usize,
538    ) -> Result<(Expression, Span), ParseError> {
539        let (arguments, ..) = self.parse_expression_list(&TokenKind::RPAREN)?;
540        let end = self.current_token.span.end;
541        let callee = Box::new(expr);
542        let span = Span {
543            start,
544            end,
545        };
546
547        Ok((
548            Expression::FunctionCall(FunctionCall {
549                callee,
550                arguments,
551                span: span.clone(),
552            }),
553            span,
554        ))
555    }
556
557    fn parse_expression_list(
558        &mut self,
559        end: &TokenKind,
560    ) -> Result<(Vec<Expression>, Span), ParseError> {
561        let start = self.current_token.span.start;
562        let mut expr_list = Vec::new();
563        if self.peek_token_is(end) {
564            self.next_token();
565            let end = self.current_token.span.end;
566            return Ok((
567                expr_list,
568                Span {
569                    start,
570                    end,
571                },
572            ));
573        }
574
575        self.next_token();
576
577        expr_list.push(self.parse_expression(Precedence::LOWEST)?.0);
578
579        while self.peek_token_is(&TokenKind::COMMA) {
580            self.next_token();
581            self.next_token();
582            expr_list.push(self.parse_expression(Precedence::LOWEST)?.0);
583        }
584
585        self.expect_peek(end)?;
586        let end = self.current_token.span.end;
587
588        return Ok((
589            expr_list,
590            Span {
591                start,
592                end,
593            },
594        ));
595    }
596
597    fn parse_index_expression(
598        &mut self,
599        left: Expression,
600        start: usize,
601    ) -> Result<(Expression, Span), ParseError> {
602        self.next_token();
603        let index = self.parse_expression(Precedence::LOWEST)?.0;
604
605        self.expect_peek(&TokenKind::RBRACKET)?;
606
607        let end = self.current_token.span.end;
608
609        let span = Span {
610            start,
611            end,
612        };
613        return Ok((
614            Expression::Index(Index {
615                object: Box::new(left),
616                index: Box::new(index),
617                span: span.clone(),
618            }),
619            span,
620        ));
621    }
622
623    fn parse_property_expression(
624        &mut self,
625        object: Expression,
626        start: usize,
627    ) -> Result<(Expression, Span), ParseError> {
628        self.next_token();
629        let property = match &self.current_token.kind {
630            TokenKind::IDENTIFIER {
631                name,
632            } => IDENTIFIER {
633                name: name.clone(),
634                span: self.current_token.span.clone(),
635            },
636            _ => return Err("expected property name after '.'".to_string()),
637        };
638        let span = Span {
639            start,
640            end: property.span.end,
641        };
642        Ok((
643            Expression::Property(PropertyExpression {
644                object: Box::new(object),
645                property,
646                span: span.clone(),
647            }),
648            span,
649        ))
650    }
651
652    fn parse_new_expression(&mut self) -> Result<Expression, ParseError> {
653        let start = self.current_token.span.start;
654        self.next_token();
655        let callee = match &self.current_token.kind {
656            TokenKind::IDENTIFIER {
657                name,
658            } => IDENTIFIER {
659                name: name.clone(),
660                span: self.current_token.span.clone(),
661            },
662            _ => return Err("expected class name after 'new'".to_string()),
663        };
664
665        if !self.peek_token_is(&TokenKind::LPAREN) {
666            return Err("new expression requires an argument list".to_string());
667        }
668        self.next_token();
669        let (arguments, arguments_span) = self.parse_expression_list(&TokenKind::RPAREN)?;
670        Ok(Expression::New(NewExpression {
671            callee,
672            arguments,
673            span: Span {
674                start,
675                end: arguments_span.end,
676            },
677        }))
678    }
679
680    fn parse_class_declaration(&mut self) -> Result<Statement, ParseError> {
681        let start = self.current_token.span.start;
682        self.next_token();
683        let class_name = match &self.current_token.kind {
684            TokenKind::IDENTIFIER {
685                name,
686            } => IDENTIFIER {
687                name: name.clone(),
688                span: self.current_token.span.clone(),
689            },
690            _ => return Err("expected class name after 'class'".to_string()),
691        };
692
693        self.expect_peek(&TokenKind::LBRACE)?;
694        let mut methods = Vec::new();
695        let mut method_names = std::collections::HashSet::new();
696        let mut has_constructor = false;
697
698        while !self.peek_token_is(&TokenKind::RBRACE) {
699            self.next_token();
700            if self.current_token_is(&TokenKind::EOF) {
701                return Err(format!("expected '}}' after class {}", class_name.name));
702            }
703
704            let method_name = match &self.current_token.kind {
705                TokenKind::IDENTIFIER {
706                    name,
707                } => IDENTIFIER {
708                    name: name.clone(),
709                    span: self.current_token.span.clone(),
710                },
711                _ => return Err("expected method definition in class body".to_string()),
712            };
713            let method_start = method_name.span.start;
714            let kind = if method_name.name == "constructor" {
715                if has_constructor {
716                    return Err(format!("class {} has more than one constructor", class_name.name));
717                }
718                has_constructor = true;
719                MethodKind::Constructor
720            } else {
721                if !method_names.insert(method_name.name.clone()) {
722                    return Err(format!(
723                        "duplicate method {}.{}",
724                        class_name.name, method_name.name
725                    ));
726                }
727                MethodKind::Method
728            };
729
730            self.expect_peek(&TokenKind::LPAREN)?;
731            let params = self.parse_fn_parameters()?;
732            self.expect_peek(&TokenKind::LBRACE)?;
733            let body = self.parse_block_statement()?;
734            let method_end = body.span.end;
735            methods.push(MethodDefinition {
736                kind,
737                name: method_name,
738                params,
739                body,
740                span: Span {
741                    start: method_start,
742                    end: method_end,
743                },
744            });
745        }
746
747        self.next_token();
748        Ok(Statement::Class(ClassDeclaration {
749            name: class_name,
750            methods,
751            span: Span {
752                start,
753                end: self.current_token.span.end,
754            },
755        }))
756    }
757
758    fn parse_hash_expression(&mut self) -> Result<Expression, ParseError> {
759        let mut map = Vec::new();
760        let start = self.current_token.span.start;
761        while !self.peek_token_is(&TokenKind::RBRACE) {
762            self.next_token();
763
764            let key = self.parse_expression(Precedence::LOWEST)?.0;
765
766            self.expect_peek(&TokenKind::COLON)?;
767
768            self.next_token();
769            let value = self.parse_expression(Precedence::LOWEST)?.0;
770
771            map.push((key, value));
772
773            if !self.peek_token_is(&TokenKind::RBRACE) {
774                self.expect_peek(&TokenKind::COMMA)?;
775            }
776        }
777
778        self.expect_peek(&TokenKind::RBRACE)?;
779        let end = self.current_token.span.end;
780
781        Ok(Expression::LITERAL(Literal::Hash(Hash {
782            elements: map,
783            span: Span {
784                start,
785                end,
786            },
787        })))
788    }
789}
790
791pub fn parse(input: &str) -> Result<Node, ParseErrors> {
792    let lexer = Lexer::new(input);
793    let mut parser = Parser::new(lexer);
794    let program = parser.parse_program()?;
795
796    Ok(Node::Program(program))
797}
798
799pub fn parse_ast_json_string(input: &str) -> Result<String, ParseErrors> {
800    let ast = match parse(input) {
801        Ok(node) => serde_json::to_string_pretty(&node).unwrap(),
802        Err(e) => return Err(e),
803    };
804
805    return Ok(ast);
806}
parser/lib.rs

parser/
lib.rs
