一小时表达语言

这篇博文最好以其原始格式查看。

这篇文章回顾了题为一小时表达语言的演示，回顾了概念和代码。¹

表达式语言²，在此上下文中，计算表达式 - 字节序列，很可能是 UTF-8 字符。³ 示例包括：

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

表达式语言（或 DSL⁴）的示例是：

• JQ
• Kibana 查询语言
• XPath 语言
• Symfony 表达语言

为什么要构建自己的表达语言？ 为什么不呢？ 太忙？ 不用担心！它不需要几个月、几周甚至几天。 使用一小时表达语言在一小时内创建一个！⁵

ProCalc2000

我们将构建 ProCalc2000 表达式语言 - 2000 年及以后的下一代非科学算术计算器。

它评估诸如 1 1 或 1 2 之类的表达式，并且可以处理诸如 1 3 2 / 2.

之类的除法问题

哥斯拉

由于浮点数，哥斯拉不喜欢除法。

该语言包含数字（例如 1、2）和运算符（、-、）。 它不会*支持运算符优先级（参见附录一）或除法。

尽管它很简单，但它为添加功能提供了基础：变量、函数、管道运算符、后缀、字符串连接，甚至（违背哥斯拉的意愿）除法。

请问，One 里有什么？

评估字节序列的方法有很多，但我们将使用分词器、解析器和评估器：

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

分词器

也称为词法分析器或扫描器。此类将字符串拆分为称为标记的分类块。

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

例如，1 2 3 产生五个标记：

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

分词器从左到右扫描，识别有趣的块：正整数以及 、 - 和 * 运算符。空白被忽略；其他字符会导致错误。 令牌类型有整数、加号、减号和乘号。

哥斯拉

哥斯拉建议使用分词器和堆栈机，但我们将使用解析器和评估器，因为哥斯拉关心。

分词器不检查表达式的有效性；它仅对块进行分类。⁶ 标记将传递给解析器。

解析器

解析器解释标记，将它们转换为抽象语法树（AST）。

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

给定一个标记列表，解析器返回一个 AST——树的根节点。 每个节点都是一个可评估的表达式；节点类型有 BinaryOp 和 Integer。

二元运算有两个操作数（例如，foo or bar 可以是 BinaryOp(Variable('foo'), 'or', Variable('bar'))）。

一元运算有一个操作数（例如，-1）。

三元运算有三个操作数（例如，foo ? bar : baz）。

表达式1 1 / 5是一个以 为运算符的BinaryOp，一个操作数为1，另一个为另一个BinaryOp（1 / 5）。

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

评估者

求值器接受一个 Node 并返回一个值（这里是一个整数）。 这是一个树行走翻译器。

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

请显示您的代码？

此代码源自 PHPSW 聚会，由单元测试驱动（此处省略）。查看存储库。

哥斯拉

哥斯拉会对这段代码感到愤怒并建议重构。

分词器

首先，一个带有 Token 枚举和可选值的 TokenType 类：

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>

令牌看起来像：

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

Tokenizer 类完成以下工作：⁷

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

Tokens系列：

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

哥斯拉

Godzilla 更喜欢使用数组和 array_shift 或生成器来同时进行标记化和解析。

解析器

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

这是添加运算符优先级、后缀解析和管道运算符的地方。 例如，后缀解析可以处理“5 英里”这样的表达式。

评估者

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

就是这样

此代码是实时编码的，包括测试。 完整的代码可以在存储库中找到。

运算符优先级

表达式 1 * 3 4 应该是 (1 * 3) 4 = 7，但由于解析方法，我们的语言将其计算为 1 * (3 4) = 7。⁸ Pratt 解析器纠正了这一点：

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

哥斯拉

哥斯拉了解递归。

延伸阅读

• 制作口译员：罗伯特·尼斯特罗姆 (Robert Nystrom) 所著的书籍（免费网络版）
• 表达式解析变得简单：Robert Nystrom 的博客文章
• 堆栈机 RPN 计算器：2014 年 Igor Wiedler 发表
• 学说词法分析器
• PHPStan Phpdoc 解析器⁹

---

1. 代码随着每次迭代而变化。
2. 或更具体地说，是一个表达式语言解释器。
3. 在 PHP 中通常称为字符串。
4. 领域特定语言。
5. 不存在专利。
6. 分词器对于语法突出显示很有用。
7. preg_方法可能会更高效。
8. 只有在期望不同的答案时才是错误的。
9. 树遍历是通过 Doctrine 的查询构建器发现的。

以上是一小时表达语言的详细内容。更多信息请关注PHP中文网其他相关文章！