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