Mengapa tata bahasa ambigu buruk?

Saya mengerti bahwa jika ada 2 atau lebih pohon derivasi kiri atau kanan, maka tata bahasanya ambigu, tetapi saya tidak dapat memahami mengapa hal itu sangat buruk sehingga semua orang ingin menyingkirkannya.

Pertimbangkan tata bahasa berikut untuk ekspresi aritmatika:

Menurut yang di sebelah kiri, kita harus menafsirkan $a-b-c$ sebagai $(a-b)-c$ , yang merupakan interpretasi biasa. Menurut yang di sebelah kanan, kita harus menafsirkannya sebagai $a-(b-c) = a-b+c$ , yang mungkin bukan yang dimaksudkan.

Saat menyusun program, kami ingin interpretasi sintaksinya tidak ambigu. Cara termudah untuk menegakkan ini adalah menggunakan tata bahasa yang tidak ambigu. Jika tata bahasanya ambigu, kami dapat memberikan aturan yang mengikat, seperti prioritas operator dan asosiatif. Aturan-aturan ini dapat diekspresikan secara ekivalen dengan membuat tata bahasa tidak ambigu dengan cara tertentu.

Pohon parsing dihasilkan menggunakan generator pohon sintaks .

Berbeda dengan jawaban lain yang ada [ 1 , 2 ], memang ada bidang aplikasi, di mana tata bahasa yang ambigu berguna . Di bidang pemrosesan bahasa alami (NLP), ketika Anda ingin mengurai bahasa alami (NL) dengan tata bahasa formal, Anda punya masalah bahwa NL secara inheren ambigu pada tingkat yang berbeda [diadaptasi dari Koh18, ch. 6.4]:

• Ambuigitas sintaksis:

  Peter mengejar pria itu dengan mobil sport merah

  Apakah Peter atau laki-laki di mobil sport merah?

• Ambiguitas semantik:

  Peter pergi ke bank

  Bank tempat duduk atau bank untuk menarik uang?

• Ambiguitas pragmatis:

  Dua pria membawa dua tas

  Apakah mereka membawa tas bersama-sama atau masing-masing membawa dua tas?

Pendekatan yang berbeda untuk NLP berurusan secara berbeda dengan pemrosesan secara umum dan khususnya ambuigitas ini. Misalnya, pipa Anda mungkin terlihat sebagai berikut:

1. Parse NL dengan tata bahasa yang ambigu
2. Untuk setiap AST yang dihasilkan: jalankan pembuatan model untuk menghasilkan makna semantik yang mendua dan untuk mengesampingkan ambiguitas sintaksis yang tidak mungkin dari langkah 1
3. Untuk setiap model yang dihasilkan: simpan di cache Anda.

Anda melakukan pipa ini untuk setiap kalimat. Semakin banyak teks, katakanlah, dari buku yang sama yang Anda proses, semakin Anda dapat mengesampingkan model-model yang tidak berguna, yang bertahan sampai langkah 3, dari kalimat sebelumnya.

Berbeda dengan bahasa pemrograman, kita dapat melepaskan persyaratan bahwa setiap kalimat NL memiliki semantik yang tepat. Sebagai gantinya, kita bisa membukukan beberapa model semantik yang mungkin di seluruh parsing teks yang lebih besar. Dari saat ke saat, wawasan selanjutnya membantu kami untuk menyingkirkan ambiguitas sebelumnya.

Jika Anda ingin membuat tangan Anda kotor dengan parser yang mampu menghasilkan banyak derivasi untuk tata bahasa yang ambigu, lihatlah di Grammatical Framework . Juga, [Koh18, ch. 5] memiliki pengantar untuk itu menunjukkan sesuatu yang mirip dengan pipa saya di atas. Namun perlu dicatat bahwa karena [Koh18] adalah catatan kuliah, catatan itu mungkin tidak akan mudah dimengerti sendiri tanpa kuliah.

Referensi

[Koh18]: Michael Kohlhase. "Pemrosesan Bahasa Alam Berbasis Logika. Semester Musim Dingin 2018/19. Catatan Kuliah." URL: https://kwarc.info/teaching/LBS/notes.pdf . URL deskripsi kursus: https://kwarc.info/courses/lbs/ (dalam bahasa Jerman)

[Koh18, ch. 5]: Lihat bab 5, "Menerapkan Fragmen: Kerangka Kerja Tata Bahasa dan Logika", dalam [Koh18]

[Koh18, ch. 6.4] Lihat bab 6.4, "Peran Ambiguitas Komputasi", dalam [Koh18]

Bahkan jika ada cara yang didefinisikan dengan baik untuk menangani ambiguitas (ekspresi ambigu adalah kesalahan sintaks, misalnya), tata bahasa ini masih menyebabkan masalah. Segera setelah Anda memperkenalkan ambiguitas ke dalam tata bahasa, pengurai tidak dapat lagi memastikan bahwa kecocokan pertama yang didapat adalah pasti. Perlu terus mencoba semua cara lain untuk mengurai pernyataan, untuk mengesampingkan ambiguitas. Anda juga tidak berurusan dengan sesuatu yang sederhana seperti bahasa LL (1), jadi Anda tidak bisa menggunakan pengurai sederhana, kecil, dan cepat. Tata bahasa Anda memiliki simbol-simbol yang dapat dibaca banyak cara, jadi Anda harus siap untuk mundur banyak.

