Library to transform a Doctrine lexer into a RPN expression and solve it
- What is Shunting Yard algorithm
- The Shunting Yard implementation
- The RPN expression Solver
- The AST Tree builder
- Similar projects
The main goal of this library is to transform an expression into a computer understandable expression, by using
- Doctrine Lexer
- The Shunting Yard algorithm
As the input of the Shunting Yard is a Doctrine Lexer, the library is not limited to mathematics expression.
The library provide an "evaluator" of the Shunting Yard algorithm output, or transform it into a AST Tree
But to make simple, the main idea is to transform a list of chars into multiple of small group.
(1 + 2) * 3 is really simple for us (human) to process, but a computer can do it, it need to split it into small chunk. And evaluate it piece by piece.
For a computer, the expression need to be evaluate like this:
* / \ + 3 / \ 1 2
This a binary tree, and yes it's also a kind of AST. So to solve the expression a computer first evaluate the group (we will name the result as (a)):
+ / \ 1 2
And then it evaluate the group:
* / \ (a) 3
The Shunting Yard algorithm transform your expression into an intermediate expression: a RPN expression.
The RPN expression of
(1 + 2) * 3 is
1 2 + 3 *.
This expression can be read as:
+(that take 2 parameters: the two previous parameters)
*(that take 2 parameters: the result of the operation and the previous parameter)
Like most of Shunting Yard implementation, it can parse "simple" expression (with simple operator) and make parenthesis reduction.
It can parse unary, and binary functions (like
max(x,y)) but also any functions (ex:
But the main "feature" it's the use of Doctrine Lexer.
The RPN solver allow you to solve a RPN expression (a list of Doctrine Lexer token). It support Operator/Function with any arity.
The AST Tree builder can transform the RPN expression (a list of Doctrine Lexer token) into an AST Tree.
The tree root is a node, the last(final) node (in the What is Shunting Yard algorithm, it's the
This root node is composed of values (leafs of a tree) and nodes (branches).
The Solver can not solver function with variable arity (or optional parameters)
To install with composer:
composer require macfja/lexer-expression
use \Doctrine\ORM\Query\Lexer; $dql = 'SELECT u FROM User u WHERE u.id = MAX(5, 7)'; $lexer = new Lexer($dql); $sy = new ShuntingYard(); $sy->setLexer($lexer); $sy->setOpenParenthesis(Lexer::T_OPEN_PARENTHESIS); $sy->setCloseParenthesis(Lexer::T_CLOSE_PARENTHESIS); $sy->setOperators(array( new ShuntingYardOperator(Lexer::T_MAX, 10, ShuntingYardOperator::ASSOCIATIVITY_LEFT), new ShuntingYardOperator(Lexer::T_SELECT, 10, ShuntingYardOperator::ASSOCIATIVITY_LEFT), new ShuntingYardOperator(Lexer::T_FROM, 10, ShuntingYardOperator::ASSOCIATIVITY_LEFT), new ShuntingYardOperator(Lexer::T_WHERE, 2, ShuntingYardOperator::ASSOCIATIVITY_LEFT), new ShuntingYardOperator(Lexer::T_DOT, 10, ShuntingYardOperator::ASSOCIATIVITY_LEFT), new ShuntingYardOperator(Lexer::T_EQUALS, 10, ShuntingYardOperator::ASSOCIATIVITY_LEFT) )); $sy->setArgumentSeparator(Lexer::T_COMMA); var_dump($sy->parse());
3 examples are available in the
test directory. The expression is
(1 + 2) / ((3 + 4 * 5) - 6).
test/MathRPN.php: Just an expression to RPN example
test/MathSolve.php: An example with the solver
test/MathAST.php: An example with the tree builder
The tree of the expression is:
"/" / \ / \ / "-" / / \ / "+" 6 / / \ "+" 3 "*" / \ / \ 1 2 4 5