Model komputasi mana yang dapat diekspresikan melalui tata bahasa?

Ini adalah reformulasi program tata bahasa Are? sebelumnya ditanya oleh Vag dan dengan banyak saran dari para komentator.

Dalam hal apa tata bahasa dapat dilihat sebagai spesifikasi model komputasi? Misalnya, jika kita mengambil tata bahasa bebas konteks sederhana seperti

G ::= '1' -> '0' '+' '1'
      '1' -> '1' '+' '0'
      '2' -> '2' '+' '0'
      '2' -> '1' '+' '1'
      '2' -> '0' '+' '2'
      '3' -> '3' '+' '0'
      '3' -> '2' '+' '1'
      '3' -> '1' '+' '2'
      '3' -> '1' '+' '2'

Dengan asumsi bahwa parser tidak membedakan antara terminal dan simbol nonterminal seperti yang saya tunjukkan di sini, maka dimungkinkan untuk melakukan aritmatika sederhana untuk angka hingga 3.

Misalnya, ambil senarnya

"2 + 0 + 1"

Menjalankan LR (1) parser pada string ini harus memberi kita pohon sintaksis beton berikut di mana hasil perhitungan disimpan di akar pohon:

           '3'
         /  |  \
        /   |   \
      '2'  '+'  '1'
     / | \
    /  |  \
  '2' '+' '0' 

Jadi, jika kita mengambil tata bahasa untuk menjadi sebuah program dan generator pengurai menjadi kompiler , dapatkah kita melihat bahasa spesifikasi tata bahasa sebagai bahasa pemrograman ?

Lebih lanjut, dapatkah kita membangun program lengkap Turing dengan menentukan tata bahasa yang mirip dengan bagaimana Anda dapat membangun program lengkap turing celullar automata atau kalkulus lambda ?

Dengan kata lain, diketahui bahwa dalam arti mengenali bahasa, bahasa reguler berhubungan dengan automata keadaan terbatas , bahasa bebas konteks berhubungan dengan push down automata , dan bahasa peka konteks berhubungan dengan automata terbatas linier . Namun, jika kita melihat tata bahasa sebagai perangkat komputasi (yaitu program dalam arti contoh di atas), lalu bagaimana kita mengklasifikasikan kekuatan komputasi masing-masing kelas tata bahasa dalam hierarki Chomsky?

• Tata bahasa biasa
• Tata bahasa bebas konteks
• Tata bahasa yang sensitif terhadap konteks
• Tata bahasa tidak terbatas (untuk bahasa yang berulang secara berulang )

Juga, bagaimana dengan subclass tata bahasa yang kurang dikenal seperti

• Tata bahasa bebas konteks deterministik (juga LR (k) / LL (k) / SLR / LALR dll)
• Tata bahasa kata bersarang
• Tata bahasa sebelah pohon
• Tata bahasa terindeks

EDIT: Ngomong-ngomong, ini adalah nitpick pada pertanyaan saya sendiri tetapi saya tidak menyebutkan bahwa saya tidak memberikan simbol awal untuk contoh tata bahasa dan melambaikan tangan pada kebutuhan untuk membedakan antara terminal dan nonterminals. Secara teknis atau tradisional saya pikir tata bahasanya mungkin harus ditulis dalam bentuk yang lebih rumit seperti ini (di mana S adalah simbol awal dan $ mewakili terminal end-of-stream):

G ::= S -> R0 '$'
      S -> R1 '$'
      S -> R2 '$'
      R0 -> '0'
      R0 -> R0 '+' '0'
      R1 -> '1'
      R1 -> R0 '+' '1'
      R1 -> '1' '+' R0
      R1 -> R0 '+' '1' '+' R0
      R2 -> '2'
      R2 -> R0 '+' '2'
      R2 -> '2' '+' R0
      R2 -> R0 '+' '2' '+' R0
      R2 -> R1 '+' '1'
      R2 -> R1 '+' '1' '+' R0

... bukan berarti itu benar-benar mengubah apa pun, tetapi saya pikir saya harus menyebutkannya.

EDIT: Hal lain yang terlintas dalam pikiran ketika saya membaca jawaban gasche adalah bahwa setiap cabang di pohon dalam contoh saya mewakili sub-perhitungan. Jika Anda melihat setiap aturan produksi sebagai fungsi di mana LHS mewakili hasil dan RHS mewakili argumennya, maka struktur tata bahasa menentukan bagaimana fungsi disusun.

