Hubungan antara penguraian shift-kurangi dan kelanjutan yang dibatasi?

13

Adakah yang meresmikan hubungan antara teknik parsing pengurangan-pengurangan dan kelanjutan yang dibatasi?

Ketika membuat parser bottom-up (mis., Parser LR), kami mengambil tata bahasa dan kemudian menyatakan status parse sebagai set item : produksi augmented dari bentuk , di mana α dan β adalah urutan terminal dan nonterminals. Marker ∙ menunjukkan seberapa jauh parser masuk ke dalam string, dengan α mewakili apa yang telah dilihat sejauh ini, dan β mewakili prediksi dari apa yang belum dapat diuraikan.SEBUAH→α∙βαβ∙αβ

αSEBUAH

Adakah yang pernah mempelajari koneksi antara operator pengurang shift-parsing dan dibatasi seperti shift / reset?

pl.programming-languages parsing Neel Krishnaswami
sumber
Pengamatan menarik.
Dave Clarke
Orang bisa berharap Michael Sperber menulis di suatu tempat tentang hubungan ini, mengingat karyanya tentang penguraian CPS LR dan kelanjutan yang dibatasi, tetapi saya belum menemukan apa pun.
Sylvain
Saya ingat Ken Shan menyebutkan hubungan ini dengan saya di tahun 2004, dan menyarankan bahwa itu akan menjadi peluang permainan kata yang bagus. Tapi saya tidak tahu bahwa dia menulis / membuat kode tentang hal itu sejak itu.
Noam Zeilberger

Jawaban:

4

Saya percaya bahwa makalah berikut ini mengeksplorasi beberapa koneksi ini, sebagian besar dengan menggunakan kelanjutan untuk mundur ketika hal-hal terjadi di parser. Tapi pasti ada lagi yang bisa dilakukan di sini.

Rollback modular melalui logging kontrol: Sepasang mutiara fungsional kembar

Olin Shivers, Aaron Turon , ICFP 2011.

Sam Tobin-Hochstadt
sumber