Pull to refresh

Внедряем формулы как в Эксель

Level of difficultyMedium
Reading time11 min
Views9K

Пользователи постоянно меняют логику подсчёта? Они не довольны скоростью, с которой ты меняешь код? Тебя самого достало, так часто менять одно и тоже? Если да, то вот тебе решение: пускай пользователи сами пишут формулы на языке, который им более знаком: это формулы эксель. Тебе лишь надо научить своё приложение считать это. Как это сделать? С помощью чёрной магии конечно!

И так, предположим, мы хотим использовать у себя следующую формулу:

=ЕСЛИ(A1>A2; "Больше"; "Меньше")

Но у нас же может не быть ячеек A1 и A2, но может быть и да, что угодно может. Поэтому давай честно скажем: A1 и A2 - это переменные, и наша система должна обрабатывать формулу следующего типа:

=ЕСЛИ(Переменная_1>Переменная_2; "Больше"; "Меньше")

Всё, с синтаксисом определились. Функции у нас могут быть любые, желательно как в эксель. Что ещё ? Числа , строки и операторы и вроде всё! Пора заняться чёрной магией ! (если что, весь код есть на github )

И так нам нужны следующие заклинания:

1) Lexer

2) Абстрактное синтаксическое дерево. Далее по тексту AST.

3) Parser

Lexer.

Его задача просто пройтись по тексту и сказать, что вот тут функция , тут строка , оператор и т.д. Такие разметки называют токенами.

Lexer
class Lexer
{
    private int $position = 0;

    private int $column = 0;

    private int $row = 0;

    /** @var Token[] */
    private array $tokens = [];

    /** @var string[] */
    protected array $conditionalOperators = ['=', '<', '>'];

    /** @var string[] */
    protected array $operators = ['*', '/', '+', '-', '^'];

    /** @var string[] */
    protected array $spatialSymbol = ['\\', '$'];

    private string $text;

    public function __construct()
    {
    }

    /**
     * @param string $code
     *
     * @throws SyntaxError
     */
    public function setCode(string $code): void
    {
        $this->text = $code;
        $this->tokens = $this->parse();
        $this->position = 0;
        $this->column = 0;
        $this->row = 0;
    }

    /**
     * @return Token[]
     */
    public function getAllTokens(): array
    {
        return $this->tokens;
    }

    /**
     * @return Token[]
     */
    private function parse(): array
    {
        $result = [];
        $this->position = 0;

        while (!$this->isEnd()) {
            $value = $this->readNext();

            if ($value !== null) {
                $result[] = $value;
            }
        }

        return $result;
    }

    private function readNext(): ?Token
    {
        while (!$this->isEnd()) {
            if ($this->isEscaped()) {
                return $this->readString();
            }

            if ($this->isNumber()) {
                return $this->readNumber();
            }

            if ($this->isConditionalOperator()) {
                return $this->readConditionalOperator();
            }

            if ($this->isOperator()) {
                return $this->readOperator();
            }

            if ($this->isSpatialSymbol()) {
                return $this->readSpatialVariable();
            }

            if ($this->isVariable()) {
                return $this->readVariable();
            }
            $currentSymbol = $this->getCurrentSymbol();

            if ($currentSymbol === ';') {
                $result = $this->getToken(TokenType::Separator, $currentSymbol, $this->column);
                $this->nextSymbol();

                return $result;
            }

            if ($currentSymbol === '(' || $currentSymbol === ')') {
                $result = $this->getToken(TokenType::Parentheses, $currentSymbol, $this->column);
                $this->nextSymbol();

                return $result;
            }

            if ($currentSymbol !== ' ' && $currentSymbol !== '' && !$this->isNewLine()) {
                $symbol = $currentSymbol;
                throw new SyntaxError(
                    "Неизвестный символ: {$symbol}",
                    new Token(TokenType::Unknown, $currentSymbol, $this->row, $this->column)
                );
            }

            $this->nextSymbol();
        }

        return null;
    }

