Apakah lexers dan parser benar-benar berbeda dalam teori?
Tampaknya modis untuk membenci ekspresi reguler: pengkodean horor , posting blog lain .
Namun, alat berbasis lexing yang populer: pygments , geshi , atau prettify , semuanya menggunakan ekspresi reguler. Mereka tampaknya lex apa pun ...
Kapan cukup lexing, kapan Anda membutuhkan EBNF?
Adakah yang menggunakan token yang diproduksi oleh para lexer ini dengan generator parser bison atau antlr?
Jawaban:
Apa kesamaan parser dan lexer:
Mereka membaca simbol beberapa alfabet dari masukan mereka.
Mereka menganalisis simbol - simbol ini dan mencoba mencocokkannya dengan tata bahasa yang mereka pahami.
Mereka melampirkan semantik (makna) ke potongan bahasa yang mereka temukan.
*
,==
,<=
,^
akan diklasifikasikan sebagai "operator" token dengan C / C ++ lexer.[number][operator][number]
,[id][operator][id]
,[id][operator][number][operator][number]
akan diklasifikasikan sebagai "ekspresi" nonterminal oleh C / C ++ parser.Mereka dapat melampirkan beberapa makna tambahan (data) ke elemen yang dikenali.
Mereka semua menghasilkan kalimat yang tepat dari bahasa yang mereka kenali.
[TXT][TAG][TAG][TXT][TAG][TXT]...
.Seperti yang Anda lihat, parser dan tokenizer memiliki banyak kesamaan. Satu parser bisa menjadi tokenizer untuk parser lain, yang membaca token inputnya sebagai simbol dari alfabetnya sendiri (token hanyalah simbol dari beberapa alfabet) dengan cara yang sama seperti kalimat dari satu bahasa dapat menjadi simbol alfabet dari yang lain, level yang lebih tinggi bahasa. Misalnya, jika
*
dan-
merupakan simbol alfabetM
(sebagai "simbol kode Morse"), maka Anda dapat membuat parser yang mengenali string dari titik-titik dan garis-garis ini sebagai huruf yang disandikan dalam kode Morse. Kalimat dalam bahasa "Morse Code" bisa menjadi token untuk parser lain, yang token iniadalah simbol atom dari bahasanya (mis. Bahasa "Kata-kata Bahasa Inggris"). Dan "Kata Bahasa Inggris" ini bisa menjadi token (simbol alfabet) untuk beberapa parser tingkat tinggi yang mengerti bahasa "Kalimat Bahasa Inggris". Dan semua bahasa ini hanya berbeda dalam kompleksitas tata bahasa . Tidak ada lagi.Jadi ada apa dengan "level tata bahasa Chomsky" ini? Nah, Noam Chomsky mengklasifikasikan tata bahasa menjadi empat tingkat tergantung pada kompleksitasnya:
Level 3: Tata bahasa reguler
Mereka menggunakan ekspresi reguler, yaitu, mereka dapat hanya terdiri dari simbol-simbol alfabet (a
,b
), concatenations mereka (ab
,aba
,bbb
ETD.), Atau alternatif (misalnyaa|b
).Mereka dapat diimplementasikan sebagai finite state automata (FSA), seperti NFA (Nondeterministic Finite Automaton) atau DFA yang lebih baik (Deterministic Finite Automaton).
Tata bahasa reguler tidak dapat menangani sintaks bertingkat , mis. Tanda kurung bersarang / cocok dengan benar
(()()(()()))
, tag HTML / BB bersarang, blok bersarang dll. Karena state automata untuk menanganinya harus memiliki banyak negara bagian yang tak terhingga untuk menangani level bersarang yang tak terhingga banyaknya.Level 2: Tata bahasa bebas konteks
Mereka dapat memiliki cabang bersarang, rekursif, mirip dengan diri sendiri di pohon sintaksis mereka, sehingga mereka dapat menangani dengan baik struktur bersarang.Mereka dapat diimplementasikan sebagai otomat negara dengan stack. Tumpukan ini digunakan untuk mewakili level sintaks yang bersarang. Dalam praktiknya, mereka biasanya diimplementasikan sebagai parser top-down, recursive-descent yang menggunakan stack panggilan prosedur mesin untuk melacak tingkat bersarang, dan menggunakan prosedur / fungsi yang disebut secara rekursif untuk setiap simbol non-terminal dalam sintaksanya.
Tetapi mereka tidak dapat menangani dengan sintaks konteks-sensitif . Misalnya ketika Anda memiliki ekspresi
x+3
dan dalam satu konteks inix
bisa menjadi nama variabel, dan dalam konteks lain itu bisa menjadi nama fungsi dll.Level 1: Tata bahasa yang sensitif terhadap konteks
Level 0: Tata bahasa tidak terbatas
Disebut juga tata bahasa enumerable rekursif.
sumber
STMT_END
di sintaks Anda (untuk parser) untuk menunjukkan akhir instruksi. Sekarang Anda dapat memiliki token dengan nama yang sama yang dikaitkan dengannya, yang dihasilkan oleh lexer. Tetapi Anda dapat mengubah leksem yang sebenarnya. Misalnya. Anda dapat menentukanSTMT_END
sebagai;
memiliki C / C ++ - seperti kode sumber. Atau Anda dapat mendefinisikannyaend
agar mirip dengan gaya Pascal. Atau Anda dapat mendefinisikannya hanya'\n'
untuk mengakhiri instruksi dengan akhir baris, seperti pada Python. Tetapi sintaks instruksi (dan parser) tetap tidak berubah :-) Hanya lexer yang perlu diubah.Ya, mereka sangat berbeda dalam teori, dan dalam implementasi.
Lexers digunakan untuk mengenali "kata-kata" yang membentuk elemen bahasa, karena struktur kata-kata tersebut umumnya sederhana. Ekspresi reguler sangat bagus dalam menangani struktur yang lebih sederhana ini, dan ada mesin pencocokan ekspresi reguler berkinerja tinggi yang digunakan untuk mengimplementasikan lexer.
Parser digunakan untuk mengenali "struktur" frasa bahasa. Struktur seperti itu umumnya jauh melampaui apa yang bisa dikenali oleh "ekspresi reguler", sehingga orang perlu parser "sensitif konteks" untuk mengekstraksi struktur tersebut. Parser peka konteks sulit dibangun, jadi kompromi tekniknya adalah menggunakan tata bahasa "bebas konteks" dan menambahkan retasan ke parser ("tabel simbol", dll.) Untuk menangani bagian peka konteks.
Baik teknologi lexing maupun parsing sepertinya tidak akan segera hilang.
Mereka dapat disatukan dengan memutuskan untuk menggunakan teknologi "parsing" untuk mengenali "kata", seperti yang saat ini dieksplorasi oleh parser GLR tanpa pemindai. Itu memiliki biaya runtime, karena Anda menerapkan mesin yang lebih umum untuk apa yang sering merupakan masalah yang tidak memerlukannya, dan biasanya Anda membayar untuk itu dalam overhead. Di mana Anda memiliki banyak siklus gratis, overhead itu mungkin tidak masalah. Jika Anda memproses banyak teks, maka overhead itu penting dan parser ekspresi reguler klasik akan terus digunakan.
sumber
EBNF benar-benar tidak menambah banyak kekuatan tata bahasa. Ini hanya notasi kenyamanan / jalan pintas / "gula sintaksis" atas aturan tata bahasa Chomsky Normal Form (CNF) standar. Misalnya, alternatif EBNF:
Anda dapat mencapainya di CNF hanya dengan mendaftar setiap produksi alternatif secara terpisah:
Elemen opsional dari EBNF:
Anda dapat mencapai di CNF dengan menggunakan produksi yang dapat dibatalkan , yaitu yang dapat diganti dengan string kosong (dilambangkan dengan hanya produksi kosong di sini; yang lain menggunakan epsilon atau lambda atau lingkaran silang):
Produksi dalam bentuk seperti yang terakhir di
B
atas disebut "penghapusan", karena dapat menghapus apa pun kepanjangan dari produksi lain (produk string kosong bukan yang lain).Tidak ada atau lebih banyak pengulangan dari EBNF:
Anda dapat memperoleh dengan menggunakan produksi rekursif , yaitu, yang menanamkan sendiri di suatu tempat di dalamnya. Itu bisa dilakukan dengan dua cara. Yang pertama adalah rekursi kiri (yang biasanya harus dihindari, karena parser Keturunan Rekursif Top-Down tidak dapat menguraikannya):
Mengetahui bahwa itu hanya menghasilkan string kosong (akhirnya) diikuti oleh nol atau lebih
A
, string yang sama ( tetapi bukan bahasa yang sama! ) Dapat diekspresikan menggunakan rekursi kanan :Dan ketika datang
+
untuk satu atau lebih pengulangan dari EBNF:itu dapat dilakukan dengan memfaktorkan satu
A
dan menggunakan*
seperti sebelumnya:yang bisa Anda ungkapkan dalam CNF seperti itu (saya menggunakan rekursi yang benar di sini; coba cari tahu sendiri yang lain sebagai latihan):
Mengetahui hal itu, Anda sekarang mungkin dapat mengenali tata bahasa untuk ekspresi reguler (yaitu, tata bahasa reguler ) sebagai yang dapat diekspresikan dalam produksi EBNF tunggal yang hanya terdiri dari simbol terminal. Secara umum, Anda dapat mengenali tata bahasa reguler ketika Anda melihat produksi yang mirip dengan ini:
Artinya, hanya menggunakan string kosong, simbol terminal, non-terminal sederhana untuk penggantian dan perubahan keadaan, dan menggunakan rekursi hanya untuk mencapai pengulangan (iterasi, yang hanya rekursi linier - yang tidak bercabang seperti pohon). Tidak ada yang lebih maju di atas ini, maka Anda yakin itu adalah sintaksis biasa dan Anda bisa menggunakan hanya lexer untuk itu.
Tetapi ketika sintaks Anda menggunakan rekursi dengan cara yang tidak sepele, untuk menghasilkan struktur bersarang seperti pohon, mirip diri, seperti yang berikut ini:
maka Anda dapat dengan mudah melihat bahwa ini tidak dapat dilakukan dengan ekspresi reguler, karena Anda tidak dapat menyelesaikannya menjadi satu produksi EBNF dengan cara apa pun; Anda akan berakhir dengan mengganti
S
tanpa batas, yang akan selalu menambaha
s danb
s di kedua sisi. Lexers (lebih khusus: Finite State Automata yang digunakan oleh lexers) tidak dapat menghitung ke angka arbitrer (mereka terbatas, ingat?), Jadi mereka tidak tahu berapa banyaka
yang ada untuk mencocokkan mereka secara merata dengan begitu banyakb
. Tata bahasa seperti ini disebut tata bahasa bebas konteks (paling tidak), dan mereka membutuhkan parser.Tata bahasa bebas konteks dikenal untuk diuraikan, sehingga mereka banyak digunakan untuk menggambarkan sintaks bahasa pemrograman. Tapi masih ada lagi. Kadang-kadang tata bahasa yang lebih umum diperlukan - ketika Anda memiliki lebih banyak hal untuk dihitung pada saat yang sama, secara mandiri. Misalnya, ketika Anda ingin mendeskripsikan bahasa di mana orang dapat menggunakan kurung bundar dan kurung kurawal, tetapi mereka harus dipasangkan dengan benar satu sama lain (kurung kurawal dengan kurawal, bundar dengan putaran). Tata bahasa semacam ini disebut konteks-sensitif . Anda dapat mengenalinya dengan memiliki lebih dari satu simbol di sebelah kiri (sebelum panah). Sebagai contoh:
Anda dapat menganggap simbol-simbol tambahan ini di sebelah kiri sebagai "konteks" untuk menerapkan aturan. Mungkin ada beberapa prasyarat, postconditions dll Sebagai contoh, aturan di atas akan menggantikan
R
menjadiS
, tetapi hanya ketika itu dalam antaraA
danB
, meninggalkan merekaA
danB
diri mereka sendiri tidak berubah. Sintaks semacam ini benar-benar sulit untuk diuraikan, karena membutuhkan mesin Turing yang lengkap. Ini keseluruhan cerita lain, jadi saya akan berakhir di sini.sumber
Untuk menjawab pertanyaan sebagaimana ditanyakan (tanpa mengulangi apa yang muncul di jawaban lain)
Lexer dan parser tidak jauh berbeda, seperti yang disarankan oleh jawaban yang diterima. Keduanya didasarkan pada formalisme bahasa sederhana: bahasa reguler untuk lexers dan, hampir selalu, bahasa bebas konteks (CF) untuk parser. Keduanya terkait dengan model komputasi yang cukup sederhana, otomat keadaan terbatas dan otomat stack push-down. Bahasa reguler adalah kasus khusus bahasa bebas konteks, sehingga lexer dapat diproduksi dengan teknologi CF yang agak lebih kompleks. Tapi itu bukan ide yang baik karena setidaknya ada dua alasan.
Poin mendasar dalam pemrograman adalah bahwa komponen sistem harus dilengkapi dengan teknologi yang paling tepat, sehingga mudah diproduksi, dipahami, dan dipelihara. Teknologi ini tidak boleh berlebihan (menggunakan teknik yang jauh lebih kompleks dan mahal daripada yang dibutuhkan), juga tidak boleh berada pada batas kekuatannya, sehingga membutuhkan kontraksi teknis untuk mencapai tujuan yang diinginkan.
Itu sebabnya "Tampaknya modis untuk membenci ekspresi reguler". Meskipun mereka dapat melakukan banyak hal, mereka kadang-kadang membutuhkan pengkodean yang sangat tidak dapat dibaca untuk mencapainya, belum lagi fakta bahwa berbagai ekstensi dan pembatasan dalam implementasi agak mengurangi kesederhanaan teoretis mereka. Lexers biasanya tidak melakukan itu, dan biasanya teknologi yang sederhana, efisien, dan tepat untuk menguraikan token. Menggunakan parser CF untuk token akan berlebihan, meskipun itu mungkin.
Alasan lain untuk tidak menggunakan formalisme CF untuk lexers adalah bahwa mungkin tergoda untuk menggunakan kekuatan CF penuh. Tapi itu mungkin menimbulkan masalah struktural terkait pembacaan program.
Pada dasarnya, sebagian besar struktur teks program, dari mana makna diekstraksi, adalah struktur pohon. Ini mengungkapkan bagaimana kalimat parse (program) dihasilkan dari aturan sintaksis. Semantik diturunkan oleh teknik komposisi (homomorfisme untuk yang berorientasi matematis) dari cara aturan sintaksis disusun untuk membangun pohon parse. Karena itu struktur pohon sangat penting. Fakta bahwa token diidentifikasi dengan lexer berbasis set reguler tidak mengubah situasi, karena CF yang dikomposisi dengan regular masih memberikan CF (saya berbicara sangat longgar tentang transduser reguler, yang mengubah aliran karakter menjadi aliran token).
Namun, CF yang dikomposisikan dengan CF (melalui transduser CF ... maaf untuk matematika), tidak selalu memberikan CF, dan mungkin membuat segalanya lebih umum, tetapi kurang bisa ditelusuri dalam praktik. Jadi CF bukan alat yang tepat untuk lexers, meskipun bisa digunakan.
Salah satu perbedaan utama antara reguler dan CF adalah bahasa reguler (dan transduser) sangat baik menyusun dengan hampir semua formalisme dalam berbagai cara, sementara bahasa CF (dan transduser) tidak, bahkan dengan diri mereka sendiri (dengan beberapa pengecualian).
(Perhatikan bahwa transduser reguler dapat digunakan orang lain, seperti formalisasi beberapa teknik penanganan kesalahan sintaksis.)
BNF hanyalah sintaks khusus untuk menyajikan tata bahasa CF.
EBNF adalah gula sintaksis untuk BNF , menggunakan fasilitas notasi reguler untuk memberikan versi tersier tata bahasa BNF. Itu selalu dapat diubah menjadi BNF murni yang setara.
Namun, notasi reguler sering digunakan dalam EBNF hanya untuk menekankan bagian sintaksis yang sesuai dengan struktur elemen leksikal, dan harus dikenali dengan lexer, sedangkan sisanya dengan agak disajikan dalam BNF lurus. Tapi itu bukan aturan mutlak.
Sebagai rangkuman, struktur token yang lebih sederhana lebih baik dianalisis dengan teknologi bahasa biasa yang lebih sederhana, sedangkan struktur bahasa yang berorientasi pohon (sintaksis program) lebih baik ditangani oleh tata bahasa CF.
Saya sarankan juga melihat jawaban AHR .
Tapi ini meninggalkan pertanyaan terbuka: Mengapa pohon?
Pohon adalah dasar yang baik untuk menentukan sintaksis karena
mereka memberikan struktur sederhana pada teks
ada sangat mudah untuk menghubungkan semantik dengan teks berdasarkan struktur itu, dengan teknologi yang dipahami secara matematis (komposisionalitas melalui homomorfisme), seperti ditunjukkan di atas. Ini adalah alat aljabar dasar untuk mendefinisikan semantik formalisme matematika.
Oleh karena itu itu adalah representasi perantara yang baik, seperti yang ditunjukkan oleh keberhasilan Pohon Sintaksis Abstrak (AST). Perhatikan bahwa AST sering berbeda dari parse tree karena teknologi parsing yang digunakan oleh banyak profesional (seperti LL atau LR) hanya berlaku untuk subset tata bahasa CF, sehingga memaksa distorsi tata bahasa yang kemudian diperbaiki di AST. Ini dapat dihindari dengan teknologi parsing yang lebih umum (berdasarkan pemrograman dinamis) yang menerima tata bahasa CF.
Pernyataan tentang fakta bahwa bahasa pemrograman lebih sensitif terhadap konteks (CS) daripada CF adalah arbitrer dan dapat diperdebatkan.
Masalahnya adalah bahwa pemisahan sintaksis dan semantik adalah arbitrer. Memeriksa deklarasi atau jenis perjanjian dapat dilihat sebagai bagian dari sintaks, atau bagian dari semantik. Hal yang sama berlaku untuk gender dan kesepakatan angka dalam bahasa alami. Tetapi ada bahasa-bahasa alami di mana kesepakatan jamak bergantung pada makna kata semantik yang sebenarnya, sehingga tidak cocok dengan sintaksis.
Banyak definisi bahasa pemrograman dalam semantik denotasi menempatkan deklarasi dan ketik pengecekan dalam semantik. Jadi menyatakan seperti yang dilakukan oleh Ira Baxter bahwa parser CF sedang diretas untuk mendapatkan sensitivitas konteks yang diperlukan oleh sintaksis terbaik adalah pandangan sewenang-wenang tentang situasi. Ini mungkin diatur sebagai retasan dalam beberapa kompiler, tetapi tidak harus demikian.
Juga bukan hanya pengurai CS (dalam arti yang digunakan dalam jawaban lain di sini) sulit untuk dibuat, dan kurang efisien. Mereka juga tidak cukup untuk mengekspresikan dengan jelas bagian dari konteks-sensitivitas yang mungkin diperlukan. Dan mereka tidak secara alami menghasilkan struktur sintaksis (seperti parse-tree) yang nyaman untuk menurunkan semantik program, yaitu untuk menghasilkan kode yang dikompilasi.
sumber
Ada beberapa alasan mengapa bagian analisis kompiler biasanya dipisahkan menjadi fase analisis leksikal dan parsing (analisis sintaksis).
resource___ Compiler (Edisi ke-2) ditulis oleh- Alfred V. Abo University Columbia Monica S. Lam Stanford University Ravi Sethi Avaya Jeffrey D. Ullman Stanford University
sumber