Frase permutasi dengan parsing LR

Ungkapan permutasi adalah ekstensi ke definisi tata bahasa bebas konteks standar (E) BNF: frase permutasi berisi produksi (atau setara, nonterminals) hingga . Pada posisi kalimat permutasi, kami ingin melihat setiap produksi ini tepat satu kali, tetapi kami tidak tertarik dengan pemesanan nonterminal ini.$\{ A_1, \dots, A_n \}$$n$$A_1$$A_n$

Sebagai contoh:

S <- X { A, B, C } Y

setara dengan:

S <- X  A B C  Y
S <- X  A C B  Y
S <- X  B A C  Y
S <- X  B C A  Y
S <- X  C A B  Y
S <- X  C B A  Y

Konsep ini tampaknya diperkenalkan dalam "Memperluas tata bahasa bebas konteks dengan frase permutasi" . Di dalamnya juga dijelaskan cara mem-parse frasa-frasa ini dalam waktu linier menggunakan parser LL (1).

Makalah "Parsing permutasi frase" menjelaskan metode untuk mengurai frase permutasi menggunakan kombinator parser. Ini adalah satu-satunya dua makalah yang saya temukan yang berbicara tentang frasa permutasi dan cara menguraikannya.

Melihat bahwa kita dapat dengan mudah menguraikan jenis-jenis frase permutasi dengan parser berbasis LL (1), tebakan saya adalah bahwa kita dapat melakukan hal yang sama dengan parser gaya LR (1). Karena itu pertanyaan saya adalah:

Bisakah tata bahasa yang mengandung frasa permutasi diurai dalam waktu linier dalam ukuran string input menggunakan mesin LR (1) sambil mempertahankan tabel berukuran cukup?

Frasa permutasi tidak memperpanjang kekuatan bahasa bebas konteks: seperti pada contoh saya di atas, seseorang dapat dengan mudah menyebutkan semua permutasi yang mungkin. Namun, tata bahasa kemudian meledak karena tata bahasa yang dihasilkan bisa berukuran . Ini memungkinkan penguraian waktu linear, tetapi ukuran tata bahasa menjadi terlalu besar.$O(|G|!)$

Pendekatan di atas berfungsi untuk algoritme penguraian apa pun (meskipun tidak berguna), jadi mungkin kita bisa melakukan yang lebih baik untuk algoritme tertentu. Kita dapat mengurangi blowup menjadi 'hanya' eksponensial ( ) dengan menyandikan frasa ke dalam tabel LR: kita dapat memiliki item LR mengkodekan produksi mana yang belum dilihat, dan karenanya mengurangi blowup untuk semua himpunan bagian dari frasa permutasi.$O(2^{|G|})$

Meskipun ini lebih baik, tentu saja tidak cukup baik - memiliki frasa permutasi 30 item akan membuat tata bahasa tidak dapat digunakan. Masih ada satu bagian dari parsing LR yang belum kami sentuh, dan itu adalah prosedur berbasis stack yang sebenarnya digunakan untuk parsing. Saya membayangkan menyimpan counter di stack mungkin bisa menyelesaikan masalah, tetapi saya tidak yakin bagaimana cara melakukannya.

Saat ini saya sedang mengimplementasikan generator parser, dan dalam frase permutasi domain masalah akan menjadi hadiah dari surga. Karena saya menggunakan mesin LR (1), pertanyaan di atas diikuti.

Sudahkah Anda mempertimbangkan untuk mengubahnya menjadi masalah semantik? Alih-alih aturan tata bahasa untuk semua permutasi nonterminals {A, B, C}, hanya memiliki satu aturan untuk mengenali (A | B | C) ^ 3 bersama dengan kode internal khusus yang memastikan hanya satu dari masing-masing diakui, jika tidak menyatakan kesalahan. Saya akan memasukkan produksi kosong sebelum klausa di atas, yang pengurangan memicu inisialisasi apa pun yang Anda gunakan untuk menghitung A, B, dan C, dan satu setelah, yang pengurangan memicu cek counter dan (jika perlu) menegaskan kesalahan. (tentu saja ini bisa sedikit rumit jika tata bahasa bersifat rekursif melalui A, B, dan / atau C)

Saya tidak berpikir orang perlu counter. Pada dasarnya Anda hanya memeriksa semua permutasi tetapi istirahat

pseudo-code:

perm-match(input, pattern)
     if pattern = nil return true

     foreach(rule in pattern)
         if (match(input, rule))
             perm-match(input - matchedpart, pattern - rule)
             break
         end
     end
     return false
end

Ini adalah contoh yang lebih konkret

Misalkan kita mencoba mencocokkan permutasi abcd dan string kita adalah bcda

• Langkah 1: Temukan simbol yang cocok pertama. Dalam hal ini adalah b
• Langkah 2: Hapus simbol itu dari pola kita dan kurangi string: mis., Acd dan cda dibiarkan
• Langkah 3: Ulangi langkah 1 pada string baru
  • c cocok dengan cda yang meninggalkan kita dengan iklan dan da
  • a pertandingan di da yang meninggalkan kita dengan d dan d
  • d cocok dengan d yang membuat kita nihil di kedua string

Jadi Anda lihat algoritma sederhana ini dapat memeriksa permutasi dengan cukup mudah dengan hanya membandingkan "string" yang rusak. Perhatikan bahwa kompleksitas fungsi adalah kasus terburuk O (n!) Dan kasus terbaik O (1). Dalam arti tertentu, kita terus menghitung dengan menyimpan simbol yang cocok dengan array. Saya akan berpikir ini akan menjadi "cepat" secara umum karena orang tidak akan berurusan dengan sangat besar dan dalam banyak kasus.