Apa arti "bebas konteks" dalam istilah "tata bahasa bebas konteks"?

Mengingat jumlah materi yang mencoba menjelaskan apa itu tata bahasa bebas konteks (CFG), saya menemukan sangat mengejutkan bahwa sangat sedikit (dalam sampel saya, kurang dari 1 dalam 20) memberikan penjelasan tentang mengapa tata bahasa seperti itu disebut "konteks- Gratis". Dan, menurut saya, tidak ada yang berhasil melakukannya.

Pertanyaan saya adalah, mengapa tata bahasa bebas konteks disebut bebas konteks? Apa itu "konteksnya"? Saya memiliki intuisi bahwa konteksnya bisa berupa konstruksi bahasa lain di sekitar konstruk yang saat ini dianalisis, tetapi sepertinya tidak demikian. Adakah yang bisa memberikan penjelasan yang tepat?

Ini berarti semua aturan produksinya memiliki satu non-terminal di sisi kiri mereka.

Misalnya, tata bahasa ini yang mengenali string tanda kurung yang cocok ("()", "() ()", "(()) ()", ...) bebas konteks:

S → SS
S → (S)
S → ()

Sisi kiri setiap aturan terdiri dari satu non-terminal tunggal (dalam hal ini selalu S, tetapi mungkin ada lebih banyak.)

Sekarang pertimbangkan tata bahasa lain yang mengenali string dari bentuk {a ^ nb ^ nc ^ n: n> = 1} (mis. "Abc", "aabbcc", "aaabbbccc"):

S  → abc
S  → aSBc
cB → WB
WB → WX
WX → BX
BX → Bc
bB → bb

Jika non-terminal Bdidahului oleh karakter terminal / literal c, Anda menulis ulang istilah itu menjadi WBtetapi jika itu didahului oleh b, Anda memperluas ke bbsebaliknya. Ini mungkin disinggung oleh apa yang dimaksud dengan sensitivitas konteks dari tata bahasa konteks-sensitif.

Bahasa bebas konteks dapat dikenali sebagai otomat push-down . Sedangkan mesin keadaan terbatas tidak menggunakan penyimpanan tambahan, yaitu keputusannya hanya didasarkan pada kondisi dan input saat ini, otomat push-down juga memiliki tumpukan yang siap digunakan dan dapat mengintip bagian atas tumpukan untuk mengambil keputusan.

Untuk melihat itu dalam tindakan, Anda dapat menguraikan tanda kurung bersarang dengan bergerak dari kiri ke kanan dan mendorong tanda kurung kiri ke tumpukan setiap kali Anda menemukan satu, dan muncul setiap kali Anda menemukan tanda kurung yang tepat. Jika Anda tidak pernah mencoba pop dari tumpukan kosong, dan tumpukan kosong di akhir string, string tersebut valid.

Untuk bahasa yang peka konteks, PDA tidak cukup. Anda akan memerlukan otomat terikat-linier yang seperti Mesin Turing yang rekamannya tidak terbatas (meskipun jumlah pita yang tersedia sebanding dengan input). Perhatikan bahwa itu menggambarkan komputer dengan cukup baik - kami suka menganggapnya sebagai Mesin Turing tetapi di dunia nyata Anda tidak dapat mengambil lebih banyak RAM secara sembarangan di tengah program. Jika tidak jelas bagi Anda bagaimana LBA lebih kuat daripada PDA, LBA dapat meniru PDA dengan menggunakan bagian dari selotipnya sebagai tumpukan, tetapi ia juga dapat memilih untuk menggunakan selotipnya dengan cara lain.

(Jika Anda bertanya-tanya apa yang bisa dikenali oleh Mesin Hingga, jawabannya adalah ekspresi reguler. Tetapi bukan regex pada steroid dengan kelompok penangkap dan lihat-belakang / lihat-depan yang Anda lihat dalam bahasa program; Maksud saya yang dapat Anda bangun dengan operator seperti [abc], |, *, +, dan ?. Anda dapat melihat bahwa abbbzpertandingan regex ab*zhanya dengan menjaga posisi Anda saat ini dalam string dan regex, ada tumpukan diperlukan.)

