jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2020, Stephan Unverwerth <s.unverwerth@gmx.de>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice, this
9 * list of conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
21 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
22 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
23 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include "Parser.h"
28#include <AK/HashMap.h>
29#include <AK/StdLibExtras.h>
30#include <stdio.h>
31
32namespace JS {
33
34static HashMap<TokenType, int> g_operator_precedence;
35Parser::ParserState::ParserState(Lexer lexer)
36 : m_lexer(move(lexer))
37 , m_current_token(m_lexer.next())
38{
39}
40
41Parser::Parser(Lexer lexer)
42 : m_parser_state(move(lexer))
43{
44 if (g_operator_precedence.is_empty()) {
45 // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Operator_Precedence
46 g_operator_precedence.set(TokenType::Period, 20);
47 g_operator_precedence.set(TokenType::BracketOpen, 20);
48 g_operator_precedence.set(TokenType::ParenOpen, 20);
49 g_operator_precedence.set(TokenType::QuestionMarkPeriod, 20);
50
51 g_operator_precedence.set(TokenType::New, 19);
52
53 g_operator_precedence.set(TokenType::PlusPlus, 18);
54 g_operator_precedence.set(TokenType::MinusMinus, 18);
55
56 g_operator_precedence.set(TokenType::ExclamationMark, 17);
57 g_operator_precedence.set(TokenType::Tilde, 17);
58 g_operator_precedence.set(TokenType::Typeof, 17);
59 g_operator_precedence.set(TokenType::Void, 17);
60 g_operator_precedence.set(TokenType::Delete, 17);
61 g_operator_precedence.set(TokenType::Await, 17);
62
63 g_operator_precedence.set(TokenType::DoubleAsterisk, 16);
64
65 g_operator_precedence.set(TokenType::Asterisk, 15);
66 g_operator_precedence.set(TokenType::Slash, 15);
67 g_operator_precedence.set(TokenType::Percent, 15);
68
69 g_operator_precedence.set(TokenType::Plus, 14);
70 g_operator_precedence.set(TokenType::Minus, 14);
71
72 g_operator_precedence.set(TokenType::ShiftLeft, 13);
73 g_operator_precedence.set(TokenType::ShiftRight, 13);
74 g_operator_precedence.set(TokenType::UnsignedShiftRight, 13);
75
76 g_operator_precedence.set(TokenType::LessThan, 12);
77 g_operator_precedence.set(TokenType::LessThanEquals, 12);
78 g_operator_precedence.set(TokenType::GreaterThan, 12);
79 g_operator_precedence.set(TokenType::GreaterThanEquals, 12);
80 g_operator_precedence.set(TokenType::In, 12);
81 g_operator_precedence.set(TokenType::Instanceof, 12);
82
83 g_operator_precedence.set(TokenType::EqualsEquals, 11);
84 g_operator_precedence.set(TokenType::ExclamationMarkEquals, 11);
85 g_operator_precedence.set(TokenType::EqualsEqualsEquals, 11);
86 g_operator_precedence.set(TokenType::ExclamationMarkEqualsEquals, 11);
87
88 g_operator_precedence.set(TokenType::Ampersand, 10);
89
90 g_operator_precedence.set(TokenType::Caret, 9);
91
92 g_operator_precedence.set(TokenType::Pipe, 8);
93
94 g_operator_precedence.set(TokenType::DoubleQuestionMark, 7);
95
96 g_operator_precedence.set(TokenType::DoubleAmpersand, 6);
97
98 g_operator_precedence.set(TokenType::DoublePipe, 5);
99
100 g_operator_precedence.set(TokenType::QuestionMark, 4);
101
102 g_operator_precedence.set(TokenType::Equals, 3);
103 g_operator_precedence.set(TokenType::PlusEquals, 3);
104 g_operator_precedence.set(TokenType::MinusEquals, 3);
105 g_operator_precedence.set(TokenType::AsteriskAsteriskEquals, 3);
106 g_operator_precedence.set(TokenType::AsteriskEquals, 3);
107 g_operator_precedence.set(TokenType::SlashEquals, 3);
108 g_operator_precedence.set(TokenType::PercentEquals, 3);
109 g_operator_precedence.set(TokenType::ShiftLeftEquals, 3);
110 g_operator_precedence.set(TokenType::ShiftRightEquals, 3);
111 g_operator_precedence.set(TokenType::UnsignedShiftRightEquals, 3);
112 g_operator_precedence.set(TokenType::PipeEquals, 3);
113
114 g_operator_precedence.set(TokenType::Yield, 2);
115
116 g_operator_precedence.set(TokenType::Comma, 1);
117 }
118}
119
120int Parser::operator_precedence(TokenType type) const
121{
122 auto it = g_operator_precedence.find(type);
123 if (it == g_operator_precedence.end()) {
124 fprintf(stderr, "No precedence for operator %s\n", Token::name(type));
125 ASSERT_NOT_REACHED();
126 return -1;
127 }
128
129 return it->value;
130}
131
132Associativity Parser::operator_associativity(TokenType type) const
133{
134 switch (type) {
135 case TokenType::Period:
136 case TokenType::BracketOpen:
137 case TokenType::ParenOpen:
138 case TokenType::QuestionMarkPeriod:
139 case TokenType::Asterisk:
140 case TokenType::Slash:
141 case TokenType::Percent:
142 case TokenType::Plus:
143 case TokenType::Minus:
144 case TokenType::ShiftLeft:
145 case TokenType::ShiftRight:
146 case TokenType::UnsignedShiftRight:
147 case TokenType::LessThan:
148 case TokenType::LessThanEquals:
149 case TokenType::GreaterThan:
150 case TokenType::GreaterThanEquals:
151 case TokenType::In:
152 case TokenType::Instanceof:
153 case TokenType::EqualsEquals:
154 case TokenType::ExclamationMarkEquals:
155 case TokenType::EqualsEqualsEquals:
156 case TokenType::ExclamationMarkEqualsEquals:
157 case TokenType::Typeof:
158 case TokenType::Ampersand:
159 case TokenType::Caret:
160 case TokenType::Pipe:
161 case TokenType::DoubleQuestionMark:
162 case TokenType::DoubleAmpersand:
163 case TokenType::DoublePipe:
164 case TokenType::Comma:
165 return Associativity::Left;
166 default:
167 return Associativity::Right;
168 }
169}
170
171NonnullRefPtr<Program> Parser::parse_program()
172{
173 auto program = adopt(*new Program);
174 while (!done()) {
175 if (match(TokenType::Semicolon)) {
176 consume();
177 } else if (match_statement()) {
178 program->append(parse_statement());
179 } else {
180 expected("statement");
181 consume();
182 }
183 }
184 return program;
185}
186
187NonnullRefPtr<Statement> Parser::parse_statement()
188{
189 auto statement = [this]() -> NonnullRefPtr<Statement> {
190 switch (m_parser_state.m_current_token.type()) {
191 case TokenType::Function:
192 return parse_function_node<FunctionDeclaration>();
193 case TokenType::CurlyOpen:
194 return parse_block_statement();
195 case TokenType::Return:
196 return parse_return_statement();
197 case TokenType::Var:
198 case TokenType::Let:
199 case TokenType::Const:
200 return parse_variable_declaration();
201 case TokenType::For:
202 return parse_for_statement();
203 case TokenType::If:
204 return parse_if_statement();
205 case TokenType::Throw:
206 return parse_throw_statement();
207 case TokenType::Try:
208 return parse_try_statement();
209 case TokenType::Break:
210 return parse_break_statement();
211 case TokenType::Continue:
212 return parse_continue_statement();
213 case TokenType::Switch:
214 return parse_switch_statement();
215 case TokenType::Do:
216 return parse_do_while_statement();
217 default:
218 if (match_expression())
219 return adopt(*new ExpressionStatement(parse_expression(0)));
220 m_parser_state.m_has_errors = true;
221 expected("statement (missing switch case)");
222 consume();
223 return create_ast_node<ErrorStatement>();
224 } }();
225 if (match(TokenType::Semicolon))
226 consume();
227 return statement;
228}
229
230RefPtr<FunctionExpression> Parser::try_parse_arrow_function_expression(bool expect_parens)
231{
232 save_state();
233
234 Vector<FlyString> parameters;
235 bool parse_failed = false;
236 while (true) {
237 if (match(TokenType::Comma)) {
238 consume(TokenType::Comma);
239 } else if (match(TokenType::Identifier)) {
240 auto token = consume(TokenType::Identifier);
241 parameters.append(token.value());
242 } else if (match(TokenType::ParenClose)) {
243 if (expect_parens) {
244 consume(TokenType::ParenClose);
245 if (match(TokenType::Arrow)) {
246 consume(TokenType::Arrow);
247 } else {
248 parse_failed = true;
249 }
250 break;
251 }
252 parse_failed = true;
253 break;
254 } else if (match(TokenType::Arrow)) {
255 if (!expect_parens) {
256 consume(TokenType::Arrow);
257 break;
258 }
259 parse_failed = true;
260 break;
261 } else {
262 parse_failed = true;
263 break;
264 }
265 }
266
267 if (parse_failed) {
268 load_state();
269 return nullptr;
270 }
271
272 auto function_body_result = [this]() -> RefPtr<BlockStatement> {
273 if (match(TokenType::CurlyOpen)) {
274 // Parse a function body with statements
275 return parse_block_statement();
276 }
277 if (match_expression()) {
278 // Parse a function body which returns a single expression
279
280 // FIXME: We synthesize a block with a return statement
281 // for arrow function bodies which are a single expression.
282 // Esprima generates a single "ArrowFunctionExpression"
283 // with a "body" property.
284 auto return_expression = parse_expression(0);
285 auto return_block = create_ast_node<BlockStatement>();
286 return_block->append<ReturnStatement>(move(return_expression));
287 return return_block;
288 }
289 // Invalid arrow function body
290 return nullptr;
291 }();
292
293 if (!function_body_result.is_null()) {
294 auto body = function_body_result.release_nonnull();
295 return create_ast_node<FunctionExpression>("", move(body), move(parameters));
296 }
297
298 load_state();
299 return nullptr;
300}
301
302NonnullRefPtr<Expression> Parser::parse_primary_expression()
303{
304 if (match_unary_prefixed_expression())
305 return parse_unary_prefixed_expression();
306
307 switch (m_parser_state.m_current_token.type()) {
308 case TokenType::ParenOpen: {
309 consume(TokenType::ParenOpen);
310 if (match(TokenType::ParenClose) || match(TokenType::Identifier)) {
311 auto arrow_function_result = try_parse_arrow_function_expression(true);
312 if (!arrow_function_result.is_null()) {
313 return arrow_function_result.release_nonnull();
314 }
315 }
316 auto expression = parse_expression(0);
317 consume(TokenType::ParenClose);
318 return expression;
319 }
320 case TokenType::Identifier: {
321 auto arrow_function_result = try_parse_arrow_function_expression(false);
322 if (!arrow_function_result.is_null()) {
323 return arrow_function_result.release_nonnull();
324 }
325 return create_ast_node<Identifier>(consume().value());
326 }
327 case TokenType::NumericLiteral:
328 return create_ast_node<NumericLiteral>(consume().double_value());
329 case TokenType::BoolLiteral:
330 return create_ast_node<BooleanLiteral>(consume().bool_value());
331 case TokenType::StringLiteral:
332 return create_ast_node<StringLiteral>(consume().string_value());
333 case TokenType::NullLiteral:
334 consume();
335 return create_ast_node<NullLiteral>();
336 case TokenType::CurlyOpen:
337 return parse_object_expression();
338 case TokenType::Function:
339 return parse_function_node<FunctionExpression>();
340 case TokenType::BracketOpen:
341 return parse_array_expression();
342 case TokenType::New:
343 return parse_new_expression();
344 default:
345 m_parser_state.m_has_errors = true;
346 expected("primary expression (missing switch case)");
347 consume();
348 return create_ast_node<ErrorExpression>();
349 }
350}
351
352NonnullRefPtr<Expression> Parser::parse_unary_prefixed_expression()
353{
354 auto precedence = operator_precedence(m_parser_state.m_current_token.type());
355 auto associativity = operator_associativity(m_parser_state.m_current_token.type());
356 switch (m_parser_state.m_current_token.type()) {
357 case TokenType::PlusPlus:
358 consume();
359 return create_ast_node<UpdateExpression>(UpdateOp::Increment, parse_expression(precedence, associativity), true);
360 case TokenType::MinusMinus:
361 consume();
362 return create_ast_node<UpdateExpression>(UpdateOp::Decrement, parse_expression(precedence, associativity), true);
363 case TokenType::ExclamationMark:
364 consume();
365 return create_ast_node<UnaryExpression>(UnaryOp::Not, parse_expression(precedence, associativity));
366 case TokenType::Tilde:
367 consume();
368 return create_ast_node<UnaryExpression>(UnaryOp::BitwiseNot, parse_expression(precedence, associativity));
369 case TokenType::Plus:
370 consume();
371 return create_ast_node<UnaryExpression>(UnaryOp::Plus, parse_expression(precedence, associativity));
372 case TokenType::Minus:
373 consume();
374 return create_ast_node<UnaryExpression>(UnaryOp::Minus, parse_expression(precedence, associativity));
375 case TokenType::Typeof:
376 consume();
377 return create_ast_node<UnaryExpression>(UnaryOp::Typeof, parse_expression(precedence, associativity));
378 default:
379 m_parser_state.m_has_errors = true;
380 expected("primary expression (missing switch case)");
381 consume();
382 return create_ast_node<ErrorExpression>();
383 }
384}
385
386NonnullRefPtr<ObjectExpression> Parser::parse_object_expression()
387{
388 HashMap<FlyString, NonnullRefPtr<Expression>> properties;
389 consume(TokenType::CurlyOpen);
390
391 while (!done() && !match(TokenType::CurlyClose)) {
392 FlyString property_name;
393 if (match(TokenType::Identifier)) {
394 property_name = consume(TokenType::Identifier).value();
395 } else if (match(TokenType::StringLiteral)) {
396 property_name = consume(TokenType::StringLiteral).string_value();
397 } else if (match(TokenType::NumericLiteral)) {
398 property_name = consume(TokenType::NumericLiteral).value();
399 } else {
400 m_parser_state.m_has_errors = true;
401 auto& current_token = m_parser_state.m_current_token;
402 fprintf(stderr, "Error: Unexpected token %s as member in object initialization. Expected a numeric literal, string literal or identifier (line: %zu, column: %zu))\n",
403 current_token.name(),
404 current_token.line_number(),
405 current_token.line_column());
406 consume();
407 continue;
408 }
409
410
411 if (match(TokenType::Colon)) {
412 consume(TokenType::Colon);
413 properties.set(property_name, parse_expression(0));
414 } else {
415 properties.set(property_name, create_ast_node<Identifier>(property_name));
416 }
417
418 if (!match(TokenType::Comma))
419 break;
420
421 consume(TokenType::Comma);
422 }
423
424 consume(TokenType::CurlyClose);
425 return create_ast_node<ObjectExpression>(properties);
426}
427
428NonnullRefPtr<ArrayExpression> Parser::parse_array_expression()
429{
430 consume(TokenType::BracketOpen);
431
432 NonnullRefPtrVector<Expression> elements;
433 while (match_expression()) {
434 elements.append(parse_expression(0));
435 if (!match(TokenType::Comma))
436 break;
437 consume(TokenType::Comma);
438 }
439
440 consume(TokenType::BracketClose);
441 return create_ast_node<ArrayExpression>(move(elements));
442}
443
444NonnullRefPtr<Expression> Parser::parse_expression(int min_precedence, Associativity associativity)
445{
446 auto expression = parse_primary_expression();
447 while (match_secondary_expression()) {
448 int new_precedence = operator_precedence(m_parser_state.m_current_token.type());
449 if (new_precedence < min_precedence)
450 break;
451 if (new_precedence == min_precedence && associativity == Associativity::Left)
452 break;
453
454 Associativity new_associativity = operator_associativity(m_parser_state.m_current_token.type());
455 expression = parse_secondary_expression(move(expression), new_precedence, new_associativity);
456 }
457 return expression;
458}
459
460NonnullRefPtr<Expression> Parser::parse_secondary_expression(NonnullRefPtr<Expression> lhs, int min_precedence, Associativity associativity)
461{
462 switch (m_parser_state.m_current_token.type()) {
463 case TokenType::Plus:
464 consume();
465 return create_ast_node<BinaryExpression>(BinaryOp::Addition, move(lhs), parse_expression(min_precedence, associativity));
466 case TokenType::PlusEquals:
467 consume();
468 return create_ast_node<AssignmentExpression>(AssignmentOp::AdditionAssignment, move(lhs), parse_expression(min_precedence, associativity));
469 case TokenType::Minus:
470 consume();
471 return create_ast_node<BinaryExpression>(BinaryOp::Subtraction, move(lhs), parse_expression(min_precedence, associativity));
472 case TokenType::MinusEquals:
473 consume();
474 return create_ast_node<AssignmentExpression>(AssignmentOp::SubtractionAssignment, move(lhs), parse_expression(min_precedence, associativity));
475 case TokenType::Asterisk:
476 consume();
477 return create_ast_node<BinaryExpression>(BinaryOp::Multiplication, move(lhs), parse_expression(min_precedence, associativity));
478 case TokenType::AsteriskEquals:
479 consume();
480 return create_ast_node<AssignmentExpression>(AssignmentOp::MultiplicationAssignment, move(lhs), parse_expression(min_precedence, associativity));
481 case TokenType::Slash:
482 consume();
483 return create_ast_node<BinaryExpression>(BinaryOp::Division, move(lhs), parse_expression(min_precedence, associativity));
484 case TokenType::SlashEquals:
485 consume();
486 return create_ast_node<AssignmentExpression>(AssignmentOp::DivisionAssignment, move(lhs), parse_expression(min_precedence, associativity));
487 case TokenType::Percent:
488 consume();
489 return create_ast_node<BinaryExpression>(BinaryOp::Modulo, move(lhs), parse_expression(min_precedence, associativity));
490 case TokenType::DoubleAsterisk:
491 consume();
492 return create_ast_node<BinaryExpression>(BinaryOp::Exponentiation, move(lhs), parse_expression(min_precedence, associativity));
493 case TokenType::GreaterThan:
494 consume();
495 return create_ast_node<BinaryExpression>(BinaryOp::GreaterThan, move(lhs), parse_expression(min_precedence, associativity));
496 case TokenType::GreaterThanEquals:
497 consume();
498 return create_ast_node<BinaryExpression>(BinaryOp::GreaterThanEquals, move(lhs), parse_expression(min_precedence, associativity));
499 case TokenType::LessThan:
500 consume();
501 return create_ast_node<BinaryExpression>(BinaryOp::LessThan, move(lhs), parse_expression(min_precedence, associativity));
502 case TokenType::LessThanEquals:
503 consume();
504 return create_ast_node<BinaryExpression>(BinaryOp::LessThanEquals, move(lhs), parse_expression(min_precedence, associativity));
505 case TokenType::EqualsEqualsEquals:
506 consume();
507 return create_ast_node<BinaryExpression>(BinaryOp::TypedEquals, move(lhs), parse_expression(min_precedence, associativity));
508 case TokenType::ExclamationMarkEqualsEquals:
509 consume();
510 return create_ast_node<BinaryExpression>(BinaryOp::TypedInequals, move(lhs), parse_expression(min_precedence, associativity));
511 case TokenType::EqualsEquals:
512 consume();
513 return create_ast_node<BinaryExpression>(BinaryOp::AbstractEquals, move(lhs), parse_expression(min_precedence, associativity));
514 case TokenType::ExclamationMarkEquals:
515 consume();
516 return create_ast_node<BinaryExpression>(BinaryOp::AbstractInequals, move(lhs), parse_expression(min_precedence, associativity));
517 case TokenType::Instanceof:
518 consume();
519 return create_ast_node<BinaryExpression>(BinaryOp::InstanceOf, move(lhs), parse_expression(min_precedence, associativity));
520 case TokenType::Ampersand:
521 consume();
522 return create_ast_node<BinaryExpression>(BinaryOp::BitwiseAnd, move(lhs), parse_expression(min_precedence, associativity));
523 case TokenType::Pipe:
524 consume();
525 return create_ast_node<BinaryExpression>(BinaryOp::BitwiseOr, move(lhs), parse_expression(min_precedence, associativity));
526 case TokenType::Caret:
527 consume();
528 return create_ast_node<BinaryExpression>(BinaryOp::BitwiseXor, move(lhs), parse_expression(min_precedence, associativity));
529 case TokenType::ParenOpen:
530 return parse_call_expression(move(lhs));
531 case TokenType::Equals:
532 consume();
533 return create_ast_node<AssignmentExpression>(AssignmentOp::Assignment, move(lhs), parse_expression(min_precedence, associativity));
534 case TokenType::Period:
535 consume();
536 return create_ast_node<MemberExpression>(move(lhs), parse_expression(min_precedence, associativity));
537 case TokenType::BracketOpen: {
538 consume(TokenType::BracketOpen);
539 auto expression = create_ast_node<MemberExpression>(move(lhs), parse_expression(0), true);
540 consume(TokenType::BracketClose);
541 return expression;
542 }
543 case TokenType::PlusPlus:
544 consume();
545 return create_ast_node<UpdateExpression>(UpdateOp::Increment, move(lhs));
546 case TokenType::MinusMinus:
547 consume();
548 return create_ast_node<UpdateExpression>(UpdateOp::Decrement, move(lhs));
549 case TokenType::DoubleAmpersand:
550 consume();
551 return create_ast_node<LogicalExpression>(LogicalOp::And, move(lhs), parse_expression(min_precedence, associativity));
552 case TokenType::DoublePipe:
553 consume();
554 return create_ast_node<LogicalExpression>(LogicalOp::Or, move(lhs), parse_expression(min_precedence, associativity));
555 case TokenType::QuestionMark:
556 return parse_conditional_expression(move(lhs));
557 default:
558 m_parser_state.m_has_errors = true;
559 expected("secondary expression (missing switch case)");
560 consume();
561 return create_ast_node<ErrorExpression>();
562 }
563}
564
565NonnullRefPtr<CallExpression> Parser::parse_call_expression(NonnullRefPtr<Expression> lhs)
566{
567 consume(TokenType::ParenOpen);
568
569 NonnullRefPtrVector<Expression> arguments;
570
571 while (match_expression()) {
572 arguments.append(parse_expression(0));
573 if (!match(TokenType::Comma))
574 break;
575 consume();
576 }
577
578 consume(TokenType::ParenClose);
579
580 return create_ast_node<CallExpression>(move(lhs), move(arguments));
581}
582
583NonnullRefPtr<NewExpression> Parser::parse_new_expression()
584{
585 consume(TokenType::New);
586
587 // FIXME: Support full expressions as the callee as well.
588 auto callee = create_ast_node<Identifier>(consume(TokenType::Identifier).value());
589
590 NonnullRefPtrVector<Expression> arguments;
591
592 if (match(TokenType::ParenOpen)) {
593 consume(TokenType::ParenOpen);
594 while (match_expression()) {
595 arguments.append(parse_expression(0));
596 if (!match(TokenType::Comma))
597 break;
598 consume();
599 }
600 consume(TokenType::ParenClose);
601 }
602
603 return create_ast_node<NewExpression>(move(callee), move(arguments));
604}
605
606NonnullRefPtr<ReturnStatement> Parser::parse_return_statement()
607{
608 consume(TokenType::Return);
609 if (match_expression()) {
610 return create_ast_node<ReturnStatement>(parse_expression(0));
611 }
612 return create_ast_node<ReturnStatement>(nullptr);
613}
614
615NonnullRefPtr<BlockStatement> Parser::parse_block_statement()
616{
617 auto block = create_ast_node<BlockStatement>();
618 consume(TokenType::CurlyOpen);
619 while (!done() && !match(TokenType::CurlyClose)) {
620 if (match(TokenType::Semicolon)) {
621 consume();
622 } else if (match_statement()) {
623 block->append(parse_statement());
624 } else {
625 expected("statement");
626 consume();
627 }
628 }
629 consume(TokenType::CurlyClose);
630 return block;
631}
632
633template<typename FunctionNodeType>
634NonnullRefPtr<FunctionNodeType> Parser::parse_function_node()
635{
636 consume(TokenType::Function);
637 String name;
638 if (FunctionNodeType::must_have_name()) {
639 name = consume(TokenType::Identifier).value();
640 } else {
641 if (match(TokenType::Identifier))
642 name = consume(TokenType::Identifier).value();
643 }
644 consume(TokenType::ParenOpen);
645 Vector<FlyString> parameters;
646 while (match(TokenType::Identifier)) {
647 auto parameter = consume(TokenType::Identifier).value();
648 parameters.append(parameter);
649 if (match(TokenType::ParenClose)) {
650 break;
651 }
652 consume(TokenType::Comma);
653 }
654 consume(TokenType::ParenClose);
655 auto body = parse_block_statement();
656 return create_ast_node<FunctionNodeType>(name, move(body), move(parameters));
657}
658
659NonnullRefPtr<VariableDeclaration> Parser::parse_variable_declaration()
660{
661 DeclarationKind declaration_kind;
662
663 switch (m_parser_state.m_current_token.type()) {
664 case TokenType::Var:
665 declaration_kind = DeclarationKind::Var;
666 consume(TokenType::Var);
667 break;
668 case TokenType::Let:
669 declaration_kind = DeclarationKind::Let;
670 consume(TokenType::Let);
671 break;
672 case TokenType::Const:
673 declaration_kind = DeclarationKind::Const;
674 consume(TokenType::Const);
675 break;
676 default:
677 ASSERT_NOT_REACHED();
678 }
679
680 NonnullRefPtrVector<VariableDeclarator> declarations;
681 for (;;) {
682 auto id = consume(TokenType::Identifier).value();
683 RefPtr<Expression> init;
684 if (match(TokenType::Equals)) {
685 consume();
686 init = parse_expression(0);
687 }
688 declarations.append(create_ast_node<VariableDeclarator>(create_ast_node<Identifier>(move(id)), move(init)));
689 if (match(TokenType::Comma)) {
690 consume();
691 continue;
692 }
693 break;
694 }
695 return create_ast_node<VariableDeclaration>(declaration_kind, move(declarations));
696}
697
698NonnullRefPtr<ThrowStatement> Parser::parse_throw_statement()
699{
700 consume(TokenType::Throw);
701 return create_ast_node<ThrowStatement>(parse_expression(0));
702}
703
704NonnullRefPtr<BreakStatement> Parser::parse_break_statement()
705{
706 consume(TokenType::Break);
707 // FIXME: Handle labels.
708 return create_ast_node<BreakStatement>();
709}
710
711NonnullRefPtr<ContinueStatement> Parser::parse_continue_statement()
712{
713 consume(TokenType::Continue);
714 // FIXME: Handle labels.
715 return create_ast_node<ContinueStatement>();
716}
717
718NonnullRefPtr<ConditionalExpression> Parser::parse_conditional_expression(NonnullRefPtr<Expression> test)
719{
720 consume(TokenType::QuestionMark);
721 auto consequent = parse_expression(0);
722 consume(TokenType::Colon);
723 auto alternate = parse_expression(0);
724 return create_ast_node<ConditionalExpression>(move(test), move(consequent), move(alternate));
725}
726
727NonnullRefPtr<TryStatement> Parser::parse_try_statement()
728{
729 consume(TokenType::Try);
730
731 auto block = parse_block_statement();
732
733 RefPtr<CatchClause> handler;
734 if (match(TokenType::Catch))
735 handler = parse_catch_clause();
736
737 RefPtr<BlockStatement> finalizer;
738 if (match(TokenType::Finally)) {
739 consume();
740 finalizer = parse_block_statement();
741 }
742
743 return create_ast_node<TryStatement>(move(block), move(handler), move(finalizer));
744}
745
746NonnullRefPtr<DoWhileStatement> Parser::parse_do_while_statement()
747{
748 consume(TokenType::Do);
749
750 auto body = parse_statement();
751
752 consume(TokenType::While);
753 consume(TokenType::ParenOpen);
754
755 auto test = parse_expression(0);
756
757 consume(TokenType::ParenClose);
758
759 return create_ast_node<DoWhileStatement>(move(test), move(body));
760}
761
762NonnullRefPtr<SwitchStatement> Parser::parse_switch_statement()
763{
764 consume(TokenType::Switch);
765
766 consume(TokenType::ParenOpen);
767 auto determinant = parse_expression(0);
768 consume(TokenType::ParenClose);
769
770 consume(TokenType::CurlyOpen);
771
772 NonnullRefPtrVector<SwitchCase> cases;
773
774 while (match(TokenType::Case) || match(TokenType::Default))
775 cases.append(parse_switch_case());
776
777 consume(TokenType::CurlyClose);
778
779 return create_ast_node<SwitchStatement>(move(determinant), move(cases));
780}
781
782NonnullRefPtr<SwitchCase> Parser::parse_switch_case()
783{
784 RefPtr<Expression> test;
785
786 if (consume().type() == TokenType::Case) {
787 test = parse_expression(0);
788 }
789
790 consume(TokenType::Colon);
791
792 NonnullRefPtrVector<Statement> consequent;
793 while (match_statement())
794 consequent.append(parse_statement());
795
796 return create_ast_node<SwitchCase>(move(test), move(consequent));
797}
798
799NonnullRefPtr<CatchClause> Parser::parse_catch_clause()
800{
801 consume(TokenType::Catch);
802
803 String parameter;
804 if (match(TokenType::ParenOpen)) {
805 consume();
806 parameter = consume(TokenType::Identifier).value();
807 consume(TokenType::ParenClose);
808 }
809
810 auto body = parse_block_statement();
811 return create_ast_node<CatchClause>(parameter, move(body));
812}
813
814NonnullRefPtr<IfStatement> Parser::parse_if_statement()
815{
816 consume(TokenType::If);
817 consume(TokenType::ParenOpen);
818 auto predicate = parse_expression(0);
819 consume(TokenType::ParenClose);
820 auto consequent = parse_statement();
821 RefPtr<Statement> alternate;
822 if (match(TokenType::Else)) {
823 consume(TokenType::Else);
824 alternate = parse_statement();
825 }
826 return create_ast_node<IfStatement>(move(predicate), move(consequent), move(alternate));
827}
828
829NonnullRefPtr<ForStatement> Parser::parse_for_statement()
830{
831 consume(TokenType::For);
832
833 consume(TokenType::ParenOpen);
834
835 RefPtr<ASTNode> init;
836 switch (m_parser_state.m_current_token.type()) {
837 case TokenType::Semicolon:
838 break;
839 default:
840 if (match_expression())
841 init = parse_expression(0);
842 else if (match_variable_declaration())
843 init = parse_variable_declaration();
844 else
845 ASSERT_NOT_REACHED();
846 break;
847 }
848
849 consume(TokenType::Semicolon);
850
851 RefPtr<Expression> test;
852 switch (m_parser_state.m_current_token.type()) {
853 case TokenType::Semicolon:
854 break;
855 default:
856 test = parse_expression(0);
857 break;
858 }
859
860 consume(TokenType::Semicolon);
861
862 RefPtr<Expression> update;
863 switch (m_parser_state.m_current_token.type()) {
864 case TokenType::ParenClose:
865 break;
866 default:
867 update = parse_expression(0);
868 break;
869 }
870
871 consume(TokenType::ParenClose);
872
873 auto body = parse_statement();
874
875 return create_ast_node<ForStatement>(move(init), move(test), move(update), move(body));
876}
877
878bool Parser::match(TokenType type) const
879{
880 return m_parser_state.m_current_token.type() == type;
881}
882
883bool Parser::match_variable_declaration() const
884{
885 switch (m_parser_state.m_current_token.type()) {
886 case TokenType::Var:
887 case TokenType::Let:
888 case TokenType::Const:
889 return true;
890 default:
891 return false;
892 }
893}
894
895bool Parser::match_expression() const
896{
897 auto type = m_parser_state.m_current_token.type();
898 return type == TokenType::BoolLiteral
899 || type == TokenType::NumericLiteral
900 || type == TokenType::StringLiteral
901 || type == TokenType::NullLiteral
902 || type == TokenType::Identifier
903 || type == TokenType::New
904 || type == TokenType::CurlyOpen
905 || type == TokenType::BracketOpen
906 || type == TokenType::ParenOpen
907 || type == TokenType::Function
908 || match_unary_prefixed_expression();
909}
910
911bool Parser::match_unary_prefixed_expression() const
912{
913 auto type = m_parser_state.m_current_token.type();
914 return type == TokenType::PlusPlus
915 || type == TokenType::MinusMinus
916 || type == TokenType::ExclamationMark
917 || type == TokenType::Tilde
918 || type == TokenType::Plus
919 || type == TokenType::Minus
920 || type == TokenType::Typeof;
921}
922
923bool Parser::match_secondary_expression() const
924{
925 auto type = m_parser_state.m_current_token.type();
926 return type == TokenType::Plus
927 || type == TokenType::PlusEquals
928 || type == TokenType::Minus
929 || type == TokenType::MinusEquals
930 || type == TokenType::Asterisk
931 || type == TokenType::AsteriskEquals
932 || type == TokenType::Slash
933 || type == TokenType::SlashEquals
934 || type == TokenType::Percent
935 || type == TokenType::DoubleAsterisk
936 || type == TokenType::Equals
937 || type == TokenType::EqualsEqualsEquals
938 || type == TokenType::ExclamationMarkEqualsEquals
939 || type == TokenType::EqualsEquals
940 || type == TokenType::ExclamationMarkEquals
941 || type == TokenType::GreaterThan
942 || type == TokenType::GreaterThanEquals
943 || type == TokenType::LessThan
944 || type == TokenType::LessThanEquals
945 || type == TokenType::ParenOpen
946 || type == TokenType::Period
947 || type == TokenType::BracketOpen
948 || type == TokenType::PlusPlus
949 || type == TokenType::MinusMinus
950 || type == TokenType::Instanceof
951 || type == TokenType::QuestionMark
952 || type == TokenType::Ampersand
953 || type == TokenType::Pipe
954 || type == TokenType::Caret
955 || type == TokenType::DoubleAmpersand
956 || type == TokenType::DoublePipe;
957}
958
959bool Parser::match_statement() const
960{
961 auto type = m_parser_state.m_current_token.type();
962 return match_expression()
963 || type == TokenType::Function
964 || type == TokenType::Return
965 || type == TokenType::Let
966 || type == TokenType::Class
967 || type == TokenType::Delete
968 || type == TokenType::Do
969 || type == TokenType::If
970 || type == TokenType::Throw
971 || type == TokenType::Try
972 || type == TokenType::While
973 || type == TokenType::For
974 || type == TokenType::Const
975 || type == TokenType::CurlyOpen
976 || type == TokenType::Switch
977 || type == TokenType::Break
978 || type == TokenType::Continue
979 || type == TokenType::Var;
980}
981
982bool Parser::done() const
983{
984 return match(TokenType::Eof);
985}
986
987Token Parser::consume()
988{
989 auto old_token = m_parser_state.m_current_token;
990 m_parser_state.m_current_token = m_parser_state.m_lexer.next();
991 return old_token;
992}
993
994Token Parser::consume(TokenType type)
995{
996 if (m_parser_state.m_current_token.type() != type) {
997 m_parser_state.m_has_errors = true;
998 auto& current_token = m_parser_state.m_current_token;
999 fprintf(stderr, "Error: Unexpected token %s. Expected %s (line: %zu, column: %zu))\n",
1000 current_token.name(),
1001 Token::name(type),
1002 current_token.line_number(),
1003 current_token.line_column());
1004 }
1005 return consume();
1006}
1007
1008void Parser::expected(const char* what)
1009{
1010 m_parser_state.m_has_errors = true;
1011 auto& current_token = m_parser_state.m_current_token;
1012 fprintf(stderr, "Error: Unexpected token %s. Expected %s (line: %zu, column: %zu)\n",
1013 current_token.name(),
1014 what,
1015 current_token.line_number(),
1016 current_token.line_column());
1017}
1018
1019void Parser::save_state()
1020{
1021 m_saved_state = m_parser_state;
1022}
1023
1024void Parser::load_state()
1025{
1026 ASSERT(m_saved_state.has_value());
1027 m_parser_state = m_saved_state.value();
1028 m_saved_state.clear();
1029}
1030}