Parser adalah program yang membantu memproses teks. Compiler dan interpreter menggunakan parser untuk menganalisis program sebelum memprosesnya lebih lanjut, dan parser untuk format seperti JSON dan YAML memproses teks ke dalam struktur data asli bahasa pemrograman.
Dalam artikel ini, kita akan melihat bagaimana membangun "parser keturunan rekursif". Pengurai turunan rekursif adalah cara sederhana namun ampuh untuk membangun pengurai — untuk setiap "entitas" dalam teks yang ingin Anda proses, Anda mendefinisikan sebuah fungsi.
Pertama, kita akan melihat beberapa teori yang mendasari parsing. Kemudian, kami menggunakan Python, kami akan membuat kalkulator dan parser JSON yang mendukung komentar, tanda koma, dan string yang tidak dikutip. Terakhir, kita akan membahas bagaimana Anda dapat membuat parser untuk jenis bahasa lain yang berperilaku berbeda dari contoh yang disebutkan di atas.
Jika Anda sudah terbiasa dengan teorinya, Anda bisa langsung melompat ke bagian tempat kami membuat parser.
Isi
- 1 Bagaimana cara kerja penguraian?
- 2 Menulis aturan produksi
- 3 Pertimbangan saat membuat parser
- 3.1 Menangani prioritas dalam tata bahasa
- 3.2 Menghindari rekursi kiri
- 3.3 Menghindari mundur
- 4 Membangun basis untuk Recursive Descent Parser dengan Python
- 4.1 Kelas pengecualian
- 4.2 Kelas Parser dasar
- 4.3 Memproses rentang karakter
- 4.4 Mengekstrak karakter dari teks
- 4.5 Mengekstrak kata kunci dan simbol
- 4.6 Pembantu untuk mencocokkan beberapa produksi
- 4.7 Melihat ke depan pada apa yang berikutnya – fungsi pembantu
- 5 Contoh pengurai pertama:kalkulator
- 5.1 Aturan produksi untuk tata bahasa kalkulator
- 5.2 Menerapkan pengurai
- 5.3 Mengenal angka
- 5.4 Antarmuka untuk parser kami
- 6 Contoh pengurai kedua:pengurai JSON “diperpanjang”
- 6.1 Aturan produksi untuk tata bahasa JSON
- 6.2 Menerapkan parser dan menangani komentar
- 6.3 Mengurai daftar dan peta
- 6.4 Mengenali null dan boolean
- 6.5 Mengenali string dan angka yang tidak dikutip
- 6.6 Mengenali string yang dikutip
- 6.7 Antarmuka untuk parser JSON kami
- 7 Membangun parser jenis lain
- 7.1 Bahasa sensitif spasi putih
- 7.2 Indentasi berbasis spasi
Bagaimana cara kerja penguraian?
Untuk memproses sepotong teks, sebuah program melakukan tiga tugas. Dalam proses yang disebut "lexing" atau "tokenization", program melewati karakter dalam teks, dan mengekstrak grup logis yang disebut "token". Misalnya, dalam ekspresi seperti “3 + 5 – 10”, program untuk memproses ekspresi aritmatika dapat mengekstrak token berikut:
[{ "Type": "Number" , "Text": "3" },
{ "Type": "Operator", "Text": "+" },
{ "Type": "Number" , "Text": "5" },
{ "Type": "Operator", "Text": "-" },
{ "Type": "Number" , "Text": "10" }] Program kemudian menggunakan aturan untuk mengidentifikasi urutan token yang berarti, dan ini disebut "parsing". Aturan yang digunakan untuk mewujudkan hal ini disebut “tata bahasa” — sama seperti kata-kata dalam bahasa alami seperti bahasa Inggris dirangkai menjadi urutan yang bermakna menggunakan tata bahasa Inggris. Aturan tata bahasa individu disebut “produksi”.
Bayangkan kita sedang membangun program untuk memproses ekspresi matematika, dan kita hanya tertarik pada penjumlahan dan pengurangan. Ekspresi harus memiliki angka (seperti “3”), diikuti oleh sejumlah operator dan angka (seperti “+ 5” ). Aturan parsing dapat divisualisasikan seperti ini:
Ini menunjukkan bahwa grup dapat mengulang beberapa kali (termasuk nol).
Akhirnya, program mengambil serangkaian tindakan untuk aturan tata bahasa. Misalnya, setelah penguraian, program matematika kita perlu menghitung nilai ekspresi.
Meskipun kami telah menggambarkan ini sebagai langkah terpisah, sebuah program dapat melakukan semua ini sekaligus. Melakukan semua langkah sekaligus membawa beberapa keuntungan, dan inilah pendekatan yang akan kita ambil dalam artikel ini.
Menulis aturan produksi
Melalui sisa artikel ini, kita akan menggunakan aturan produksi untuk memvisualisasikan tata bahasa. Oleh karena itu, kami telah menjelaskan bagaimana kami menulis aturan produksi di seluruh artikel ini. Jika sebelumnya Anda telah membaca buku teks tentang penguraian, notasi yang kami gunakan di sini sedikit berbeda.
Sebelumnya, kita telah melihat contoh produksi sederhana. Ketika aturan tata bahasa berisi nama token, dan tokennya cukup sederhana, biasanya teks token ditulis dalam tata bahasa. Jika kita perhatikan contoh sebelumnya, menghasilkan + atau - , jadi kita bisa menulis ulang aturannya seperti ini:
Kami juga telah melihat bagaimana kami dapat menggunakan untuk menunjukkan bahwa sesuatu berulang beberapa kali. Demikian pula, a menunjukkan bahwa sesuatu berulang, tetapi itu harus terjadi setidaknya sekali. A menunjukkan sesuatu yang opsional.
Sebagai contoh, misalkan kita sedang membangun parser untuk memproses daftar kondisi, seperti “x> 10 dan y> 30”. Asumsikan bahwa and adalah opsional, jadi kita bisa menulis ulang kondisi ini sebagai “x> 10 y> 30”. Anda dapat merancang tata bahasa untuk hal di atas seperti ini:
Ketika ada beberapa alternatif, urutan alternatif penting. Untuk aturan seperti , kita harus mencoba mencocokkan "+" terlebih dahulu, lalu "-". Meskipun dalam contoh sepele ini mungkin tampak bahwa ketertiban tidak penting, kita akan melihat contoh nanti di mana ketertiban menjadi penting.
Terakhir, aturan produksi hanya berfokus pada token dan simbol tata bahasa lainnya — aturan ini mengabaikan spasi dan komentar.
Pertimbangan saat membuat parser
Sebelumnya, kita telah melihat beberapa tata bahasa sederhana. Namun, ketika mencoba menguraikan sesuatu yang lebih kompleks, sejumlah masalah dapat muncul. Kita akan membahasnya di sini.
Menangani prioritas dalam tata bahasa
Sebelumnya, kita telah melihat tata bahasa yang dapat menangani ekspresi matematika yang terdiri dari penambahan dan pengurangan. Sayangnya, Anda tidak dapat memperluas tata bahasa yang sama untuk perkalian (dan pembagian), karena operasi tersebut memiliki prioritas lebih tinggi daripada penambahan (dan pengurangan).
Untuk menangani skenario ini, kita harus mendesain tata bahasa kita sehingga parser menunda setiap penambahan, tetapi melakukan perkalian segera setelah ditemukan. Untuk mencapai ini, kami membagi tata bahasa menjadi dua aturan terpisah, seperti yang ditunjukkan di bawah ini:
Mari kita ambil ekspresi (seperti "3 + 2 * 5") untuk memastikan bahwa ini benar-benar berfungsi. Kami akan berasumsi bahwa setelah parser kami selesai mencocokkan aturan tata bahasa, itu secara otomatis menghitung ekspresi. Kami juga akan menggunakan teks yang digarisbawahi untuk menunjukkan apa yang dicari parser. Selain itu, kami juga menghilangkan tanda kutip untuk kejelasan.
Ketika 2 * 5 diuraikan, pengurai segera mengembalikan hasil 10. Hasil ini diterima pada langkah, dan penambahan dilakukan di akhir, menghasilkan 13 sebagai hasilnya.
Singkatnya, Anda harus mengatur aturan sehingga operator dengan prioritas terendah berada di atas, sedangkan operator dengan prioritas tertinggi berada di bawah.
Menghindari rekursi kiri
Sebelumnya, kami telah menyebutkan bahwa parser keturunan rekursif terdiri dari fungsi yang memproses "entitas" dalam teks. Sekarang setelah kita mengetahui tentang token dan aturan produksi, mari kita definisikan ulang ini sedikit lebih formal:setiap fungsi dalam parser mengekstrak token, atau mengimplementasikan logika aturan produksi.
Mari kita ambil tata bahasa sederhana, seperti untuk melihat apa artinya ini sebenarnya. Jika Anda menulis kode semu untuk tata bahasa ini, akan terlihat seperti ini:
def expression():
first_number = number()
read('+')
second_number = number()
# process these two numbers, e.g. adding them
Selanjutnya, pertimbangkan tata bahasa yang mem-parsing daftar angka yang dipisahkan koma. Anda biasanya menulisnya sebagai:
Sekarang, bayangkan bahwa untuk beberapa alasan, Anda ingin menghindari wildcard dan menulis ulang seperti ini:
Tata bahasa ini secara teoritis benar — baik memilih satu nomor dari teks, atau diperluas ke daftar dengan nomor di akhir. Daftar kedua, pada gilirannya, dapat diperluas ke nomor atau daftar lain, hingga pengurai selesai melalui teks.
Namun, ada masalah dengan pendekatan ini — Anda akan memasuki rekursi tak terbatas! Jika Anda mencoba memanggil list() berfungsi sekali, Anda akhirnya memanggilnya lagi, dan seterusnya. Anda mungkin berpikir bahwa menulis ulang tata bahasa mungkin bisa membantu. Namun, jika Anda mencoba menulis suatu fungsi, Anda akan membaca satu angka dan berhenti menguraikan. Angka yang Anda baca mungkin merupakan bagian dari daftar seperti “2, 4, 6” dan Anda tidak akan dapat membaca angka lainnya.
Ketika berhadapan dengan parsing, ini disebut rekursi kiri. Kasus yang kita lihat di atas melibatkan "rekursi kiri langsung", tetapi ada juga "rekursi kiri tidak langsung", di mana A memanggil B, B memanggil A dan seterusnya. Dalam kedua kasus tersebut, Anda harus menulis ulang tata bahasa dengan cara lain untuk menghindari masalah ini.
Menghindari pelacakan mundur
Misalkan, Anda mencoba membuat pengurai yang mengurai operasi dua angka, seperti “2 + 4”, dan menulis tata bahasa dengan cara ini:
Tata bahasa ini benar, dan juga akan berperilaku seperti yang Anda harapkan dan menghasilkan hasil yang benar. Namun, tata bahasa ini bukanlah yang ingin Anda gunakan.
Untuk melihat mengapa hal ini terjadi, pertimbangkan string input “5 – 2”. Pertama-tama kita akan menggunakan aturan penambahan, dan mengurai angka. Kemudian, kami mengharapkan "+" tetapi ketika membaca string, kami akan mendapatkan "-" yang berarti kami harus mundur dan menerapkan aturan pengurangan. Dengan demikian, kami telah membuang waktu dan siklus CPU untuk menguraikan angka, hanya untuk membuangnya dan menguraikannya lagi sebagai bagian dari aturan pengurangan.
Selain itu, saat membuat parser yang langsung bekerja di luar aliran data, seperti soket jaringan, memundurkan aliran sering kali bukan pilihan. Dalam artikel ini, kita hanya akan membahas parser yang memiliki semua teks dalam memori. Namun demikian, ini adalah praktik yang baik untuk menghindari mundur dan untuk melakukannya, Anda harus memfaktorkan bagian umum dari kiri. Ini adalah bagaimana aturan kita akan terlihat setelah pemfaktoran:
Langkah pemfaktoran selesai dan akan menghindari backtracking. Namun, untuk alasan estetika, kami hanya akan menulisnya sebagai:
Membangun basis untuk Recursive Descent Parser dengan Python
Sekarang setelah kita membahas berbagai pertimbangan untuk penguraian, kita akan membuat kalkulator dan pengurai JSON. Namun, sebelum melakukannya, kita akan menulis kelas dasar “Parser” yang memiliki beberapa metode untuk fungsi umum, seperti mengenali karakter dan menangani kesalahan.
Bagian ini mungkin tampak agak terlalu panjang, tetapi itu sepadan dengan kesabaran. Setelah menyelesaikan bagian ini, Anda akan memiliki semua alat untuk membuat parser kompleks dengan sedikit kode yang diperlukan untuk mengenali token dan menerapkan aturan produksi.
Kelas pengecualian
Karena ini adalah tugas termudah sejauh ini, jadi kami akan menangani ini terlebih dahulu. Kami akan mendefinisikan kelas pengecualian kami sendiri bernama ParseError seperti ini:
class ParseError(Exception):
def __init__(self, pos, msg, *args):
self.pos = pos
self.msg = msg
self.args = args
def __str__(self):
return '%s at position %s' % (self.msg % self.args, self.pos)
Kelas menerima posisi teks di mana kesalahan terjadi, pesan kesalahan (sebagai string format), dan argumen ke string format. Mari kita lihat bagaimana Anda dapat menggunakan jenis pengecualian ini:
e = ParseError(13, 'Expected "{" but found "%s"', "[") Saat Anda mencoba mencetak pengecualian, Anda akan mendapatkan pesan berformat seperti ini:
Expected "{" but found "[" at position 13
Perhatikan bahwa kami belum menggunakan % simbol dalam string format dan argumennya (seperti '"Expected "{" but found "%s"' % "[" ). Ini ditangani di __str__ metode kelas, tempat kami memformat self.msg dengan elemen di self.pos .
Sekarang, Anda mungkin bertanya, mengapa kami ingin memformatnya dalam __str__ metode, alih-alih menulisnya dengan % ? Ternyata menggunakan % operator untuk memformat string membutuhkan waktu yang cukup lama. Saat mengurai string, akan ada banyak pengecualian yang muncul saat pengurai mencoba menerapkan berbagai aturan. Oleh karena itu, kami telah menangguhkan pemformatan string saat benar-benar dibutuhkan.
Kelas Parser dasar
Sekarang kita memiliki kelas kesalahan, langkah selanjutnya adalah menulis kelas parser. Kami akan mendefinisikannya sebagai berikut:
class Parser:
def __init__(self):
self.cache = {}
def parse(self, text):
self.text = text
self.pos = -1
self.len = len(text) - 1
rv = self.start()
self.assert_end()
return rv
Di sini, Anda akan melihat cache anggota di __init__ metode — kita akan kembali membahas mengapa ini diperlukan saat kita membahas pengenalan karakter.
parse metode ini cukup sederhana — pertama, ia menyimpan string. Karena kami belum memindai bagian mana pun dari string, kami akan mengatur posisinya ke -1. Selain itu, kami akan menyimpan indeks maksimum string di self.len . (Indeks maksimum selalu kurang dari satu panjang string.)
Selanjutnya, kita akan mulai mengurai string dan memeriksa apakah kita telah mencapai akhir string. Ini untuk memastikan bahwa parser kami dapat memproses seluruh teks tanpa ada yang tersisa di akhir. Setelah ini, kami mengembalikan hasilnya.
assert_end metodenya sederhana:kami akan memeriksa apakah posisi saat ini kurang dari indeks maksimum. Ingatlah bahwa metode ini ada di dalam kelas, meskipun kami telah menghilangkan lekukan untuk kesederhanaan.
def assert_end(self):
if self.pos < self.len:
raise ParseError(
self.pos + 1,
'Expected end of string but got %s',
self.text[self.pos + 1]
)
Di seluruh parser, kita akan melihat karakter yang satu lebih banyak dari indeks saat ini (self.pos ). Untuk mengetahui mengapa hal ini terjadi, pertimbangkan untuk memulai dengan self.pos = -1 , jadi kita akan melihat indeks 0. Setelah kita berhasil mengenali karakter, self.pos pergi ke 0 dan kita akan melihat karakter pada indeks 1, dan seterusnya. Inilah sebabnya mengapa kesalahan menggunakan self.pos + 1 .
Dengan sebagian besar bahasa, spasi di antara token dapat dibuang dengan aman. Oleh karena itu, tampaknya logis untuk menyertakan metode yang memeriksa apakah karakter berikutnya adalah karakter spasi putih, dan jika demikian, "buang" dengan maju ke posisi berikutnya.
def eat_whitespace(self):
while self.pos < self.len and self.text[self.pos + 1] in " fvrtn":
self.pos += 1
Memproses rentang karakter
Sekarang, kita akan menulis sebuah fungsi untuk membantu kita mengenali karakter dalam teks. Sebelum kita melakukannya, kita akan mempertimbangkan fungsi kita dari sudut pandang pengguna — kita akan memberinya satu set karakter untuk dicocokkan dari teks. Misalnya, jika Anda ingin mengenali alfabet atau garis bawah, Anda dapat menulis sesuatu seperti:
self.char('A-Za-z_')
Kami akan memberikan char metode yang berisi daftar karakter atau rentang (seperti A-Z dalam contoh di atas). Rentang dilambangkan melalui dua karakter yang dipisahkan oleh - . Karakter pertama memiliki nilai numerik yang lebih kecil daripada karakter di sebelah kanan.
Sekarang, jika karakter di self.text[self.pos + 1] cocok dengan sesuatu dalam argumen self.char , kami akan mengembalikannya. Jika tidak, kami akan mengajukan pengecualian.
Secara internal, kami akan memproses string menjadi sesuatu yang lebih mudah ditangani — daftar dengan karakter atau rentang terpisah seperti ['A-Z', 'a-z', '_'] . Jadi, kami akan menulis fungsi untuk membagi rentang:
def split_char_ranges(self, chars):
try:
return self.cache[chars]
except KeyError:
pass
rv = []
index = 0
length = len(chars)
while index < length:
if index + 2 < length and chars[index + 1] == '-':
if chars[index] >= chars[index + 2]:
raise ValueError('Bad character range')
rv.append(chars[index:index + 3])
index += 3
else:
rv.append(chars[index])
index += 1
self.cache[chars] = rv
return rv
Di sini, kita mengulang melalui chars string, mencari - diikuti oleh karakter lain. Jika kondisi ini cocok dan karakter pertama lebih kecil dari yang terakhir, kami menambahkan seluruh rentang (seperti A-Z ) ke daftar rv . Jika tidak, kami menambahkan karakter di chars[index] ke rv .
Kemudian, kami menambahkan daftar di rv itu ke cache. Jika kami melihat string ini untuk kedua kalinya, kami akan mengembalikannya dari cache menggunakan try ... except KeyError: ... blok di bagian atas.
Memang, kita bisa saja memberikan daftar seperti ['A-Z', 'a-z', '_'] ke char metode. Namun, menurut kami, melakukannya dengan cara ini membuat panggilan ke char() terlihat sedikit lebih bersih.
Mengekstrak karakter dari teks
Sekarang kita memiliki metode yang memberikan daftar yang berisi rentang dan karakter, kita dapat menulis fungsi kita untuk mengekstrak karakter dari teks. Berikut kode untuk char metode:
def char(self, chars=None):
if self.pos >= self.len:
raise ParseError(
self.pos + 1,
'Expected %s but got end of string',
'character' if chars is None else '[%s]' % chars
)
next_char = self.text[self.pos + 1]
if chars == None:
self.pos += 1
return next_char
for char_range in self.split_char_ranges(chars):
if len(char_range) == 1:
if next_char == char_range:
self.pos += 1
return next_char
elif char_range[0] <= next_char <= char_range[2]:
self.pos += 1
return next_char
raise ParseError(
self.pos + 1,
'Expected %s but got %s',
'character' if chars is None else '[%s]' % chars,
next_char
)
Mari kita fokus pada argumen chars=None . Ini memungkinkan Anda untuk memanggil self.char() tanpa memberikan satu set karakter. Ini berguna ketika Anda hanya ingin mengekstrak karakter tanpa membatasinya ke set tertentu. Jika tidak, Anda dapat menyebutnya dengan berbagai karakter, seperti yang telah kita lihat di bagian sebelumnya.
Fungsi ini cukup mudah — pertama, kami memeriksa apakah kami kehabisan teks. Kemudian, kami memilih karakter berikutnya dan memeriksa apakah karakter adalah None , dalam hal ini kita dapat menaikkan posisi dan mengembalikan karakter dengan segera.
Namun, jika ada sekumpulan karakter di chars , kami membaginya menjadi daftar karakter dan rentang individual, seperti ['A-Z', 'a-z', '_'] . Dalam daftar ini, string dengan panjang 1 adalah karakter, dan yang lainnya adalah rentang. Ini memeriksa apakah karakter berikutnya cocok dengan karakter atau rentang, dan jika cocok, kami mengembalikannya. Jika kami gagal mencocokkannya dengan apa pun, itu akan keluar dari loop yang memunculkan ParseError , menyatakan bahwa kami tidak bisa mendapatkan karakter yang diharapkan.
'character' if chars is None else '[%s]' % chars hanyalah cara untuk memberikan pengecualian yang lebih mudah dibaca. Jika chars adalah None , pesan pengecualian akan membaca Expected character but got ... , tetapi jika char diatur ke sesuatu seperti A-Za-z_ , kita akan mendapatkan Expected [A-Za-z_] but got ... .
Nanti, kita akan melihat cara menggunakan fungsi ini untuk mengenali token.
Mengekstrak kata kunci dan simbol
Selain mengekstraksi karakter individu, mengenali kata kunci adalah tugas umum saat membangun parser. Kami menggunakan "kata kunci" untuk secara longgar merujuk ke string yang berdekatan yang merupakan "entitas sendiri", dan mungkin memiliki spasi sebelum dan sesudahnya. Misalnya, di JSON { bisa menjadi kata kunci, dan dalam bahasa pemrograman if , else bisa menjadi kata kunci, dan seterusnya.
Ini adalah kode untuk mengenali kata kunci:
def keyword(self, *keywords):
self.eat_whitespace()
if self.pos >= self.len:
raise ParseError(
self.pos + 1,
'Expected %s but got end of string',
','.join(keywords)
)
for keyword in keywords:
low = self.pos + 1
high = low + len(keyword)
if self.text[low:high] == keyword:
self.pos += len(keyword)
self.eat_whitespace()
return keyword
raise ParseError(
self.pos + 1,
'Expected %s but got %s',
','.join(keywords),
self.text[self.pos + 1],
)
Metode ini mengambil kata kunci, seperti self.keyword('if', 'and', 'or') . Metode ini menghapus spasi dan kemudian memeriksa apakah kita sudah kehabisan teks untuk diurai. Itu kemudian beralih melalui setiap kata kunci, memeriksa apakah kata kunci ada dalam teks. Jika memang menemukan sesuatu, kami akan menghapus spasi putih setelah kata kunci, lalu mengembalikan kata kunci.
Namun, jika tidak menemukan sesuatu, ia akan keluar dari loop yang memunculkan ParseError , menyatakan bahwa kata kunci tidak dapat ditemukan.
Pembantu untuk mencocokkan beberapa produksi
Di bagian sebelumnya, Anda telah memperhatikan bahwa kami menggunakan pengecualian untuk melaporkan kesalahan. Kita juga tahu bahwa untuk menulis parser keturunan rekursif, Anda menulis fungsi yang mengenali token atau aturan produksi. Sekarang, bayangkan Anda ingin mengurai teks sederhana, di mana Anda mengharapkan angka atau kata. Aturan produksi mungkin terlihat seperti:
Kami juga akan menganggap bahwa teks tersebut berisi sebuah kata. Ketika parser mencoba mencari digit (mungkin dengan menggunakan char() ), itu tidak akan menemukannya, dan ini menyebabkannya memunculkan pengecualian. Selain itu, Anda harus menghapus spasi putih sebelum dan sesudah mencocokkan aturan produksi. Jadi, kode untuk item() mungkin terlihat seperti ini:
def item(self): self.eat_whitespace() try: rv = self.number() except ParseError: rv = self.word() self.eat_whitespace() return rv
Ini sudah terlihat seperti banyak untuk menerapkan aturan sederhana! Bayangkan bagaimana rasanya menerapkan aturan yang rumit — Anda harus menggunakan try...except memblokir semua tempat.
Jadi, kita akan menulis match() fungsi yang akan menghapus spasi putih dan mencoba mencocokkan beberapa aturan. Fungsinya adalah sebagai berikut:
def match(self, *rules):
self.eat_whitespace()
last_error_pos = -1
last_exception = None
last_error_rules = []
for rule in rules:
initial_pos = self.pos
try:
rv = getattr(self, rule)()
self.eat_whitespace()
return rv
except ParseError as e:
self.pos = initial_pos
if e.pos > last_error_pos:
last_exception = e
last_error_pos = e.pos
last_error_rules.clear()
last_error_rules.append(rule)
elif e.pos == last_error_pos:
last_error_rules.append(rule)
if len(last_error_rules) == 1:
raise last_exception
else:
raise ParseError(
last_error_pos,
'Expected %s but got %s',
','.join(last_error_rules),
self.text[last_error_pos]
)
Sebelum kita membahas cara kerjanya, mari kita lihat betapa sederhananya menulis ulang contoh kita sebelumnya menggunakan match() :
def item(self):
return self.match('number', 'word')
Jadi, bagaimana cara kerjanya? match() mengambil nama metode untuk dijalankan (seperti number atau word dalam contoh di atas). Pertama, itu menghilangkan spasi putih di awal. Kemudian, ia mengulangi semua nama metode dan mengambil setiap metode menggunakan namanya melalui getattr() . Kemudian mencoba memanggil metode, dan jika semuanya berjalan dengan baik, itu juga akan menghapus spasi setelah teks. Terakhir, ia mengembalikan nilai yang diterimanya dengan memanggil metode
Namun, jika ada kesalahan, itu me-reset self.pos ke nilai yang ada sebelum mencoba mencocokkan aturan. Kemudian, mencoba untuk memilih pesan kesalahan yang baik dengan menggunakan aturan berikut:
- Saat mencocokkan beberapa aturan, banyak aturan yang mungkin menghasilkan kesalahan. Kesalahan yang dihasilkan setelah menguraikan sebagian besar teks mungkin adalah pesan kesalahan yang kita inginkan.
Untuk melihat mengapa hal ini terjadi, pertimbangkan string “abc1”. Mencoba menelepon number() akan gagal pada posisi 0, sedangkan word() akan gagal di posisi 2. Melihat string, kemungkinan besar pengguna ingin memasukkan kata, tetapi salah ketik.
- Jika dua atau lebih aturan yang salah berakhir dengan "tie", kami lebih suka memberi tahu pengguna tentang semua aturan yang gagal.
last_error_pos dan last_exception melacak posisi dan pengecualian kesalahan terakhir masing-masing. Selain itu, kami memelihara daftar last_error_rules sehingga jika terjadi seri, kami dapat memberi tahu pengguna tentang semua aturan yang kami coba cocokkan.
Dalam except ParseError blok, kami membandingkan posisi kesalahan terakhir dan kesalahan saat ini. Jika kesalahan saat ini sama, kami menganggapnya seri dan menambahkan ke daftar. Jika tidak, kami memperbarui posisi kesalahan, pengecualian, dan daftar aturan yang salah.
Pada akhirnya, kami memeriksa berapa banyak aturan yang gagal. Jika hanya ada satu, last_exception akan memiliki pesan kesalahan terbaik. Jika tidak, hasilnya seri, dan kami akan memberi tahu pengguna dengan pesan seperti Expected number,word but found ... .
Melihat apa yang akan terjadi selanjutnya – fungsi pembantu
Pada titik ini, kami memiliki semua hal yang diperlukan di parser kami, dan semua kegagalan menimbulkan pengecualian. Namun, terkadang kami hanya ingin mencocokkan karakter, kata kunci, atau aturan jika ada, tanpa kesulitan menangani pengecualian.
Kami akan memperkenalkan tiga pembantu kecil untuk melakukan hal itu. Dalam kasus pengecualian saat mencari barang, ini akan mengembalikan None :
def maybe_char(self, chars=None):
try:
return self.char(chars)
except ParseError:
return None
def maybe_match(self, *rules):
try:
return self.match(*rules)
except ParseError:
return None
def maybe_keyword(self, *keywords):
try:
return self.keyword(*keywords)
except ParseError:
return None
Menggunakan fungsi-fungsi ini mudah. Inilah cara Anda menggunakannya:
operator = self.maybe_keyword('+', '-'):
if operator == '+':
# add two numbers
elif operator == '-':
# subtract two numbers
else: # operator is None
# do something else
Contoh pengurai pertama:kalkulator
Sekarang setelah kita membangun fondasi untuk menulis parser, kita akan membangun parser pertama kita. Ini akan dapat mengurai ekspresi matematika dengan penambahan, pengurangan, perkalian, pembagian, dan juga menangani ekspresi tanda kurung seperti “(2 + 3) * 5”.
Kita akan mulai dengan memvisualisasikan tata bahasa dalam bentuk aturan produksi.
Aturan produksi untuk tata bahasa kalkulator
Kami sebelumnya telah melihat tata bahasa untuk menangani semuanya kecuali ekspresi tanda kurung:
Sekarang, mari kita pikirkan bagaimana ekspresi tanda kurung cocok dengan tata bahasa ini. Saat mengevaluasi "(2 + 3) * 5", kita harus menghitung "(2 + 3)" dan menguranginya menjadi angka. Artinya, dalam tata bahasa di atas, istilah “Angka” dapat merujuk ke ekspresi yang dikurung, atau sesuatu yang benar-benar angka, seperti “5”.
Jadi, kami akan mengubah aturan kami untuk mengakomodasi keduanya. Dalam aturan untuk "Istilah", kami akan mengganti "Angka" untuk istilah yang lebih tepat seperti "Faktor". "Faktor" kemudian dapat merujuk ke ekspresi tanda kurung, atau "Angka". Tata bahasa yang dimodifikasi terlihat seperti ini:
Dengan itu, mari kita terapkan aturan produksi!
Mengimplementasikan pengurai
Kami akan mengimplementasikan parser Kalkulator kami dengan memperluas kelas Parser dasar. Kami mulai mendefinisikan kelas seperti ini:
class CalcParser(Parser):
def start(self):
return self.expression()
Sebelumnya, saat mengimplementasikan kelas parser dasar, kami memiliki start() metode untuk memulai penguraian. Kita cukup memanggil expression() di sini, yang akan kita definisikan seperti di bawah ini:
def expression(self):
rv = self.match('term')
while True:
op = self.maybe_keyword('+', '-')
if op is None:
break
term = self.match('term')
if op == '+':
rv += term
else:
rv -= term
return rv
Aturan tata bahasa untuk . Jadi, kita mulai dengan membaca istilah dari teks. Kami kemudian membuat loop tak terbatas, dan mencari "+" atau "-". Jika kami tidak menemukannya, ini berarti kami telah selesai membaca daftar istilah tambahan seperti yang diberikan oleh , sehingga kami dapat keluar dari loop.
Jika tidak, kita membaca istilah lain dari teks. Kemudian, tergantung pada operatornya, kita tambahkan atau kurangi dari nilai awal. Kami melanjutkan proses ini sampai kami gagal mendapatkan "+" atau "-", dan mengembalikan nilai di akhir.
Kami akan menerapkan term() dengan cara yang sama:
def term(self):
rv = self.match('factor')
while True:
op = self.maybe_keyword('*', '/')
if op is None:
break
term = self.match('factor')
if op == '*':
rv *= term
else:
rv /= term
return rv Selanjutnya, kami akan menerapkan "Faktor". Kami akan mencoba membaca tanda kurung kiri terlebih dahulu, yang berarti ada ekspresi tanda kurung. Jika kita menemukan tanda kurung, kita membaca ekspresi dan kurung penutup, dan mengembalikan nilai ekspresi. Jika tidak, kami hanya membaca dan mengembalikan nomor.
def factor(self):
if self.maybe_keyword('('):
rv = self.match('expression')
self.keyword(')')
return rv
return self.match('number')
Di bagian selanjutnya, kita akan membuat parser kita mengenali sebuah angka.
Mengenali angka
Untuk mengenali angka, kita perlu melihat karakter individu dalam teks kita. Angka terdiri dari satu atau lebih digit, opsional diikuti oleh bagian desimal. Bagian desimal memiliki titik (.), dan diikuti oleh setidaknya satu digit. Selain itu, angka mungkin memiliki tanda seperti “+” atau “-” di depannya, seperti “-124.33”.
Kami akan menerapkan number() metode seperti ini:
def number(self):
chars = []
sign = self.maybe_keyword('+', '-')
if sign is not None:
chars.append(sign)
chars.append(self.char('0-9'))
while True:
char = self.maybe_char('0-9')
if char is None:
break
chars.append(char)
if self.maybe_char('.'):
chars.append('.')
chars.append(self.char('0-9'))
while True:
char = self.maybe_char('0-9')
if char is None:
break
chars.append(char)
rv = float(''.join(chars))
return rv
Meskipun fungsinya panjang, itu cukup sederhana. Kami memiliki chars daftar di mana kami menempatkan karakter nomor. Pertama, kita melihat simbol “+” atau “-” yang mungkin ada sebelum angka. Jika ada, kami menambahkannya ke daftar. Kemudian, kami mencari digit wajib pertama dari nomor tersebut dan terus mencari digit lainnya menggunakan maybe_char() metode. Setelah kita mendapatkan None melalui maybe_char , kita tahu bahwa kita telah melewati kumpulan digit, dan mengakhiri loop.
Demikian pula, kami mencari bagian desimal dan digitnya. Terakhir, kami mengubah semua karakter menjadi string, yang pada gilirannya, kami ubah menjadi angka floating point.
Antarmuka untuk parser kami
Kami selesai membangun parser kami. Sebagai langkah terakhir, kami akan menambahkan sedikit kode dalam lingkup global yang memungkinkan kami memasukkan ekspresi dan melihat hasilnya:
if __name__ == '__main__':
parser = CalcParser()
while True:
try:
print(parser.parse(input('> ')))
except KeyboardInterrupt:
print()
except (EOFError, SystemExit):
print()
break
except (ParseError, ZeroDivisionError) as e:
print('Error: %s' % e)
Jika Anda telah mengikuti sejauh ini, selamat! Anda telah membangun parser keturunan rekursif pertama Anda!
Jika Anda mengikuti IDE lokal, Anda dapat menjalankan kode Anda pada saat ini. Atau, Anda dapat menggunakan taman bermain di bawah ini untuk menjalankan parser. Anda dapat memasukkan ekspresi melalui tab “Input” di bawah ini:
Anda juga dapat menemukan kode lengkapnya di sini.
Contoh pengurai kedua:pengurai JSON “diperpanjang”
JSON adalah format pertukaran data yang mendukung struktur data dasar seperti angka, string, dan daftar. Ini adalah format yang sangat banyak digunakan, meskipun kesederhanaannya berarti tidak ada hal-hal seperti komentar dan ketat tentang hal-hal yang diterimanya. Misalnya, Anda tidak boleh memiliki tanda koma di daftar atau memiliki tanda “+” yang eksplisit di depan angka untuk menunjukkan tandanya.
Karena Python sudah memiliki modul JSON, kami akan membidik sedikit lebih tinggi dan membangun parser JSON yang mendukung komentar, tanda koma, dan string tanpa tanda kutip.
Menerapkan parser ini akan mengajari Anda cara menangani komentar. Ini juga akan mengilustrasikan bagaimana membuat bahasa yang mudah digunakan dapat membuat penguraian menjadi rumit, dan bagaimana Anda dapat menangani situasi seperti itu.
Sebelum menerapkan tata bahasa, mari kita pahami format JSON yang diperluas:
{
# Comments begin with a '#' and continue till the end of line.
# You can skip quotes on strings if they don't have hashes,
# brackets or commas.
Size: 1.5x,
# Trailing commas are allowed on lists and maps.
Things to buy: {
Eggs : 6,
Bread: 4,
Meat : 2,
},
# And of course, plain JSON stuff is supported too!
"Names": ["John", "Mary"],
"Is the sky blue?": true
} Aturan produksi untuk tata bahasa JSON
JSON kami yang diperluas menempel pada tipe data yang sama yang didukung JSON. JSON memiliki empat tipe data primitif — null, boolean, angka dan string, dan dua tipe data kompleks — daftar (atau larik), dan peta (juga disebut hash atau kamus). Daftar dan hash terlihat mirip dengan cara mereka melakukannya di Python.
Karena data JSON akan terdiri dari salah satu jenis ini, Anda dapat menulis aturan produksi seperti ini:
Kemudian, Anda dapat memecah kedua tipe ini menjadi tipe JSON:
Tata bahasa ini baik untuk mem-parsing JSON biasa tetapi perlu sedikit penyesuaian untuk kasus kami. Karena kita akan mendukung string yang tidak dikutip, yang berarti "1.5" (tanpa tanda kutip) adalah angka, tetapi "1.5x" (sekali lagi, tanpa tanda kutip), adalah string. Tata bahasa kami saat ini akan membaca "1.5" dari "1.5x", dan kemudian menyebabkan kesalahan karena "x" tidak diharapkan setelah angka.
Ini berarti bahwa pertama, kita harus mendapatkan set lengkap karakter yang tidak dikutip. Selanjutnya, kami akan menganalisis karakter dan menentukan apakah itu angka atau string. Jadi, kami akan menggabungkan angka dan string yang tidak dikutip ke dalam satu kategori, "Tidak Dikutip". String yang dikutip baik-baik saja, jadi kami akan memisahkannya ke dalam kategori lain, "QuotedString". Aturan produksi kami yang dimodifikasi untuk “PrimitiveType” sekarang terlihat seperti ini:
Selain itu, urutan aturan juga penting. Karena kita memiliki kunci yang tidak dikutip, pertama-tama kita harus mencoba mengurai teks sebagai null atau boolean. Jika tidak, kita mungkin akan mengenali “null” atau “true” sebagai string yang tidak diberi tanda kutip.
Menerapkan parser dan menangani komentar
Untuk mengimplementasikan parser JSON, kita akan mulai dengan memperluas class parser dasar seperti ini:
class JSONParser(Parser): # ...
Kami pertama-tama akan menangani masalah berurusan dengan komentar. Jika Anda memikirkannya, komentar benar-benar mirip dengan spasi — mereka muncul di tempat yang sama di mana spasi bisa muncul, dan bisa dibuang seperti spasi. Jadi, kami akan mengimplementasikan kembali eat_whitespace() untuk menangani komentar, seperti:
def eat_whitespace(self):
is_processing_comment = False
while self.pos < self.len:
char = self.text[self.pos + 1]
if is_processing_comment:
if char == 'n':
is_processing_comment = False
else:
if char == '#':
is_processing_comment = True
elif char not in ' fvrtn':
break
self.pos += 1
Di sini, kita perlu melacak apakah kita sedang memproses spasi putih atau komentar. Kami mengulang karakter per karakter teks, memeriksa apakah kami memiliki spasi putih atau # . Ketika ada # , kami memperbarui is_processing_comment ke True dan pada iterasi berikutnya dari while loop, kita dapat dengan aman membuang semua karakter sampai kita mencapai akhir baris. Namun, saat memproses karakter spasi putih, kita harus berhenti setelah karakter nonspasi muncul.
Selanjutnya, kami akan menerapkan aturan produksi dan start() metode. Teks input akan memiliki tipe JSON yang terkandung di dalamnya, jadi kita cukup memanggil any_type() di start() metode:
def start(self):
return self.match('any_type')
def any_type(self):
return self.match('complex_type', 'primitive_type')
def primitive_type(self):
return self.match('null', 'boolean', 'quoted_string', 'unquoted')
def complex_type(self):
return self.match('list', 'map')
Mengurai daftar dan peta
Sebelumnya, kita telah melihat cara mengurai daftar yang dipisahkan koma. Daftar JSON hanyalah daftar yang dipisahkan koma dengan tanda kurung siku, dan daftar tersebut mungkin memiliki nol atau lebih elemen. Mari kita lihat bagaimana Anda akan menerapkan penguraian daftar:
def list(self):
rv = []
self.keyword('[')
while True:
item = self.maybe_match('any_type')
if item is None:
break
rv.append(item)
if not self.maybe_keyword(','):
break
self.keyword(']')
return rv
Kita mulai dengan membaca tanda kurung siku awal diikuti dengan item dari daftar menggunakan self.maybe_match('any_type') . Jika kami gagal mendapatkan item, ini menunjukkan bahwa kami mungkin sudah selesai memeriksa semua item, jadi kami keluar dari loop. Jika tidak, kami menambahkan item ke daftar. Kami kemudian mencoba membaca koma dari daftar, dan tidak adanya koma juga menunjukkan bahwa kami selesai dengan daftar.
Demikian pula, peta hanyalah daftar "pasangan" yang dipisahkan koma dengan kurung kurawal, di mana pasangan adalah kunci string diikuti oleh titik dua (:) dan nilai. Tidak seperti dict Python s yang dapat memiliki jenis "hashable" sebagai kunci (yang mencakup int s dan tuple s), JSON hanya mendukung kunci string.
Beginilah cara Anda menerapkan aturan untuk peta dan pasangan:
def map(self):
rv = {}
self.keyword('{')
while True:
item = self.maybe_match('pair')
if item is None:
break
rv[item[0]] = item[1]
if not self.maybe_keyword(','):
break
self.keyword('}')
return rv
def pair(self):
key = self.match('quoted_string', 'unquoted')
if type(key) is not str:
raise ParseError(
self.pos + 1,
'Expected string but got number',
self.text[self.pos + 1]
)
self.keyword(':')
value = self.match('any_type')
return key, value
Di pair() , kami mencoba membaca “QuotedString” atau “Unquoted” untuk kunci tersebut. Seperti yang telah kami sebutkan sebelumnya, "Tidak Dikutip" dapat mengembalikan angka atau string, jadi kami secara eksplisit memeriksa apakah kunci yang kami baca adalah string. pair() kemudian mengembalikan Tuple dengan kunci dan nilai, dan map() panggilan pair() dan menambahkan ini ke dict Python.
Mengenali null dan boolean
Sekarang setelah bagian utama dari parser kita diimplementasikan, mari kita mulai dengan mengenali token sederhana seperti null dan boolean:
def null(self):
self.keyword('null')
return None
def boolean(self):
boolean = self.keyword('true', 'false')
return boolean[0] == 't'
None Python adalah analog terdekat dengan null JSON . In the case of booleans, the first characters is sufficient to tell whether it’s true or false , and we return the result of the comparison.
Recognizing unquoted strings and numbers
Before moving on to recognize unquoted strings, let us first define the set of acceptable characters. We’ll leave out anything that’s considered special in such as braces, quotes, colons, hashes (since they are used in comments) and backslashes (because they’re used for escape sequences). We’ll also include spaces and tabs in the acceptable set of characters so that you can write strings like “Things to buy” without using quotes.
So, what are the characters that we want to accept? We can use Python to figure this out:
>>> import string
>>> ''.join(sorted(set(string.printable) - set('{}[]:#"'fvrn')))
't !$%&()*+,-./0123456789;<=>[email protected]^_`abcdefghijklmnopqrstuvwxyz|~'
The next question is, how do you figure out if the text you read is a number or a string? The answer is — we cheat! Since Python’s int() and float() can take a string and return a number, we’ll use them and if those result in a ValueError , we’ll return a string. As for when to use int() or float() , we’ll use a simple rule. If the text contains “E”, “e” or “.”, (for example, “12.3” or “2e10”), we’ll call float(); otherwise, we’ll use int() .
Here’s the code:
def unquoted(self):
acceptable_chars = '0-9A-Za-z t!$%&()*+./;<=>?^_`|~-'
number_type = int
chars = [self.char(acceptable_chars)]
while True:
char = self.maybe_char(acceptable_chars)
if char is None:
break
if char in 'Ee.':
number_type = float
chars.append(char)
rv = ''.join(chars).rstrip(' t')
try:
return number_type(rv)
except ValueError:
return rv
Since matching rules are handled by match() , this takes care of stripping any initial whitespace before unquoted() can run. In this way, we can be sure that unquoted() won’t return a string consisting of only whitespaces. Any whitespace at the end is stripped off before we parse it as a number or return the string itself.
Recognizing quoted strings
Quoted strings are fairly simple to implement. Most programming languages (including Python) have single and double quotes that behave in the same way, and we’ll implement both of them.
We’ll support the following escape sequences — b (backspace), f (line feed), n (newline), r (carriage return), t (tab) and u(four hexadecimal digits) where those digits are used to represent an Unicode “code point”. For anything else that has a backslash followed by a character, we’ll ignore the backslash. This handles cases like using the backslash to escape itself ( ) or escaping quotes (" ).
Here’s the code for it:
def quoted_string(self):
quote = self.char('"'')
chars = []
escape_sequences = {
'b': 'b',
'f': 'f',
'n': 'n',
'r': 'r',
't': 't'
}
while True:
char = self.char()
if char == quote:
break
elif char == '':
escape = self.char()
if escape == 'u':
code_point = []
for i in range(4):
code_point.append(self.char('0-9a-fA-F'))
chars.append(chr(int(''.join(code_point), 16)))
else:
chars.append(escape_sequences.get(char, char))
else:
chars.append(char)
return ''.join(chars)
We first read a quote and then read additional characters in a loop. If this character is the same type of quote as the first character we read, we can stop reading further and return a string by joining the elements of chars .
Otherwise, we check if it’s an escape sequence and handle it in the aforementioned way, and add it to chars . Finally, if it matches neither of them, we treat it as a regular character and add it to our list of characters.
An interface for our JSON parser
To make sure we can interact with our parser, we’ll add a few lines of code that accepts input and parses it as JSON. Again, this code will be in global scope:
if __name__ == '__main__':
import sys
from pprint import pprint
parser = JSONParser()
try:
pprint(parser.parse(sys.stdin.read()))
except ParseError as e:
print('Error: '+ str(e))
To ensure we can read multiple lines, we have used sys.stdin.read() . If you’re going to run this locally, you can enter text and use Ctrl+D to stop the program from asking for more input. Otherwise, you can use this runnable snippet:
You can find the complete code here.
Building other kinds of parsers
Now that we’ve gone through building two parsers, you might have a fairly good idea of how to roll your own for the task at hand. While every language is unique (and therefore, their parsers), there are some common situations that we haven’t covered. For the sake of brevity, we won’t cover any code in these sections.
Whitespace sensitive languages
Before we begin, let us clarify that we’re not referring to languages that use whitespace-based indentation — we’ll cover them in the next section. Here, we’ll discuss languages where the meaning of things change based on the whitespace you put between elements.
An example of such a language would be where “a=10” is different than “a =10”. With bash and some other shells, “a=10” sets an environment variable, whereas “a =10” runs the program “a” with “=” and “10” as command-line arguments. You can even combine the two! Consider this:
a=10 b=20 c = 30
This sets the environment variables “a” and “b” only for the program “c”. The only way to parse such a language is to handle the whitespaces manually, and you’d have to remove all the eat_whitespace() calls in keyword() and match() . This is how you might write the production rules:
Whitespace based indentation
Languages like C and Javascript use curly braces to indicate the body of loops and if-statements. However, Python uses indentation for the same purpose, which makes parsing tricky.
One of the methods to handle this is to introduce a term such as “INDENT” to keep track of indented statements. To see how this would work, consider the following production rule:
After matching a condition, our parser would look for INDENT. Since this is the first time it’s trying to match INDENT, it takes whatever whitespace (except for newlines) that appears along with a non-whitespace character (since that would be part of a statement).
In subsequent iterations, it looks for the same whitespace in the text. If it encounters a different whitespace, it can raise an error. However, if there’s no whitespace at all, it indicates that the “while” loop is finished.
For nested indentations, you’d need to maintain a list of all indentations that you’re currently handling. When the parser handles a new indented block, it should add the new indentation string on the list. You can tell if you’re done parsing the block, by checking that you were able to retrieve less whitespace than you did previously. At this point, you should pop off the last indentation off the list.