    private function getToken(
        TokenType $type,
        mixed $value,
        int $column,
    ): Token {
        return new Token($type, $value, $this->row, $column);
    }

    private function getCurrentSymbol(): string
    {
        return mb_substr($this->text, $this->position, 1);
    }

    private function nextSymbol(): void
    {
        $this->position++;

        if ($this->isNewLine()) {
            $this->position++;
            $this->column = 0;
            $this->row++;
        } else {
            $this->column++;
        }
    }

    private function isNewLine(): bool
    {
        $currentSymbol = $this->getCurrentSymbol();

        if ($currentSymbol == "\n\r" || $currentSymbol == "\n" || $currentSymbol == "\r") {
            return true;
        }

        return false;
    }

    private function isNumber(): bool
    {
        if (preg_match('/[0-9]/i', $this->getCurrentSymbol())) {
            return true;
        }

        return false;
    }

    private function isVariable(): bool
    {
        if (preg_match('/[a-zа-я._]/i', $this->getCurrentSymbol())) {
            return true;
        }

        return false;
    }

    private function isConditionalOperator(): bool
    {
        if (array_search($this->getCurrentSymbol(), $this->conditionalOperators) !== false) {
            return true;
        }

        return false;
    }

    private function isOperator(): bool
    {
        if (array_search($this->getCurrentSymbol(), $this->operators) !== false) {
            return true;
        }

        return false;
    }

    private function isSpatialSymbol(): bool
    {
        if (array_search($this->getCurrentSymbol(), $this->spatialSymbol) !== false) {
            return true;
        }

        return false;
    }

    private function isEscaped(): bool
    {
        $currentSymbol = $this->getCurrentSymbol();

        if ($currentSymbol === '"') {
            return true;
        }

        if ($currentSymbol === "'") {
            return true;
        }

        return false;
    }

    private function isEnd(): bool
    {
        return $this->position >= \strlen($this->text);
    }

    private function readString(): Token
    {
        $startColumn = $this->column;
        $startRow = $this->row;

        if ($this->isEscaped()) {
            $this->nextSymbol();
        }
        $result = '';

        while (!$this->isEscaped() && !$this->isEnd()) {
            $result .= $this->getCurrentSymbol();
            $this->nextSymbol();
        }
        $this->nextSymbol();

        return new Token(TokenType::String, $result, $startRow, $startColumn);
    }

    private function readNumber(): Token
    {
        $hasDot = false;
        $result = '';
        $startColumn = $this->column;
        $startRow = $this->row;

        while ($this->isNumber() && !$this->isEnd()) {
            $result .= $this->getCurrentSymbol();
            $this->nextSymbol();
            $next = $this->getCurrentSymbol();

            if ($next === '.' || $next === ',') {
                $hasDot = true;
                $result .= $next;
                $this->nextSymbol();
            }
        }

        if ($hasDot) {
            return new Token(TokenType::Float, (float)$result, $startRow, $startColumn);
        }

        return new Token(TokenType::Int, (int)$result, $startRow, $startColumn);
    }

    private function readConditionalOperator(): Token
    {
        $result = '';
        $startColumn = $this->column;
        $startRow = $this->row;

        while ($this->isConditionalOperator() && !$this->isEnd()) {
            $result .= $this->getCurrentSymbol();
            $this->nextSymbol();
        }

        return new Token(TokenType::ConditionalOperator, $result, $startRow, $startColumn);
    }

    private function readOperator(): Token
    {
        $result = '';
        $startColumn = $this->column;
        $startRow = $this->row;

        while ($this->isOperator() && !$this->isEnd()) {
            $result .= $this->getCurrentSymbol();
            $this->nextSymbol();
        }

        return new Token(TokenType::BinaryOperator, $result, $startRow, $startColumn);
    }

