Cara menghuraikan kod komputer, Advent of Code ay 3

Setelah menangani beberapa cabaran Advent of Code, saya ingin melawat semula Hari 3, yang memberikan masalah penghuraian yang menarik. Tugas itu melibatkan mengekstrak kod yang sah daripada input yang bising, latihan yang hebat dalam pembangunan parser dan lexer. Sertai saya sambil saya meneroka pendekatan saya terhadap cabaran ini.

Imej yang dijana menunjukkan kecintaan saya terhadap teka-teki (?) oleh Microsoft Copilot

Apabila saya mula-mula menulis tentang pembaris DSL, saya bergantung pada Hy untuk menghurai. Walau bagaimanapun, penerokaan AI generatif saya baru-baru ini telah memperkenalkan kaedah penghuraian baharu: kod yang dijana menggunakan perpustakaan funcparserlib. Cabaran Advent of Code ini membolehkan saya menyelidiki selok-belok funcparserlib dan membangunkan pemahaman yang lebih kuat tentang kefungsian kod yang dijana.

Melaksanakan Lexer (Analisis Leksikal)

Langkah pertama dalam memproses input rosak kami ialah lexing (atau tokenisasi). lexer (atau tokenizer) mengimbas rentetan input dan membahagikannya kepada token individu, yang merupakan blok binaan asas untuk pemprosesan selanjutnya. token mewakili unit yang bermakna dalam input, dikategorikan mengikut jenisnya. Untuk teka-teki ini, kami berminat dengan jenis token ini:

• Pengendali (OP): Ini mewakili nama fungsi, seperti mul, lakukan dan jangan. Contohnya, input mul(2, 3) mengandungi token operator mul.
• Nombor: Ini adalah nilai berangka. Sebagai contoh, dalam input mul(2, 3), 2 dan 3 akan dikenali sebagai token nombor.
• Koma: Aksara koma (,) bertindak sebagai pemisah antara hujah.
• Kurungan: Tanda kurung buka ( dan tutup ) mentakrifkan struktur panggilan fungsi.
• Gibberish: Kategori ini merangkumi mana-mana aksara atau jujukan aksara yang tidak sepadan dengan jenis token yang lain. Di sinilah bahagian input yang "rosak" masuk. Contohnya, %$#@ atau mana-mana huruf rawak akan dianggap omong kosong.

Walaupun funcparserlib sering menggunakan rentetan ajaib dalam tutorialnya, saya lebih suka pendekatan yang lebih berstruktur. Rentetan ajaib boleh menyebabkan kesilapan menaip dan menyukarkan untuk memfaktorkan semula kod. Menggunakan Enum untuk menentukan jenis token menawarkan beberapa kelebihan: kebolehbacaan yang lebih baik, kebolehselenggaraan yang lebih baik dan keselamatan jenis yang dipertingkatkan. Begini cara saya mentakrifkan jenis token menggunakan Enum:

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

Dengan menggunakan Spec.OP, Spec.NUMBER, dsb., kami mengelakkan kekaburan dan kemungkinan ralat yang dikaitkan dengan penggunaan rentetan biasa.

Untuk menyepadukan Enum dengan funcparserlib dengan lancar, saya mencipta penghias tersuai bernama TokenSpec_. Penghias ini bertindak sebagai pembalut di sekeliling fungsi TokenSpec asal daripada funcparserlib. Ia memudahkan definisi token dengan menerima nilai daripada Spec Enum kami sebagai hujah spec. Secara dalaman, ia mengekstrak perwakilan rentetan enum (spec.name) dan menghantarnya bersama-sama dengan sebarang argumen lain kepada fungsi TokenSpec asal.

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

Dengan fungsi TokenSpec_ yang dihias, ini membolehkan kami mentakrifkan tokenizer. Kami menggunakan make_tokenizer daripada funcparserlib untuk mencipta tokenizer yang mengambil senarai definisi TokenSpec_. Setiap takrifan menentukan jenis token (daripada Spec ENUM kami) dan ungkapan biasa untuk memadankannya.

from funcparserlib.lexer import TokenSpec

def TokenSpec_(spec: Spec, *args: Any, **kwargs: Any) -> TokenSpec:
    return TokenSpec(spec.name, *args, **kwargs)

