Pertanyaan yang diberi tag parsers

Orang sering mengatakan bahwa parser LR (k) lebih kuat daripada parser LL (k) . Pernyataan-pernyataan ini sebagian besar tidak jelas; khususnya, haruskah kita membandingkan kelas untuk tetap atau serikat atas semua ? Jadi bagaimana sebenarnya situasinya? Secara khusus, saya tertarik pada bagaimana...

EPAL, bahasa bahkan palindrom, didefinisikan sebagai bahasa yang dihasilkan oleh tata bahasa bebas konteks berikut: S→aaS→aaS \rightarrow a a S→bbS→bbS \rightarrow b b S→aSaS→aSaS \rightarrow a S a S→bSbS→bSbS \rightarrow b S b EPAL adalah 'kutukan' dari banyak algoritma penguraian:...

Saya ingin mengurai bahasa khusus domain yang ditentukan pengguna. Bahasa-bahasa ini biasanya dekat dengan notasi matematika (saya tidak menguraikan bahasa alami). Pengguna menentukan DSL mereka dalam notasi BNF, seperti ini: expr ::= LiteralInteger | ( expr ) | expr + expr | expr *...

Rupanya, serangan ReDos mengeksploitasi karakteristik dari beberapa ekspresi reguler (yang berguna) ... pada dasarnya menyebabkan ledakan jalur yang mungkin melalui grafik yang ditentukan oleh NFA. Apakah mungkin untuk menghindari masalah seperti itu dengan menulis regex 'non-evil' yang setara?...

Jika saya memiliki Tata Bahasa Tipe 3, itu dapat direpresentasikan pada otomat pushdown (tanpa melakukan operasi apa pun pada stack) sehingga saya dapat mewakili ekspresi reguler dengan menggunakan bahasa bebas konteks. Tapi bisakah saya tahu jika tata bahasa tipe 3 adalah , L L ( 1 ) , S L R ( 1 )...

Dimungkinkan untuk menguraikan dokumen menggunakan pass tunggal dari mesin negara. Apa manfaatnya memiliki dua lintasan, yaitu. memiliki lexer untuk mengonversi teks menjadi token, dan memiliki pengurai untuk menguji aturan produksi pada token itu? Mengapa tidak memiliki satu pass yang menerapkan...

Menurut artikel Wikipedia , L dalam berarti "pemindaian kiri-ke-kanan", dan "R" berarti "derivasi paling kanan." Namun, dalam kertas asli Knuth pada L R ( k ) tata bahasa , ia mendefinisikan L R ( k ) (pada halaman 610) sebagai bahasa yang "diterjemahkan dari kiri ke kanan dengan terikat k ."L R (...

Saya mencoba belajar sendiri tentang penggunaan bison. Halaman manual bison (1) mengatakan tentang bison: Hasilkan parser LR deterministik atau LR (GLR) umum yang menggunakan LALR (1), IELR (1), atau tabel parser LR (1) kanonik. Apa itu parser IELR? Semua artikel relevan yang saya temukan di...

Saya sedang memikirkan tata bahasa untuk bahasa indendasi-sensitif dan sepertinya tata bahasa CF akan melakukan trik jika dikombinasikan dengan parameter. Sebagai contoh, pertimbangkan fragmen ini untuk tata bahasa Python yang disederhanakan dalam format seperti ANTLR: // on top-level the...

Saya sering bekerja dengan lexer / parser , sebagai lawan dari parser combinator dan melihat orang-orang yang tidak pernah mengambil kelas dalam parsing, bertanya tentang parsing data biner. Biasanya data tidak hanya biner tetapi juga peka konteks. Ini pada dasarnya menyebabkan hanya memiliki satu...

Saya punya masalah dengan latihan ini: Biarkan G menjadi tata bahasa ambigu berikut untuk kalkulus λ: E → v | λv.E | EE | (E) di mana E adalah simbol non-terminal tunggal, λv.E mewakili abstraksi dari variabel v di E, dan EE mewakili aplikasi. Definisikan tata bahasa LL (1) G ′...

Saya mencoba memahami apa yang dimaksud dengan "deterministik" dalam ungkapan seperti "tata bahasa bebas konteks deterministik". (Ada lebih banyak "hal-hal" deterministik dalam bidang ini). Saya akan menghargai contoh lebih dari penjelasan yang paling rumit! Jika memungkinkan. Sumber kebingungan...

Ini pertanyaan dari Buku Naga. Ini adalah tata bahasanya: S→AaAb∣BbBaS→AaAb∣BbBaS \to AaAb \mid BbBa A→εA→εA \to \varepsilon B→εB→εB \to \varepsilon Pertanyaannya adalah bagaimana menunjukkan bahwa itu LL (1) tetapi tidak SLR (1). Untuk membuktikan bahwa itu adalah LL (1), saya mencoba...

Saya baru-baru ini mempelajari tentang perancangan Compiler. Saya jadi tahu tentang dua jenis tata bahasa satu adalah tata bahasa LL dan lainnya adalah tata bahasa LR. Kita juga tahu fakta bahwa setiap tata bahasa LL adalah LR yang tata bahasa LL adalah bagian yang tepat dari tata bahasa LR. Yang...

Saya ingin mengubah pengguna memasukkan ekspresi reguler ke NFA sehingga saya kemudian dapat menjalankan NFA terhadap string untuk tujuan yang cocok. Apa mesin minimum yang dapat digunakan untuk mem-parsing ekspresi reguler? Saya menganggap itu harus berupa push down automaton karena keberadaan...

Dapatkah seseorang mencerahkan saya mengapa keturunan parser rekursif dengan backtracking yang mencoba produksi dan S → a a (agar) tidak mengakui bahasa yang dibentuk oleh grammar S → a S a | a a .S→ a SSebuahS→SebuahSSebuahS \rightarrow aSaS→ a aS→SebuahSebuahS \rightarrow aaS→ a Sa | a...

Dalam parser LR (0), setiap negara terdiri dari koleksi item LR (0), yang merupakan produksi yang dianotasi dengan suatu posisi. Dalam parser LR (1), setiap negara terdiri dari kumpulan item LR (1), yang merupakan produksi yang dianotasi dengan posisi dan karakter lookahead. Diketahui bahwa diberi...

Ada cara untuk melakukan parsing fuzzy (menerima string bahkan dengan kesalahan pengetikan untuk jarak edit tertentu), dengan DFA dan run-time yang dibuat oleh Levenshtein Automata dari kata input. Bisakah hal serupa dilakukan dengan pengurai Earley? Saya merasa sulit untuk memahami algoritma,...

Menggunakan vektor Earley sebagai pengenal cukup mudah: ketika akhir string tercapai, Anda hanya perlu memeriksa untuk produksi aksiomatik lengkap mulai dari posisi 0. Jika Anda memiliki setidaknya satu, maka string diterima. Menggunakan vektor Earley untuk merekonstruksi pohon parsing kurang...

Di perguruan tinggi kami telah belajar tentang teori komputasi secara umum dan mesin Turing lebih khusus. Salah satu hasil teoretis yang hebat adalah bahwa dengan mengorbankan alfabet (simbol) yang berpotensi besar, Anda dapat mengurangi jumlah status menjadi hanya 2. Saya mencari contoh Mesin...