Ganti parsing - pecahkan pertanyaan

Saya baru-baru ini menemukan makalah yang menggambarkan teknik parsing yang disebutkan dalam judul. Sayangnya, terminologi yang digunakan dalam makalah tersebut agak di luar pemahaman saya, jadi saya telah berusaha memahami algoritma konstruksi lebih intuitif. Saya percaya saya berhasil ( presentasi ini adalah sumber dari momen ah-ha), tetapi verifikasi kebenaran dari seseorang yang akrab dengan teknik atau terminologi yang terkandung di dalamnya akan sangat dihargai.

Saya akan menjelaskan bagaimana saya mengambil solusinya (jika itu benar, saya yakin ini bisa membantu orang lain yang mencoba memahami teknik ini) dan mengajukan pertanyaan tambahan sesudahnya. Untuk memastikan tidak ada kesalahpahaman, saya akan menggunakan notasi standar berikut: , , , dan, seperti di koran, untuk menunjukkan aturan nomor . Namun, saya mungkin akan menggunakan nama yang berbeda untuk konsep daripada makalah aslinya.A , B , C , . . . ∈ N . . . X , Y , Z ∈ N ∪ T α , β , γ , . . . ∈ { N ∪ T } ∗ A i → ω $a, b, c, ... \in T$$A, B, C, ... \in N$$... X, Y, Z \in N \cup T$$\alpha, \beta, \gamma, ... \in \{N \cup T\}^*$$A \xrightarrow{i} \omega$$i$

Selain itu, sepanjang deskripsi, relasi ekivalensi digunakan.$\kappa_0$

Konstruksi

Ada dua jenis item di dalam parsing automaton: LR sederhana (0) item dari bentuk yang saya sebut item pergeseran dan item dari bentuk yang saya sebut item penyelesaian ; ini memberi tahu parser untuk menekan simbol kembali ke input stream dan kemudian mengurangi dengan aturan nomor pada simbol pertama .$A \xrightarrow{i} \alpha \bullet \beta$$A \xrightarrow{i} \alpha \bullet \beta, m, n$m $n$$m$$\beta$

Tata bahasanya ditambah dengan aturan dan konstruksi dimulai dengan item shift dalam kondisi awal.S ′ 0 → ∙ S $S' \xrightarrow{0} S \$$$S' \xrightarrow{0} \bullet S \$$

Sekarang, untuk membuat automaton, tentukan di antara alternatif ini untuk setiap item dalam keadaan :$q$

1. Jika item tersebut adalah item shift , akan ada transisi dalam otomaton, di mana adalah simbol pertama .q X → q ′ X $A \xrightarrow{i} \alpha \bullet \beta$$q \xrightarrow{X} q'$$X$$\beta$

2. Jika item tersebut adalah item shift jadi , tambahkan item tekad untuk setiap aturan .B j → α A ∙ β , i , 0 B j → α A $A \xrightarrow{i} \omega \bullet$$B \xrightarrow{j} \alpha A \bullet \beta, i, 0$$B \xrightarrow{j} \alpha A \beta$

3. Jika item tersebut adalah item penyelesaian , misalkan menjadi simbol pertama dari . Jika , tambahkan item shift untuk setiap aturan . Jika item selain memiliki sebagai dot lookahead mereka, tambahkan transisi ke otomaton. Setiap item penyelesaian di akan menghasilkan item penyelesaian inX β X ∈ N X j → ∙ ω X j → ω A i → α ∙ β , m , n X q X → q $A \xrightarrow{i} \alpha \bullet \beta, m, n$$X$$\beta$$X \in N$$X \xrightarrow{j} \bullet \omega$$X \xrightarrow{j} \omega$$A \xrightarrow{i} \alpha \bullet \beta, m, n$$X$$q \xrightarrow{X} q'$q C i → α X ∙ β , $C \xrightarrow{i} \alpha \bullet X \beta, m, n$$q$q $C \xrightarrow{i} \alpha X \bullet \beta, m, n + 1$$q'$ .

4. Jika item tersebut adalah item tekad itu tidak akan menyumbangkan informasi lookahead apa pun dan dapat dibuang, tetapi pertama-tama tambahkan item tekad untuk setiap aturan .$A \xrightarrow{i} \omega \bullet, m, n$$B \xrightarrow{j} \alpha A \bullet \beta, m, n$$B \xrightarrow{j} \alpha A \beta$

Ini, tentu saja, hanya sebuah sketsa; sebenarnya, penutupan negara harus dihitung dulu dan baru setelah itu kita bisa berurusan dengan transisi / perubahan dan resolusi.

Mengubah otomat menjadi tabel parsing shift-resolve sepele setelahnya; hanya, sebagai variasi kecil, penulis makalah menafsirkan resolusi sebagai tindakan menerima. Mengingat hasil otomatisnya, saya merasa lebih mudah memperlakukan pergeseran sebagai tindakan penerimaan.$r_{0,0}$$\$$

Pertanyaan

Yang pertama adalah, jelas, apakah proses yang dijelaskan di atas benar.

Yang kedua adalah tentang hubungan ekivalensi. Saya hanya bisa menebak bahwa relasi ekivalensi adalah yang bertanggung jawab untuk memutuskan item penyelesaian yang dibawa ketika item shift selesai telah terlihat. tampaknya menghasilkan lookahead yang sangat mirip dengan dari parser LSLR. Makalah ini menjelaskan "hubungan kesetaraan yang lebih baik" di halaman 11; adakah cara untuk menafsirkan hubungan ini dalam istilah intuitif? Apakah ada hubungan lain yang diketahui?$\kappa$$\kappa_0$$FOLLOW_{LM}$

Dan yang terakhir adalah tentang resolusi konflik. Makalah ini menjelaskan dengan baik apa yang merupakan ketidakmampuan dalam otomat penyelesaian-perubahan; Adakah cara untuk menyelesaikan kekurangan ini, mirip dengan cara menyelesaikan konflik dalam parser LR tradisional? Bisakah sesuatu seperti resolusi konflik gaya- yacc melalui presedensi dan asosiatif diimplementasikan dalam generator parser ShRe?

Terima kasih jika Anda membaca semua ini dan jawaban apa pun akan sangat dihargai :)

Periksa apakah ini dibahas dalam ensiklopedia D. Grune, CJH Jacobs, "Teknik Parsing: Panduan Praktis" (Spinger, 2008). Jika tidak, mungkin itu cukup mirip dengan teknik yang dibahas.