1d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch// Copyright (c) 2013 The Chromium Authors. All rights reserved. 2d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch// Use of this source code is governed by a BSD-style license that can be 3d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch// found in the LICENSE file. 4d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 5d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch#include "tools/gn/parser.h" 6d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 7d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch#include "base/logging.h" 8d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch#include "tools/gn/functions.h" 9d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch#include "tools/gn/operators.h" 10d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch#include "tools/gn/token.h" 11d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 123551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// grammar: 133551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// 143551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// file := (statement)* 153551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// statement := block | if | assignment 163551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// block := '{' statement* '}' 173551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// if := 'if' '(' expr ')' statement [ else ] 183551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// else := 'else' (if | statement)* 193551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// assignment := ident {'=' | '+=' | '-='} expr 203551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 213551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)enum Precedence { 223551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) PRECEDENCE_ASSIGNMENT = 1, 233551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) PRECEDENCE_OR = 2, 243551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) PRECEDENCE_AND = 3, 253551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) PRECEDENCE_EQUALITY = 4, 263551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) PRECEDENCE_RELATION = 5, 273551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) PRECEDENCE_SUM = 6, 283551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) PRECEDENCE_PREFIX = 7, 293551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) PRECEDENCE_CALL = 8, 303551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)}; 313551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 323551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// The top-level for blocks/ifs is still recursive descent, the expression 333551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// parser is a Pratt parser. The basic idea there is to have the precedences 343551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// (and associativities) encoded relative to each other and only parse up 353551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// until you hit something of that precedence. There's a dispatch table in 363551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// expressions_ at the top of parser.cc that describes how each token 373551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// dispatches if it's seen as either a prefix or infix operator, and if it's 383551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// infix, what its precedence is. 393551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// 403551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// Refs: 413551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// - http://javascript.crockford.com/tdop/tdop.html 423551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// - http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ 433551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 443551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// Indexed by Token::Type. 453551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)ParserHelper Parser::expressions_[] = { 463551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, NULL, -1}, // INVALID 473551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {&Parser::Literal, NULL, -1}, // INTEGER 483551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {&Parser::Literal, NULL, -1}, // STRING 493551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {&Parser::Literal, NULL, -1}, // TRUE_TOKEN 503551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {&Parser::Literal, NULL, -1}, // FALSE_TOKEN 513551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, &Parser::Assignment, PRECEDENCE_ASSIGNMENT}, // EQUAL 523551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, &Parser::BinaryOperator, PRECEDENCE_SUM}, // PLUS 533551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, &Parser::BinaryOperator, PRECEDENCE_SUM}, // MINUS 543551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, &Parser::Assignment, PRECEDENCE_ASSIGNMENT}, // PLUS_EQUALS 553551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, &Parser::Assignment, PRECEDENCE_ASSIGNMENT}, // MINUS_EQUALS 563551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, &Parser::BinaryOperator, PRECEDENCE_EQUALITY}, // EQUAL_EQUAL 573551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, &Parser::BinaryOperator, PRECEDENCE_EQUALITY}, // NOT_EQUAL 583551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, &Parser::BinaryOperator, PRECEDENCE_RELATION}, // LESS_EQUAL 593551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, &Parser::BinaryOperator, PRECEDENCE_RELATION}, // GREATER_EQUAL 603551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, &Parser::BinaryOperator, PRECEDENCE_RELATION}, // LESS_THAN 613551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, &Parser::BinaryOperator, PRECEDENCE_RELATION}, // GREATER_THAN 623551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, &Parser::BinaryOperator, PRECEDENCE_AND}, // BOOLEAN_AND 633551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, &Parser::BinaryOperator, PRECEDENCE_OR}, // BOOLEAN_OR 643551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {&Parser::Not, NULL, -1}, // BANG 653551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {&Parser::Group, NULL, -1}, // LEFT_PAREN 663551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, NULL, -1}, // RIGHT_PAREN 673551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {&Parser::List, &Parser::Subscript, PRECEDENCE_CALL}, // LEFT_BRACKET 683551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, NULL, -1}, // RIGHT_BRACKET 693551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, NULL, -1}, // LEFT_BRACE 703551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, NULL, -1}, // RIGHT_BRACE 713551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, NULL, -1}, // IF 723551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, NULL, -1}, // ELSE 733551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {&Parser::Name, &Parser::IdentifierOrCall, PRECEDENCE_CALL}, // IDENTIFIER 743551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, NULL, -1}, // COMMA 753551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) {NULL, NULL, -1}, // COMMENT 763551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)}; 773551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 78d3868032626d59662ff73b372b5d584c1d144c53Ben MurdochParser::Parser(const std::vector<Token>& tokens, Err* err) 793551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) : tokens_(tokens), err_(err), cur_(0) { 80d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch} 81d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 82d3868032626d59662ff73b372b5d584c1d144c53Ben MurdochParser::~Parser() { 83d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch} 84d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 85d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch// static 86d3868032626d59662ff73b372b5d584c1d144c53Ben Murdochscoped_ptr<ParseNode> Parser::Parse(const std::vector<Token>& tokens, 87d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch Err* err) { 88d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch Parser p(tokens, err); 893551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return p.ParseFile().PassAs<ParseNode>(); 90d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch} 91d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 92d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch// static 93d3868032626d59662ff73b372b5d584c1d144c53Ben Murdochscoped_ptr<ParseNode> Parser::ParseExpression(const std::vector<Token>& tokens, 94d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch Err* err) { 95d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch Parser p(tokens, err); 96d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch return p.ParseExpression().Pass(); 97d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch} 98d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 993551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)bool Parser::IsAssignment(const ParseNode* node) const { 1003551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return node && node->AsBinaryOp() && 1013551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) (node->AsBinaryOp()->op().type() == Token::EQUAL || 1023551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) node->AsBinaryOp()->op().type() == Token::PLUS_EQUALS || 1033551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) node->AsBinaryOp()->op().type() == Token::MINUS_EQUALS); 104d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch} 105d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 1063551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)bool Parser::IsStatementBreak(Token::Type token_type) const { 1073551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) switch (token_type) { 1083551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) case Token::IDENTIFIER: 1093551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) case Token::LEFT_BRACE: 1103551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) case Token::RIGHT_BRACE: 1113551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) case Token::IF: 1123551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) case Token::ELSE: 1133551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return true; 1143551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) default: 1153551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return false; 116d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch } 117d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch} 118d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 1193551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)bool Parser::LookAhead(Token::Type type) { 1203551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (at_end()) 1213551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return false; 1223551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return cur_token().type() == type; 1233551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)} 124d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 1253551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)bool Parser::Match(Token::Type type) { 1263551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (!LookAhead(type)) 1273551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return false; 1283551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Consume(); 1293551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return true; 1303551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)} 131d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 1323551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)Token Parser::Consume(Token::Type type, const char* error_message) { 1333551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Token::Type types[1] = { type }; 1343551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return Consume(types, 1, error_message); 135d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch} 136d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 1373551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)Token Parser::Consume(Token::Type* types, 1383551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) size_t num_types, 1393551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) const char* error_message) { 1403551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (has_error()) { 1413551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) // Don't overwrite current error, but make progress through tokens so that 1423551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) // a loop that's expecting a particular token will still terminate. 1433551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) cur_++; 1443551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return Token(Location(), Token::INVALID, base::StringPiece()); 145d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch } 146d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch if (at_end()) { 1473551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) const char kEOFMsg[] = "I hit EOF instead."; 1483551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (tokens_.empty()) 1493551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) *err_ = Err(Location(), error_message, kEOFMsg); 1503551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) else 1513551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) *err_ = Err(tokens_[tokens_.size() - 1], error_message, kEOFMsg); 1523551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return Token(Location(), Token::INVALID, base::StringPiece()); 153d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch } 154d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 1553551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) for (size_t i = 0; i < num_types; ++i) { 1563551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (cur_token().type() == types[i]) 1573551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return tokens_[cur_++]; 158d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch } 1593551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) *err_ = Err(cur_token(), error_message); 1603551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return Token(Location(), Token::INVALID, base::StringPiece()); 1613551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)} 162d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 1633551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)Token Parser::Consume() { 1643551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return tokens_[cur_++]; 165d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch} 166d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 167d3868032626d59662ff73b372b5d584c1d144c53Ben Murdochscoped_ptr<ParseNode> Parser::ParseExpression() { 1683551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return ParseExpression(0); 1693551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)} 170d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 1713551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)scoped_ptr<ParseNode> Parser::ParseExpression(int precedence) { 172d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch if (at_end()) 1733551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<ParseNode>(); 174d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 1753551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Token token = Consume(); 1763551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) PrefixFunc prefix = expressions_[token.type()].prefix; 177d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 1783551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (prefix == NULL) { 1793551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) *err_ = Err(token, 1803551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) std::string("Unexpected token '") + token.value().as_string() + 1813551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) std::string("'")); 1823551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<ParseNode>(); 1833551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 1843551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1853551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<ParseNode> left = (this->*prefix)(token); 18658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) if (has_error()) 18758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) return left.Pass(); 1883551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1893551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) while (!at_end() && !IsStatementBreak(cur_token().type()) && 1903551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) precedence <= expressions_[cur_token().type()].precedence) { 1913551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) token = Consume(); 1923551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) InfixFunc infix = expressions_[token.type()].infix; 1933551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (infix == NULL) { 1943551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) *err_ = Err(token, 1953551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) std::string("Unexpected token '") + 1963551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) token.value().as_string() + std::string("'")); 197d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch return scoped_ptr<ParseNode>(); 198d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch } 1993551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) left = (this->*infix)(left.Pass(), token); 200d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch if (has_error()) 201d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch return scoped_ptr<ParseNode>(); 202d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch } 203d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 2043551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return left.Pass(); 205d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch} 206d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 2073551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)scoped_ptr<ParseNode> Parser::Literal(Token token) { 2083551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<ParseNode>(new LiteralNode(token)).Pass(); 2093551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)} 210d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 2113551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)scoped_ptr<ParseNode> Parser::Name(Token token) { 2123551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return IdentifierOrCall(scoped_ptr<ParseNode>(), token).Pass(); 2133551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)} 214d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 2153551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)scoped_ptr<ParseNode> Parser::Group(Token token) { 2163551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<ParseNode> expr = ParseExpression(); 2173551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (has_error()) 2183551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<ParseNode>(); 2193551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Consume(Token::RIGHT_PAREN, "Expected ')'"); 2203551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return expr.Pass(); 2213551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)} 222d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 2233551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)scoped_ptr<ParseNode> Parser::Not(Token token) { 2243551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<ParseNode> expr = ParseExpression(PRECEDENCE_PREFIX + 1); 2253551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (has_error()) 2263551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<ParseNode>(); 2273551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<UnaryOpNode> unary_op(new UnaryOpNode); 2283551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) unary_op->set_op(token); 2293551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) unary_op->set_operand(expr.Pass()); 2303551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return unary_op.PassAs<ParseNode>(); 2313551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)} 232d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 2333551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)scoped_ptr<ParseNode> Parser::List(Token node) { 2343551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<ParseNode> list(ParseList(Token::RIGHT_BRACKET, true)); 2353551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (!has_error() && !at_end()) 2363551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Consume(Token::RIGHT_BRACKET, "Expected ']'"); 2373551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return list.Pass(); 2383551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)} 239d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 2403551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)scoped_ptr<ParseNode> Parser::BinaryOperator(scoped_ptr<ParseNode> left, 2413551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Token token) { 2423551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<ParseNode> right = 2433551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) ParseExpression(expressions_[token.type()].precedence + 1); 2443551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (!right) { 2453551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) *err_ = 2463551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Err(token, 2473551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) "Expected right hand side for '" + token.value().as_string() + "'"); 2483551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<ParseNode>(); 249d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch } 2503551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<BinaryOpNode> binary_op(new BinaryOpNode); 2513551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) binary_op->set_op(token); 2523551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) binary_op->set_left(left.Pass()); 2533551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) binary_op->set_right(right.Pass()); 2543551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return binary_op.PassAs<ParseNode>(); 2553551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)} 256d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 2573551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)scoped_ptr<ParseNode> Parser::IdentifierOrCall(scoped_ptr<ParseNode> left, 2583551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Token token) { 2593551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<ListNode> list(new ListNode); 2603551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) list->set_begin_token(token); 2613551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) list->set_end_token(token); 2623551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<BlockNode> block; 2633551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) bool has_arg = false; 2643551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (Match(Token::LEFT_PAREN)) { 2653551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) // Parsing a function call. 2663551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) has_arg = true; 2673551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (Match(Token::RIGHT_PAREN)) { 2683551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) // Nothing, just an empty call. 2693551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } else { 2703551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) list = ParseList(Token::RIGHT_PAREN, false); 2713551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (has_error()) 2723551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<ParseNode>(); 2733551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Consume(Token::RIGHT_PAREN, "Expected ')' after call"); 2743551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 2753551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) // Optionally with a scope. 2763551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (LookAhead(Token::LEFT_BRACE)) { 2773551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) block = ParseBlock(); 2783551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (has_error()) 2793551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<ParseNode>(); 2803551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 281d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch } 282d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 2833551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (!left && !has_arg) { 2843551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) // Not a function call, just a standalone identifier. 2853551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<ParseNode>(new IdentifierNode(token)).Pass(); 286d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch } 2873551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<FunctionCallNode> func_call(new FunctionCallNode); 2883551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) func_call->set_function(token); 2893551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) func_call->set_args(list.Pass()); 2903551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (block) 2913551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) func_call->set_block(block.Pass()); 2923551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return func_call.PassAs<ParseNode>(); 293d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch} 294d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 2953551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)scoped_ptr<ParseNode> Parser::Assignment(scoped_ptr<ParseNode> left, 2963551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Token token) { 2973551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (left->AsIdentifier() == NULL) { 2983551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) *err_ = Err(left.get(), "Left-hand side of assignment must be identifier."); 2993551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<ParseNode>(); 300d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch } 3013551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<ParseNode> value = ParseExpression(PRECEDENCE_ASSIGNMENT); 3023551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<BinaryOpNode> assign(new BinaryOpNode); 3033551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) assign->set_op(token); 3043551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) assign->set_left(left.Pass()); 3053551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) assign->set_right(value.Pass()); 3063551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return assign.PassAs<ParseNode>(); 3073551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)} 308d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 3093551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)scoped_ptr<ParseNode> Parser::Subscript(scoped_ptr<ParseNode> left, 3103551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Token token) { 3113551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) // TODO: Maybe support more complex expressions like a[0][0]. This would 3123551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) // require work on the evaluator too. 3133551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (left->AsIdentifier() == NULL) { 3143551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) *err_ = Err(left.get(), "May only subscript simple identifiers"); 3153551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<ParseNode>(); 316d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch } 3173551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<ParseNode> value = ParseExpression(); 3183551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Consume(Token::RIGHT_BRACKET, "Expecting ']' after subscript."); 3193551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<AccessorNode> accessor(new AccessorNode); 3203551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) accessor->set_base(left->AsIdentifier()->value()); 3213551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) accessor->set_index(value.Pass()); 3223551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return accessor.PassAs<ParseNode>(); 323d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch} 324d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 3253551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)// Does not Consume the start or end token. 3263551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)scoped_ptr<ListNode> Parser::ParseList(Token::Type stop_before, 3273551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) bool allow_trailing_comma) { 328d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch scoped_ptr<ListNode> list(new ListNode); 3293551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) list->set_begin_token(cur_token()); 3303551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) bool just_got_comma = false; 3313551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) while (!LookAhead(stop_before)) { 3323551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) just_got_comma = false; 3333551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) // Why _OR? We're parsing things that are higher precedence than the , 3343551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) // that separates the items of the list. , should appear lower than 3353551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) // boolean expressions (the lowest of which is OR), but above assignments. 3363551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) list->append_item(ParseExpression(PRECEDENCE_OR)); 337d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch if (has_error()) 338d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch return scoped_ptr<ListNode>(); 3393551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (at_end()) { 3403551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) *err_ = 3413551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Err(tokens_[tokens_.size() - 1], "Unexpected end of file in list."); 3423551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<ListNode>(); 343d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch } 3443551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) just_got_comma = Match(Token::COMMA); 3453551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 3463551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (just_got_comma && !allow_trailing_comma) { 3473551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) *err_ = Err(cur_token(), "Trailing comma"); 3483551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<ListNode>(); 349d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch } 3503551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) list->set_end_token(cur_token()); 351d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch return list.Pass(); 352d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch} 353d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 3543551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)scoped_ptr<ParseNode> Parser::ParseFile() { 3553551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<BlockNode> file(new BlockNode(false)); 3563551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) for (;;) { 3573551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (at_end()) 3583551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) break; 3593551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<ParseNode> statement = ParseStatement(); 3603551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (!statement) 3613551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) break; 3623551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) file->append_statement(statement.Pass()); 3633551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 3643551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (!at_end() && !has_error()) 3653551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) *err_ = Err(cur_token(), "Unexpected here, should be newline."); 366d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch if (has_error()) 367d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch return scoped_ptr<ParseNode>(); 3683551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return file.PassAs<ParseNode>(); 3693551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)} 370d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 3713551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)scoped_ptr<ParseNode> Parser::ParseStatement() { 3723551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (LookAhead(Token::LEFT_BRACE)) { 3733551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return ParseBlock().PassAs<ParseNode>(); 3743551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } else if (LookAhead(Token::IF)) { 3753551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return ParseCondition(); 3763551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } else { 3773551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) // TODO(scottmg): Is this too strict? Just drop all the testing if we want 3783551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) // to allow "pointless" expressions and return ParseExpression() directly. 3793551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<ParseNode> stmt = ParseExpression(); 3803551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (stmt) { 3813551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (stmt->AsFunctionCall() || IsAssignment(stmt.get())) 3823551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return stmt.Pass(); 3833551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 3843551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (!has_error()) { 3853551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Token token = at_end() ? tokens_[tokens_.size() - 1] : cur_token(); 3863551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) *err_ = Err(token, "Expecting assignment or function call."); 3873551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 388d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch return scoped_ptr<ParseNode>(); 389d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch } 390d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch} 391d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 3923551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)scoped_ptr<BlockNode> Parser::ParseBlock() { 3933551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Token begin_token = 3943551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Consume(Token::LEFT_BRACE, "Expected '{' to start a block."); 3953551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (has_error()) 3963551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<BlockNode>(); 3973551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<BlockNode> block(new BlockNode(true)); 3983551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) block->set_begin_token(begin_token); 399d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 4003551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) for (;;) { 4013551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (LookAhead(Token::RIGHT_BRACE)) { 4023551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) block->set_end_token(Consume()); 4033551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) break; 4043551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 405d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 4063551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<ParseNode> statement = ParseStatement(); 4073551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (!statement) 4083551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<BlockNode>(); 4093551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) block->append_statement(statement.Pass()); 410d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch } 4113551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return block.Pass(); 412d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch} 413d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 4143551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)scoped_ptr<ParseNode> Parser::ParseCondition() { 4153551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) scoped_ptr<ConditionNode> condition(new ConditionNode); 4163551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Consume(Token::IF, "Expected 'if'"); 4173551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Consume(Token::LEFT_PAREN, "Expected '(' after 'if'."); 4183551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) condition->set_condition(ParseExpression()); 4193551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (IsAssignment(condition->condition())) 4203551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) *err_ = Err(condition->condition(), "Assignment not allowed in 'if'."); 4213551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Consume(Token::RIGHT_PAREN, "Expected ')' after condition of 'if'."); 4223551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) condition->set_if_true(ParseBlock().Pass()); 4233551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (Match(Token::ELSE)) 4243551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) condition->set_if_false(ParseStatement().Pass()); 4253551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) if (has_error()) 4263551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return scoped_ptr<ParseNode>(); 4273551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return condition.PassAs<ParseNode>(); 428d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch} 429