lexers vs parser

308

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?

Naveen
sumber
2
Iya. Saya mencoba menguraikan autohotkey. Saya dapat membuat stabilo sintaks menggunakan pygments sangat cepat. Tapi antlr butuh waktu lebih lama ... Saya belum melihat banyak penyerbukan silang antara dua alat.
Naveen
67
Hanya modis untuk membenci ekspresi reguler ketika mereka disalahgunakan. Banyak orang mencoba menggunakan ekspresi reguler ketika parsing bebas konteks diperlukan. Mereka selalu gagal. Dan mereka menyalahkan teknologi ekspresi reguler. Itu seperti mengeluh bahwa palu Anda adalah gergaji yang payah. Benar, tetapi Anda tidak akan mendapatkan banyak simpati.
Ira Baxter
2
Saya mulai menambah kecepatan dengan antlr, untungnya. Banyak lexing bebas konteks dan kadang-kadang bahkan tergantung konteks juga.
Naveen
1
Salah satu aspek mendasar dari masalah lexer vs parser adalah bahwa lexer didasarkan pada finite automata (FSA), atau lebih tepatnya finite transducers (FST). Kebanyakan parsing formalisme (bukan hanya Context-Free) ditutup di bawah persimpangan dengan FSA atau aplikasi FST. Oleh karena itu menggunakan formalnalisme berbasis ekspresi reguler sederhana untuk lexer tidak meningkatkan kompleksitas struktur sintaksis formalisme pengurai yang lebih kompleks. Ini adalah masalah modularitas yang benar - benar utama ketika mendefinisikan struktur dan semantik bahasa, dengan senang hati diabaikan oleh jawaban yang terpilih.
babou
Perlu dicatat bahwa lexer dan parser tidak harus berbeda, misalnya LLLPG dan versi ANTLR sebelumnya menggunakan sistem parsing LL (k) yang sama untuk lexer dan parser. Perbedaan utama adalah bahwa regex biasanya cukup untuk lexer tetapi tidak parser.
Qwertie

Jawaban:

475