Ungkapan biasa OP menggunakan seli (|) untuk memadankan format fungsi yang berbeza. Khususnya:

• mul(?=(d{1,3},d{1,3})): Memadankan mul hanya jika ia diikuti dengan kurungan yang mengandungi dua nombor yang dipisahkan dengan koma. Pernyataan pandang ke hadapan yang positif (?=...) memastikan tanda kurungan dan nombor hadir tetapi tidak digunakan oleh padanan.
• do(?=()): Perlawanan hanya dilakukan jika diikuti dengan kurungan kosong.
• jangan(?=()): Padanan bukan hanya jika diikuti dengan kurungan kosong.

Perwakilan graf bagi ungkapan biasa

Akhir sekali, fungsi tokenize menapis sebarang token GIBBERISH semasa tokenisasi untuk menumpukan pada bahagian input yang berkaitan untuk pemprosesan selanjutnya.

Proses mentafsir kod biasanya melibatkan dua peringkat utama: analisis leksikal (atau lexing) dan penghuraian. Kami telah melaksanakan peringkat pertama: fungsi tokenize kami bertindak sebagai lexer, mengambil rentetan input dan menukarnya menjadi urutan token. Token ini ialah blok binaan asas yang akan digunakan oleh penghurai untuk memahami struktur dan makna kod. Sekarang, mari kita terokai cara penghurai menggunakan token ini.

Melaksanakan parser

Token yang dihuraikan yang dikembalikan oleh fungsi tokenize kemudiannya dihantar ke penghurai untuk diproses selanjutnya. Untuk merapatkan jurang antara Spec Enum kami dan fungsi tok, kami memperkenalkan penghias bernama tok_.

from funcparserlib.lexer import make_tokenizer

def tokenize(input: str) -> tuple[Token, ...]:
    tokenizer = make_tokenizer(
        [
            TokenSpec_(
                Spec.OP, r"mul(?=\(\d{1,3},\d{1,3}\))|do(?=\(\))|don\'t(?=\(\))"
            ),
            TokenSpec_(Spec.NUMBER, r"\d{1,3}"),
            TokenSpec_(Spec.LPAREN, r"\("),
            TokenSpec_(Spec.RPAREN, r"\)"),
            TokenSpec_(Spec.COMMA, r","),
            TokenSpec_(Spec.GIBBERISH, r"[\s\S]"),
        ]
    )

    return tuple(
        token for token in tokenizer(input) if token.type != Spec.GIBBERISH.name
    )

Sebagai contoh, jika kita mempunyai token Spec.NUMBER, penghurai yang dikembalikan akan menerima token dan mengembalikan nilai, seperti berikut:

from funcparserlib.parser import tok

def tok_(spec: Spec, *args: Any, **kwargs: Any) -> Parser[Token, str]:
    return tok(spec.name, *args, **kwargs)

Nilai yang dikembalikan kemudiannya boleh diubah menjadi jenis data yang diingini menggunakan >> operator, seperti yang ditunjukkan di bawah:

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

Lazimnya, amalan terbaik menggunakan ast.literal_eval apabila menghuraikan input yang tidak diketahui untuk mengelakkan potensi kelemahan keselamatan. Walau bagaimanapun, kekangan teka-teki Advent of Code ini—khususnya, bahawa semua nombor adalah integer yang sah—membolehkan kami menggunakan fungsi int yang lebih langsung dan cekap untuk menukar perwakilan rentetan kepada integer.

from funcparserlib.lexer import TokenSpec

def TokenSpec_(spec: Spec, *args: Any, **kwargs: Any) -> TokenSpec:
    return TokenSpec(spec.name, *args, **kwargs)

Kami boleh menentukan peraturan penghuraian untuk menguatkuasakan jujukan token tertentu dan mengubahnya menjadi objek yang bermakna. Sebagai contoh, untuk menghuraikan panggilan fungsi mul, kami memerlukan urutan berikut: kurungan kiri, nombor, koma, nombor lain, kurungan kanan. Kami kemudian menukar jujukan ini menjadi objek Mul:

from funcparserlib.lexer import make_tokenizer