Jawaban lainnya cukup panjang, meskipun akurat dan benar. Ini versi singkatnya.

Jika Anda memiliki string karakter (terminal dan nonterminals) dan Anda ingin mengganti nonterminal dalam string, tata bahasa bebas konteks memungkinkan Anda untuk melakukan itu terlepas dari karakter di sekitar nonterminal.

Pertimbangkan aturan berikut (huruf kecil adalah terminal, huruf besar adalah nonterminals):

A -> a
AB -> a

Dalam aturan pertama, Anda dapat mengganti A terlepas dari apa yang muncul di sekitarnya (konteks). Dalam aturan kedua, Anda tidak bisa mengganti Akecuali diikuti oleh B. Sementara kedua nonterminals akan diganti dalam kasus itu, poin penting adalah bahwa nonterminals mengelilingi Amasalah tersebut. Seseorang tidak dapat menggantikan BAdengan a, atau Bdengan a: hanya Adiikuti oleh Bkarena urutan, konteks nonterminals penting. Ini berarti konteks dari hal-hal nonterminal dalam aturan kedua, menjadikannya peka konteks, sedangkan aturan pertama bebas konteks.

Untuk memahami perbedaan dan terminologi yang lebih baik, itu ide yang baik untuk kontras bahasa bebas konteks seperti ⁿ b ⁿ dengan satu konteks-sensitif seperti ⁿ b ⁿ c ⁿ . (Notasi: a, b, dan c adalah literal di sini dan eksponen n berarti mengulangi literal n kali, n > 0, katakan.) Misalnya, aabbcatau aabbbcctidak dalam bahasa yang terakhir, sedangkan aabbcc.

Akseptor untuk bahasa bebas konteks a ⁿ b ⁿ dapat kontrak sepasang adan bterlepas apa yang di sekitar itu (yaitu terlepas dari konteks di mana ab muncul) dan itu akan berfungsi dengan benar, hanya menerima string dalam bahasa dan menolak apa pun, yaitu tata bahasanya S -> aSb | ab. Perhatikan bahwa tidak ada terminal di sisi kiri produksi . (Ada dua aturan produksi, tetapi kami hanya menuliskannya dengan kompak.) Akseptor pada dasarnya dapat membuat keputusan lokal, bebas konteks.

Sebaliknya, Anda tidak dapat melakukan sesuatu seperti itu untuk bahasa yang peka konteks a ⁿ b ⁿ c ⁿ , karena untuk yang terakhir Anda harus mengingat entah bagaimana konteks Anda, yaitu berapa banyak kontraksi yang Anda lakukan untuk mencocokkannya dengan kontraksi dari bc. Tata bahasa untuk bahasa yang terakhir adalah

S -> abc | aBSc
Ba -> aB
Bb -> bb

Perhatikan bahwa Anda memiliki terminal dan non-terminal di sebelah kiri dalam dua aturan terakhir. Terminal di sebelah kiri adalah konteks di mana non-terminal dapat diperluas.

Bootnote tentang "kontrak" vs. "Perluas" terminologi dll: walaupun tata bahasa formal [secara formal, hah] generatif, cara mereka sebenarnya diterapkan dalam parser sebenarnya reduksionis, yaitu Anda menghubungi semuanya ke non-terminal, pada dasarnya menerapkan aturan "terbalik", itulah sebabnya bahkan tata bahasa pertama yang diberikan di atas tidak praktis dalam suatu program (itu akan memberi Anda konflik shift-pengurangan yang terkenal karena Anda tidak dapat memutuskan aturan mana yang akan diterapkan), tetapi dua di atas tata bahasa cukup untuk menggambarkan perbedaan antara bebas konteks dan peka konteks. Masalah ambiguitas dalam tata bahasa bebas konteks agak rumit, dan sebenarnya bukan topik pertanyaan ini, jadi saya tidak akan mengatakan lebih banyak di sini, terutama karena ternyata Wikipedia memiliki artikel yang layak tentang itu.. Sebaliknya artikel-artikelnya tentang bebas konteks dan terutama pada bahasa yang peka konteks adalah! @ # $ @! # $ Terutama jika Anda baru mengenal topik ... Saya rasa itu lebih banyak dalam daftar TODO saya.

