Agar suatu bahasa dapat diprogram, apakah wajib didasarkan pada tata bahasa bebas konteks

Secara praktis, untuk bahasa yang pada akhirnya dapat dikompilasi / diubah menjadi instruksi tingkat sistem, apakah perlu bahwa itu adalah tata bahasa bebas konteks?

mis: Apakah semua bahasa pemrograman / scripting konteks tata bahasa gratis? Java didasarkan pada CFG, tetapi apakah sebenarnya semua bahasa pemrograman didasarkan pada CFG?

Tampaknya tidak wajib, tetapi ada kesenjangan dalam pemahaman saya.

Beberapa konteks untuk pertanyaan: Saya melihat spesifikasi bahasa Jawa, yang juga menyediakan aturan tata bahasa . Ini membuat saya berpikir tentang pertanyaan ini.

Dua kali tidak.

Pertama, sebagian besar HPL tidak bebas konteks. Walaupun mereka biasanya memiliki sintaksis berdasarkan CFG, mereka juga memiliki apa yang disebut orang dengan semantik statis (yang juga sering dimasukkan dalam sintaksis istilah). Ini dapat mencakup nama dan tipe yang harus memeriksa program yang benar. Contohnya,

class A {
  String a = "a";
  int b = a + d;
}

adalah program Java yang secara sintaksis benar tetapi tidak akan dikompilasi karena dtidak didefinisikan dan atidak memiliki tipe pemasangan.

Kedua, Anda dapat mem - parsing bahasa yang tidak bebas konteks (seperti yang jelas dibuktikan dengan keberadaan kompiler). Hanya CFG yang dapat diurai secara efisien, sedangkan CSG tidak bisa, secara umum. Namun, Anda dapat menambahkan fitur-fitur non-konteks-bebas tertentu sambil tetap efisien.

Compiler sering dijalankan dalam fase: tokenization pertama (reguler), kemudian parsing bebas konteks, kemudian analisis nama dan tipe (peka konteks, kadang-kadang bahkan lebih sulit). Anda dapat mengamati perilaku itu dengan jenis pesan kesalahan yang Anda dapatkan.

Parsing perl tidak dapat ditentukan.

http://www.jeffreykegler.com/Home/perl-and-undecidability/perl-and-undecidability-files/TPR3.pdf?attredirects=0

http://www.perlmonks.org/?node_id=663393

Saya tidak percaya bahwa tata bahasa Python bebas konteks. Persyaratan bahwa baris dalam blok kode yang sama memiliki jumlah indentasi yang sama bukanlah hal yang dapat ditangani dengan baik oleh tata bahasa bebas konteks.

Lebih tepatnya, tampaknya ada homomorfisme dari bahasa Python blok formulir

jika kondisi:
     line1
     line2
     line3
lain:
     line4

ke bahasa bebas-konteks mana blok nol pertama berasal dari set spasi di awal line1, blok kedua datang set spasi di awal line2, blok ketiga berasal dari himpunan ruang pada awal line3, dan baris yang tersisa dengan yang lain dll ada untuk memaksa line1, line2, dan line3 menjadi milik blok yang sama.$0^n10^n10^n$

Bodo Manthey dan Martin Böhme menunjukkan bahwa setiap C ++ Compiler adalah Turing yang lengkap, yaitu, ia dapat menghitung fungsi rekursif parsial pada waktu kompilasi . Jadi itu jauh lebih buruk daripada hanya peka konteks.

http://wwwhome.math.utwente.nl/~mantheyb/journals/BotEATCS_BoehmeManthey_CompilingCPP.pdf

Saya pikir deklarasi sebelum penggunaan variabel dan polimorfisme fungsi dari bahasa OOP adalah contoh lain dari spesifikasi bahasa pemrograman yang tidak dapat ditangani oleh tata bahasa bebas konteks:

int myfun(int a) { ... }
int myfun(int a, int b) { ... }
int myfun(int a, int b, int c, ...) { ... }
...
int I_m_I_cfg = myfun(1,2);
...

Saya membuat sedikit pencarian Google dan saya menemukan artikel ini: " Tata Bahasa Boolean untuk Bahasa Boolean Sederhana " oleh A.Okhotin (2004); menurutnya, masalah sebenarnya adalah menemukan bahasa pemrograman yang sepenuhnya dijelaskan oleh tata bahasa formal:

Bahasa pemrograman prosedural mainan didefinisikan, dan tata bahasa Boolean untuk sekumpulan program yang terbentuk dengan baik dalam bahasa ini dibangun. Ini rupanya spesifikasi pertama dari bahasa pemrograman sepenuhnya oleh tata bahasa formal.

Bagian Pendahuluan dari artikel ini singkat tetapi sangat menjelaskan.

Saya percaya bahwa tata bahasa C hanya bebas konteks teknis karena parser selalu menggunakan teknik bebas konteks untuk mendukung perangkat Duff .

Bahasa berbasis indentasi juga tidak bebas konteks seperti yang dikatakan David, tetapi mereka menjadi bebas konteks dibandingkan dengan token indentasi parameter.

Haskell memungkinkan Anda mengubah prioritas operator dengan infix dan infixl. Modul pragma ketat Perl diimplementasikan menggunakan pengaturan leksikal $ ^ H dan% ^ H, yang membuatnya tidak bebas konteks, mungkin juga pengaturan lain.

Ada bahasa expander makro seperti TeX di mana afaik parsing tidak masuk akal tanpa mengeksekusi.

Bahkan mungkin ada dua tata bahasa bebas konteks yang persimpangannya tidak bebas konteks tetapi masih menggambarkan mesin Turing.

Java dan assembler mungkin secara alami bebas konteks.

Tidak, dan banyak bahasa praktis tidak bebas konteks. Misalnya tata bahasa C ++ tidak, karena dalam beberapa konteks resolusi tata bahasa tergantung pada pengetikan informasi yang tidak bebas konteks.

Pertama-tama izinkan saya membuat perbedaan antara sintaksis bahasa pemrograman dan bahasa itu sendiri.

Sintaks banyak bahasa (setidaknya didasarkan pada) Tata Bahasa Konteks Gratis (CFG) karena ini dipelajari dengan baik dan ada algoritma yang dapat secara efisien mengurai CFG dan kasus tepi yang tidak dapat diselesaikan oleh CFG dapat ditangani secara khusus

Namun banyak bahasa sebenarnya bukan Bebas-Konteks (ketika simbol menyatakan sebelum digunakan digunakan, misalnya dalam java, C (++), D).

Fakta asyik: D memiliki evaluasi fungsi kompilasi-waktu-kompilasi Turing-lengkap dan perluasan membuat bahasa itu sendiri tidak bisa-Turing-bisa dipilih Namun pencipta bahasa berusaha keras untuk membuat sintaksis menjadi CFG.

Sejauh "Apakah semua bahasa pemrograman / scripting konteks tata bahasa gratis?" bagian yang bersangkutan, jawabannya adalah TIDAK.

Re: pertanyaan utama "untuk bahasa yang pada akhirnya dapat dikompilasi / diubah menjadi instruksi tingkat sistem," Saya tidak tahu mengapa perlu menjadi CFG. Namun, mungkin ada penjelasan yang lebih baik.

Bahasa pemrograman perlu didasarkan pada semacam formalisme tata bahasa, yang contohnya adalah CFG. Meskipun CFG adalah yang paling umum (dan merupakan hal yang biasa diajarkan dalam kursus penyusun di universitas), ada formalisme lain seperti Parsing Expression Grammars, yang dapat Anda baca lebih lanjut di sini (pdf) atau di Wikipedia untuk bacaan berukuran lebih besar.