首页 >后端开发 >php教程 >一小时表达语言

一小时表达语言

Mary-Kate Olsen原创: 2025-01-21 08:16:09290浏览

The One Hour Expression Language

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

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

表达式语言²，在此上下文中，计算表达式 - 字节序列，很可能是 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>

分词器

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

<code class="language-php">class Tokenizer
{
    public function tokenize(string $expression): Tokens
    {
        // ...
    }
}</code>

例如，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）。

<code class="language-php">class Tokenizer
{
    public function tokenize(string $expression): Tokens
    {
        // ...
    }
}</code>

评估者

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

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

请显示您的代码？

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

哥斯拉

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

分词器

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

<code class="language-php">class Parser
{
    public function parse(Tokens $tokens): Node
    {
        // ...
    }
}</code>

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

令牌看起来像：

<code class="language-php">class Evaluator
{
    public function evaluate(Node $node): int
    {
        // ...
    }
}</code>

Tokenizer 类完成以下工作：⁷

<code class="language-php">class Token
{
    public function __construct(
        public TokenType $type,
        public ?string $value = null
    ) {}
}</code>

Tokens系列：

<code class="language-php">enum TokenType
{
    case Plus;
    case Minus;
    case Multiply;
    case Integer;
}</code>

哥斯拉

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

解析器

<code class="language-php">[
    new Token(TokenType::Integer, 50),
    new Token(TokenType::Plus),
    // ...
]</code>

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

评估者

<code class="language-php">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);
    }
}</code>

就是这样

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

运算符优先级

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

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

哥斯拉

哥斯拉了解递归。