Apa kesamaan parser dan lexer:

  1. Mereka membaca simbol beberapa alfabet dari masukan mereka.

    • Petunjuk: Alfabet tidak harus berupa huruf. Tetapi harus simbol yang atom untuk bahasa dipahami oleh parser / lexer.
    • Simbol untuk lexer: karakter ASCII.
    • Simbol untuk parser: token tertentu, yang merupakan simbol terminal dari tata bahasa mereka.
  2. Mereka menganalisis simbol - simbol ini dan mencoba mencocokkannya dengan tata bahasa yang mereka pahami.

    • Di sinilah letak perbedaan sebenarnya. Lihat di bawah untuk lebih lanjut.
    • Tata bahasa dipahami oleh lexers: tata bahasa biasa (level 3 Chomsky).
    • Tata bahasa dipahami oleh parser: tata bahasa bebas konteks (level 2 Chomsky).
  3. Mereka melampirkan semantik (makna) ke potongan bahasa yang mereka temukan.

    • Lexers melampirkan makna dengan mengklasifikasikan leksem (string simbol dari input) sebagai token tertentu . Misalnya Semua leksem ini: *, ==, <=, ^akan diklasifikasikan sebagai "operator" token dengan C / C ++ lexer.
    • Parser melampirkan makna dengan mengklasifikasikan string token dari input (kalimat) sebagai nonterminals tertentu dan membangun pohon parse . Misalnya semua ini string tanda: [number][operator][number], [id][operator][id], [id][operator][number][operator][number]akan diklasifikasikan sebagai "ekspresi" nonterminal oleh C / C ++ parser.
  4. Mereka dapat melampirkan beberapa makna tambahan (data) ke elemen yang dikenali.

    • Ketika lexer mengenali urutan karakter yang merupakan angka yang tepat, ia dapat mengubahnya menjadi nilai binernya dan menyimpannya dengan token "angka".
    • Demikian pula, ketika parser mengenali suatu ekspresi, ia dapat menghitung nilainya dan menyimpannya dengan simpul "ekspresi" dari pohon sintaksis.
  5. Mereka semua menghasilkan kalimat yang tepat dari bahasa yang mereka kenali.

    • Lexers menghasilkan token , yang merupakan kalimat dari bahasa reguler yang mereka kenali. Setiap token dapat memiliki sintaksis dalam (meskipun level 3, bukan level 2), tetapi itu tidak masalah untuk data output dan untuk yang membacanya.
    • Parser menghasilkan pohon sintaks , yang merupakan representasi kalimat dari bahasa bebas konteks yang mereka kenali. Biasanya hanya satu pohon besar untuk seluruh dokumen / file sumber, karena seluruh dokumen / file sumber adalah kalimat yang tepat untuk mereka. Tetapi tidak ada alasan mengapa parser tidak dapat menghasilkan serangkaian pohon sintaks pada hasilnya. Misalnya itu bisa menjadi pengurai yang mengenali tag SGML yang ditempel ke teks biasa. Sehingga akan tokenize dokumen SGML menjadi serangkaian token: [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 alfabet M(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, bbbETD.), Atau alternatif (misalnya a|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+3dan dalam satu konteks ini xbisa 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.

SasQ
sumber
70
Oh ya? Jadi apakah "kata atau token" itu? Itu hanya kalimat dalam bahasa biasa, yang terdiri dari huruf-huruf alfabet. Dan apa "konstruksi" atau "pohon" di dalam pengurai? Mereka juga kalimat , tetapi dalam bahasa yang berbeda, tingkat yang lebih tinggi, yang token tertentu adalah simbol alfabet. Perbedaannya bukan apa yang Anda katakan, tetapi dalam KOMPLEKSITAS BAHASA YANG DIGUNAKAN . Hadapi -1 Anda dengan buku pegangan apa pun tentang teori parsing.
SasQ
3
@ SasQ Apakah adil untuk mengatakan bahwa baik Lexers dan Parsers mengambil beberapa tata bahasa dan serangkaian token sebagai input?
Parag
4
Kira-kira. Mereka berdua mengambil serangkaian simbol dari alfabet yang mereka kenali. Untuk lexer, alfabet ini hanya terdiri dari karakter polos. Untuk parser, alfabet terdiri dari simbol terminal, apa pun yang didefinisikan. Mereka juga bisa berupa karakter, jika Anda tidak menggunakan lexer dan menggunakan pengenal satu karakter dan satu digit angka dll. (Sangat berguna pada tahap pertama pengembangan). Tapi mereka biasanya token (kelas leksikal) karena token adalah abstraksi yang baik: Anda dapat mengubah leksem sebenarnya (string) yang mereka perjuangkan, dan parser tidak melihat perubahan.
SasQ
6
Misalnya, Anda dapat menggunakan simbol terminal STMT_ENDdi 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 menentukan STMT_ENDsebagai ;memiliki C / C ++ - seperti kode sumber. Atau Anda dapat mendefinisikannya endagar 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.
SasQ
24
Berjam-jam di wikipedia dan google tidak membantu, tetapi Anda menjelaskan tata bahasa Chomsky dalam 3 menit. Terima kasih.
enrey
107

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.

Ira Baxter
sumber
40
Penjelasan yang bagus, Ira. Menambah analogi Anda: Sementara lexers adalah tentang memperbaiki kata-kata, parser adalah tentang memperbaiki kalimat. "Lihat spot run" dan "spot run See" keduanya valid sejauh menyangkut lexer. Dibutuhkan pengurai untuk menentukan bahwa struktur frasa salah (dalam tata bahasa Inggris).
Alan
Saya kira parser adalah untuk lexer sebagai walker pohon adalah parser. Saya tidak yakin bahwa teorinya berbeda: antlr.org/wiki/display/~admin/ANTLR+v4+lexers tetapi saya mulai memahami perbedaan dalam konvensi di antara mereka ...
Naveen
4
Teorinya sangat berbeda. Sebagian besar teknologi parser berusaha untuk menangani bahasa bebas konteks sampai tingkat tertentu (beberapa hanya melakukan sebagian, misalnya, LALR, beberapa melakukan semuanya, misalnya, GLR). Sebagian besar teknologi lexer hanya mencoba melakukan ekspresi reguler.
Ira Baxter
3
Teorinya berbeda, karena telah diusulkan oleh banyak orang dan menggunakan terminologi dan algoritma yang berbeda. Tetapi jika Anda mencermati mereka, Anda dapat melihat kesamaan. Misalnya, masalah rekursi kiri sangat mirip dengan masalah non-determinisme pada NFA, dan menghilangkan rekursi kiri mirip dengan menghilangkan non-determinisme dan mengubah NFA menjadi DFA. Token adalah kalimat untuk tokenizer (output), tetapi simbol abjad untuk parser (input). Saya tidak menyangkal perbedaan (level Chomsky), tetapi kesamaan banyak membantu dalam desain.
SasQ
1
Perwira saya berada dalam teori kategori. Dia menunjukkan bagaimana gagasan teori kategorik berkas gandum mencakup semua jenis pencocokan pola, dan mampu memperoleh LR parsing dari spesifikasi kategorikal abstrak. Jadi sebenarnya, jika Anda cukup abstrak, Anda dapat menemukan kesamaan tersebut. Inti dari teori kategori adalah Anda dapat sering mengabstraksikan "sepenuhnya"; Saya yakin Anda bisa membangun parser teori kategori yang menghapus perbedaan. Tetapi setiap penggunaan praktis itu harus instantiate ke domain masalah spesifik, dan kemudian perbedaan muncul sebagai nyata.
Ira Baxter
32

Kapan cukup lexing, kapan Anda membutuhkan EBNF?

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:

S --> A | B

Anda dapat mencapainya di CNF hanya dengan mendaftar setiap produksi alternatif secara terpisah:

S --> A      // `S` can be `A`,
S --> B      // or it can be `B`.

Elemen opsional dari EBNF:

S --> X?

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):

S --> B       // `S` can be `B`,
B --> X       // and `B` can be just `X`,
B -->         // or it can be empty.

Produksi dalam bentuk seperti yang terakhir di Batas 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:

S --> A*

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):

