4 * This file is part of the Symfony package.
6 * (c) Fabien Potencier <fabien@symfony.com>
8 * For the full copyright and license information, please view the LICENSE
9 * file that was distributed with this source code.
12 namespace Symfony\Component\ExpressionLanguage;
15 * Parsers a token stream.
17 * This parser implements a "Precedence climbing" algorithm.
19 * @see http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
20 * @see http://en.wikipedia.org/wiki/Operator-precedence_parser
22 * @author Fabien Potencier <fabien@symfony.com>
26 const OPERATOR_LEFT = 1;
27 const OPERATOR_RIGHT = 2;
30 private $unaryOperators;
31 private $binaryOperators;
35 public function __construct(array $functions)
37 $this->functions = $functions;
39 $this->unaryOperators = array(
40 'not' => array('precedence' => 50),
41 '!' => array('precedence' => 50),
42 '-' => array('precedence' => 500),
43 '+' => array('precedence' => 500),
45 $this->binaryOperators = array(
46 'or' => array('precedence' => 10, 'associativity' => self::OPERATOR_LEFT),
47 '||' => array('precedence' => 10, 'associativity' => self::OPERATOR_LEFT),
48 'and' => array('precedence' => 15, 'associativity' => self::OPERATOR_LEFT),
49 '&&' => array('precedence' => 15, 'associativity' => self::OPERATOR_LEFT),
50 '|' => array('precedence' => 16, 'associativity' => self::OPERATOR_LEFT),
51 '^' => array('precedence' => 17, 'associativity' => self::OPERATOR_LEFT),
52 '&' => array('precedence' => 18, 'associativity' => self::OPERATOR_LEFT),
53 '==' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
54 '===' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
55 '!=' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
56 '!==' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
57 '<' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
58 '>' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
59 '>=' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
60 '<=' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
61 'not in' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
62 'in' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
63 'matches' => array('precedence' => 20, 'associativity' => self::OPERATOR_LEFT),
64 '..' => array('precedence' => 25, 'associativity' => self::OPERATOR_LEFT),
65 '+' => array('precedence' => 30, 'associativity' => self::OPERATOR_LEFT),
66 '-' => array('precedence' => 30, 'associativity' => self::OPERATOR_LEFT),
67 '~' => array('precedence' => 40, 'associativity' => self::OPERATOR_LEFT),
68 '*' => array('precedence' => 60, 'associativity' => self::OPERATOR_LEFT),
69 '/' => array('precedence' => 60, 'associativity' => self::OPERATOR_LEFT),
70 '%' => array('precedence' => 60, 'associativity' => self::OPERATOR_LEFT),
71 '**' => array('precedence' => 200, 'associativity' => self::OPERATOR_RIGHT),
76 * Converts a token stream to a node tree.
78 * The valid names is an array where the values
79 * are the names that the user can use in an expression.
81 * If the variable name in the compiled PHP code must be
82 * different, define it as the key.
84 * For instance, ['this' => 'container'] means that the
85 * variable 'container' can be used in the expression
86 * but the compiled code will use 'this'.
88 * @param TokenStream $stream A token stream instance
89 * @param array $names An array of valid names
91 * @return Node\Node A node tree
95 public function parse(TokenStream $stream, $names = array())
97 $this->stream = $stream;
98 $this->names = $names;
100 $node = $this->parseExpression();
101 if (!$stream->isEOF()) {
102 throw new SyntaxError(sprintf('Unexpected token "%s" of value "%s"', $stream->current->type, $stream->current->value), $stream->current->cursor, $stream->getExpression());
108 public function parseExpression($precedence = 0)
110 $expr = $this->getPrimary();
111 $token = $this->stream->current;
112 while ($token->test(Token::OPERATOR_TYPE) && isset($this->binaryOperators[$token->value]) && $this->binaryOperators[$token->value]['precedence'] >= $precedence) {
113 $op = $this->binaryOperators[$token->value];
114 $this->stream->next();
116 $expr1 = $this->parseExpression(self::OPERATOR_LEFT === $op['associativity'] ? $op['precedence'] + 1 : $op['precedence']);
117 $expr = new Node\BinaryNode($token->value, $expr, $expr1);
119 $token = $this->stream->current;
122 if (0 === $precedence) {
123 return $this->parseConditionalExpression($expr);
129 protected function getPrimary()
131 $token = $this->stream->current;
133 if ($token->test(Token::OPERATOR_TYPE) && isset($this->unaryOperators[$token->value])) {
134 $operator = $this->unaryOperators[$token->value];
135 $this->stream->next();
136 $expr = $this->parseExpression($operator['precedence']);
138 return $this->parsePostfixExpression(new Node\UnaryNode($token->value, $expr));
141 if ($token->test(Token::PUNCTUATION_TYPE, '(')) {
142 $this->stream->next();
143 $expr = $this->parseExpression();
144 $this->stream->expect(Token::PUNCTUATION_TYPE, ')', 'An opened parenthesis is not properly closed');
146 return $this->parsePostfixExpression($expr);
149 return $this->parsePrimaryExpression();
152 protected function parseConditionalExpression($expr)
154 while ($this->stream->current->test(Token::PUNCTUATION_TYPE, '?')) {
155 $this->stream->next();
156 if (!$this->stream->current->test(Token::PUNCTUATION_TYPE, ':')) {
157 $expr2 = $this->parseExpression();
158 if ($this->stream->current->test(Token::PUNCTUATION_TYPE, ':')) {
159 $this->stream->next();
160 $expr3 = $this->parseExpression();
162 $expr3 = new Node\ConstantNode(null);
165 $this->stream->next();
167 $expr3 = $this->parseExpression();
170 $expr = new Node\ConditionalNode($expr, $expr2, $expr3);
176 public function parsePrimaryExpression()
178 $token = $this->stream->current;
179 switch ($token->type) {
180 case Token::NAME_TYPE:
181 $this->stream->next();
182 switch ($token->value) {
185 return new Node\ConstantNode(true);
189 return new Node\ConstantNode(false);
193 return new Node\ConstantNode(null);
196 if ('(' === $this->stream->current->value) {
197 if (false === isset($this->functions[$token->value])) {
198 throw new SyntaxError(sprintf('The function "%s" does not exist', $token->value), $token->cursor, $this->stream->getExpression());
201 $node = new Node\FunctionNode($token->value, $this->parseArguments());
203 if (!in_array($token->value, $this->names, true)) {
204 throw new SyntaxError(sprintf('Variable "%s" is not valid', $token->value), $token->cursor, $this->stream->getExpression());
207 // is the name used in the compiled code different
208 // from the name used in the expression?
209 if (is_int($name = array_search($token->value, $this->names))) {
210 $name = $token->value;
213 $node = new Node\NameNode($name);
218 case Token::NUMBER_TYPE:
219 case Token::STRING_TYPE:
220 $this->stream->next();
222 return new Node\ConstantNode($token->value);
225 if ($token->test(Token::PUNCTUATION_TYPE, '[')) {
226 $node = $this->parseArrayExpression();
227 } elseif ($token->test(Token::PUNCTUATION_TYPE, '{')) {
228 $node = $this->parseHashExpression();
230 throw new SyntaxError(sprintf('Unexpected token "%s" of value "%s"', $token->type, $token->value), $token->cursor, $this->stream->getExpression());
234 return $this->parsePostfixExpression($node);
237 public function parseArrayExpression()
239 $this->stream->expect(Token::PUNCTUATION_TYPE, '[', 'An array element was expected');
241 $node = new Node\ArrayNode();
243 while (!$this->stream->current->test(Token::PUNCTUATION_TYPE, ']')) {
245 $this->stream->expect(Token::PUNCTUATION_TYPE, ',', 'An array element must be followed by a comma');
248 if ($this->stream->current->test(Token::PUNCTUATION_TYPE, ']')) {
254 $node->addElement($this->parseExpression());
256 $this->stream->expect(Token::PUNCTUATION_TYPE, ']', 'An opened array is not properly closed');
261 public function parseHashExpression()
263 $this->stream->expect(Token::PUNCTUATION_TYPE, '{', 'A hash element was expected');
265 $node = new Node\ArrayNode();
267 while (!$this->stream->current->test(Token::PUNCTUATION_TYPE, '}')) {
269 $this->stream->expect(Token::PUNCTUATION_TYPE, ',', 'A hash value must be followed by a comma');
272 if ($this->stream->current->test(Token::PUNCTUATION_TYPE, '}')) {
278 // a hash key can be:
282 // * a name, which is equivalent to a string -- a
283 // * an expression, which must be enclosed in parentheses -- (1 + 2)
284 if ($this->stream->current->test(Token::STRING_TYPE) || $this->stream->current->test(Token::NAME_TYPE) || $this->stream->current->test(Token::NUMBER_TYPE)) {
285 $key = new Node\ConstantNode($this->stream->current->value);
286 $this->stream->next();
287 } elseif ($this->stream->current->test(Token::PUNCTUATION_TYPE, '(')) {
288 $key = $this->parseExpression();
290 $current = $this->stream->current;
292 throw new SyntaxError(sprintf('A hash key must be a quoted string, a number, a name, or an expression enclosed in parentheses (unexpected token "%s" of value "%s"', $current->type, $current->value), $current->cursor, $this->stream->getExpression());
295 $this->stream->expect(Token::PUNCTUATION_TYPE, ':', 'A hash key must be followed by a colon (:)');
296 $value = $this->parseExpression();
298 $node->addElement($value, $key);
300 $this->stream->expect(Token::PUNCTUATION_TYPE, '}', 'An opened hash is not properly closed');
305 public function parsePostfixExpression($node)
307 $token = $this->stream->current;
308 while ($token->type == Token::PUNCTUATION_TYPE) {
309 if ('.' === $token->value) {
310 $this->stream->next();
311 $token = $this->stream->current;
312 $this->stream->next();
315 $token->type !== Token::NAME_TYPE
317 // Operators like "not" and "matches" are valid method or property names,
319 // In other words, besides NAME_TYPE, OPERATOR_TYPE could also be parsed as a property or method.
320 // This is because operators are processed by the lexer prior to names. So "not" in "foo.not()" or "matches" in "foo.matches" will be recognized as an operator first.
321 // But in fact, "not" and "matches" in such expressions shall be parsed as method or property names.
323 // And this ONLY works if the operator consists of valid characters for a property or method name.
325 // Other types, such as STRING_TYPE and NUMBER_TYPE, can't be parsed as property nor method names.
327 // As a result, if $token is NOT an operator OR $token->value is NOT a valid property or method name, an exception shall be thrown.
328 ($token->type !== Token::OPERATOR_TYPE || !preg_match('/[a-zA-Z_\x7f-\xff][a-zA-Z0-9_\x7f-\xff]*/A', $token->value))
330 throw new SyntaxError('Expected name', $token->cursor, $this->stream->getExpression());
333 $arg = new Node\ConstantNode($token->value);
335 $arguments = new Node\ArgumentsNode();
336 if ($this->stream->current->test(Token::PUNCTUATION_TYPE, '(')) {
337 $type = Node\GetAttrNode::METHOD_CALL;
338 foreach ($this->parseArguments()->nodes as $n) {
339 $arguments->addElement($n);
342 $type = Node\GetAttrNode::PROPERTY_CALL;
345 $node = new Node\GetAttrNode($node, $arg, $arguments, $type);
346 } elseif ('[' === $token->value) {
347 if ($node instanceof Node\GetAttrNode && Node\GetAttrNode::METHOD_CALL === $node->attributes['type'] && PHP_VERSION_ID < 50400) {
348 throw new SyntaxError('Array calls on a method call is only supported on PHP 5.4+', $token->cursor, $this->stream->getExpression());
351 $this->stream->next();
352 $arg = $this->parseExpression();
353 $this->stream->expect(Token::PUNCTUATION_TYPE, ']');
355 $node = new Node\GetAttrNode($node, $arg, new Node\ArgumentsNode(), Node\GetAttrNode::ARRAY_CALL);
360 $token = $this->stream->current;
369 public function parseArguments()
372 $this->stream->expect(Token::PUNCTUATION_TYPE, '(', 'A list of arguments must begin with an opening parenthesis');
373 while (!$this->stream->current->test(Token::PUNCTUATION_TYPE, ')')) {
375 $this->stream->expect(Token::PUNCTUATION_TYPE, ',', 'Arguments must be separated by a comma');
378 $args[] = $this->parseExpression();
380 $this->stream->expect(Token::PUNCTUATION_TYPE, ')', 'A list of arguments must be closed by a parenthesis');
382 return new Node\Node($args);