The One Hour Expression Language-PHP Tutorial-php.cn

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>

Copy after login

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
    {
        // ...
    }
}

Copy after login

For example, 1 2 3 yields five tokens:

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

Copy after login

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>

Copy after login

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
    {
        // ...
    }
}

Copy after login

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>

Copy after login

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
    {
        // ...
    }
}

Copy after login

<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>

Copy after login

Tokens look like:

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

Copy after login

The Tokenizer class does the work:⁷

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

Copy after login

The Tokens collection:

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

Copy after login

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),
    // ...
]

Copy after login

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);
    }
}

Copy after login

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>

Copy after login

Godzilla

Godzilla understands recursion.