S --> S A    // `S` is just itself ended with `A` (which can be done many times),
S -->        // or it can begin with empty-string, which stops the recursion.

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 :

S --> A S    // `S` can be `A` followed by itself (which can be done many times),
S -->        // or it can be just empty-string end, which stops the recursion.

Dan ketika datang +untuk satu atau lebih pengulangan dari EBNF:

S --> A+

itu dapat dilakukan dengan memfaktorkan satu Adan menggunakan *seperti sebelumnya:

S --> A A*

yang bisa Anda ungkapkan dalam CNF seperti itu (saya menggunakan rekursi yang benar di sini; coba cari tahu sendiri yang lain sebagai latihan):

S --> A S   // `S` can be one `A` followed by `S` (which stands for more `A`s),
S --> A     // or it could be just one single `A`.

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:

A -->        // Empty (nullable) production (AKA erasure).
B --> x      // Single terminal symbol.
C --> y D    // Simple state change from `C` to `D` when seeing input `y`.
E --> F z    // Simple state change from `E` to `F` when seeing input `z`.
G --> G u    // Left recursion.
H --> v H    // Right recursion.

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:

S --> a S b    // `S` can be itself "parenthesized" by `a` and `b` on both sides.
S -->          // or it could be (ultimately) empty, which ends recursion.

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 Stanpa batas, yang akan selalu menambah as dan bs 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 banyak ayang ada untuk mencocokkan mereka secara merata dengan begitu banyak b. 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:

A R B --> A S B

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 Rmenjadi S, tetapi hanya ketika itu dalam antara Adan B, meninggalkan mereka Adan Bdiri 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.

SasQ
sumber
1
Anda menyatakan bahwa EBNF adalah "hanya notasi kenyamanan / jalan pintas /" gula sintaksis "di atas aturan tata bahasa Chomsky's Normal Form (CNF)". Tapi CNF hampir tidak ada hubungannya dengan topik yang ada. EBNF dapat dengan mudah diubah menjadi BNF standar. Titik. Ini adalah gula sintaksis untuk BNF standar.
babou
11

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.

