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

這篇文章回顧了題為一小時表達(dá)語言的演示，回顧了概念和代碼。¹

表達(dá)式語言²，在此上下文中，計算表達(dá)式 - 字節(jié)序列，很可能是 UTF-8 字符。³ 示例包括：

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

表達(dá)式語言（或 DSL⁴）的示例是：

• JQ
• Kibana 查詢語言
• XPath 語言
• Symfony 表達(dá)語言

為什么要構(gòu)建自己的表達(dá)語言？ 為什么不呢？ 太忙？ 不用擔(dān)心！它不需要幾個月、幾周甚至幾天。 使用一小時表達(dá)語言在一小時內(nèi)創(chuàng)建一個！⁵

ProCalc2000

我們將構(gòu)建 ProCalc2000 表達(dá)式語言 - 2000 年及以后的下一代非科學(xué)算術(shù)計算器。

它評估諸如 1 1 或 1 2 之類的表達(dá)式，并且可以處理諸如 1 3 2 / 2.

該語言包含數(shù)字（例如 1、2）和運(yùn)算符（、-、）。 它不會*支持運(yùn)算符優(yōu)先級（參見附錄一）或除法。

盡管它很簡單，但它為添加功能提供了基礎(chǔ)：變量、函數(shù)、管道運(yùn)算符、后綴、字符串連接，甚至（違背哥斯拉的意愿）除法。

請問，One 里有什么？

評估字節(jié)序列的方法有很多，但我們將使用分詞器、解析器和評估器：

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

分詞器

也稱為詞法分析器或掃描器。此類將字符串拆分為稱為標(biāo)記的分類塊。

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

例如，1 2 3 產(chǎn)生五個標(biāo)記：

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

分詞器從左到右掃描，識別有趣的塊：正整數(shù)以及 、 - 和 * 運(yùn)算符?？瞻妆缓雎?；其他字符會導(dǎo)致錯誤。 令牌類型有整數(shù)、加號、減號和乘號。

分詞器不檢查表達(dá)式的有效性；它僅對塊進(jìn)行分類。⁶ 標(biāo)記將傳遞給解析器。

解析器

解析器解釋標(biāo)記，將它們轉(zhuǎn)換為抽象語法樹（AST）。

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

給定一個標(biāo)記列表，解析器返回一個 AST——樹的根節(jié)點。 每個節(jié)點都是一個可評估的表達(dá)式；節(jié)點類型有 BinaryOp 和 Integer。

二元運(yùn)算有兩個操作數(shù)（例如，foo or bar 可以是 BinaryOp(Variable('foo'), 'or', Variable('bar'))）。

一元運(yùn)算有一個操作數(shù)（例如，-1）。

三元運(yùn)算有三個操作數(shù)（例如，foo ? bar : baz）。

表達(dá)式1 1 / 5是一個以 為運(yùn)算符的BinaryOp，一個操作數(shù)為1，另一個為另一個BinaryOp（1 / 5）。

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

評估者

求值器接受一個 Node 并返回一個值（這里是一個整數(shù)）。 這是一個樹行走翻譯器。

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

請顯示您的代碼？

此代碼源自 PHPSW 聚會，由單元測試驅(qū)動（此處省略）。查看存儲庫。

分詞器

首先，一個帶有 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;
}

解析器

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

這是添加運(yùn)算符優(yōu)先級、后綴解析和管道運(yùn)算符的地方。 例如，后綴解析可以處理“5 英里”這樣的表達(dá)式。

評估者

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

就是這樣

此代碼是實時編碼的，包括測試。 完整的代碼可以在存儲庫中找到。

運(yùn)算符優(yōu)先級

表達(dá)式 1 * 3 4 應(yīng)該是 (1 * 3) 4 = 7，但由于解析方法，我們的語言將其計算為 1 * (3 4) = 7。⁸ Pratt 解析器糾正了這一點：

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

延伸閱讀

• 制作口譯員：羅伯特·尼斯特羅姆 (Robert Nystrom) 所著的書籍（免費(fèi)網(wǎng)絡(luò)版）
• 表達(dá)式解析變得簡單：Robert Nystrom 的博客文章
• 堆棧機(jī) RPN 計算器：2014 年 Igor Wiedler 發(fā)表
• 學(xué)說詞法分析器
• PHPStan Phpdoc 解析器⁹

1. 代碼隨著每次迭代而變化。
2. 或更具體地說，是一個表達(dá)式語言解釋器。
3. 在 PHP 中通常稱為字符串。
4. 領(lǐng)域特定語言。
5. 不存在專利。
6. 分詞器對于語法突出顯示很有用。
7. preg_方法可能會更高效。
8. 只有在期望不同的答案時才是錯誤的。
9. 樹遍歷是通過 Doctrine 的查詢構(gòu)建器發(fā)現(xiàn)的。

以上是一小時表達(dá)語言的詳細(xì)內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！