1 時間の表現言語

このブログ投稿は、元の形式で表示するのが最適です。

この投稿は、1 時間の式言語 というタイトルのプレゼンテーションを要約し、概念とコードの両方をレビューします。¹

式言語²は、このコンテキストでは、式 (バイトのシーケンス、おそらく 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 式言語

なぜ独自の表現言語を構築するのでしょうか? なぜだめですか？ 忙しすぎますか？ 心配しないで！数か月、数週間、さらには数日も必要ありません。 One Hour Expression Language を使用して 1 時間で 1 つ作成しましょう!⁵

プロカルク2000

私たちは、2000 年以降に向けた次世代の非科学算術計算機である ProCalc2000 式言語を構築します。

1 1 や 1 2 などの式を評価し、1 3 2 / 2 などの除算問題を処理できます。

ゴジラ

ゴジラは浮動小数点数による割り算を嫌います。

言語は数字 (例: 1、2) と演算子 (、、-、) で構成されます。 演算子の優先順位 (付録 I を参照) や除算は*サポートされません。

そのシンプルさにもかかわらず、変数、関数、パイプ演算子、サフィックス、文字列の連結、さらには (ゴジラの希望に反して) 除算などの機能を追加するための基盤を提供します。

1 つには何が入っていますか?

バイト シーケンスを評価するには多くの方法がありますが、ここではトークナイザー、パーサー、およびエバリュエーターを使用します。

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

トークナイザー

レクサーまたはスキャナーとも呼ばれます。このクラスは、文字列をトークンと呼ばれる分類されたチャンクに分割します。

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

たとえば、1 2 3 は 5 つのトークンを生成します。

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

トークナイザーは左から右にスキャンして、興味深いチャンク (正の整数、 、 - 、および * 演算子) を識別します。空白は無視されます。他の文字を使用するとエラーが発生します。 トークンのタイプは、整数、プラス、マイナス、乗算です。

ゴジラ

Godzilla はトークナイザーとスタック マシンを提案しますが、Godzilla が気にするのでパーサーと評価器を使用します。

トークナイザーは式の有効性をチェックしません。チャンクを分類するだけです。⁶ トークンはパーサーに渡されます。

パーサー

パーサーはトークンを解釈し、抽象構文ツリー (AST) に変換します。

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

トークン リストが与えられると、パーサーは AST (ツリーのルート ノード) を返します。 各ノードは評価可能な式です。ノード タイプは BinaryOp と Integer です。

二項演算には 2 つのオペランドがあります (たとえば、foo or bar は BinaryOp(Variable('foo'), 'or', Variable('bar')) である可能性があります)。

単項演算にはオペランドが 1 つあります (例: -1)。

三項演算には 3 つのオペランドがあります (例: foo ? bar : baz)。

式 1 1 / 5 は、演算子として を持つ BinaryOp で、一方のオペランドは 1 で、もう一方のオペランドは別の BinaryOp (1 / 5) です。

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

評価者

エバリュエーターはノードを受け入れ、値 (ここでは整数) を返します。 木歩き通訳です

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

ゴジラ

ゴジラは再帰性を理解しています。

続きを読む

• Crafting Interpreters: 書籍 (無料 Web 版付き) by Robert Nystrom
• 式の解析が簡単に: Robert Nystrom によるブログ投稿
• スタック マシン RPN 計算機: Igor Wiedler による 2014 年の投稿
• ドクトリンレクサー
• PHPStan Phpdoc パーサー⁹

---

1. コードは反復ごとに変更されます。
2. より具体的には、式言語インタープリタ。
3. PHP では文字列と呼ばれることがよくあります。
4. ドメイン固有の言語
5. 特許は存在しません。
6. トークナイザーは構文の強調表示に役立ちます。
7. preg_ メソッドの方がパフォーマンスが高い可能性があります。
8. 異なる答えが期待されていた場合のみ、間違っています。
9. ツリートラバーサルは、Doctrine のクエリビルダーを通じて発見されました。

以上が1 時間の表現言語の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。