Mengapa tata bahasa ambigu buruk?

30

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.

HIRAK MONDAL
sumber
1
Terkait tetapi tidak identik: softwareengineering.stackexchange.com/q/343872/206652 (penafian: Saya menulis jawaban yang diterima)
marstato
1
Memang bentuk yang tidak ambigu lebih baik untuk penggunaan praktis, bentuk yang tidak ambigu menggunakan lebih sedikit aturan produksi yang membangun pohon yang lebih tinggi (karenanya penyusun yang efisien - butuh waktu lebih sedikit untuk menguraikan). Sebagian besar alat memberikan kemampuan menyelesaikan ambiguitas secara eksplisit di luar tata bahasa.
Grijesh Chauhan
3
"Semua orang ingin menyingkirkannya". Yah, itu tidak benar. Dalam bahasa yang relevan secara komersial, adalah umum untuk melihat ambiguitas ditambahkan ketika bahasa berkembang. Misalnya C ++ sengaja menambahkan ambiguitas std::vector<std::vector<int>>pada 2011, yang dulu membutuhkan ruang antara >>sebelumnya. Wawasan kunci adalah bahwa bahasa-bahasa ini memiliki lebih banyak pengguna daripada vendor, jadi memperbaiki sedikit gangguan bagi pengguna membenarkan banyak pekerjaan oleh para implementor.
MSalters

Jawaban:

52

Pertimbangkan tata bahasa berikut untuk ekspresi aritmatika:

XX+XXXXXX/Xvarconst
mempertimbangkan ekspresi berikut:
abc
Apa nilainya? Berikut adalah dua pohon parse yang mungkin:

(X - X) - X masukkan deskripsi gambar di sini

Menurut yang di sebelah kiri, kita harus menafsirkan abc sebagai (ab)c , yang merupakan interpretasi biasa. Menurut yang di sebelah kanan, kita harus menafsirkannya sebagai a(bc)=ab+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 .

Yuval Filmus
sumber
12
@HIRAKMONDAL Fakta bahwa sintaksnya ambigu bukan masalah nyata. masalahnya adalah bahwa dua pohon parse yang berbeda memiliki perilaku yang berbeda. Jika bahasa Anda memiliki tata bahasa yang ambigu tetapi semua pohon parse untuk ekspresi setara secara semantik maka itu tidak akan menjadi masalah (misalnya, ambil contoh Yuval dan pertimbangkan kasus di mana satu-satunya operator Anda +).
Bakuriu
14
@ Bakuriu Apa yang Anda katakan itu benar, tetapi "setara secara semantik" adalah hal yang sulit. Sebagai contoh, aritmatika titik apung sebenarnya tidak asosiatif (jadi dua "+" pohon tidak akan setara). Selain itu, bahkan jika jawabannya keluar dengan cara yang sama, urutan evaluasi yang tidak ditentukan sangat penting dalam bahasa di mana ekspresi dapat memiliki efek samping. Jadi apa yang Anda katakan secara teknis benar tetapi dalam praktiknya akan sangat tidak biasa bagi ambiguitas tata bahasa untuk tidak memiliki dampak terhadap penggunaan tata bahasa itu.
Richard Rast
Beberapa bahasa saat ini memeriksa integer overflow dalam penambahan, sehingga bahkan a + b + c untuk bilangan bulat tergantung pada urutan evaluasi.
gnasher729
3
Lebih buruk lagi, dalam beberapa kasus tata bahasa tidak memberikan cara apa pun untuk mencapai makna alternatif. Saya telah melihat ini dalam bahasa query, di mana pilihan tata bahasa escape (misalnya menggandakan karakter khusus untuk menghindarinya) membuat pertanyaan tertentu tidak mungkin untuk diungkapkan.
Stop Harming Monica
12

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]

ComFreek
sumber
Terima kasih banyak .. Saya memiliki keraguan yang sama dan Anda mengatasinya .. :)
HIRAK MONDAL
1
Belum lagi masalah dengan kerbau kerbau kerbau Kerbau kerbau ... untuk jumlah kerbau yang sesuai
Hagen von Eitzen
Anda menulis, "berbeda," tetapi saya menyebutnya sebagai sisi lain dari koin dari jawaban saya. Mengurai bahasa alami dengan tata bahasa ambigu mereka sangat sulit sehingga pengurai tradisional tidak dapat melakukannya!
Davislor
1
@ComFreek Saya harus lebih tepat di sini. Pandangan singkat pada GF (Terima kasih atas tautannya!) Menunjukkan bahwa ia membaca tata bahasa bebas konteks dengan tiga ekstensi (seperti memperbolehkan reduplikasi) dan mengembalikan daftar semua kemungkinan derivasi. Algoritma untuk melakukan itu sudah ada sejak tahun 50-an. Namun, mampu menangani CFG umum sepenuhnya berarti runtime kasus terburuk Anda meledak, dan dalam praktiknya, bahkan ketika menggunakan parser umum seperti GLL, insinyur perangkat lunak mencoba menggunakan subset CFG, seperti tata bahasa LL, yang dapat diurai lebih efisien.
Davislor
1
@ComFreek Jadi bukan berarti komputer tidak dapat menangani CFG (meskipun bahasa alami tidak benar-benar bebas konteks dan terjemahan mesin yang benar-benar bermanfaat menggunakan teknik yang sama sekali berbeda). Itu, jika Anda meminta parser Anda untuk menangani ambiguitas, yang mengesampingkan pintasan tertentu yang akan membuatnya lebih efisien.
Davislor
10

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).

Davislor
sumber
9

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 .

David Richerby
sumber
1
Itu adalah contoh yang baik yang menunjukkan bahwa bahkan tata bahasa non-ambigu (seperti di Jawa, C, C ++, ...) memungkinkan ambiguitas nyata (!) Dari perspektif manusia. Meskipun kami secara formal dan komputasi baik-baik saja, kami sekarang memiliki lebih dari masalah pengembangan UX / bebas bug.
ComFreek
5

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.

ratchet freak
sumber
5

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).

Jerry Coffin
sumber
***, seandainya aku punya penjelasan yang sangat bagus tentang konflik pengurangan-pengurangan 5 bulan yang lalu! ^^; +1
HotelCalifornia