Jawaban di atas memberikan definisi yang cukup bagus tentang apa itu. Mari kita lihat apakah saya dapat menuliskannya dengan kata-kata saya sendiri, sehingga Anda akan memiliki 23 penjelasan, bukan 20. Seluruh tujuan tata bahasa, tata bahasa apa pun, adalah untuk mencari tahu apakah kalimat tertentu adalah kalimat dalam bahasa yang diberikan. Namun, apa yang sebenarnya kita gunakan untuk tata bahasa dan penguraian adalah untuk mencari tahu apa arti kalimat itu. Ini seperti diagram lama dari kalimat yang mungkin Anda lakukan atau tidak pernah lakukan di kelas bahasa Inggris di sekolah. Sebuah kalimat dibuat dari bagian subjek dan bagian predikat, bagian subjek memiliki kata benda dan mungkin beberapa kata sifat, bagian predikat memiliki kata kerja dan mungkin objek kata benda, dengan beberapa kata sifat lagi, dll.

Jika ada tata bahasa untuk bahasa Inggris (dan saya pikir tidak ada, tidak dalam pengertian ilmu komputer) maka itu akan memiliki aturan bentuk berikut, yang disebut produksi.

Sentence -> SubjectPart PredicatePart
SubjectPart -> Adjective Noun

dll ...

Anda kemudian dapat menulis sebuah program dan memberikannya kalimat apa pun, dan program tersebut dapat menggunakan tata bahasa untuk mencari tahu bagian mana dari kalimat setiap kata, dan hubungan apa yang mereka miliki satu sama lain.

Jika dalam setiap produksi, hanya ada satu hal di sisi kiri, maka itu berarti bahwa setiap kali Anda melihat sisi kanan dalam kalimat, Anda diperbolehkan untuk mengganti di sisi kiri. Misalnya setiap kali Anda melihat kata sifat kata benda, Anda bisa mengatakan "Itu Subjek Bagian" tanpa memperhatikan apa pun di luar frasa itu.

Namun, bahasa Inggris (bahkan deskripsi bahasa Inggris yang saya berikan di atas) adalah peka konteks. "Kata benda kata sifat" tidak selalu menjadi SubjectPart, itu bisa menjadi NounPhrase di PredicatePart. Itu tergantung pada konteksnya. Mari kita sedikit mengembangkan tata bahasa pseudo-Inggris kami:

Sentence -> SubjectPart PredicatePart
SubjectPart -> Adjective Noun
PredicatePart -> VerbPhrase ObjectNounPhrase
VerbPhrase ObjectNounPhrase -> VerbPhrase Adjective Noun

Anda hanya dapat membuat "kata sifat kata sifat" menjadi ObjectNounPhrase jika itu datang tepat setelah VerbPhrase.

Pada dasarnya, jika Anda memiliki produksi dan Anda dapat menerapkannya kapan saja Anda inginkan, apa pun yang mengelilinginya, itu bebas konteks.

Anda selalu dapat mengetahui apakah tata bahasa bebas konteks dengan mudah. Cukup periksa apakah ada lebih dari satu simbol di sisi kiri panah.

Bahasa apa pun dapat dijelaskan oleh lebih dari satu tata bahasa. Jika beberapa tata bahasa untuk bebas konteks, bahasa bebas konteks. Dapat dibuktikan untuk beberapa bahasa bahwa tidak ada tata bahasa bebas konteks yang memungkinkan. Saya kira mungkin ada tata bahasa bebas konteks untuk subset pseudo-Inggris yang disederhanakan yang saya jelaskan di atas.

