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 #ifndef TOOLS_GN_PARSER_H_ 6 #define TOOLS_GN_PARSER_H_ 7 8 #include <stddef.h> 9 10 #include <map> 11 #include <memory> 12 #include <vector> 13 14 #include "base/gtest_prod_util.h" 15 #include "base/macros.h" 16 #include "gn/err.h" 17 #include "gn/parse_tree.h" 18 19 extern const char kGrammar_Help[]; 20 21 struct ParserHelper; 22 23 // Parses a series of tokens. The resulting AST will refer to the tokens passed 24 // to the input, so the tokens an the file data they refer to must outlive your 25 // use of the ParseNode. 26 class Parser { 27 public: 28 // Will return a null pointer and set the err on error. 29 static std::unique_ptr<ParseNode> Parse(const std::vector<Token>& tokens, 30 Err* err); 31 32 // Alternative to parsing that assumes the input is an expression. 33 static std::unique_ptr<ParseNode> ParseExpression( 34 const std::vector<Token>& tokens, 35 Err* err); 36 37 // Alternative to parsing that assumes the input is a literal value. 38 static std::unique_ptr<ParseNode> ParseValue(const std::vector<Token>& tokens, 39 Err* err); 40 41 private: 42 // Vector must be valid for lifetime of call. 43 Parser(const std::vector<Token>& tokens, Err* err); 44 ~Parser(); 45 46 std::unique_ptr<ParseNode> ParseExpression(); 47 48 // Parses an expression with the given precedence or higher. 49 std::unique_ptr<ParseNode> ParseExpression(int precedence); 50 51 // |PrefixFunc|s used in parsing expressions. 52 std::unique_ptr<ParseNode> Block(const Token& token); 53 std::unique_ptr<ParseNode> Literal(const Token& token); 54 std::unique_ptr<ParseNode> Name(const Token& token); 55 std::unique_ptr<ParseNode> Group(const Token& token); 56 std::unique_ptr<ParseNode> Not(const Token& token); 57 std::unique_ptr<ParseNode> List(const Token& token); 58 std::unique_ptr<ParseNode> BlockComment(const Token& token); 59 60 // |InfixFunc|s used in parsing expressions. 61 std::unique_ptr<ParseNode> BinaryOperator(std::unique_ptr<ParseNode> left, 62 const Token& token); 63 std::unique_ptr<ParseNode> IdentifierOrCall(std::unique_ptr<ParseNode> left, 64 const Token& token); 65 std::unique_ptr<ParseNode> Assignment(std::unique_ptr<ParseNode> left, 66 const Token& token); 67 std::unique_ptr<ParseNode> Subscript(std::unique_ptr<ParseNode> left, 68 const Token& token); 69 std::unique_ptr<ParseNode> DotOperator(std::unique_ptr<ParseNode> left, 70 const Token& token); 71 72 // Helper to parse a comma separated list, optionally allowing trailing 73 // commas (allowed in [] lists, not in function calls). 74 std::unique_ptr<ListNode> ParseList(const Token& start_token, 75 Token::Type stop_before, 76 bool allow_trailing_comma); 77 78 std::unique_ptr<ParseNode> ParseFile(); 79 std::unique_ptr<ParseNode> ParseStatement(); 80 // Expects to be passed the token corresponding to the '{' and that the 81 // current token is the one following the '{'. 82 std::unique_ptr<BlockNode> ParseBlock(const Token& begin_brace, 83 BlockNode::ResultMode result_mode); 84 std::unique_ptr<ParseNode> ParseCondition(); 85 86 // Generates a pre- and post-order traversal of the tree. 87 void TraverseOrder(const ParseNode* root, 88 std::vector<const ParseNode*>* pre, 89 std::vector<const ParseNode*>* post); 90 91 // Attach comments to nearby syntax. 92 void AssignComments(ParseNode* file); 93 94 bool IsAssignment(const ParseNode* node) const; 95 bool IsStatementBreak(Token::Type token_type) const; 96 97 bool LookAhead(Token::Type type); 98 bool Match(Token::Type type); 99 const Token& Consume(Token::Type type, const char* error_message); 100 const Token& Consume(Token::Type* types, 101 size_t num_types, 102 const char* error_message); 103 const Token& Consume(); 104 105 // Call this only if !at_end(). cur_token()106 const Token& cur_token() const { return tokens_[cur_]; } 107 cur_or_last_token()108 const Token& cur_or_last_token() const { 109 return at_end() ? tokens_[tokens_.size() - 1] : cur_token(); 110 } 111 done()112 bool done() const { return at_end() || has_error(); } at_end()113 bool at_end() const { return cur_ >= tokens_.size(); } has_error()114 bool has_error() const { return err_->has_error(); } 115 116 std::vector<Token> tokens_; 117 std::vector<Token> line_comment_tokens_; 118 std::vector<Token> suffix_comment_tokens_; 119 120 static ParserHelper expressions_[Token::NUM_TYPES]; 121 122 Token invalid_token_; 123 Err* err_; 124 125 // Current index into the tokens. 126 size_t cur_; 127 128 FRIEND_TEST_ALL_PREFIXES(Parser, BinaryOp); 129 FRIEND_TEST_ALL_PREFIXES(Parser, Block); 130 FRIEND_TEST_ALL_PREFIXES(Parser, Condition); 131 FRIEND_TEST_ALL_PREFIXES(Parser, Expression); 132 FRIEND_TEST_ALL_PREFIXES(Parser, FunctionCall); 133 FRIEND_TEST_ALL_PREFIXES(Parser, List); 134 FRIEND_TEST_ALL_PREFIXES(Parser, ParenExpression); 135 FRIEND_TEST_ALL_PREFIXES(Parser, UnaryOp); 136 137 DISALLOW_COPY_AND_ASSIGN(Parser); 138 }; 139 140 using PrefixFunc = std::unique_ptr<ParseNode> (Parser::*)(const Token& token); 141 using InfixFunc = std::unique_ptr<ParseNode> ( 142 Parser::*)(std::unique_ptr<ParseNode> left, const Token& token); 143 144 struct ParserHelper { 145 PrefixFunc prefix; 146 InfixFunc infix; 147 148 // Used only for infix operators. 149 int precedence; 150 }; 151 152 // Renders parse subtree as a formatted text, indenting by the given number of 153 // spaces. 154 void RenderToText(const base::Value& node, 155 int indent_level, 156 std::ostringstream& os); 157 158 #endif // TOOLS_GN_PARSER_H_ 159