Tata bahasanya bahkan lebih baik jika Anda dapat menambahkan (beberapa) semantik sesuai aturan. Khususnya, untuk penganalisis Python yang saya kembangkan, saya perlu mengembalikan simpul AST dari setiap alternatif, karena saya ingin tetap menggunakan implementasi AST saat ini di CPython.
Konten Seri Parser Python PEG Banyak tata bahasa menggunakan konvensi yang memungkinkan Anda untuk menambahkan tindakan ke aturan - biasanya satu blok kode di dalam {kurung kurawal}. Lebih tepatnya, mereka terikat dengan alternatif. Kode dalam blok ini ditulis dalam bahasa yang sama dengan sisa kompiler, misalnya, dalam C, ditambah dengan beberapa kemampuan untuk merujuk ke elemen-elemen dalam alternatif. Dalam pgen Python asli, saya tidak menambahkan fungsi ini, tetapi untuk proyek baru saya ingin mengimplementasikannya.
Inilah cara kami melakukannya untuk generator parser sederhana yang saya kembangkan sebagai bagian dari seri posting ini.
Sintaks untuk tindakan biasanya ini:
rule: item item item { action 1 } | item item { action 2 }
Karena ini membuat tata bahasa lebih verbose, generator parser biasanya memungkinkan aturan multi-line, misalnya:
rule: item item item { action 1 } | item item { action 2}
Ini membuat parser sedikit lebih rumit, tetapi penting untuk keterbacaan, jadi saya akan mendukung catatan semacam itu.
Pertanyaan abadi adalah kapan harus menjalankan blok ini. Di Yacc / Bison, ini dilakukan segera setelah parser mengenali aturan, karena tidak ada rollback dalam daftar token. Menjalankan setiap tindakan tepat sekali berarti bahwa mungkin ada efek samping global (seperti memperbarui tabel simbol atau struktur data kompilator lain).
Dalam pengurai PEG dengan pengembalian tanpa batas ke daftar token, kami memiliki beberapa opsi:
- Jangan melakukan tindakan apa pun sampai semuanya telah dianalisis. Saya tidak akan mempertimbangkan ini, karena saya ingin membangun hak AST selama parsing.
- Lakukan kapan saja alternatifnya diakui. Kode mereka harus idempoten (mis., Memiliki efek yang sama tidak peduli berapa kali telah dieksekusi). Ini berarti bahwa tindakan dapat dieksekusi, tetapi hasilnya pada akhirnya dapat dibuang.
- Tembolok hasilnya dan lakukan tindakan hanya untuk pertama kali - ketika alternatifnya dikenali pada posisi ini.
Saya memilih opsi ketiga - dalam hal apa pun, kami menyimpan hasil dari metode ini menggunakan algoritma packrat, jadi kami juga dapat menyimpan hasilnya.
Adapun konten dalam {curlies}, menurut tradisi menggunakan kode C dengan kesepakatan berdasarkan $ untuk merujuk ke elemen dalam alternatif yang dikenal (misalnya, $1 untuk merujuk ke elemen pertama) dan penugasan $$ untuk menunjukkan hasil tindakan. Kedengarannya sangat kuno (saya memiliki kenangan menggunakan penugasan fungsi di Algol-60 untuk menunjukkan nilai kembali), jadi saya akan membuatnya lebih Pythonic: di dalam tanda kurung Anda harus meletakkan satu ekspresi, yang hasilnya akan menjadi hasil dari tindakan, dan tautan ke elemen akan menjadi nama-nama sederhana yang memberikan teks elemen. Sebagai contoh, berikut ini adalah kalkulator sederhana yang dapat menambah dan mengurangi angka:
start: expr NEWLINE { expr } expr: expr '+' term { expr + term } | expr '-' term { expr - term } | term { term } term: NUMBER { float(number.string) }
Mari kita jalankan pada contoh 100 + 50 - 38 - 70 . Dia akan menghitung jawabannya, karena ia mengenali bagian-bagian itu dengan menghitung ((100 + 50) - 38) - 70 , yang tentu saja 42 .
Satu detail kecil: dalam aksi untuk term number variabel berisi objek TokenInfo , jadi Anda perlu menggunakan atribut .string untuk mendapatkan token dalam bentuk string.
Apa yang kita lakukan ketika alternatif memiliki beberapa kejadian dengan nama aturan yang sama? Generator parser memberikan nama unik setiap kejadian, menambahkan 1 , 2 , dll. Untuk kejadian selanjutnya dalam alternatif yang sama. Sebagai contoh:
factor: atom '**' atom { atom ** atom1 } | atom { atom }
Implementasi penuhnya agak membosankan, jadi saya tidak ingin memikirkannya. Saya mengundang Anda untuk melihat ke repositori saya dan bermain dengan kode :
python3.8 -m story5.driver story5/calc.txt -g story5.calc.CalcParser
Visualisasi sekarang memungkinkan Anda untuk bergerak maju dan mundur menggunakan tombol panah kiri dan kanan!
Lisensi untuk artikel ini dan kode yang dikutip: CC BY-NC-SA 4.0