Apa itu IARR (1) -parser?

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 world wide web adalah paywalled.

formal-languages terminology formal-grammars parsers FUZxxl
sumber

Termasuk cs.clemson.edu/~malloy/papers/sac08/paper.pdf ?

reinierpost

@reinierpost Saya merasa sangat bodoh sekarang. Mengapa saya tidak menemukan ini?

FUZxxl

Saya tidak tahu - Google mempersonalisasi hasil ...

reinierpost

@reinierpost, apakah Anda ingin menjawab pertanyaan ini dengan mengutip tautan Anda, sehingga dapat membersihkan pertanyaan ini ?

Merbs

Hmmm ... kalau itu yang diperlukan, oke.

reinierpost

Jawaban:

The IELR (1) Algoritma Parsing

The IELR algoritma (1) parsing dikembangkan pada tahun 2008 oleh Joel E. Denny sebagai bagian dari gelar Ph.D. penelitian di bawah pengawasan Brian A. Malloy di Universitas Clemson. Algoritma IELR (1) adalah variasi dari apa yang disebut algoritma "minimal" LR (1) yang dikembangkan oleh David Pager pada tahun 1977 , yang merupakan variasi dari algoritma parsing LR (k) yang ditemukan oleh Donald Knuth pada tahun 1965 . IE in IELR (1) adalah singkatan dari eliminasi ketidakcukupan (lihat bagian terakhir).

Algoritma LR (1)

The LR (1) bagian dari IELR (1) singkatan L TDE ke kanan, R ightmost derivasi dengan 1 lookahead tanda. LR (1) parser juga disebut parser kanonik. Kelas algoritma parsing ini menggunakan strategi parsing bottom-up, shift-mengurangi parsing dengan stack dan tabel transisi status menentukan tindakan selanjutnya yang akan diambil selama parsing.

Secara historis, algoritma LR (1) telah dirugikan oleh kebutuhan memori yang besar untuk tabel transisi mereka. Perbaikan Pager adalah untuk mengembangkan metode menggabungkan keadaan transisi ketika tabel transisi dihasilkan, secara signifikan mengurangi ukuran tabel. Dengan demikian algoritma Pager membuat LR (1) parser kompetitif dengan strategi parsing lainnya sehubungan dengan efisiensi ruang dan waktu. Frasa "minimal LR (1) parser" mengacu pada ukuran minimal tabel transisi yang diperkenalkan oleh algoritma Pager.

Keterbatasan Algoritma Pager

Algoritma LR minimal (1) menghasilkan tabel transisi berdasarkan tata bahasa input tertentu untuk bahasa yang akan diuraikan. Tata bahasa yang berbeda dapat menghasilkan bahasa yang sama. Memang, dimungkinkan untuk tata bahasa non-LR (1) untuk menghasilkan bahasa yang dapat diurai LR (1). Dalam praktiknya, generator parser LR (1) menerima tata bahasa non-LR (1) dengan spesifikasi untuk menyelesaikan konflik antara dua kemungkinan transisi negara ("konflik pengurangan-konflik") untuk mengakomodasi fakta ini. Denny dan Malloy menemukan bahwa algoritma Pager gagal menghasilkan parser yang cukup kuat untuk mem-parsing bahasa LR (1) ketika disediakan tata bahasa non-LR (1) tertentu meskipun tata bahasa non-LR (1) menghasilkan bahasa LR (1).

Denny dan Malloy menunjukkan bahwa batasan ini tidak hanya bersifat akademis dengan menunjukkan bahwa Gawk dan Gpic, yang keduanya banyak digunakan, perangkat lunak dewasa, melakukan tindakan parser yang salah.

Perbaikan IELR (1)

Denny dan Malloy mempelajari sumber kekurangan algoritma Pager dengan membandingkan tabel transisi yang dihasilkan oleh algoritma Pager dengan tabel transisi dari tata bahasa LR (1) yang setara dan mengidentifikasi dua sumber dari apa yang mereka sebut kekurangan yang muncul dalam tabel transisi dari Pager's algoritma tetapi tidak dalam tabel transisi LR (1). Algoritma IELR (1) ( Inadequacy Elimination LR (1)) Denny dan Malloy adalah algoritma yang dirancang untuk menghilangkan kekurangan ini ketika membuat tabel transisi yang ukurannya hampir identik dengan ukuran algoritma Pager.

Robert Jacobson
sumber

Sebuah artikel yang mengklaim memperkenalkannya: IELR (1): Praktis LR (1) Tabel Parser untuk Non-LR (1) Tata Bahasa dengan Resolusi Konflik (via archive.org) oleh Joel E. Denny dan Brian A. Malloy, Clemson University , tersedia secara gratis dari situs Malloy.

Nilai mereka adalah sesuatu yang tidak bisa saya jawab. (Secara pribadi saya tidak mengerti perlunya penguraian CFG yang lumpuh - mengapa membatasi kekuatan ekspresif Anda ketika Anda bisa menggunakan GLR ? Apa yang masuk akal bagi saya adalah sesuatu seperti TAG atau PEG (mereka tampak alami dan menambah daya ekspresif) atau pohon tata bahasa (untuk bahasa seperti XML, di mana mengenali pohon parse tidak bermasalah dengan desain.)

reinierpost
sumber

Sementara saya setuju pada prinsip mengenai teknologi, masalahnya sering bahwa parsing deterministik tradisional memiliki implementasi yang lebih baik, lebih lengkap. Masalah lainnya adalah parsing CF Umum lebih kuat, tetapi GLR mungkin bukan versi terbaiknya.

babou

Alasan utama mengapa orang mengembangkan parser CFG pincang adalah bahwa parser GLR tidak harus berjalan dalam waktu linier — ini adalah masalah besar bagi banyak aplikasi. Pengurai IELR dapat menjamin runtime linier dan banyak lagi.

FUZxxl

Saya tidak mengerti mengapa itu menjadi masalah.

reinierpost

O (n^{4})

$O(n^4)$

O (n^{3})

$O(n^3)$

l i m_{x \to \infty} O (n^{x})

$lim_{x\rightarrow\infty} O(n^x)$ . Manusia tidak hidup selamanya dan memiliki banyak hal untuk dilakukan. Membuang-buang waktu mereka umumnya buruk.

pengguna

Saya ingin mencatat bahwa "Secara pribadi saya tidak mengerti perlunya penguraian CFG yang lumpuh - mengapa membatasi kekuatan ekspresif Anda ketika Anda bisa menggunakan GLR?" agak salah arah dalam konteks ini. IELR (1) digunakan untuk menghasilkan tabel parser LR (1) yang lebih efisien , yang memungkinkan parser GLR yang lebih efisien .

orlp