Bahasa Ungkapan Satu Jam

Catatan blog ini terbaik dilihat dalam format asalnya.

Siaran ini mengimbas semula pembentangan bertajuk Bahasa Ekspresi Satu Jam, menyemak kedua-dua konsep dan kod.¹

Bahasa ungkapan², dalam konteks ini, menilai ungkapan—jujukan bait, kemungkinan besar aksara UTF-8.³ Contohnya termasuk:

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

Contoh bahasa ungkapan (atau DSL⁴) ialah:

• JQ
• Bahasa Pertanyaan Kibana
• Bahasa XPath
• Bahasa Ungkapan Symfony

Mengapa membina bahasa ekspresi anda sendiri? kenapa tidak Terlalu sibuk? jangan risau! Ia tidak memerlukan bulan, minggu, atau hari. Buat satu dalam sejam dengan Bahasa Ungkapan Satu Jam!⁵

ProCalc2000

Kami akan membina bahasa ekspresi ProCalc2000—kalkulator aritmetik bukan saintifik generasi akan datang untuk tahun 2000 dan seterusnya.

Ia menilai ungkapan seperti 1 1 atau 1 2 dan boleh menangani masalah pembahagian seperti 1 3 2 / 2.

Godzilla

Godzilla tidak menyukai pembahagian kerana nombor titik terapung.

Bahasa ini terdiri daripada nombor (cth., 1, 2) dan operator ( , -, ). Ia tidak akan* menyokong keutamaan pengendali (lihat Lampiran I) atau pembahagian.

Walaupun ringkas, ia menyediakan asas untuk menambah ciri: pembolehubah, fungsi, pengendali paip, akhiran, penyambungan rentetan dan juga pembahagian (yang bertentangan dengan kehendak Godzilla).

Apa yang ada dalam One, Tolong?

Banyak cara wujud untuk menilai jujukan bait, tetapi kami akan menggunakan tokenizer, parser dan penilai:

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

Tokenizer

Juga dikenali sebagai lexer atau pengimbas. Kelas ini membahagikan rentetan kepada ketulan yang dikategorikan yang dipanggil token.

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

Sebagai contoh, 1 2 3 menghasilkan lima token:

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

Tokenizer mengimbas dari kiri ke kanan, mengenal pasti bahagian yang menarik: integer positif dan pengendali , -, dan *. Ruang putih diabaikan; watak lain menyebabkan ralat. Jenis token ialah Integer, Tambah, Tolak dan Darab.

Godzilla

Godzilla mencadangkan mesin tokenizer dan tindanan, tetapi kami akan menggunakan penghurai dan penilai kerana Godzilla mengambil berat.

Tokenizer tidak menyemak kesahihan ungkapan; ia hanya mengkategorikan ketulan.⁶ Token dihantar kepada penghurai.

Penghuraikan

Penghurai mentafsir token, mengubahnya menjadi Pokok Sintaks Abstrak (AST).

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

Diberikan senarai token, penghurai mengembalikan AST—nod akar pokok. Setiap nod ialah ungkapan yang boleh dinilai; jenis nod ialah BinaryOp dan Integer.

Operasi binari mempunyai dua operan (cth., foo or bar boleh jadi BinaryOp(Variable('foo'), 'or', Variable('bar'))).

Operasi unary mempunyai satu operan (cth., -1).

Operasi ternary mempunyai tiga operan (cth., foo ? bar : baz).

Ungkapan 1 1 / 5 ialah BinaryOp dengan sebagai pengendali, satu operan ialah 1, dan satu lagi ialah satu lagi BinaryOp (1 / 5).

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

Penilai

Penilai menerima Nod dan mengembalikan nilai (di sini, integer). Ia adalah jurubahasa berjalan pokok.

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

Tolong Tunjukkan Kod Anda?

Kod ini berasal dari pertemuan PHPSW, didorong oleh ujian unit (diabaikan di sini). Lihat repositori.

Godzilla

Godzilla akan marah dengan kod ini dan mencadangkan pemfaktoran semula.

Tokenizer

Pertama, kelas Token dengan TokenType enum dan nilai pilihan:

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>

Token kelihatan seperti:

class Evaluator
{
    public function evaluate(Node $node): int
    {
        // ...
    }
}

Kelas Tokenizer melakukan kerja:⁷

class Token
{
    public function __construct(
        public TokenType $type,
        public ?string $value = null
    ) {}
}

Koleksi Tokens:

enum TokenType
{
    case Plus;
    case Minus;
    case Multiply;
    case Integer;
}

Godzilla

Godzilla lebih suka tatasusunan dan `array_shift` atau penjana untuk tokenisasi dan penghuraian secara serentak.

Penghuraikan

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

Di sinilah keutamaan operator, penghuraian akhiran dan operator paip akan ditambahkan. Penghuraian akhiran, sebagai contoh, akan mengendalikan ungkapan seperti "5 batu".

Penilai

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

Itu sahaja

Kod ini dikodkan secara langsung, termasuk ujian. Kod lengkap tersedia dalam repositori.

Keutamaan Operator

Ungkapan 1 * 3 4 sepatutnya (1 * 3) 4 = 7, tetapi bahasa kita menilainya sebagai 1 * (3 4) = 7 kerana kaedah penghuraian.⁸ Penghurai Pratt membetulkannya:

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

Godzilla

Godzilla memahami rekursi.

Bacaan Lanjut

• Jurubahasa Kraf: Buku (dengan edisi web percuma) oleh Robert Nystrom
• Penghuraian Ungkapan Dipermudahkan: Catatan blog oleh Robert Nystrom
• Kalkulator RPN Mesin Tindanan: 2014 Siaran oleh Igor Wiedler
• Doktrin Lexer
• PHPStan Phpdoc Parser⁹

---

1. Kod berubah dengan setiap lelaran.
2. Atau lebih khusus, penterjemah bahasa ungkapan.
3. Selalunya dipanggil rentetan dalam PHP.
4. Bahasa khusus domain.
5. Tiada paten wujud.
6. Tokenizer berguna untuk penyerlahan sintaks.
Kaedah
7. preg_ mungkin lebih berprestasi.
8. Hanya salah jika jawapan yang berbeza dijangkakan.
9. Pelintasan pokok ditemui melalui pembina pertanyaan Doktrin.

Atas ialah kandungan terperinci Bahasa Ungkapan Satu Jam. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!