Sekarang saya telah membuat sketsa dasar-dasar parser berpemilik, mari beralih ke menghasilkan metodenya dari tata bahasa, seperti yang saya janjikan. Saya juga akan menunjukkan bagaimana menerapkan parser packrat menggunakan dekorator @memoize .
Konten Seri Parser Python PEG Terakhir kali, kami melihat beberapa metode parser. Dengan beberapa batasan yang akan kami hapus sedikit kemudian, mereka mudah dihasilkan dari tata bahasa secara otomatis.
Kami membutuhkan dua hal: sesuatu yang membaca tata bahasa dan membangun struktur data yang sesuai; dan sesuatu yang mengambil struktur data ini dan menghasilkan parser. Kami juga membutuhkan metode pembantu lain, tetapi mereka tidak menarik, jadi saya akan menghilangkannya.
Jadi, kami membuat kompiler kompiler sederhana. Saya akan sedikit menyederhanakan notasi tata bahasa sejauh kita hanya memiliki aturan dan alternatif; ini sebenarnya cukup untuk tata bahasa mainan yang saya gunakan di bagian sebelumnya:
statement: assignment | expr | if_statement expr: expr '+' term | expr '-' term | term term: term '*' atom | term '/' atom | atom atom: NAME | NUMBER | '(' expr ')' assignment: target '=' expr target: NAME if_statement: 'if' expr ':' statement
Menggunakan notasi penuh, kita dapat menggambarkan tata bahasa sebagai:
grammar: rule+ ENDMARKER rule: NAME ':' alternative ('|' alternative)* NEWLINE alternative: item+ item: NAME | STRING
Ini adalah meta-grammar pertama kami (tata bahasa untuk tata bahasa), dan generator parser kami akan menjadi kompiler meta (kompiler adalah program yang menerjemahkan program dari satu bahasa ke bahasa lain; meta-kompiler adalah kompiler di mana inputnya adalah tata bahasa, dan outputnya adalah parser).
Cara mudah untuk menggambarkan tata bahasa meta adalah dengan hanya menggunakan tipe data bawaan: sisi kanan aturan adalah daftar daftar elemen, yang masing-masing dapat berupa string. (Omong-omong, kami dapat memisahkan NAME dan STRING dengan memeriksa apakah karakter pertama adalah tanda kutip)
Untuk aturan, saya menggunakan kelas Rule sederhana, dan seluruh tata bahasa adalah daftar objek seperti itu. Ini adalah kelas Rule , tidak termasuk __repr__ dan __eq__ :
class Rule: def __init__(self, name, alts): self.name = name self.alts = alts
Dan di sini adalah kelas GrammarParser yang menggunakannya:
class GrammarParser(Parser): def grammar(self): pos = self.mark() if rule := self.rule(): rules = [rule] while rule := self.rule(): rules.append(rule) if self.expect(ENDMARKER): return rules
Perhatikan penggunaan ENDMARKER . Di sana saya memastikan bahwa tidak ada yang tersisa setelah aturan terakhir (dan ini bisa terjadi jika ada kesalahan ketik dalam tata bahasa). Saya juga menunjuk ke tempat di mana metode grammar() mengembalikan daftar aturan. Segala sesuatu yang lain sangat mirip dengan kelas ToyParser dari artikel terakhir, jadi saya tidak akan memikirkannya. Hanya perhatikan bahwa item() mengembalikan string, alternative() mengembalikan daftar string, dan variabel alts di dalam rule() mengumpulkan daftar daftar string. Kemudian, metode rule() menggabungkan nama aturan (string) dan mengubahnya menjadi objek Rule .
Jika kami menerapkan algoritma ini ke tata bahasa mainan kami, maka metode grammar() akan mengembalikan daftar aturan berikut:
[ Rule('statement', [['assignment'], ['expr'], ['if_statement']]), Rule('expr', [['term', "'+'", 'expr'], ['term', "'-'", 'term'], ['term']]), Rule('term', [['atom', "'*'", 'term'], ['atom', "'/'", 'atom'], ['atom']]), Rule('atom', [['NAME'], ['NUMBER'], ["'('", 'expr', "')'"]]), Rule('assignment', [['target', "'='", 'expr']]), Rule('target', [['NAME']]), Rule('if_statement', [["'if'", 'expr', "':'", 'statement']]), ]
Sekarang kita memiliki bagian parsing dari kompiler meta kita, mari kita membuat generator kode. Bersama-sama mereka membentuk kompiler meta dasar:
def generate_parser_class(rules): print(f"class ToyParser(Parser):") for rule in rules: print() print(f" @memoize") print(f" def {rule.name}(self):") print(f" pos = self.mark()") for alt in rule.alts: items = [] print(f" if (True") for item in alt: if item[0] in ('"', "'"): print(f" and self.expect({item})") else: var = item.lower() if var in items: var += str(len(items)) items.append(var) if item.isupper(): print(" " + f"and ({var} := self.expect({item}))") else: print(f" " + f"and ({var} := self.{item}())") print(f" ):") print(f" " + f"return Node({rule.name!r}, [{', '.join(items)}])") print(f" self.reset(pos)") print(f" return None")
Kode ini cukup jelek, tetapi berhasil (semacam), dan di masa depan saya akan menulis ulang.
Beberapa baris di dalam for alt in rule.alts mungkin memerlukan penjelasan: untuk setiap elemen dalam alternatif, kami memilih satu dari 3 opsi:
- jika elemen tersebut adalah string literal, misalnya
'+' , kami menghasilkan self.expect('+') - jika elemen huruf besar sepenuhnya, misalnya
NAME , kami menghasilkan (name := self.expect(NAME)) - jika tidak, misalnya, jika
expr , kami menghasilkan (expr := self.expr())
Jika ada beberapa elemen dengan nama yang sama dalam satu varian (misalnya, term '-' term ), maka kami menambahkan digit ke yang kedua. Ada juga kesalahan kecil di sini yang akan saya koreksi di episode berikutnya.
Ini sedikit hasil karyanya (seluruh kelas akan sangat membosankan). Jangan khawatir tentang redundan if (True and ... ) kode yang diperlukan sehingga setiap kondisi yang dihasilkan dapat dimulai dengan and . Kompiler byte Python mengoptimalkan ini.
class ToyParser(Parser): @memoize def statement(self): pos = self.mark() if (True and (assignment := self.assignment()) ): return Node('statement', [assignment]) self.reset(pos) if (True and (expr := self.expr()) ): return Node('statement', [expr]) self.reset(pos) if (True and (if_statement := self.if_statement()) ): return Node('statement', [if_statement]) self.reset(pos) return None ...
Perhatikan dekorator @memoize : Saya memperkenalkannya untuk beralih ke topik lain: menggunakan memoisasi untuk membuat parser yang dihasilkan cukup cepat.
Berikut adalah fungsi memoize() yang mengimplementasikan dekorator ini:
def memoize(func): def memoize_wrapper(self, *args): pos = self.mark() memo = self.memos.get(pos) if memo is None: memo = self.memos[pos] = {} key = (func, args) if key in memo: res, endpos = memo[key] self.reset(endpos) else: res = func(self, *args) endpos = self.mark() memo[key] = res, endpos return res return memoize_wrapper
Seperti pada dekorator lainnya, ini berisi fungsi bersarang yang menggantikan (atau membungkus) fungsi yang didekorasi, misalnya, metode statement() dari kelas ToyParser . Karena fungsi yang dibungkus adalah sebuah metode, wrapper sebenarnya juga adalah sebuah metode: argumen pertamanya disebut self dan merujuk ke instance ToyParser yang disebut metode yang didekorasi.
Wrapper melakukan cache hasil dari pemanggilan metode untuk setiap posisi input - inilah mengapa ini disebut pengurai packrat! [sekitar trans. packrat adalah "pencuri," tetapi istilah ini tidak diterjemahkan dalam sumber berbahasa Rusia.] Cache adalah kamus kamus, yang disimpan dalam contoh Parser . Kunci kamus eksternal adalah posisi dalam aliran data input; Saya juga menambahkan self.memos = {} ke Parser .__ init__() untuk menginisialisasi. Kamus internal ditambahkan sesuai kebutuhan; kunci mereka terdiri dari metode dan argumennya. (Tidak ada argumen dalam desain saat ini, tetapi kami dapat memoisasi fungsi expect() yang memiliki satu, yang cukup sepele)
Hasil dari metode parser disajikan dalam bentuk tuple, karena sebenarnya ada dua nilai: hasil itu sendiri (untuk metode yang kami hasilkan, ini adalah Node untuk aturan yang cocok) dan sebuah penunjuk ke posisi saat ini di aliran input, yang kami dapatkan dari self.mark() . Dengan demikian, kami menyimpan nilai kembalian ( res ) dan posisi baru ( endpos ) dalam kamus internal dengan nilai yang di-memo. Pada panggilan selanjutnya ke metode parsing yang sama dengan argumen yang sama di posisi input yang sama, kami akan mengambilnya dari cache. Untuk melakukan ini, cukup gerakkan pointer ke posisi input menggunakan self.reset() dan lihat di cache.
Penting juga untuk men-cache hasil negatif - pada kenyataannya, sebagian besar panggilan akan negatif. Dalam hal ini, nilai kembali adalah None , dan posisi input tidak berubah. Anda dapat menambahkan assert untuk memeriksa ini.
Catatan Dalam Python, sudah biasa menerapkan cache dalam variabel lokal di fungsi memoize() . Dalam kasus kami, ini tidak akan berfungsi: seperti yang saya temukan di akhir debugging, setiap instance Parser harus memiliki cache sendiri. Namun, Anda dapat menyingkirkan kamus bersarang dengan menggunakan ( pos , func , args ) sebagai kuncinya.
Minggu depan saya akan menyiapkan kode dan jejak untuk menunjukkan bagaimana semua ini sebenarnya dirakit dan dieksekusi ketika mem-parsing contoh program. Saya masih mencari cara yang lebih baik untuk memvisualisasikan kolaborasi buffer tokenization, parser dan cache. Mungkin saya akan dapat membuat animasi gif di ASCII alih-alih hanya menampilkan daftar jejak sebagai teks.
Lisensi untuk artikel ini dan kode yang dikutip: CC BY-NC-SA 4.0