Adapun mengapa itu penting, itu memerlukan jenis program yang lebih sederhana untuk mengurai tata bahasa bebas konteks. Seperti dicatat dalam jawaban lain, itu tidak memerlukan kekuatan penuh dari mesin Turing untuk mengurai tata bahasa bebas konteks. Pengukur LR (1) lookahead (yang merupakan semacam mesin pushdown) untuk tata bahasa bebas konteks tertentu dapat menguraikan kalimat apa pun dalam tata bahasa itu dalam waktu dan ruang yang linear terhadap panjang kalimat. Jika kalimat dalam bahasa, parser akan menghasilkan struktur pohon yang mengidentifikasi apa arti setiap simbol dalam kalimat (atau setidaknya bagian apa yang dimainkannya dalam struktur). Jika kalimat tidak ada dalam tata bahasa, parser akan memperhatikan dan berhenti pada simbol pertama yang tidak mungkin untuk didamaikan dengan tata bahasa dan simbol sebelumnya (pada "kesalahan" pertama).

Apa yang lebih baik adalah bahwa ada program yang dapat Anda berikan deskripsi tata bahasa, dan daftar instruksi tentang apa yang harus dilakukan dengan setiap bagian (dalam arti melampirkan "makna" untuk setiap produksi) dan program akan menulis parser untukmu. Program akan mem-parsing kalimat, menemukan struktur, dan menjalankan instruksi Anda pada setiap bagian struktur. Program semacam ini disebut parser-generator atau compiler-compiler.

Analisis bahasa semacam ini diciptakan untuk analisis otomatis bahasa alami (seperti bahasa Inggris) tetapi ternyata ini yang paling berguna untuk menganalisis bahasa komputer. Seorang perancang bahasa dapat menulis tata bahasa yang menangkap bahasa barunya, kemudian menjalankannya melalui parser-generator untuk mendapatkan program yang mem-parsing bahasanya, dan menerjemahkan, mengartikan, mengkompilasi, mengeksekusi, dll jika ia mau.

Bahkan, dalam banyak kasus Anda tidak dapat benar-benar melakukan ini. Misalnya, tanda kurung yang seimbang adalah bahasa bebas konteks, tetapi bahasa yang mengharuskannya mendeklarasikan semua variabel sebelum Anda menggunakannya adalah peka konteks. Parser adalah bagian dari kompiler, tetapi logika tambahan diperlukan untuk menegakkan persyaratan lain ini. Yang kemudian harus Anda lakukan adalah menulis tata bahasa yang menangkap sebanyak mungkin bahasa Anda, menjalankannya melalui parser-generator, kemudian menulis kode yang memberlakukan sisa persyaratan (simbol table handler, dll).

Kami umumnya tidak menggunakan tata bahasa konteks-sensitif karena mereka jauh lebih buruk didukung. Saya tidak tahu apakah ada yang setara dengan LR (k) parser-generator untuk bahasa konteks-sensitif. Ya, mesin Turing (atau mesin terikat linier) dapat menguraikannya, tapi saya tidak tahu apakah ada algoritma umum untuk mengubah tata bahasa yang sensitif terhadap konteks menjadi program untuk mesin Turing, dalam arti bahwa LR (1 ) generator membuat tabel parse untuk mesin pushdown. Dugaan saya adalah bahwa tabel yang mendasari parser akan secara eksponensial lebih besar. Dalam kasus apa pun, siswa CS (seperti saya, pada zaman dahulu) biasanya diajarkan tata bahasa bebas konteks dan generator pengurai LR (1) seperti YACC.

Tata bahasa bebas konteks tidak mempertimbangkan konteks aturan produksi. Konteks adalah terminal atau non-terminal.

Jadi: Tata bahasa bebas konteks hanya memiliki satu non-terminal di sisi kiri aturan produksi.