Dengan kata lain, konteks parser bersama dengan mekanisme lookahead membantu untuk menentukan tidak hanya fungsi yang diterapkan ('agak' seperti parametrik polimorfisme) tetapi bagaimana mereka harus disusun bersama untuk membentuk fungsi baru.

Setidaknya, saya kira Anda bisa melihatnya dengan cara ini untuk CFG yang jelas, untuk tata bahasa lain senam mental agak terlalu banyak bagi saya saat ini.

Ada korespondensi satu-ke-satu antara tata bahasa Chomsky Type-0 dan mesin Turing.

Ini dieksploitasi di Internet bahasa pemrograman Thue yang memungkinkan Anda untuk menulis program lengkap Turing yang ditentukan oleh string awal dan seperangkat aturan penulisan ulang string ( tata bahasa semi-Thue , yang setara dengan tata bahasa tipe-0).

MEMPERBARUI:

Selain bahasa "Turing tar-pit" esoteris seperti Thue, berbagai bahasa tujuan umum yang memungkinkan pemrogram untuk memperluas sintaks mereka sendiri dapat digunakan untuk melakukan perhitungan Turing-complete selama tahap parsing-kompilasi.

Bahasa dalam keluarga Lisp , khususnya Common Lisp , mungkin adalah contoh yang paling jelas, tetapi juga, secara umum, bahasa dengan pemeriksaan tipe statis yang tidak selalu perlu dihentikan, seperti C ++ dengan templat , Scala dan Qi .

Jawaban saya tidak dimaksudkan untuk menjadi formal, tepat dan benar-benar sesuai topik. Saya pikir jawaban Marc Hamman solid, tetapi pertanyaan Anda membuat saya memikirkan topik terkait.

Tata bahasa dapat dianggap sebagai kasus khusus dari sistem deduktif: input adalah penilaian, dan pohon parse adalah turunan dari penilaian, atau bukti bahwa penilaian tersebut valid sesuai dengan aturan (tata bahasa).

Dalam hal itu, pertanyaan Anda dapat dikaitkan dengan pendekatan beberapa bagian dari pemrograman logika / komunitas pencarian bukti (saya berpikir tentang Dale Miller misalnya), yaitu bahwa pencarian bukti memiliki konten komputasi, sebagai lawan dari yang lebih klasik Jenis / teori bukti sudut pandang di mana komputasi adalah normalisasi bukti .

Catatan: membaca ulang jawaban saya, saya pikir gagasan bahwa "konstruksi parse tree adalah pencarian bukti" agak sedikit dibuat-buat di sini. Pencarian bukti agak mengalir ke arah lain: seseorang mulai dari penilaian yang diberikan, agak rumit dan, dengan penggunaan berulang dari aturan inferensi yang bekerja pada struktur bukti, seseorang diharapkan mencapai aksioma sederhana yang tidak perlu dibuktikan lebih lanjut. Jadi akan lebih alami untuk melihat, dalam hal tata bahasa, penilaian kompleks sebagai non-terminal, atom sebagai terminal, dan pencarian bukti sebagai masalah pembuatan kata, atau uji ketidak-kekosongan.

Selanjutnya, dapatkah kita membangun program lengkap Turing dengan menetapkan tata bahasa ...?

Saya tidak yakin apakah saya memahami pertanyaan Anda dengan benar, tetapi jika Anda mencari bahasa pemrograman berdasarkan semacam sistem penulisan ulang string, Anda mungkin akan tertarik pada Refal , yang didasarkan pada formalisme algoritma Markov (sebuah Turing- formalisme lengkap yang juga merupakan sistem penulisan ulang string yang mirip tata bahasa).

(Hanya beberapa pertimbangan sepele. Bisa jadi komentar, tapi terlalu lama.)

Bahkan, apa yang Anda gambarkan terlihat berlaku sebagai pandangan yang sangat alami tentang apa bahasa itu (dalam pemahaman manusia tentang "bahasa", tujuannya) dan bagaimana tata bahasa mendefinisikan suatu bahasa.

Bahasa terdiri dari (sangat banyak) bentuk sintaksis yang benar yang ditafsirkan untuk memberikan nilai semantik .