babou
sumber
Ya, pohon parse dan AST berbeda, tetapi cukup banyak tidak dalam cara yang sangat berguna. Lihat diskusi saya tentang ini: stackoverflow.com/a/1916687/120163
Ira Baxter
@IraBaxter Saya tidak setuju dengan Anda, tapi saya benar-benar tidak punya waktu sekarang untuk menyusun jawaban bersih untuk posting Anda. Pada dasarnya, Anda mengambil sudut pandang pragmatis (dan saya pikir juga mempertahankan sistem Anda sendiri). Ini bahkan lebih mudah karena Anda menggunakan parser CF umum (namun GLR mungkin bukan yang paling efisien), daripada yang deterministik seperti pada beberapa sistem. Saya menganggap AST sebagai representasi referensi, yang cocok untuk perawatan yang didefinisikan secara formal, terbukti memperbaiki transformasi, bukti matematis, tidak memparse untuk beberapa representasi konkret, dll.
babou
Pandangan "pragmatis" adalah alasan saya mengklaim mereka tidak jauh berbeda dengan cara yang bermanfaat. Dan saya benar-benar tidak percaya bahwa menggunakan (ad hoc AST) memberi Anda "transformasi yang terbukti benar"; AST ad hoc Anda tidak memiliki hubungan yang jelas dengan tata bahasa sebenarnya dari langauge yang sedang diproses (dan di sini, ya, sistem saya dapat dipertahankan karena "AST" kami terbukti setara dengan isomorfik dengan BNF). AST Ad hoc tidak memberi Anda kemampuan tambahan apa pun untuk membatalkan "beberapa representasi konkret). Anda keberatan dengan GLR (tidak paling efisien) tampaknya tidak ada gunanya. Juga tidak bersifat deterministik.
Ira Baxter
Jadi sebenarnya saya tidak mengerti bagian dari keberatan Anda terhadap komentar saya. Anda harus menulis "jawaban bersih" itu.
Ira Baxter
@IraBaxter Komentar terlalu terbatas untuk jawaban yang tepat (saran?). "Ad hoc" bukan kualifikasi yang tepat untuk advokasi AST I, yang seharusnya (kadang-kadang) sintaks referensi. Ini secara historis benar, melihat baik pada sejarah konsep AST dalam ilmu komputer, dan pada sejarah sistem formal sebagai istilah (pohon) dalam aljabar yang diurutkan, bersama dengan interpretasi. AST adalah bentuk referensi, bukan yang diturunkan. Lihat juga sistem bukti modern dan pembuatan program otomatis. Anda mungkin bias oleh kenyataan bahwa Anda harus bekerja dari sintaksis yang dirancang oleh orang lain.
babou
7

Ada beberapa alasan mengapa bagian analisis kompiler biasanya dipisahkan menjadi fase analisis leksikal dan parsing (analisis sintaksis).

  1. Kesederhanaan desain adalah pertimbangan terpenting. Pemisahan analisis leksikal dan sintaksis seringkali memungkinkan kita untuk menyederhanakan setidaknya satu dari tugas-tugas ini. Sebagai contoh, parser yang harus berurusan dengan komentar dan spasi sebagai unit sintaksis. Jauh lebih kompleks daripada yang dapat mengasumsikan komentar dan ruang putih telah dihapus oleh penganalisa leksikal. Jika kita merancang bahasa baru, memisahkan masalah leksikal dan sintaksis dapat menyebabkan desain bahasa yang lebih bersih secara keseluruhan.
  2. Efisiensi penyusun ditingkatkan. Alat analisis leksikal yang terpisah memungkinkan kita untuk menerapkan teknik khusus yang hanya melayani tugas leksikal, bukan pekerjaan parsing. Selain itu, teknik buffering khusus untuk membaca karakter input dapat mempercepat kompiler secara signifikan.
  3. Portabilitas kompiler ditingkatkan. Keunikan khusus perangkat input dapat dibatasi untuk penganalisa leksikal.

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

AHR
sumber