Bahasa Bebas Konteks dan Automata Pushdown

Tata bahasa bebas konteks menghasilkan bahasa dengan struktur bersarang dan rekursif, dan automata pushdown mengenali bahasa-bahasa ini secara tepat dengan menambahkan kontrol terbatas dengan tumpukan tak terbatas.

Definition

Bahasa bebas konteks dihasilkan oleh tata bahasa yang aturannya menulis ulang satu simbol nonterminal secara independen dari konteks, dan dikenali oleh automata pushdown, yaitu automata terbatas yang dilengkapi dengan tumpukan yang menyediakan memori last-in, first-out dengan kedalaman tak terbatas.

Scope

Topik ini mencakup tata bahasa bebas konteks dan derivasi, pohon parse dan ambiguitas, kesetaraan tata bahasa bebas konteks dengan automata pushdown, bentuk normal seperti bentuk normal Chomsky, lemma pumping untuk bahasa bebas konteks, serta sifat penutupan dan keputusan yang membedakan kelas ini dari bahasa reguler.

Core questions

• Jenis pola bersarang atau rekursif apa yang membutuhkan tumpukan daripada memori terbatas?
• Mengapa tata bahasa bebas konteks dan automata pushdown setara dalam kekuatan?
• Kapan tata bahasa ambigu, dan mengapa ambiguitas penting untuk parsing?
• Masalah keputusan mana untuk bahasa bebas konteks yang dapat dipecahkan, dan mana yang tidak?

Key theories

Kesetaraan Tata Bahasa–Automata

Suatu bahasa adalah bebas konteks jika dan hanya jika diterima oleh automata pushdown tertentu, sehingga pandangan tata bahasa generatif dan pandangan mesin tumpukan menggambarkan kelas bahasa yang sama.

Bentuk normal Chomsky

Setiap tata bahasa bebas konteks dapat ditulis ulang sehingga setiap aturan menghasilkan dua nonterminal atau satu terminal, sebuah bentuk normal yang mendasari algoritma parsing dan bukti induktif tentang kelas tersebut.

Lemma pumping untuk bahasa bebas konteks

Setiap string yang cukup panjang dalam bahasa bebas konteks dapat dibagi sehingga dua bagiannya dipompa bersama, sebuah properti yang gagal untuk bahasa yang membutuhkan lebih dari memori tumpukan dan karenanya membuktikan bahwa bahasa tersebut bukan bebas konteks.

Clinical relevance

Tata bahasa bebas konteks menentukan sintaksis hampir setiap bahasa pemrograman dan banyak format data, dan algoritma parsing bergaya pushdown mengubah tata bahasa ini menjadi penganalisis sintaksis yang menjadi inti kompiler dan interpreter, menjadikan topik ini fondasi teoretis pemrosesan bahasa pemrograman.

History

Chomsky memperkenalkan tata bahasa bebas konteks pada akhir tahun 1950-an sebagai bagian dari hierarkinya, dan secara independen digunakan oleh Backus dan Naur untuk mendefinisikan sintaksis bahasa pemrograman ALGOL. Kesetaraan dengan automata pushdown dan teori struktural kelas ini dikembangkan sepanjang tahun 1960-an.

Key figures

• Noam Chomsky
• John Backus
• Seymour Ginsburg
• Sheila Greibach

Seminal works

• sipser2013
• hopcroft2006

Frequently asked questions

Mengapa parsing bahasa pemrograman membutuhkan tumpukan?

Program berisi konstruksi bersarang seperti tanda kurung, blok, dan panggilan fungsi yang kedalaman pencocokannya tidak terbatas. Tumpukan mencatat setiap konstruksi yang belum selesai dan mengeluarkannya saat ditutup, yang merupakan disiplin memori yang disediakan oleh automata pushdown dan tidak dimiliki oleh automata terbatas.

Apa artinya tata bahasa ambigu?

Tata bahasa ambigu ketika beberapa string memiliki lebih dari satu pohon parse, yang berarti dapat diturunkan dengan struktur yang benar-benar berbeda. Ambiguitas tidak diinginkan untuk bahasa pemrograman karena membuat makna kode tidak jelas, sehingga perancang bahasa mencari tata bahasa yang tidak ambigu atau menambahkan aturan disambiguasi.