def tokenize(input: str) -> tuple[Token, ...]:
    tokenizer = make_tokenizer(
        [
            TokenSpec_(
                Spec.OP, r"mul(?=\(\d{1,3},\d{1,3}\))|do(?=\(\))|don\'t(?=\(\))"
            ),
            TokenSpec_(Spec.NUMBER, r"\d{1,3}"),
            TokenSpec_(Spec.LPAREN, r"\("),
            TokenSpec_(Spec.RPAREN, r"\)"),
            TokenSpec_(Spec.COMMA, r","),
            TokenSpec_(Spec.GIBBERISH, r"[\s\S]"),
        ]
    )

    return tuple(
        token for token in tokenizer(input) if token.type != Spec.GIBBERISH.name
    )

Peraturan ini menggabungkan penghurai tok_ untuk token yang diperlukan (OP, LPAREN, KOMA, RPAREN) dengan penghurai nombor. Yang >> operator kemudian menukar jujukan yang dipadankan menjadi objek Mul, mengekstrak dua nombor daripada elem tuple pada indeks 2 dan 4.

Kami boleh menggunakan prinsip yang sama untuk mentakrifkan peraturan penghuraian untuk operasi lakukan dan jangan. Operasi ini tidak mengambil hujah (diwakili oleh kurungan kosong) dan diubah menjadi objek Keadaan:

from funcparserlib.parser import tok

def tok_(spec: Spec, *args: Any, **kwargs: Any) -> Parser[Token, str]:
    return tok(spec.name, *args, **kwargs)

Peraturan do mencipta objek Syarat dengan can_proceed = True, manakala peraturan jangan buat satu dengan can_proceed = False.

Akhir sekali, kami menggabungkan peraturan penghuraian individu ini (buat, jangan, dan mul) ke dalam penghurai expr tunggal menggunakan | (atau) pengendali:

>>> from funcparserlib.lexer import Token
>>> number_parser = tok_(Spec.NUMBER)
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
'123'

Penghurai expr ini akan cuba memadankan input dengan setiap peraturan secara bergilir-gilir, mengembalikan keputusan perlawanan pertama yang berjaya.

Penghurai expr kami mengendalikan ungkapan lengkap seperti mul(2,3), lakukan(), dan jangan(). Walau bagaimanapun, input mungkin juga mengandungi token individu yang bukan sebahagian daripada ungkapan berstruktur ini. Untuk mengendalikan perkara ini, kami mentakrifkan penghurai catch-all yang dipanggil segala-galanya:

>>> from funcparserlib.lexer import Token
>>> from ast import literal_eval
>>> number_parser = tok_(Spec.NUMBER) >> literal_eval
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
123

Penghurai ini menggunakan | (atau) pengendali untuk memadankan mana-mana token tunggal jenis NUMBER, LPAREN, RPAREN atau COMMA. Ini pada asasnya satu cara untuk menangkap sebarang token sesat yang bukan sebahagian daripada ungkapan yang lebih besar.

Dengan semua komponen yang ditakrifkan, kami kini boleh menentukan apa yang membentuk program yang lengkap. Program terdiri daripada satu atau lebih "panggilan", dengan "panggilan" ialah ungkapan yang berpotensi dikelilingi oleh token sesat.

Penghurai panggilan mengendalikan struktur ini: ia sepadan dengan sebarang bilangan token sesat (banyak(semuanya)), diikuti dengan satu ungkapan (expr), diikuti dengan sebarang bilangan token sesat tambahan. Fungsi operator.itemgetter(1) kemudian mengekstrak ungkapan yang dipadankan daripada jujukan yang terhasil.

number = tok_(Spec.NUMBER) >> int

Atur cara penuh, yang diwakili oleh penghurai program, terdiri daripada sifar atau lebih panggilan, memastikan keseluruhan input digunakan dengan menggunakan penghurai selesai. Hasil yang dihuraikan kemudiannya ditukar menjadi tuple ungkapan.

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

Akhir sekali, kami mengumpulkan semua definisi ini ke dalam fungsi parse. Fungsi ini mengambil tuple token sebagai input dan mengembalikan tuple ungkapan yang dihuraikan. Semua penghurai ditakrifkan dalam badan fungsi untuk mengelakkan pencemaran ruang nama global dan kerana penghurai nombor bergantung pada fungsi tok_.

from funcparserlib.lexer import TokenSpec

def TokenSpec_(spec: Spec, *args: Any, **kwargs: Any) -> TokenSpec:
    return TokenSpec(spec.name, *args, **kwargs)

Menyelesaikan teka-teki

