The One Hour Expression Language

This blog post is best viewed in its original format.

This post recaps a presentation titled The One Hour Expression Language, reviewing both the concepts and code.¹

An expression language², in this context, evaluates an expression—a sequence of bytes, most likely UTF-8 characters.³ Examples include:

• 1 1
• //article[@title="foobar"]//image
• .items[].foo|select(.bar = "foo")
• a.comments > 1 and a.category not in ["misc"]

Examples of expression languages (or DSLs⁴) are:

• JQ
• Kibana Query Language
• XPath Language
• Symfony Expression Language

Why build your own expression language? Why not? Too busy? Don't worry! It doesn't require months, weeks, or even days. Create one in an hour with the One Hour Expression Language!⁵

ProCalc2000

We'll build the ProCalc2000 expression language—a next-generation, non-scientific arithmetic calculator for the year 2000 and beyond.

It evaluates expressions like 1 1 or 1 2, and can handle division problems such as 1 3 2 / 2.

Godzilla

Godzilla dislikes division due to floating-point numbers.

The language comprises numbers (e.g., 1, 2) and operators ( , -, ). It will not* support operator precedence (see Appendix I) or division.

Despite its simplicity, it provides a foundation for adding features: variables, functions, pipe operators, suffixes, string concatenation, and even (against Godzilla's wishes) division.

What's in One, Please?

Many ways exist to evaluate a byte sequence, but we'll use a tokenizer, parser, and evaluator:

<code>              +-----------+  tokens  +--------+  ast  +-----------+ 
EXPRESSION ==>| Tokenizer |--------->| Parser |------>| Evaluator | => VALUE
              +-----------+          +--------+       +-----------+</code>

Tokenizer

Also known as a lexer or scanner. This class splits the string into categorized chunks called tokens.

class Tokenizer
{
    public function tokenize(string $expression): Tokens
    {
        // ...
    }
}

For example, 1 2 3 yields five tokens:

<code>Token(Integer, 1)
Token(Plus)
Token(Integer, 2)
Token(Plus)
Token(Integer, 3)</code>

The tokenizer scans left-to-right, identifying interesting chunks: positive integers and the , -, and * operators. Whitespace is ignored; other characters cause errors. Token types are Integer, Plus, Minus, and Multiply.

Godzilla

Godzilla suggests a tokenizer and stack machine, but we'll use a parser and evaluator because Godzilla cares.

The tokenizer doesn't check expression validity; it only categorizes chunks.⁶ The tokens are passed to the parser.

Parser

The parser interprets the tokens, transforming them into an Abstract Syntax Tree (AST).

<code>              +-----------+  tokens  +--------+  ast  +-----------+ 
EXPRESSION ==>| Tokenizer |--------->| Parser |------>| Evaluator | => VALUE
              +-----------+          +--------+       +-----------+</code>

Given a token list, the parser returns an AST—a root node of a tree. Each node is an evaluable expression; node types are BinaryOp and Integer.

A binary operation has two operands (e.g., foo or bar could be BinaryOp(Variable('foo'), 'or', Variable('bar'))).

Unary operations have one operand (e.g., -1).

Ternary operations have three operands (e.g., foo ? bar : baz).

The expression 1 1 / 5 is a BinaryOp with as the operator, one operand being 1, and the other being another BinaryOp (1 / 5).

class Tokenizer
{
    public function tokenize(string $expression): Tokens
    {
        // ...
    }
}

Evaluator

The evaluator accepts a Node and returns a value (here, an integer). It's a tree-walking interpreter.

<code>Token(Integer, 1)
Token(Plus)
Token(Integer, 2)
Token(Plus)
Token(Integer, 3)</code>

Show Me Your Code, Please?

This code originated at a PHPSW meetup, driven by unit tests (omitted here). See the repository.

Godzilla

Godzilla would be angry with this code and suggests refactoring.

Tokenizer

First, a Token class with a TokenType enum and an optional value:

class Parser
{
    public function parse(Tokens $tokens): Node
    {
        // ...
    }
}

<code>                        +-------------+
                        | Binary Op + | 



<p>In PHP:</p>

```php
$ast = new BinaryOp(
    left:     new Integer(1),
    operator: '+',
    right:    new BinaryOp(
        left:     new Integer(1),
        operator: '/',
        right:    new Integer(5),
    )
);</code>

Tokens look like:

class Evaluator
{
    public function evaluate(Node $node): int
    {
        // ...
    }
}

The Tokenizer class does the work:⁷

class Token
{
    public function __construct(
        public TokenType $type,
        public ?string $value = null
    ) {}
}

The Tokens collection:

enum TokenType
{
    case Plus;
    case Minus;
    case Multiply;
    case Integer;
}

Godzilla

Godzilla prefers an array and `array_shift` or a generator for tokenization and parsing simultaneously.

Parser

[
    new Token(TokenType::Integer, 50),
    new Token(TokenType::Plus),
    // ...
]

This is where operator precedence, suffix parsing, and pipe operators would be added. Suffix parsing, for example, would handle expressions like "5 miles".

Evaluator

class Tokenizer
{
    public function tokenize(string $expression): Tokens 
    {
        $offset = 0;
        $tokens = [];
        while (isset($expression[$offset])) {
            $char = $expression[$offset++];
            if (is_numeric($char)) {
                while (is_numeric($expression[$offset] ?? null)) {
                    $char .= $expression[$offset++];
                }
                $tokens[] = new Token(TokenType::Integer, $char);
                continue;
            }
            $token = match ($char) {
                '+' => new Token(TokenType::Plus),
                '-' => new Token(TokenType::Minus),
                '*' => new Token(TokenType::Multiply),
                ' ' => null,
                default => throw new RuntimeException(sprintf(
                    'Invalid operator: "%s"', $char
                )),
            };
            if ($token === null) {
                continue;
            }
            $tokens[] = $token;
        }
        return new Tokens($tokens);
    }
}

That's It

This code was live-coded, including tests. The complete code is available in the repository.

Operator Precedence

The expression 1 * 3 4 should be (1 * 3) 4 = 7, but our language evaluates it as 1 * (3 4) = 7 because of the parsing method.⁸ A Pratt parser corrects this:

<code>              +-----------+  tokens  +--------+  ast  +-----------+ 
EXPRESSION ==>| Tokenizer |--------->| Parser |------>| Evaluator | => VALUE
              +-----------+          +--------+       +-----------+</code>

Godzilla

Godzilla understands recursion.

Further Reading

• Crafting Interpreters: Book (with free web edition) by Robert Nystrom
• Expression Parsing Made Easy: Blog post by Robert Nystrom
• Stack Machine RPN Calculator: 2014 Post by Igor Wiedler
• Doctrine Lexer
• PHPStan Phpdoc Parser⁹

---

1. The code changes with each iteration.
2. Or more specifically, an expression language interpreter.
3. Often called a string in PHP.
4. Domain-specific language.
5. No patent exists.
6. A tokenizer is useful for syntax highlighting.
7. preg_ methods might be more performant.
8. Only wrong if a different answer was expected.
9. Tree traversal was discovered through Doctrine's query builders.

The above is the detailed content of The One Hour Expression Language. For more information, please follow other related articles on the PHP Chinese website!