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