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

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

表達(dá)式語言²，在此上下文中，計算表達(dá)式 - 位元組序列，很可能是 UTF-8 字元。 ³ 範(fàn)例包括：

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

表達(dá)式語言（或 DSL⁴）的範(fàn)例是：

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

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

ProCalc2000

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

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

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

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

請問，One 裡面有什麼？

評估位元組序列的方法有很多，但我們將使用分詞器、解析器和評估器：

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

分詞器

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

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>

分詞器從左到右掃描，辨識有趣的區(qū)塊：正整數(shù)以及 、 - 和 * 運算子?？瞻妆缓雎裕黄渌衷獣?dǎo)致錯誤。 令牌類型有整數(shù)、加號、減號和乘號。

分詞器不檢查表達(dá)式的有效性；它僅對區(qū)塊進(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。

二元運算有兩個運算元（例如，foo or bar 可以是 BinaryOp(Variable('foo'), 'or', Variable('bar'))）。

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

三元運算有三個運算元（例如，foo ? bar : baz）。

表達(dá)式1 1 / 5是一個以 為運算子的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ōu)先權(quá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ōu)先權(quán)

表達(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) 所寫的書籍（免費網(wǎng)路版）
• 表達(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)文章！