一小時表達語言

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

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

表達式語言²，在此上下文中，計算表達式 - 位元組序列，很可能是 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中文網其他相關文章！