Terinspirasi hanya oleh pemahaman parsial tentang PEG, saya memutuskan untuk mencoba mengimplementasikannya. Hasilnya mungkin bukan yang terbaik di antara parser PEG tujuan umum - sudah ada banyak dari mereka (misalnya, TatSu ditulis dalam Python dan menghasilkan kode Python) - tetapi ini adalah cara yang baik untuk memahami PEG. Di masa depan, saya ingin menggantinya dengan implementasi parser saat ini di CPython.
Konten Seri Parser Python PEG Pada bagian ini, saya meletakkan dasar untuk memahami pekerjaan parser, menggunakan contoh implementasi tata bahasa mainan sederhana yang ditulis sendiri dari artikel sebelumnya.
(Ngomong-ngomong, sebagai percobaan, saya tidak menempatkan tautan di teks saya. Jika Anda tidak memahami sesuatu, Anda dapat mencarinya di google. :-)
Biasanya, PEG menggunakan parser keturunan rekursif dengan buffer tak terbatas untuk kembali. Berikut ini adalah tata bahasa mainan dari artikel 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
Pengurai super-abstrak dari keturunan rekursif untuk bahasa ini akan menentukan fungsinya untuk setiap aturan di mana alternatif akan dipahami. Misalnya, untuk statement , kita akan memiliki fungsi ini:
def statement(): if assignment(): return True if expr(): return True if if_statement(): return True return False
Tentu saja, ini adalah contoh yang terlalu sederhana: ia menghilangkan detail penting, misalnya, apa yang dimasukkan ke input fungsi ini dan apa yang akan menjadi hasil dari pelaksanaannya.
Mari kita mulai dengan argumen. Parser klasik menggunakan tokenizer terpisah, yang membagi input (file teks atau baris) menjadi serangkaian token, seperti kata kunci, pengidentifikasi (nama), angka, dan operator. Parser PEG (seperti parser modern lainnya seperti ANTLR) sering menggabungkan tokenization dan parsing, tetapi untuk proyek saya, saya memutuskan untuk meninggalkan tokenizer terpisah.
Tokenisasi python cukup rumit, jadi saya tidak ingin menerapkannya pada aturan PEG. Misalnya, Anda harus melacak lekukan (ini membutuhkan tumpukan di dalam tokenizer); Pemrosesan baris baru dalam Python juga menarik (mereka signifikan, kecuali yang terlampir dalam kurung yang sesuai). Banyak jenis string juga menyebabkan beberapa kompleksitas. Singkatnya, saya tidak punya keluhan tentang tokenizer Python yang ada, jadi saya ingin membiarkannya apa adanya. Omong-omong, CPython memiliki dua tokenizers: yang internal, yang digunakan oleh parser, ditulis dalam C, dan satu library standar, yang merupakan salinan tepat yang diimplementasikan dalam Python murni. Ini akan berguna dalam proyek saya.
Tokenizer klasik biasanya memiliki antarmuka sederhana yang terdiri dari fungsi get_token() tunggal. Setiap kali, itu mengembalikan token berikutnya dalam urutan input, menganalisis sekelompok karakter. Modul tokenize CPython tidak terkecuali: API intinya adalah generator yang mengeluarkan satu token pada satu waktu. Setiap token adalah objek bertipe TypeInfo , yang memiliki beberapa bidang, yang paling penting adalah jenis token (misalnya, NAME , NUMBER , STRING ) dan nilai stringnya adalah himpunan karakter yang terdiri dari (misalnya, abc , 42 atau "Hello, world" ). Ada juga bidang tambahan. Misalnya, untuk indeks token dalam aliran input, yang berguna dalam pesan kesalahan.
Jenis token khusus adalah ENDMARKER , yang menunjukkan bahwa akhir file input telah tercapai. Generator akan jatuh jika Anda mengabaikannya dan mencoba untuk mendapatkan token berikutnya.
Tapi saya terganggu. Bagaimana kita mewujudkan pengembalian tanpa batas? Mengembalikan daftar token mengharuskan Anda untuk mengingat posisi dalam kode sumber dan menganalisis kembali dari titik itu. API tokenizer tidak memungkinkan kami untuk memindahkan penunjuknya, tetapi Anda dapat menangkap aliran token ke dalam array dan memutarnya dari sana, yang akan kami lakukan. Anda juga dapat mengulangi ini dengan itertools.tee() , tetapi ini mungkin kurang efektif dalam kasus kami, jika Anda melihat peringatan dalam dokumentasi.
Saya kira Anda bisa tokenize semua input ke daftar terlebih dahulu, dan kemudian menggunakannya sebagai input ke parser. Tetapi jika ada token yang tidak valid di akhir file (misalnya, sebuah baris dengan kutipan penutup yang hilang) dan ada juga kesalahan sintaksis dalam file, maka Anda akan terlebih dahulu menerima pesan kesalahan dari tokenizer. Saya percaya ini buruk bagi pengguna, karena kesalahan sintaksis dapat menjadi penyebab utama dari garis yang tidak valid. Jadi saya memiliki persyaratan yang sedikit berbeda untuk tokenizer, khususnya, itu harus diimplementasikan sebagai daftar malas.
API inti sangat sederhana. Objek Tokenizer merangkum array token dan posisi dalam array ini. Dia memiliki tiga metode utama:
get_token() mengembalikan token berikutnya, menggerakkan pointer (atau membaca token berikutnya dari sumber, jika kita berada di akhir buffer token);mark() mengembalikan posisi saat ini di buffer;reset(pos) mengatur posisi dalam buffer (argumen harus diperoleh dari mark() ).
Kami menambahkan satu fungsi helper peek_token() , yang mengembalikan token berikutnya tanpa menggeser posisi di buffer.
Beginilah dasar dari kelas Tokenizer :
class Tokenizer: def __init__(self, tokengen): """Call with tokenize.generate_tokens(...).""" self.tokengen = tokengen self.tokens = [] self.pos = 0 def mark(self): return self.pos def reset(self, pos): self.pos = pos def get_token(self): token = self.peek_token() self.pos += 1 return token def peek_token(self): if self.pos == len(self.tokens): self.tokens.append(next(self.tokengen)) return self.tokens[self.pos]
Di sini, sesuatu dihilangkan karena kesederhanaan (misalnya, nama metode dan variabel instan harus dimulai dengan garis bawah), tetapi ini hanyalah prototipe API Tokenizer .
Parser juga harus menjadi kelas sehingga statement() , expr() , dll. dapat diimplementasikan sebagai metode. Tokenizer akan menjadi variabel instan, tetapi saya tidak ingin metode parser untuk langsung memanggil get_token() - sebagai gantinya, kami menerapkan metode wait() di kelas Parser , yang dapat berhasil atau gagal seperti metode parser. Argumen ke fungsi wait() adalah token yang diharapkan: baik string (misalnya, + ) atau jenis token (misalnya, NAME ). Jenis nilai kembalian belum penting, saya akan kembali ke sana setelah membahas hasil pekerjaan parser.
Biarkan fungsi aturan tata bahasa hanya mengembalikan True atau False . Ini bagus untuk ilmu komputer teoretis (ada pengurai menjawab pertanyaan "Apakah ini string yang valid dalam bahasa?"), Tapi tidak untuk kita. Tugas kita adalah membuat AST. Jadi, mari kita menulis ulang kode ini sehingga setiap metode analisis mengembalikan objek Node berhasil atau tidak None yang gagal.
Kelas Node bisa sangat sederhana:
class Node: def __init__(self, type, children): self.type = type self.children = children
Di sini, type menentukan jenis simpul AST (misalnya, add atau if ), dan turunannya adalah daftar simpul dan token (contoh TokenInfo ). Ini cukup bagi kompiler untuk menghasilkan kode atau melakukan analisis lain, seperti pemeriksaan linting atau statis. Meskipun di masa depan saya ingin mengubah cara AST disajikan.
Agar sesuai dengan skema ini, metode expect() harus mengembalikan objek TokenInfo pada kesuksesan dan None pada kegagalan. Untuk dapat memutar kembali ke token sebelumnya, saya membungkus panggilan ke metode mark() dan reset() dari tokenizer (di sini API tidak berubah). Inilah yang terjadi:
class Parser: def __init__(self, tokenizer): self.tokenizer = tokenizer def mark(self): return self.tokenizer.mark() def reset(self, pos): self.tokenizer.reset(pos) def expect(self, arg): token = self.tokenizer.peek_token() if token.type == arg or token.string == arg: return self.tokenizer.get_token() return None
Sekali lagi: Saya menghilangkan beberapa detail, tetapi ini sudah kode yang berfungsi.
Sekarang saya perlu memperkenalkan persyaratan penting untuk metode parser. Setiap orang harus mengembalikan Node , menempatkan tokenizer setelah token terakhir dari aturan tata bahasa yang mereka kenali; baik None dan biarkan posisi tokenizer tidak berubah. Jika metode parser membaca beberapa token dan kemudian jatuh, itu harus mengembalikan posisi tokenizer. Untuk melakukan ini, mark() dan reset() dimaksudkan. Perhatikan bahwa expect() juga mematuhi aturan ini.
Jadi, inilah sketsa parser yang sebenarnya. Di sini saya menggunakan operator walrus dari Python 3.8 ( := ):
class ToyParser(Parser): def statement(self): if a := self.assignment(): return a if e := self.expr(): return e if i := self.if_statement(): return i return None def expr(self): if t := self.term(): pos = self.mark() if op := self.expect("+"): if e := self.expr(): return Node("add", [t, e]) self.reset(pos) if op := self.expect("-"): if e := self.expr(): return Node("sub", [t, e]) self.reset(pos) return t return None def term(self):
Saya menghilangkan penerapan beberapa metode sehingga pembaca memiliki kesempatan untuk berlatih sendiri. Ini benar-benar lebih baik daripada hanya membaca tentang bagaimana parser diimplementasikan. Pada akhirnya, kami akan menghasilkan kode seperti itu secara otomatis dari tata bahasa. Konstanta seperti NAME dan NUMBER diimpor dari modul token pustaka standar. Ini lebih lanjut mengikat kita dengan implementasi tokenizer Python saat ini. Jika kita ingin membuat parser PEG umum, maka kita harus menemukan cara untuk menghindari ini.
Perhatikan juga bahwa saya sedikit tertipu. Metode expr harus dibiarkan rekursif, tapi saya membuat parser benar rekursif karena parser keturunan rekursif tidak bekerja dengan aturan tata bahasa rekursif kiri. Ini dapat diperbaiki, tetapi masih menjadi topik penelitian ilmiah, dan saya ingin membicarakannya secara terpisah. Perlu diingat bahwa implementasi ini tidak 100% konsisten dengan tata bahasa kami yang disederhanakan.
Hal-hal kunci yang saya ingin Anda mengerti sejauh ini:
- Aturan tata bahasa berhubungan dengan metode parser, dan ketika aturan tata bahasa merujuk ke yang lain, itu akan memanggil metode aturan lain.
- Ketika urutan token dapat diartikan berbeda, metode parser yang sesuai dipanggil satu demi satu.
- Ketika aturan tata bahasa merujuk ke token, metode ini memanggil fungsi
expect() . - Jika parser berhasil mengenali aturan tata bahasanya pada posisi saat ini, ia mengembalikan node AST yang sesuai; jika dia tidak bisa mengenali aturan tata bahasanya, dia mengembalikan
None . - Metode Parser harus secara eksplisit mengatur ulang posisi tokenizer ketika mereka berhenti melakukan parsing setelah menggunakan satu atau lebih token (secara langsung atau tidak langsung, menggunakan metode parsing lain yang berhasil). Ini berlaku tidak hanya ketika salah satu opsi ditolak untuk melanjutkan ke yang berikutnya, tetapi juga ketika analisis ditolak secara keseluruhan.
Jika semua metode penguraian mematuhi aturan ini, maka tidak perlu membungkus masing-masing mark() dan reset() panggilan. Ini bisa dibuktikan dengan induksi.
Selain itu, tergoda untuk mencoba menyingkirkan panggilan eksplisit untuk mark() dan reset() menggunakan manajer konteks dan pernyataan with , tetapi itu tidak akan berfungsi: Anda tidak boleh memanggil reset() jika berhasil! Sebagai perbaikan lebih lanjut, Anda dapat mencoba menggunakan pengecualian untuk aliran kontrol sehingga manajer konteks tahu apakah tokenizer harus diatur ulang (saya pikir TatSu melakukan hal yang serupa). Misalnya, sesuatu seperti ini:
def statement(self): with self.alt(): return self.assignment() with self.alt(): return self.expr() with self.alt(): return self.if_statement() raise ParsingFailure
Secara khusus, tangga kecil if dalam atom() untuk mengenali ekspresi dalam tanda kurung dapat ditulis sebagai:
with self.alt(): self.expect("(") e = self.expr() self.expect(")") return e
Tapi menurut saya terlalu "ajaib" - ketika membaca kode seperti itu, Anda harus ingat bahwa setiap metode parsing (termasuk wait() ) dapat memberikan pengecualian. Dan bahwa pengecualian ini ditangkap dan diabaikan oleh manajer konteks dalam pernyataan with . Ini agak tidak biasa, meskipun dapat diwujudkan (dengan mengembalikan True dari __exit__ ). Namun, tujuan akhir saya adalah untuk menghasilkan kode dalam C, bukan Python, dan dalam C tidak ada pernyataan untuk mengubah aliran kontrol.
Bagaimanapun, berikut adalah beberapa topik untuk bagian-bagian berikut:
- generasi metode parser dari tata bahasa;
- packrat-parsing (memoization);
- Fitur EBNF seperti
(x | y) , [xy ...] , x* , x+ ; - tracing (untuk men-debug parser atau tata bahasa);
- Fitur PEG seperti lookahead and cut;
- bagaimana menangani aturan rekursif kiri;
- Pembuatan kode C
Lisensi untuk artikel ini dan kode yang dikutip: CC BY-NC-SA 4.0