Jika interpretasi dapat dihitung, maka bentuk sintaksis suatu bahasa dapat dilihat sebagai program yang menghitung nilai semantik.

Jika kita menganggap bahwa suatu bahasa diimplementasikan sebagai perangkat yang terbatas, kita dapat menyebut representasi terbatas dari bahasa ini sebagai "tata bahasa". Menurut pemahaman ini, tata bahasa peduli tentang sintaks, tetapi juga tentang semantik, yaitu, bagaimana menghitung nilai semantik dari seluruh ekspresi dari nilai bagian-bagiannya (bagian atom dan nilainya disimpan dalam "leksikon") .

Beberapa teori bahasa alami memiliki bentuk seperti itu (bentuk yang konsisten dengan pertimbangan di atas; sudah disebutkan dalam jawaban @ gasche di sini): sistem deduktif yang mencari derivasi input (ditambah dengan perhitungan semantik nilai, atau pembangunan istilah bukti; lih. Korespondensi Curry-Horward). Jadi, jika kita melihat sistem seperti itu dan menganggapnya tata bahasa, maka pertanyaan Anda sepele : sistem ini dirancang untuk melakukan perhitungan dengan cara yang Anda gambarkan.

$f$$G$$I$ $f(I)=S$$I$$S$$G$

(Faktanya, kompiler nyata untuk bahasa pemrograman lebih mirip sistem dengan sintaks dan semantik: mereka mengubah bentuk sintaksis suatu program menjadi executable, yang merupakan makna semantik dari program, dan lebih dari sekadar simbol awal. tata bahasa.)

Tambahkan saja:

Program logika murni memiliki bacaan deklaratif dan bacaan prosedural. Laporan ini membahas gagasan bahwa ini dapat dilengkapi dengan pembacaan tata bahasa, di mana klausul dianggap sebagai aturan penulisan ulang tata bahasa. Tujuannya adalah untuk menunjukkan bahwa sudut pandang ini memfasilitasi transfer keahlian dari pemrograman logika ke penelitian lain tentang bahasa pemrograman dan sebaliknya. Beberapa contoh transfer semacam itu dibahas. Di sisi lain pandangan tata bahasa yang disajikan membenarkan beberapa ekstensi ad hoc untuk pemrograman logika murni dan memfasilitasi pengembangan fondasi teoritis untuk ekstensi tersebut.

Pandangan Tata Bahasa Pemrograman Logika oleh Pierre Deransart dan Jan Maluszynski.

Bagaimana dengan sesuatu seperti angka Peano:

S    -> int
int  -> zero
int  -> succ
zero -> "0"
succ -> "#" int

itu akan mengenali string (nomor) dari formulir ini:

0   // zero
#0  // one
##0 // two

dan itu harus mengembalikan struktur bersarang, dengan kedalaman adalah jumlahnya.

Tapi itu mulai menjadi rumit ketika seseorang ingin mengimplementasikan katakan saja penambahan:

S    -> int
int  -> sum
int  -> zero
int  -> succ
zero -> "0"
succ -> "#" int
sum  -> int "+" int

Masuk akal jika hanya mengenali int yang terbentuk dengan baik seperti ini:

#####0 + ####0

Tetapi tata bahasa ini memperkenalkan perpecahan dalam pohon parse setiap kali ada jumlah, jadi alih-alih memiliki pohon bercabang satu yang bagus, yang langsung memetakan ke angka, kita memiliki struktur ekspresi, masih beberapa perhitungan jauh dari efektif nilai. Jadi tidak ada perhitungan yang dilakukan, hanya pengakuan. Masalahnya mungkin bukan tata bahasa tetapi pengurai. Seseorang malah dapat menggunakan sesuatu yang lain, idk ... Poin lain yang muncul dalam pikiran adalah kecukupan formalisme tata bahasa untuk mengekspresikan perhitungan. Ketika Anda melihat aksioma Peano (dalam notasi mirip Haskell):

1) Nat = Zero
2) Nat = Succ Nat
3) Sum ( Succ X ) ( Y ) = Succ ( X + Y )
4) Sum Zero X = X

Aturan ketiga secara eksplisit menyatakan transformasi. Adakah yang bisa membayangkan membawa makna yang sama dalam aturan tata bahasa bebas konteks. Dan jika demikian, bagaimana!?