    private function readSpatialVariable(): Token
    {
        $startColumn = $this->column;
        $startRow = $this->row;

        if ($this->isSpatialSymbol()) {
            $this->nextSymbol();
        }
        $result = '';

        while (!$this->isSpatialSymbol() && !$this->isEnd()) {
            $result .= $this->getCurrentSymbol();
            $this->nextSymbol();
        }
        $this->nextSymbol();

        return new Token(TokenType::Variable, $result, $startRow, $startColumn);
    }

    private function readVariable(): Token
    {
        $result = '';
        $isFunction = false;
        $startColumnt = $this->column;
        $startRow = $this->row;

        while (!$this->isEnd()) {
            $currentSymbol = $this->getCurrentSymbol();

            if ($currentSymbol === '(') {
                $isFunction = true;
                $this->nextSymbol();
                break;
            }

            if (!$this->isVariable() && !$this->isNumber()) {
                break;
            }

            $result .= $currentSymbol;
            $this->nextSymbol();
        }

        if ($isFunction) {
            return new Token(TokenType::Function, strtoupper($result), $startRow, $startColumnt);
        }

        return new Token(TokenType::Variable, $result, $startRow, $startColumnt);
    }
}

Token
class Token 
{
    public function __construct(
        public TokenType $type,
        public mixed $value,
        public int $row = 0,
        public int $column = 0,
    ) {
    }
   
}

TokenType
enum TokenType: string
{
    case String = 'string';

    case Int = 'int';

    case Float = 'float';

    case Function = 'function';

    case ConditionalOperator = 'conditionalOperator';

    case BinaryOperator = 'operator';

    case Variable = 'variable';

    case Parentheses = 'parentheses';

    case Separator = 'separator';

    case Unknown = 'unknown';    
}

AST

И так, давай посмотри ещё раз на нашу формулу:

=ЕСЛИ(Переменная_1>Переменная_2; "Больше"; "Меньше")

По сути, это выражение, состоящее из других выражений. В нашем случае, выражение "ЕСЛИ" имеет следующую структуру:

ЕСЛИ(Выражение; Выражение;  Выражение)

AST - когда мы каждое такое выражение представляем в виде класса. И так, давай сначала опишем интерфейс нашего выражения:

interface Expression
{   
    /**
     * /**
     * Подсчитывает  и возвращает значение.
     *
     * @param ValueRepositoryInterface $repository
     *
     * @return mixed
     */
    public function calculate(?ValueRepositoryInterface $repository = null): mixed;
  
}

Как видим, в нём есть функция: calculate, которая должна вернуть посчитанное значение. Она принимает класс репозиторий для поиска значений переменных.

interface ValueRepositoryInterface
{
    /**
     * Возвращает значение по идентификатору переменной;.
     *
     * @param string $identificator
     *
     * @return mixed
     */
    public function getValueByIdentifier(string $identificator): mixed;
}

Зачем так? Чтобы получать значения только тех переменных, которые нужны, так получается производительней и удобней.

Теперь можно описать каждое наше выражение:

Строка
class StringExpression implements Expression
{
    public function __construct(protected Token $token)
    {
    }
    public function calculate(?ValueRepositoryInterface $repository = null): mixed
    {
        return (string)$this->token->value;
    }   
}

Переменная
class VariableExpression implements Expression
{
    public function __construct(private string $identifier, protected Token $token)
    {
    }

    public function calculate(?ValueRepositoryInterface $repository = null): mixed
    {
        if ($repository === null) {
            throw new UnsupportedError('Не указан репозиторий для получения значения для переменной');
        }

        return $repository->getValueByIdentifier($this->identifier);
    }
   
}

Функция ЕСЛИ
class Funif implements Expression
{
   public function __construct(
        protected Token $token,
        protected array $args,
    ) {
    }
   public function calculate(?ValueRepositoryInterface $repository = null): mixed
    {
        $condition = $this->args[0]->calculate($repository);

        if ($condition) {
            return $this->args[1]->calculate($repository);
        }

        return $this->args[2]->calculate($repository);
    }
}

