Apakah bahasa C biasa?

8

Apakah bahasa C atau C ++ biasa ? Jika tidak, di bawah kategori mana kita menempatkan bahasa pemrograman seperti C / C ++, perl, Python?

programming-languages c++ c perl Robert Harvey
sumber
Tidak, egrep adalah bahasa biasa; C tidak.
tchrist
Sebagian besar bahasa pemrograman adalah semacam bahasa bebas konteks. Inilah sebabnya mengapa mereka biasanya direpresentasikan sebagai pohon selama kompilasi. en.wikipedia.org/wiki/Context-free_grammar
Laurent Bourgault-Roy
1
@ LaurentBourgault-Roy Saya pikir sebagian besar bahkan tidak bebas konteks bahkan jika mereka memiliki CFG biasanya ada aturan tambahan yang diterapkan di luar CFG
jk.
Bahkan regex sudah tidak biasa lagi
CodesInChaos

Jawaban:

30

Satu-satunya definisi universal yang saya tahu untuk "bahasa biasa" adalah definisi yang dapat diurai dengan otomat terbatas deterministik, atau diekspresikan sebagai ekspresi reguler yang benar (bukan RE yang diperluas dalam banyak implementasi saat ini). Ekspresi reguler dapat ditulis dalam serangkaian karakter, dengan pengulangan yang berpotensi tak terbatas dan pilihan alternatif.

Karena C dan C ++ memungkinkan penyangga kurung kurawal, kurung, dan kurung ke kedalaman yang sewenang-wenang, mereka bukan bahasa biasa (lihat Pumping Lemma untuk detailnya).

David Thornley
sumber
2
Saya akan menambahkan bahwa tidak ada bahasa pemrograman yang dapat digunakan secara teratur karena bahkan tidak mengizinkan jenis ekspresi numerik apa pun.
Giorgio
1
@Giorgio Anda dapat mengekspresikan ekspresi numerik sebagai bahasa biasa (urutan operator dan angka bergantian dimulai dan diakhiri dengan angka) parsing (dengan prioritas) mereka membutuhkan tata bahasa sekalipun
ratchet freak
@ scratchet freak: Bagaimana Anda menangani tanda kurung, misalnya di (1 + 2) * 6?
Giorgio
@Giorgio saya seharusnya menambahkan "tanpa tanda kurung"
ratchet freak
1
@Iorgio: Sepele benar bahwa ekspresi postfix yang benar secara sintaksis tidak membentuk bahasa biasa. Tidak penting. Bahasa dapat berupa ekspresi reguler dan sewenang-wenang, termasuk ekspresi postfix, selama pemeriksaan stack ditunda sampai runtime. Keempat adalah contoh yang sangat baik, dan dc akan menjadi yang lain.
david.pfx