Diberikan string dan CFG, karakter apa yang dapat mengikuti string (dalam bentuk sentimental CFG)?

Mari adalah himpunan terminal dan himpunan simbol non-terminal dari beberapa bebas konteks tata bahasa .$\Sigma$$N$$G$

Katakanlah saya memiliki string sedemikian rupa sehingga mana dan adalah bentuk sentensial .$a \in (\Sigma \cup N)^+$$x a y \in \mathcal{S}(G)$$x,y\in (\Sigma \cup N)^*$$\mathcal{S}(G)$$G$

Diberikan , saya ingin menentukan himpunan .$G$$C = \{ b \mid wabz \in \mathcal{S}(G), b \in \Sigma \cup N \}$

Untuk memperjelas, dalam hal ini, adalah string terminal dan non-terminal dan adalah panjang satu.$w, x, y, z, a, b$$b$

Saya bisa melihat bagaimana melakukan ini jika juga panjang satu; masing-masing adalah anggota dari rangkaian tindak (termasuk bukan terminal).$a$$b$$a$

Namun, saya ingin tahu apakah mungkin untuk urutan karakter. Untuk aplikasi saya, string tidak lebih lama dari sisi kanan dari produksi di .$a$$G$

Perbedaan antara terminal dan non-terminal agak bisu dalam aplikasi saya karena saya menggunakan tata bahasa generatif; dan saya percaya bahwa ini tidak akan menyebabkan banyak masalah karena adalah panjang satu.$b$

Saya akan menjelaskan algoritma yang berfungsi. Ini waktu yang berjalan seharusnya tidak terlalu buruk. Anda dapat melakukan precompute sedikit ini juga.

Saya akan berasumsi bahwa tidak mengandung nonterminals (meskipun mungkin mudah untuk beradaptasi dengan kasus itu) dan bahwa Anda tidak tahu , atau derivasi dari . Saya juga akan menganggap tata bahasa Anda tidak mengandung produksi yang tidak pernah digunakan dalam derivasi apa pun (misalnya ).$a$$x$$y$$a$$A \rightarrow A$

Masalah utama benar-benar adalah untuk mengurai , seperti yang Anda ingin tahu apa jenis negara Anda berakhir di, sehingga Anda tahu apa yang dapat mengikuti . Ini tidak mudah karena Anda tidak tahu .$a$$a$$x$

Kami menggunakan adaptasi algoritma Earley . Anda harus terlebih dahulu memahami algoritma itu. Algoritma kami bekerja dengan cara yang hampir sama, kecuali langkah inisialisasi dan penyelesaian kami berbeda.

Untuk inisialisasi, kami menyemai set pertama kami dengan item Earley untuk setiap kemunculan (karakter pertama dalam ) dalam setiap produksi tata bahasa Anda. Kami menetapkan pointer belakang item ini ke -1, nilai yang tidak valid. Ini penting dalam penyelesaian yang kami modifikasi. Pada dasarnya, -1 berarti 'Saya tidak tahu di mana produksi ini dimulai'.$a_1$$a$

Sekarang, kami melakukan algoritma Earley secara terpisah untuk setiap item Earley awal yang mungkin. Kita tidak bisa begitu saja melakukan semuanya pada saat yang sama, karena parse dapat saling mengganggu. Saya tidak dapat dengan mudah melihat metode yang lebih cepat daripada mundur di sini.

Untuk langkah penyelesaian, kita hanya perlu membuat modifikasi untuk menangani -1 pointer belakang. Karena kami telah menyelesaikan produksi yang asalnya tidak kami ketahui, kami dalam masalah. Namun, metode yang digunakan untuk menghitung set lookahead$LALR(1)$ oleh Pennello dan DeRemer menyelamatkan kita: apa yang kita butuhkan di sini adalah set lookhead . Setiap item dalam set lookahead ini memiliki posisi yang sesuai dalam tata bahasa, yang pada gilirannya sesuai dengan kemungkinan kelanjutan dari produksi yang selesai.$LALR(1)$

Sayangnya, saya tidak benar-benar melihat pilihan lain selain mundur sekali lagi di sini. Untuk setiap posisi dalam set lookahead, Anda melakukan langkah penyelesaian dengan posisi ini, dan melanjutkan parse dari sana. Anda melakukan ini secara terpisah untuk setiap parse. Perhatikan bahwa jika tata bahasa Anda adalah , kepala pencarian Anda akan secara unik menentukan posisi mana yang harus Anda tuju, sehingga Anda tidak harus mundur.$LALR(1)$

Anda melanjutkan algoritma di atas satu karakter di luar , di mana Anda menganggap karakter virtual ekstra ini sebagai 'karakter apa saja', yang segera memberi Anda set 'follow' yang Anda cari - kapan pun fase pemindai menemukan sesuatu untuk tugas akhir ini atur, Anda dapat menambahkan karakter ini ke set jawaban Anda.$a$

Sunting: Saya pikir saya telah menemukan metode yang menghilangkan sebagian besar overhead yang dikenalkan oleh backtracking. Kami mengaitkan dengan setiap item Earley satu set pengidentifikasi, yang merupakan string, karena kami harus menggunakan awalan dari pengidentifikasi ini. Pada inisialisasi, kami menambahkan semua item awal ke set Earley, dan mengaitkan pengidentifikasi unik dengan setiap set.

Pada langkah-langkah pemindai dan prediktor, pengidentifikasi dibawa ke item baru. Item Earley di set Earley yang sama yang hanya berbeda dalam pengidentifikasi mereka digabung bersama dengan menggabungkan pengidentifikasi mereka bersama. Perhatikan bahwa kita dapat melakukan langkah-langkah pemindai dan prediksi pada item baru ini dengan pengidentifikasi, tanpa harus melakukan langkah ini untuk setiap pengidentifikasi secara terpisah.

Penyelesai mempertimbangkan pengidentifikasi secara terpisah, dan hanya menyelesaikan item jika item yang sesuai dalam itemset sebelumnya memiliki pengidentifikasi yang merupakan awalan dari pengidentifikasi. Untuk setiap kemungkinan penyelesaian (jadi untuk setiap item dalam set lookupead ), kami menambahkan karakter unik ke pengidentifikasi item yang selesai.$LALR(1)$

Pada dasarnya, kami melakukan backtracking menggunakan pengidentifikasi ini, sehingga kami tidak melakukan pekerjaan ganda dalam langkah-langkah pemindai dan prediktor.