Apakah bahasa Ekspresi Reguler memerlukan push down automata untuk menguraikannya?

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 kurung berarti kebutuhan untuk menghitung dan DFA / NFA tidak dapat melakukan penghitungan yang sewenang-wenang. Apakah asumsi ini benar? Sebagai contoh, ekspresi a (bc *) d akan membutuhkan PDA sehingga sub-ekspresi dalam kurung ditangani dengan benar.

formal-languages parsers regular-expressions pushdown-automata Phil Wright
sumber

Apa yang Anda maksud dengan "parsing"? Maksud Anda memeriksa apakah input benar-benar ekspresi reguler atau apakah Anda memiliki hal yang lebih rumit, misalnya mesin yang mengeluarkan deskripsi NFA yang sesuai? (jika Anda tidak yakin apakah input benar-benar ekspresi reguler dan Anda perlu memeriksanya maka Anda harus dapat memeriksa bahwa tanda kurung sudah benar dan itu biasanya berarti menggunakan tumpukan.)

Kaveh

Untuk jawaban yang praktis, Anda bisa melihat Rencana 9 sumber Grep untuk grep.y .

Bruce Ediger

Jawaban:

Anda benar. Sangat mudah untuk menunjukkan bahwa sintaks ekspresi reguler tidak teratur menggunakan teknik standar .

$\mathrm{REG}$ $(^p)^p$

Yang mengatakan, Anda mungkin tidak ingin kode PDA dengan tangan. Pertimbangkan untuk menggunakan generator pengurai seperti ANTLR atau byacc . Jika, di sisi lain, Anda ingin menyelidiki parsing bahasa dengan memprogram parser sendiri, Anda harus melanjutkan dengan algoritma parsing dasar lainnya seperti CYK , Earley , keturunan rekursif dan LR .

Raphael
sumber

Terima kasih. menulis kode untuk tugas-tugas ini menciptakan pemahaman yang lebih baik dan tidak dimaksudkan untuk seefisien utilitas yang ada seperti lex, yacc, bison dll.

Phil Wright

@ PhilWright: Begitu, bagus! Saya mengedit petunjuk lebih lanjut untuk kasus ini.

Raphael

Saya lebih suka parser keturunan rekursif tangan-kode untuk yang satu ini.

Dave Clarke

Jika menulis parser dengan tangan untuk ini, baik penurunan rekursif (setelah anjak piutang dan pemijatan) adalah sebuah opsi, parser LCC untuk C < sites.google.com/site/lccretargetablecompiler > memiliki pandangan yang menarik untuk menangani banyak operator. Tapi mungkin yang paling mudah untuk membangun tangan adalah penguraian yang diutamakan.

vonbrand

Saya sarankan Anda untuk membaca jawaban Jukka yang bagus untuk pertanyaan " Mencocokkan ekspresi reguler dengan ekspresi reguler " di cstheory, juga. Kutipan:

Misalnya, kita dapat memodifikasi notasi standar sebagai berikut untuk mendapatkan ekspresi reguler "terkompresi" :

Anda diizinkan untuk menghapus awalan yang terdiri dari urutan (

Anda diizinkan menghapus sufiks apa pun yang terdiri dari urutan)

Artinya, ((a|b)*c)de(f|g)dapat dinyatakan dalam "kompresi" notasi menggunakan, misalnya, salah satu bentuk berikut: a|b)*c)de(f|gatau ((a|b)*c)de(f|gatau (a|b)*c)de(f|g).

[...]

Notasi "terkompresi" (dari ekspresi reguler) adalah bahasa biasa.

Ini hanya tautan ke "pandangan berbeda" yang menarik (menurut saya) tentang bahasa ekspresi reguler; seperti yang digarisbawahi dalam komentar di bawah ini, tidak berguna untuk membangun pohon sintaks. Jika Anda ingin memberikan kode parser Anda, saya akan menyarankan Anda artikel sederhana ini pada codeproject " Writing-own-regular-expression-parser ".

Vor
sumber

Jukka pada dasarnya menghilangkan persyaratan bahwa tanda kurung seimbang. Saya tahu tidak ada contoh di mana ini sebenarnya dilakukan, tetapi perlu berkomentar bahwa dengan mengubah semantik, Anda dapat "menyederhanakan" sintaksis.

Raphael

Anda (dan Jukka) tidak parsing regexps, hanya mengenali mereka. "Yup, itu regexp (terkompresi)."

Gilles 'SO- stop being evil'