Код оператора ">"
class Operator implements Expression
{
   public function __construct(
        protected Token $token,
        protected Expression $leftExpression,
        protected Expression $rightExpression,
    ) {
    }
    public function calculate(?ValueRepositoryInterface $repository = null): mixed
    {
       return $left > $riht;
    }
}

Думаю, дополнить своими вам уже не составит труда.

Parser

Осталось дело за малым, преобразовать наши токены в AST. Этим и займется наш parser.

Код Parser
class Parser 
{
    // приоритет операторов
    public const BINOP_PRECEDENCE = [
        '-' => 20,
        '+' => 20,
        '*' => 40,
        '/' => 40,
        '^' => 80,
        '=' => 20,
        '<' => 20,
        '>' => 20,
    ];

    /** @var Token[] */
    private $tokens = [];
    private int $currentPosition = 0;

    public function __construct(
        private Lexer $lexer = new Lexer(),
        private VariableRepositoryInterface $repository = new EmptyVariableRepository(),
        private FunctionBuilder $functionBuilder = new FunctionBuilder(),
    ) {
    }

    /**
     * @param string $code
     *
     * @return FormulaAST
     */
    public function parse(string $code): ?Expression
    {
        $this->lexer->setCode($code);
        $this->tokens = $this->lexer->getAllTokens();
        return $this->parseExpression();      
    }

    private function nextToken(): void
    {
        $this->currentPosition++;
    }

    /**
     * получить приоритет текущего оператора.
     */
    private function getTokPrecedence(Token $operatorToken): int
    {
        $operator = (string)$operatorToken->value;

        if (!\array_key_exists($operator, self::BINOP_PRECEDENCE)) {
            return -1;
        }

        return self::BINOP_PRECEDENCE[$operator];
    }

    private function isEnd(): bool
    {
        if ($this->currentPosition >= \count($this->tokens)) {
            return true;
        }

        return false;
    }

    private function getCurrentToken(): ?Token
    {
        if ($this->currentPosition >= \count($this->tokens)) {
            return null;
        }

        return $this->tokens[$this->currentPosition];
    }

    /**
     * Распарсить текущий токен.
     */
    private function parsePrimary(): ?Expression
    {
        $token = $this->getCurrentToken();

        if (!$token) {
            return null;
        }

        switch ($token->type) {
            case TokenType::String:
                return $this->parseStringExpr($token);
          
            case TokenType::Function:
                return $this->parseFuntion($token);

            case TokenType::Variable:
                return $this->parseVariableExpr($token);

            case TokenType::Parentheses:
                if ($token->value === '(') {
                    return $this->parseParenthesesExpr();
                }
                break;
        }

        $this->logError('Не ожидаенный тип токена: ' . $token->value, $token);

        return null;
    }

    private function parseStringExpr(Token $currentToken): StringExpression
    {
        $this->nextToken();

        return new StringExpression($currentToken);
    }    
 

    private function parseVariableExpr(Token $currentToken): VariableExpression
    {
        $identifier = $this->repository->getIdentifierByName((string)$currentToken->value);
        $this->nextToken();

        return new VariableExpression($identifier, $currentToken);
    }

    private function parseFuntion(Token $fun): AbstractFunction
    {
        $this->nextToken();
        $args = [];

        while (!$this->isEnd()) {
            $token = $this->getCurrentToken();

            if ($token === null) {
                break;
            }

            if ($token->type === TokenType::Parentheses && $token->value === ')') {
                $this->nextToken();
                break;
            }

            if ($token->type === TokenType::Separator) {
                $this->nextToken();
                continue;
            }

            $expression = $this->parseExpression();

            if (!$expression) {
                break;
            }
            $args[] = $expression;
            $token = $this->getCurrentToken();

            if ($token == null) {
                $this->logError('Ожидается ")"  в конце ');
                break;
            }

            if ($token->type !== TokenType::Separator && $token->type !== TokenType::Parentheses) {
                $this->logError('Ожидается ")" или ";". Дано: ' . $token->value, $token);
            }
        }

        return $this->functionBuilder->build($fun, $args);
    }