Di beberapa domain terbatas, Anda mungkin dapat membuktikan bahwa semua cara yang mungkin untuk menguraikan ekspresi adalah sama (misalnya, karena mereka mewakili operasi asosiatif). (a + b) + c = a + (b + c).

Apakah IF a THEN IF b THEN x ELSE yartinya

IF a THEN
    IF b THEN
        x
    ELSE
        y

atau

IF a THEN
    IF b THEN x
ELSE
    y

? AKA masalah menjuntai lain .

Ambil parse yang paling menjengkelkan di C ++ misalnya:

bar foo(foobar());

Apakah ini deklarasi fungsi footipe bar(foobar())(parameternya adalah pointer fungsi yang mengembalikan a foobar), atau deklarasi variabel footipe intdan diinisialisasi dengan default yang diinisialisasi foobar?

Ini dibedakan dalam kompiler dengan mengasumsikan yang pertama kecuali ekspresi di dalam daftar parameter tidak dapat diartikan sebagai tipe.

ketika Anda mendapatkan ekspresi yang ambigu, kompiler memiliki 2 opsi

1. mengasumsikan bahwa ekspresi adalah derivasi tertentu dan menambahkan beberapa disambiguator ke tata bahasa untuk memungkinkan derivasi lainnya diekspresikan.

2. salah dan perlu disambiguasi dengan cara apa pun

Yang pertama dapat jatuh secara alami, yang kedua mensyaratkan bahwa programmer kompiler tahu tentang ambiguitas.

Jika ambiguitas ini tetap tidak terdeteksi maka ada kemungkinan bahwa 2 kompiler yang berbeda default ke derivasi yang berbeda untuk ekspresi ambigu tersebut. Menuju kode menjadi non-portabel karena alasan yang tidak jelas. Yang membuat orang menganggap itu bug di salah satu kompiler sementara itu sebenarnya kesalahan dalam spesifikasi bahasa.

Saya pikir pertanyaannya berisi asumsi bahwa hanya batas yang paling baik.

Dalam kehidupan nyata itu cukup umum untuk hidup dengan tata bahasa yang ambigu, selama mereka tidak (sehingga untuk berbicara) terlalu ambigu.

Misalnya, jika Anda melihat-lihat tata bahasa yang dikompilasi dengan yacc (atau serupa, seperti bison atau byacc) Anda akan menemukan bahwa beberapa menghasilkan peringatan tentang "N shift / reduksi konflik" ketika Anda menyusunnya. Ketika Anda menemukan pergeseran / mengurangi konflik, itu menandakan ambiguitas dalam tata bahasa.

Pergeseran / pengurangan konflik, bagaimanapun, biasanya merupakan masalah yang cukup kecil. Generator parser akan menyelesaikan konflik demi "shift" daripada mengurangi. Tata bahasanya baik-baik saja jika itu yang Anda inginkan (dan tampaknya berhasil dengan baik dalam praktiknya).

Pergeseran / pengurangan konflik biasanya muncul dalam kasus pada pesanan umum ini (menggunakan tutup untuk non-terminal dan huruf kecil untuk terminal):

A -> B | c
B -> a | c

Ketika kita menjumpai a c, ada ambiguitas: haruskah kita menguraikan csecara langsung sebagai A, atau haruskah kita menguraikannya sebagai B, yang pada gilirannya adalah A? Dalam kasus seperti ini, yacc dan semacamnya akan memilih rute yang lebih sederhana / lebih pendek, dan mem-parsing clangsung sebagai rute, Adaripada memilih rute c-> B-> A. Ini bisa salah, tetapi jika demikian, itu mungkin berarti Anda memiliki kesalahan tata bahasa yang sangat sederhana, dan Anda seharusnya tidak membiarkan copsi itu sama sekali memungkinkan A.

Sebaliknya, kita dapat memiliki sesuatu yang lebih seperti ini:

A -> B | C
B -> a | c
C -> b | c

Sekarang ketika kita menghadapi a ckita memiliki konflik antara apakah memperlakukan csebagai a Batau a C. Ada sedikit kemungkinan bahwa strategi resolusi konflik otomatis akan memilih apa yang benar-benar kita inginkan. Tak satu pun dari ini adalah "shift" - keduanya adalah "reduksi", jadi ini adalah "mengurangi / mengurangi konflik" (yang mereka terbiasa dengan yacc dan umumnya dikenal sebagai masalah yang jauh lebih besar daripada pergeseran / pengurangan konflik).

Jadi, meskipun saya tidak yakin saya akan mengatakan bahwa ada orang yang benar-benar menyambut ambiguitas dalam tata bahasa mereka, setidaknya dalam beberapa kasus itu cukup kecil sehingga tidak ada yang benar-benar peduli banyak tentang hal itu. Secara abstrak mereka mungkin menyukai gagasan untuk menghapus semua ambiguitas - tetapi tidak cukup untuk selalu benar-benar melakukannya. Misalnya, tata bahasa kecil dan sederhana yang berisi ambiguitas kecil dapat lebih disukai daripada tata bahasa yang lebih besar dan lebih kompleks yang menghilangkan ambiguitas (terutama ketika Anda masuk ke ranah praktis untuk benar-benar menghasilkan parser dari tata bahasa, dan menemukan bahwa tidak ambigu grammar menghasilkan parser yang tidak akan berjalan di mesin target Anda).