Interpreter pattern – own discount rule grammar, parser, expression tree

Interpreter is the GoF pattern for implementing a mini-language. Instead of hardcoding discount rules, you define a grammar and an interpreter that evaluates expressions at runtime. This makes complex pricing rules configurable without code deployments. I build a complete discount rule language in PHP: grammar definition, recursive descent parser, AST, and evaluation.

The problem – hardcoded rules

<?php

// Rules hardcoded in PHP - every change requires a deployment
class DiscountEngine
{
    public function calculate(array $cart, array $customer): float
    {
        if ($cart['total'] > 500 && $customer['group'] === 'wholesale') {
            return $cart['total'] * 0.15;
        }
        if ($customer['orders_count'] > 10 && $cart['item_count'] >= 3) {
            return $cart['total'] * 0.10;
        }
        // ...more hardcoded rules
        return 0.0;
    }
}

// With Interpreter: rules are strings stored in the database or config
// "total > 500 AND group = 'wholesale'" -> 15%
// "orders_count > 10 AND item_count >= 3" -> 10%

Grammar definition

Grammar (simplified BNF):
  expression  ::= and_expr
  and_expr    ::= or_expr ('AND' or_expr)*
  or_expr     ::= primary ('OR' primary)*
  primary     ::= '(' expression ')' | comparison | 'NOT' primary
  comparison  ::= identifier operator value
  operator    ::= '>' | '>=' | '<' | '<=' | '=' | '!='
  identifier  ::= [a-z_]+
  value       ::= number | string
  number      ::= [0-9]+ ('.' [0-9]+)?
  string      ::= "'" [^']* "'"

Lexer - tokenise the input

<?php

declare(strict_types=1);

enum TokenType
{
    case AND_OP;
    case OR_OP;
    case NOT_OP;
    case LPAREN;
    case RPAREN;
    case IDENTIFIER;
    case NUMBER;
    case STRING;
    case GT; case GTE; case LT; case LTE; case EQ; case NEQ;
    case EOF;
}

readonly class Token
{
    public function __construct(
        public TokenType $type,
        public string $value,
    ) {}
}

class Lexer
{
    private int $pos = 0;
    private array $tokens = [];

    public function tokenise(string $input): array
    {
        $this->pos = 0;
        $this->tokens = [];
        $input = trim($input);

        while ($this->pos < strlen($input)) {
            $this->skipWhitespace($input);
            if ($this->pos >= strlen($input)) break;

            $char = $input[$this->pos];

            if (ctype_alpha($char) || $char === '_') {
                $this->readIdentifierOrKeyword($input);
            } elseif (ctype_digit($char)) {
                $this->readNumber($input);
            } elseif ($char === "'") {
                $this->readString($input);
            } elseif ($char === '(') {
                $this->tokens[] = new Token(TokenType::LPAREN, '(');
                $this->pos++;
            } elseif ($char === ')') {
                $this->tokens[] = new Token(TokenType::RPAREN, ')');
                $this->pos++;
            } elseif ($char === '>') {
                if (isset($input[$this->pos + 1]) && $input[$this->pos + 1] === '=') {
                    $this->tokens[] = new Token(TokenType::GTE, '>=');
                    $this->pos += 2;
                } else {
                    $this->tokens[] = new Token(TokenType::GT, '>');
                    $this->pos++;
                }
            } elseif ($char === '<') {
                if (isset($input[$this->pos + 1]) && $input[$this->pos + 1] === '=') {
                    $this->tokens[] = new Token(TokenType::LTE, '<=');
                    $this->pos += 2;
                } else {
                    $this->tokens[] = new Token(TokenType::LT, '<');
                    $this->pos++;
                }
            } elseif ($char === '=') {
                $this->tokens[] = new Token(TokenType::EQ, '=');
                $this->pos++;
            } elseif ($char === '!' && isset($input[$this->pos + 1]) && $input[$this->pos + 1] === '=') {
                $this->tokens[] = new Token(TokenType::NEQ, '!=');
                $this->pos += 2;
            } else {
                throw new \RuntimeException("Unexpected character: {$char}");
            }
        }

        $this->tokens[] = new Token(TokenType::EOF, '');
        return $this->tokens;
    }

    private function skipWhitespace(string $input): void
    {
        while ($this->pos < strlen($input) && ctype_space($input[$this->pos])) {
            $this->pos++;
        }
    }

    private function readIdentifierOrKeyword(string $input): void
    {
        $start = $this->pos;
        while ($this->pos < strlen($input) && (ctype_alnum($input[$this->pos]) || $input[$this->pos] === '_')) {
            $this->pos++;
        }
        $word = substr($input, $start, $this->pos - $start);
        $this->tokens[] = new Token(match(strtoupper($word)) {
            'AND' => TokenType::AND_OP,
            'OR'  => TokenType::OR_OP,
            'NOT' => TokenType::NOT_OP,
            default => TokenType::IDENTIFIER,
        }, $word);
    }

    private function readNumber(string $input): void
    {
        $start = $this->pos;
        while ($this->pos < strlen($input) && (ctype_digit($input[$this->pos]) || $input[$this->pos] === '.')) {
            $this->pos++;
        }
        $this->tokens[] = new Token(TokenType::NUMBER, substr($input, $start, $this->pos - $start));
    }

    private function readString(string $input): void
    {
        $this->pos++; // skip opening quote
        $start = $this->pos;
        while ($this->pos < strlen($input) && $input[$this->pos] !== "'") {
            $this->pos++;
        }
        $value = substr($input, $start, $this->pos - $start);
        $this->pos++; // skip closing quote
        $this->tokens[] = new Token(TokenType::STRING, $value);
    }
}

Parser and AST nodes

<?php

// AST Nodes
interface AstNode { public function evaluate(array $context): mixed; }

readonly class ComparisonNode implements AstNode
{
    public function __construct(
        public string $identifier,
        public string $operator,
        public string|float $value,
    ) {}

    public function evaluate(array $context): bool
    {
        $left  = $context[$this->identifier] ?? null;
        $right = $this->value;

        return match($this->operator) {
            '>'  => $left > $right,
            '>=' => $left >= $right,
            '<'  => $left < $right,
            '<=' => $left <= $right,
            '='  => $left == $right,
            '!=' => $left != $right,
            default => false,
        };
    }
}

readonly class AndNode implements AstNode
{
    public function __construct(public AstNode $left, public AstNode $right) {}
    public function evaluate(array $context): bool
    {
        return $this->left->evaluate($context) && $this->right->evaluate($context);
    }
}

readonly class OrNode implements AstNode
{
    public function __construct(public AstNode $left, public AstNode $right) {}
    public function evaluate(array $context): bool
    {
        return $this->left->evaluate($context) || $this->right->evaluate($context);
    }
}

readonly class NotNode implements AstNode
{
    public function __construct(public AstNode $node) {}
    public function evaluate(array $context): bool
    {
        return !$this->node->evaluate($context);
    }
}

// Recursive descent parser
class Parser
{
    private int $pos = 0;
    private array $tokens;

    public function parse(array $tokens): AstNode
    {
        $this->tokens = $tokens;
        $this->pos    = 0;
        return $this->parseExpression();
    }

    private function parseExpression(): AstNode { return $this->parseAnd(); }

    private function parseAnd(): AstNode
    {
        $left = $this->parseOr();
        while ($this->current()->type === TokenType::AND_OP) {
            $this->advance();
            $left = new AndNode($left, $this->parseOr());
        }
        return $left;
    }

    private function parseOr(): AstNode
    {
        $left = $this->parsePrimary();
        while ($this->current()->type === TokenType::OR_OP) {
            $this->advance();
            $left = new OrNode($left, $this->parsePrimary());
        }
        return $left;
    }

    private function parsePrimary(): AstNode
    {
        $token = $this->current();

        if ($token->type === TokenType::NOT_OP) {
            $this->advance();
            return new NotNode($this->parsePrimary());
        }

        if ($token->type === TokenType::LPAREN) {
            $this->advance();
            $node = $this->parseExpression();
            $this->expect(TokenType::RPAREN);
            return $node;
        }

        // Comparison: identifier operator value
        $identifier = $this->expect(TokenType::IDENTIFIER)->value;
        $operator   = $this->expectOperator()->value;
        $valueToken = $this->current();
        $this->advance();

        $value = $valueToken->type === TokenType::NUMBER
            ? (float)$valueToken->value
            : $valueToken->value;

        return new ComparisonNode($identifier, $operator, $value);
    }

    private function current(): Token { return $this->tokens[$this->pos]; }
    private function advance(): Token  { return $this->tokens[$this->pos++]; }

    private function expect(TokenType $type): Token
    {
        $token = $this->current();
        if ($token->type !== $type) throw new \RuntimeException("Expected {$type->name}, got {$token->type->name}");
        $this->advance();
        return $token;
    }

    private function expectOperator(): Token
    {
        $token = $this->current();
        if (!in_array($token->type, [TokenType::GT, TokenType::GTE, TokenType::LT, TokenType::LTE, TokenType::EQ, TokenType::NEQ])) {
            throw new \RuntimeException("Expected operator, got {$token->type->name}");
        }
        $this->advance();
        return $token;
    }
}

Usage in a Magento discount rule engine

<?php

class DiscountRuleEngine
{
    private Lexer $lexer;
    private Parser $parser;
    private array $ruleCache = [];

    public function __construct()
    {
        $this->lexer  = new Lexer();
        $this->parser = new Parser();
    }

    public function evaluate(string $rule, array $context): bool
    {
        if (!isset($this->ruleCache[$rule])) {
            $tokens = $this->lexer->tokenise($rule);
            $this->ruleCache[$rule] = $this->parser->parse($tokens);
        }

        return (bool)$this->ruleCache[$rule]->evaluate($context);
    }
}

// Rules stored in database, evaluated at runtime
$engine = new DiscountRuleEngine();
$context = [
    'total'        => 650.0,
    'group'        => 'wholesale',
    'orders_count' => 15,
    'item_count'   => 5,
];

$rules = [
    ["total > 500 AND group = 'wholesale'", 0.15],
    ["orders_count > 10 AND item_count >= 3", 0.10],
    ["total >= 1000 OR (group = 'vip' AND total > 200)", 0.20],
];

foreach ($rules as [$expression, $discountRate]) {
    if ($engine->evaluate($expression, $context)) {
        echo "Rule matched: discount {$discountRate}\n";
    }
}
// Rule matched: discount 0.15
// Rule matched: discount 0.10

Summary

The Interpreter pattern transforms complex conditional logic into a configurable mini-language. The investment is the lexer and parser - once built, adding operators or functions to the grammar is incremental. The payoff is business users who can define discount rules without developer involvement, and a testable expression evaluator that replaces sprawling if-else chains. In Magento context this pattern fits promotion rules, shipping rate conditions, and any rule-heavy business logic that changes frequently.