1 // Copyright (c) 2013 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "tools/gn/parser.h" 6 7 #include "base/logging.h" 8 #include "tools/gn/functions.h" 9 #include "tools/gn/operators.h" 10 #include "tools/gn/token.h" 11 12 // grammar: 13 // 14 // file := (statement)* 15 // statement := block | if | assignment 16 // block := '{' statement* '}' 17 // if := 'if' '(' expr ')' statement [ else ] 18 // else := 'else' (if | statement)* 19 // assignment := ident {'=' | '+=' | '-='} expr 20 21 enum Precedence { 22 PRECEDENCE_ASSIGNMENT = 1, 23 PRECEDENCE_OR = 2, 24 PRECEDENCE_AND = 3, 25 PRECEDENCE_EQUALITY = 4, 26 PRECEDENCE_RELATION = 5, 27 PRECEDENCE_SUM = 6, 28 PRECEDENCE_PREFIX = 7, 29 PRECEDENCE_CALL = 8, 30 }; 31 32 // The top-level for blocks/ifs is still recursive descent, the expression 33 // parser is a Pratt parser. The basic idea there is to have the precedences 34 // (and associativities) encoded relative to each other and only parse up 35 // until you hit something of that precedence. There's a dispatch table in 36 // expressions_ at the top of parser.cc that describes how each token 37 // dispatches if it's seen as either a prefix or infix operator, and if it's 38 // infix, what its precedence is. 39 // 40 // Refs: 41 // - http://javascript.crockford.com/tdop/tdop.html 42 // - http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ 43 44 // Indexed by Token::Type. 45 ParserHelper Parser::expressions_[] = { 46 {NULL, NULL, -1}, // INVALID 47 {&Parser::Literal, NULL, -1}, // INTEGER 48 {&Parser::Literal, NULL, -1}, // STRING 49 {&Parser::Literal, NULL, -1}, // TRUE_TOKEN 50 {&Parser::Literal, NULL, -1}, // FALSE_TOKEN 51 {NULL, &Parser::Assignment, PRECEDENCE_ASSIGNMENT}, // EQUAL 52 {NULL, &Parser::BinaryOperator, PRECEDENCE_SUM}, // PLUS 53 {NULL, &Parser::BinaryOperator, PRECEDENCE_SUM}, // MINUS 54 {NULL, &Parser::Assignment, PRECEDENCE_ASSIGNMENT}, // PLUS_EQUALS 55 {NULL, &Parser::Assignment, PRECEDENCE_ASSIGNMENT}, // MINUS_EQUALS 56 {NULL, &Parser::BinaryOperator, PRECEDENCE_EQUALITY}, // EQUAL_EQUAL 57 {NULL, &Parser::BinaryOperator, PRECEDENCE_EQUALITY}, // NOT_EQUAL 58 {NULL, &Parser::BinaryOperator, PRECEDENCE_RELATION}, // LESS_EQUAL 59 {NULL, &Parser::BinaryOperator, PRECEDENCE_RELATION}, // GREATER_EQUAL 60 {NULL, &Parser::BinaryOperator, PRECEDENCE_RELATION}, // LESS_THAN 61 {NULL, &Parser::BinaryOperator, PRECEDENCE_RELATION}, // GREATER_THAN 62 {NULL, &Parser::BinaryOperator, PRECEDENCE_AND}, // BOOLEAN_AND 63 {NULL, &Parser::BinaryOperator, PRECEDENCE_OR}, // BOOLEAN_OR 64 {&Parser::Not, NULL, -1}, // BANG 65 {&Parser::Group, NULL, -1}, // LEFT_PAREN 66 {NULL, NULL, -1}, // RIGHT_PAREN 67 {&Parser::List, &Parser::Subscript, PRECEDENCE_CALL}, // LEFT_BRACKET 68 {NULL, NULL, -1}, // RIGHT_BRACKET 69 {NULL, NULL, -1}, // LEFT_BRACE 70 {NULL, NULL, -1}, // RIGHT_BRACE 71 {NULL, NULL, -1}, // IF 72 {NULL, NULL, -1}, // ELSE 73 {&Parser::Name, &Parser::IdentifierOrCall, PRECEDENCE_CALL}, // IDENTIFIER 74 {NULL, NULL, -1}, // COMMA 75 {NULL, NULL, -1}, // COMMENT 76 }; 77 78 Parser::Parser(const std::vector<Token>& tokens, Err* err) 79 : tokens_(tokens), err_(err), cur_(0) { 80 } 81 82 Parser::~Parser() { 83 } 84 85 // static 86 scoped_ptr<ParseNode> Parser::Parse(const std::vector<Token>& tokens, 87 Err* err) { 88 Parser p(tokens, err); 89 return p.ParseFile().PassAs<ParseNode>(); 90 } 91 92 // static 93 scoped_ptr<ParseNode> Parser::ParseExpression(const std::vector<Token>& tokens, 94 Err* err) { 95 Parser p(tokens, err); 96 return p.ParseExpression().Pass(); 97 } 98 99 bool Parser::IsAssignment(const ParseNode* node) const { 100 return node && node->AsBinaryOp() && 101 (node->AsBinaryOp()->op().type() == Token::EQUAL || 102 node->AsBinaryOp()->op().type() == Token::PLUS_EQUALS || 103 node->AsBinaryOp()->op().type() == Token::MINUS_EQUALS); 104 } 105 106 bool Parser::IsStatementBreak(Token::Type token_type) const { 107 switch (token_type) { 108 case Token::IDENTIFIER: 109 case Token::LEFT_BRACE: 110 case Token::RIGHT_BRACE: 111 case Token::IF: 112 case Token::ELSE: 113 return true; 114 default: 115 return false; 116 } 117 } 118 119 bool Parser::LookAhead(Token::Type type) { 120 if (at_end()) 121 return false; 122 return cur_token().type() == type; 123 } 124 125 bool Parser::Match(Token::Type type) { 126 if (!LookAhead(type)) 127 return false; 128 Consume(); 129 return true; 130 } 131 132 Token Parser::Consume(Token::Type type, const char* error_message) { 133 Token::Type types[1] = { type }; 134 return Consume(types, 1, error_message); 135 } 136 137 Token Parser::Consume(Token::Type* types, 138 size_t num_types, 139 const char* error_message) { 140 if (has_error()) { 141 // Don't overwrite current error, but make progress through tokens so that 142 // a loop that's expecting a particular token will still terminate. 143 cur_++; 144 return Token(Location(), Token::INVALID, base::StringPiece()); 145 } 146 if (at_end()) { 147 const char kEOFMsg[] = "I hit EOF instead."; 148 if (tokens_.empty()) 149 *err_ = Err(Location(), error_message, kEOFMsg); 150 else 151 *err_ = Err(tokens_[tokens_.size() - 1], error_message, kEOFMsg); 152 return Token(Location(), Token::INVALID, base::StringPiece()); 153 } 154 155 for (size_t i = 0; i < num_types; ++i) { 156 if (cur_token().type() == types[i]) 157 return tokens_[cur_++]; 158 } 159 *err_ = Err(cur_token(), error_message); 160 return Token(Location(), Token::INVALID, base::StringPiece()); 161 } 162 163 Token Parser::Consume() { 164 return tokens_[cur_++]; 165 } 166 167 scoped_ptr<ParseNode> Parser::ParseExpression() { 168 return ParseExpression(0); 169 } 170 171 scoped_ptr<ParseNode> Parser::ParseExpression(int precedence) { 172 if (at_end()) 173 return scoped_ptr<ParseNode>(); 174 175 Token token = Consume(); 176 PrefixFunc prefix = expressions_[token.type()].prefix; 177 178 if (prefix == NULL) { 179 *err_ = Err(token, 180 std::string("Unexpected token '") + token.value().as_string() + 181 std::string("'")); 182 return scoped_ptr<ParseNode>(); 183 } 184 185 scoped_ptr<ParseNode> left = (this->*prefix)(token); 186 if (has_error()) 187 return left.Pass(); 188 189 while (!at_end() && !IsStatementBreak(cur_token().type()) && 190 precedence <= expressions_[cur_token().type()].precedence) { 191 token = Consume(); 192 InfixFunc infix = expressions_[token.type()].infix; 193 if (infix == NULL) { 194 *err_ = Err(token, 195 std::string("Unexpected token '") + 196 token.value().as_string() + std::string("'")); 197 return scoped_ptr<ParseNode>(); 198 } 199 left = (this->*infix)(left.Pass(), token); 200 if (has_error()) 201 return scoped_ptr<ParseNode>(); 202 } 203 204 return left.Pass(); 205 } 206 207 scoped_ptr<ParseNode> Parser::Literal(Token token) { 208 return scoped_ptr<ParseNode>(new LiteralNode(token)).Pass(); 209 } 210 211 scoped_ptr<ParseNode> Parser::Name(Token token) { 212 return IdentifierOrCall(scoped_ptr<ParseNode>(), token).Pass(); 213 } 214 215 scoped_ptr<ParseNode> Parser::Group(Token token) { 216 scoped_ptr<ParseNode> expr = ParseExpression(); 217 if (has_error()) 218 return scoped_ptr<ParseNode>(); 219 Consume(Token::RIGHT_PAREN, "Expected ')'"); 220 return expr.Pass(); 221 } 222 223 scoped_ptr<ParseNode> Parser::Not(Token token) { 224 scoped_ptr<ParseNode> expr = ParseExpression(PRECEDENCE_PREFIX + 1); 225 if (has_error()) 226 return scoped_ptr<ParseNode>(); 227 scoped_ptr<UnaryOpNode> unary_op(new UnaryOpNode); 228 unary_op->set_op(token); 229 unary_op->set_operand(expr.Pass()); 230 return unary_op.PassAs<ParseNode>(); 231 } 232 233 scoped_ptr<ParseNode> Parser::List(Token node) { 234 scoped_ptr<ParseNode> list(ParseList(Token::RIGHT_BRACKET, true)); 235 if (!has_error() && !at_end()) 236 Consume(Token::RIGHT_BRACKET, "Expected ']'"); 237 return list.Pass(); 238 } 239 240 scoped_ptr<ParseNode> Parser::BinaryOperator(scoped_ptr<ParseNode> left, 241 Token token) { 242 scoped_ptr<ParseNode> right = 243 ParseExpression(expressions_[token.type()].precedence + 1); 244 if (!right) { 245 *err_ = 246 Err(token, 247 "Expected right hand side for '" + token.value().as_string() + "'"); 248 return scoped_ptr<ParseNode>(); 249 } 250 scoped_ptr<BinaryOpNode> binary_op(new BinaryOpNode); 251 binary_op->set_op(token); 252 binary_op->set_left(left.Pass()); 253 binary_op->set_right(right.Pass()); 254 return binary_op.PassAs<ParseNode>(); 255 } 256 257 scoped_ptr<ParseNode> Parser::IdentifierOrCall(scoped_ptr<ParseNode> left, 258 Token token) { 259 scoped_ptr<ListNode> list(new ListNode); 260 list->set_begin_token(token); 261 list->set_end_token(token); 262 scoped_ptr<BlockNode> block; 263 bool has_arg = false; 264 if (Match(Token::LEFT_PAREN)) { 265 // Parsing a function call. 266 has_arg = true; 267 if (Match(Token::RIGHT_PAREN)) { 268 // Nothing, just an empty call. 269 } else { 270 list = ParseList(Token::RIGHT_PAREN, false); 271 if (has_error()) 272 return scoped_ptr<ParseNode>(); 273 Consume(Token::RIGHT_PAREN, "Expected ')' after call"); 274 } 275 // Optionally with a scope. 276 if (LookAhead(Token::LEFT_BRACE)) { 277 block = ParseBlock(); 278 if (has_error()) 279 return scoped_ptr<ParseNode>(); 280 } 281 } 282 283 if (!left && !has_arg) { 284 // Not a function call, just a standalone identifier. 285 return scoped_ptr<ParseNode>(new IdentifierNode(token)).Pass(); 286 } 287 scoped_ptr<FunctionCallNode> func_call(new FunctionCallNode); 288 func_call->set_function(token); 289 func_call->set_args(list.Pass()); 290 if (block) 291 func_call->set_block(block.Pass()); 292 return func_call.PassAs<ParseNode>(); 293 } 294 295 scoped_ptr<ParseNode> Parser::Assignment(scoped_ptr<ParseNode> left, 296 Token token) { 297 if (left->AsIdentifier() == NULL) { 298 *err_ = Err(left.get(), "Left-hand side of assignment must be identifier."); 299 return scoped_ptr<ParseNode>(); 300 } 301 scoped_ptr<ParseNode> value = ParseExpression(PRECEDENCE_ASSIGNMENT); 302 scoped_ptr<BinaryOpNode> assign(new BinaryOpNode); 303 assign->set_op(token); 304 assign->set_left(left.Pass()); 305 assign->set_right(value.Pass()); 306 return assign.PassAs<ParseNode>(); 307 } 308 309 scoped_ptr<ParseNode> Parser::Subscript(scoped_ptr<ParseNode> left, 310 Token token) { 311 // TODO: Maybe support more complex expressions like a[0][0]. This would 312 // require work on the evaluator too. 313 if (left->AsIdentifier() == NULL) { 314 *err_ = Err(left.get(), "May only subscript simple identifiers"); 315 return scoped_ptr<ParseNode>(); 316 } 317 scoped_ptr<ParseNode> value = ParseExpression(); 318 Consume(Token::RIGHT_BRACKET, "Expecting ']' after subscript."); 319 scoped_ptr<AccessorNode> accessor(new AccessorNode); 320 accessor->set_base(left->AsIdentifier()->value()); 321 accessor->set_index(value.Pass()); 322 return accessor.PassAs<ParseNode>(); 323 } 324 325 // Does not Consume the start or end token. 326 scoped_ptr<ListNode> Parser::ParseList(Token::Type stop_before, 327 bool allow_trailing_comma) { 328 scoped_ptr<ListNode> list(new ListNode); 329 list->set_begin_token(cur_token()); 330 bool just_got_comma = false; 331 while (!LookAhead(stop_before)) { 332 just_got_comma = false; 333 // Why _OR? We're parsing things that are higher precedence than the , 334 // that separates the items of the list. , should appear lower than 335 // boolean expressions (the lowest of which is OR), but above assignments. 336 list->append_item(ParseExpression(PRECEDENCE_OR)); 337 if (has_error()) 338 return scoped_ptr<ListNode>(); 339 if (at_end()) { 340 *err_ = 341 Err(tokens_[tokens_.size() - 1], "Unexpected end of file in list."); 342 return scoped_ptr<ListNode>(); 343 } 344 just_got_comma = Match(Token::COMMA); 345 } 346 if (just_got_comma && !allow_trailing_comma) { 347 *err_ = Err(cur_token(), "Trailing comma"); 348 return scoped_ptr<ListNode>(); 349 } 350 list->set_end_token(cur_token()); 351 return list.Pass(); 352 } 353 354 scoped_ptr<ParseNode> Parser::ParseFile() { 355 scoped_ptr<BlockNode> file(new BlockNode(false)); 356 for (;;) { 357 if (at_end()) 358 break; 359 scoped_ptr<ParseNode> statement = ParseStatement(); 360 if (!statement) 361 break; 362 file->append_statement(statement.Pass()); 363 } 364 if (!at_end() && !has_error()) 365 *err_ = Err(cur_token(), "Unexpected here, should be newline."); 366 if (has_error()) 367 return scoped_ptr<ParseNode>(); 368 return file.PassAs<ParseNode>(); 369 } 370 371 scoped_ptr<ParseNode> Parser::ParseStatement() { 372 if (LookAhead(Token::LEFT_BRACE)) { 373 return ParseBlock().PassAs<ParseNode>(); 374 } else if (LookAhead(Token::IF)) { 375 return ParseCondition(); 376 } else { 377 // TODO(scottmg): Is this too strict? Just drop all the testing if we want 378 // to allow "pointless" expressions and return ParseExpression() directly. 379 scoped_ptr<ParseNode> stmt = ParseExpression(); 380 if (stmt) { 381 if (stmt->AsFunctionCall() || IsAssignment(stmt.get())) 382 return stmt.Pass(); 383 } 384 if (!has_error()) { 385 Token token = at_end() ? tokens_[tokens_.size() - 1] : cur_token(); 386 *err_ = Err(token, "Expecting assignment or function call."); 387 } 388 return scoped_ptr<ParseNode>(); 389 } 390 } 391 392 scoped_ptr<BlockNode> Parser::ParseBlock() { 393 Token begin_token = 394 Consume(Token::LEFT_BRACE, "Expected '{' to start a block."); 395 if (has_error()) 396 return scoped_ptr<BlockNode>(); 397 scoped_ptr<BlockNode> block(new BlockNode(true)); 398 block->set_begin_token(begin_token); 399 400 for (;;) { 401 if (LookAhead(Token::RIGHT_BRACE)) { 402 block->set_end_token(Consume()); 403 break; 404 } 405 406 scoped_ptr<ParseNode> statement = ParseStatement(); 407 if (!statement) 408 return scoped_ptr<BlockNode>(); 409 block->append_statement(statement.Pass()); 410 } 411 return block.Pass(); 412 } 413 414 scoped_ptr<ParseNode> Parser::ParseCondition() { 415 scoped_ptr<ConditionNode> condition(new ConditionNode); 416 Consume(Token::IF, "Expected 'if'"); 417 Consume(Token::LEFT_PAREN, "Expected '(' after 'if'."); 418 condition->set_condition(ParseExpression()); 419 if (IsAssignment(condition->condition())) 420 *err_ = Err(condition->condition(), "Assignment not allowed in 'if'."); 421 Consume(Token::RIGHT_PAREN, "Expected ')' after condition of 'if'."); 422 condition->set_if_true(ParseBlock().Pass()); 423 if (Match(Token::ELSE)) 424 condition->set_if_false(ParseStatement().Pass()); 425 if (has_error()) 426 return scoped_ptr<ParseNode>(); 427 return condition.PassAs<ParseNode>(); 428 } 429