    private function parseParenthesesExpr(): ?Expression
    {
        $this->nextToken();
        $expression = $this->parseExpression();

        if (!$expression) {
            return null;
        }
        $token = $this->getCurrentToken();

        if ($token == null || ($token->type != TokenType::Parentheses && $token->value !== ')')) {
            $this->logError('Ожидается ")"', $token);

            return null;
        }
        $this->nextToken();

        return $expression;
    }

    private function parseExpression(): ?Expression
    {
        $lhs = $this->parsePrimary();

        if ($lhs === null) {
            return null;
        }

        return $this->parseBinOpRHS(0, $lhs);
    }

    private function parseBinOpRHS(int $exprPrec, Expression $lhs): ?Expression
    {
        while (true) {
            $operator = $this->getCurrentToken();

            if (!$operator) {
                return $lhs;
            }
            $tokPrec = $this->getTokPrecedence($operator);

            if ($tokPrec < $exprPrec) {
                return $lhs;
            }
            $this->nextToken();
            $rhs = $this->parsePrimary();

            if (!$rhs) {
                return null;
            }
            $nextToken = $this->getCurrentToken();

            if ($nextToken) {
                $nextPrec = $this->getTokPrecedence($nextToken);

                if ($tokPrec < $nextPrec) {
                    $rhs = $this->parseBinOpRHS($tokPrec + 1, $rhs);

                    if (!$rhs) {
                        return null;
                    }
                }
            }

            $lhs = new Operator($operator, $lhs, $rhs);
        }
    }

    private function logError(string $error, ?Token $token = null): void
    {
        throw new SyntaxError($error, $token);
    }
}

FunctionBuilder
class FunctionBuilder
{
    /** @var array<string, string> */
    private array $functions = [
        'ЕСЛИ'        => Funif::class,        
    ];

    /**
     * @param Token        $token
     * @param Expression[] $args
     *
     * @return AbstractFunction
     *
     * @throws SyntaxError
     */
    public function build(Token $token, array $args): AbstractFunction
    {
        $funname = $token->value;

        if (\array_key_exists($funname, $this->functions)) {
            $className = $this->functions[$funname];

            $classObje = new $className($token, $args);

            if ($classObje instanceof AbstractFunction) {
                return $classObje;
            }
            throw new ASTException("Функция {$funname} не является  AbstractFunction");
        }
        throw new SyntaxError('Неизвестная функция: ' . $token->value, $token);
    }
}

Всё... Теперь можно пробовать посчитать нашу формулу, для этого создадим репозиторий:

class ValueRepository implements ValueRepositoryInterface
{
    /** @var array<string, int> */
    private array $variables = [
        'Переменная_1'   => 3,
        'Переменная_2'    => 2,       
    ];

    public function getValueByIdentifier(string $identificator): mixed
    {
        return $this->variables[$identificator];
    }   
}

И, наконец, посчитаем:

$parser = new Parser();
$ast = $parser->parse('ЕСЛИ(Переменная_1>Переменная_2; "Больше"; "Меньше")');// Получили синтаксическое дерево

$repository = new ValueRepository();// Наш репозиторий

$answer = $ast->calculate($repository); // $answer = "Больше"

Итог:

1) У нас есть эксель-подобный синтаксис, который более понятен конечному пользователю.

2) Значения переменных берутся только когда они действительно нужны, а не инициализируются изначально.

3) Добавлять свои функции, тем самым тонко подстраиваясь под проект.

4) Мы не используем eval в php.

И мы также можем с помощью лексера сделать синтаксическую подсветку. Но это, если будет интересно, уже в другой раз.

Tags:
Hubs:
Total votes 11: ↑10 and ↓1+16
Comments4

Articles