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

parser/
lib.rs