Dengan penghurai kami tersedia, menyelesaikan Bahagian 1 adalah mudah. Kita perlu mencari semua operasi mul, melakukan pendaraban, dan menjumlahkan hasilnya. Kita mulakan dengan mentakrifkan fungsi penilaian yang mengendalikan ekspresi Mul

from funcparserlib.lexer import make_tokenizer

def tokenize(input: str) -> tuple[Token, ...]:
    tokenizer = make_tokenizer(
        [
            TokenSpec_(
                Spec.OP, r"mul(?=\(\d{1,3},\d{1,3}\))|do(?=\(\))|don\'t(?=\(\))"
            ),
            TokenSpec_(Spec.NUMBER, r"\d{1,3}"),
            TokenSpec_(Spec.LPAREN, r"\("),
            TokenSpec_(Spec.RPAREN, r"\)"),
            TokenSpec_(Spec.COMMA, r","),
            TokenSpec_(Spec.GIBBERISH, r"[\s\S]"),
        ]
    )

    return tuple(
        token for token in tokenizer(input) if token.type != Spec.GIBBERISH.name
    )

Untuk menyelesaikan Bahagian 1, kami tokenize dan menghuraikan input, kemudian gunakan fungsi evaluate_skip_condition yang baru kami tentukan untuk mendapatkan hasil akhir:

from funcparserlib.parser import tok

def tok_(spec: Spec, *args: Any, **kwargs: Any) -> Parser[Token, str]:
    return tok(spec.name, *args, **kwargs)

Untuk Bahagian 2, kita perlu melangkau menilai operasi mul jika syarat tidak telah ditemui. Kami mentakrifkan fungsi penilaian baharu, evaluate_with_condition, untuk mengendalikan perkara ini:

>>> from funcparserlib.lexer import Token
>>> number_parser = tok_(Spec.NUMBER)
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
'123'

Fungsi ini menggunakan pengurangan dengan fungsi pengurang tersuai untuk mengekalkan jumlah berjalan dan bendera boolean (keadaan). Bendera syarat dikemas kini apabila ungkapan Syarat (lakukan atau jangan) ditemui. Ungkapan Mul hanya dinilai dan ditambah pada jumlah jika keadaannya Benar.

Lelaran Sebelumnya

Pada mulanya, pendekatan saya untuk menghurai melibatkan dua pas yang berbeza. Pertama, saya akan tokenize keseluruhan rentetan input, mengumpul semua token tanpa mengira jenisnya. Kemudian, dalam langkah yang berasingan, saya akan melakukan tokenisasi kedua dan menghurai secara khusus untuk mengenal pasti dan memproses operasi mul.

>>> from funcparserlib.lexer import Token
>>> from ast import literal_eval
>>> number_parser = tok_(Spec.NUMBER) >> literal_eval
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
123

Pendekatan yang dipertingkatkan menghapuskan lebihan ini dengan melakukan tokenisasi dan penghuraian dalam satu pas. Kami kini mempunyai satu penghurai yang mengendalikan semua jenis token, termasuk yang berkaitan dengan mul, lakukan, jangan dan token individu lain.

number = tok_(Spec.NUMBER) >> int

Daripada membuat token semula input untuk mencari operasi mul, kami memanfaatkan jenis token yang dikenal pasti semasa tokenisasi awal. Fungsi parse kini menggunakan jenis token ini untuk membina secara langsung objek ekspresi yang sesuai (Mul, Condition, dsb.). Ini mengelakkan pengimbasan berlebihan input dan meningkatkan kecekapan dengan ketara.

Itu melengkapkan pengembaraan penghuraian kami untuk Advent of Code minggu ini. Walaupun siaran ini memerlukan komitmen masa yang ketara, proses menyemak semula dan mengukuhkan pengetahuan saya tentang lexing dan menghurai menjadikannya satu usaha yang berbaloi. Ini adalah teka-teki yang menyeronokkan dan berwawasan, dan saya tidak sabar-sabar untuk menangani cabaran yang lebih kompleks pada minggu-minggu akan datang dan berkongsi pembelajaran saya.

Seperti biasa, terima kasih kerana membaca, dan saya akan menulis lagi, minggu depan.

Atas ialah kandungan terperinci Cara menghuraikan kod komputer, Advent of Code ay 3. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!