Apa yang akan Anda dapatkan jika Anda menambahkan parameter ke tata bahasa bebas konteks?

13

Saya sedang memikirkan tata bahasa untuk bahasa indendasi-sensitif dan sepertinya tata bahasa CF akan melakukan trik jika dikombinasikan dengan parameter. Sebagai contoh, pertimbangkan fragmen ini untuk tata bahasa Python yang disederhanakan dalam format seperti ANTLR:

// on top-level the statements have empty indent
program  
    : statement('')+
    ;

// let's consider only one compound statement and one simple statement for now
statement(indent) 
    : ifStatement(indent)
    | passStatement(indent)
    ;

passStatement(indent)
    : indent 'pass' NEWLINE
    ;

// statements under if must have current indent plus 4 spaces
ifStatement(indent)
    : indent 'if' expression ':' NEWLINE (statement(indent '    ')+)
    ;

Pertanyaan saya: Apakah tata bahasa semacam ini (CFG dengan parameter) memiliki nama?

Tampaknya tidak akan sulit untuk menulis parser keturunan rekursif untuk tata bahasa ini (parameter pada dasarnya harus parser). Apa yang bisa menjadi kesulitan dengan pendekatan ini?

Apakah penambahan parameter meningkatkan kelas bahasa yang didukung di atas bebas konteks?

Aivar
sumber
1
Jika himpunan nilai yang dapat diambil oleh parameter adalah terbatas, maka itu masih bersifat konteks sepele (Anda dapat mengulangi semua nilai dan menulis semuanya).
ratchet freak
1
Patut dicatat bahwa proposal Anda adalah bahasa sensitif lekukan dengan lekukan tetap. Python (dan bahasa lain semacam itu) tidak dibatasi dengan cara ini; mereka menerima lekukan apa pun yang diinginkan pengguna. Itu tidak memengaruhi parseabilitas (kecuali untuk menangani karakter tab) tetapi akan sulit untuk diungkapkan dengan proposal Anda, setidaknya seperti yang saya mengerti.
rici
tata bahasa atribut
Hendrik Jan
@HendrikJan, atribut grammar adalah cara menjelaskan tata bahasa dengan aksi semantik, mereka tidak mengontrol parsing.
Pemrogram
1
Jika tujuannya adalah untuk menangani lekukan, itu lebih cocok untuk tokenizer daripada parser. Minta tokenizer memancarkan token INDENT dan UNINDENT virtual saat tingkat indentasi berubah. Maka tidak perlu menambah tata bahasa dengan informasi tentang indentasi.
John Kugelman

Jawaban:

14

Tata bahasa Affix ( tata bahasa bebas parameterisasi konteks) dipelajari secara luas oleh ilmuwan komputer Belanda terkemuka Cornelis HA Koster , dimulai dengan makalahnya tahun 1962 "Basic English, tata bahasa generatif untuk bagian dari bahasa Inggris", yang ditulis bersama dengan LGLT Meertens. Pada tahun 1970, ia menghasilkan formalisme konsep; ikhtisar yang berguna tersedia dalam makalahnya pada tahun 1971 "Affix Grammars for Programming Languages", sebuah versi yang saya temukan di Citeseer .

Dalam makalah itu, Koster membandingkan formalismenya (dan yang serupa lainnya) dengan Van Wijngaarden tata bahasa dua tingkat , dan menemukan mereka sangat mirip.

Bibliografi beranotasi Dick Grune yang tak ternilai tentang teknik penguraian meliputi sejumlah besar referensi bermanfaat lainnya untuk tata bahasa tambahan dan formalisme non-Chomsky lainnya. (Lihat bagian 18.2.6 dari daftar pustaka, meskipun ada makalah yang berguna di bagian lain.) Grune mencakup tata bahasa imbuhan singkat di §15.3.2 edisi kedua Teknik Parsing: Panduan Praktis (dan bahkan lebih singkat lagi di edisi pertama , tersedia online) menyebutkan fakta bahwa mudah untuk mengadaptasi teknik parsing top-down (dan lainnya).

Sebuahnbncn dapat ditemukan dalam referensi Teknik Parsing Dick Grune di atas.)

Koster, yang juga seorang editor laporan Algol 68, adalah pengembang asli dari Compiler Description Language (CDL) , berdasarkan ide-idenya tentang tata bahasa tambahan. Toolkit ini dan turunannya kemudian digunakan dalam produksi selama bertahun-tahun. Halaman ini , yang saya temukan dengan pencarian Google dan keabadiannya saya tidak bisa jamin, memiliki tautan ke manual dan situs pengunduhan untuk CDL3.

rici
sumber
Saya merasa bahasa CDL lebih seperti tata bahasa atribut : nilai-nilai atribut dapat dihitung dengan fungsi yang didefinisikan secara eksternal. Saya akan menggunakan nama tata bahasa imbuhan untuk kasus-kasus di mana hubungan antara nilai-nilai afiks (atribut) didefinisikan dalam formalisme, seperti dalam Tata Bahasa Affix Diperpanjang .
reinierpost
@reinierpost: Anda tentu saja berhak atas terminologi Anda sendiri; hak istimewa tidak terbatas pada telur antropomorfik. Namun, manual CDL sendiri mengklaim bahwa "CDL3 adalah bahasa implementasi yang didasarkan pada tata bahasa tambahan," yang menurut saya harus diperhitungkan. (Manual tersedia di ftp.cs.kun.nl/pub/cdl3/cdl3-manual-1.2.7.pdf ). Itulah yang saya klaimkan dalam jawaban saya: bahwa CDL didasarkan pada karya Koster tentang tata bahasa tambahan. Seperti yang ditunjukkan Grune, perbedaan antara tata bahasa imbuhan dan atribut adalah sedikit; Perbedaannya adalah apakah afiks digunakan untuk memutuskan validitas sintaksis.
rici
(Kutipan dari halaman pertama manual.)
rici
Saya tahu ... dan Anda benar. Komentar saya tidak dimaksudkan untuk menentang Anda.
reinierpost
6

Ambil lemma pemompaan untuk CFG :

Ambil tata bahasanya

S -> A("")
A(p) -> p 
      | p '\n' A(p"*") '\n' p 

Ini menggambarkan segitiga bintang:

*
**
***
**
*

kamuvwxy{kamuvnwxny|n>0}vx

Ini berarti bahwa segitiga bintang bukan bahasa bebas konteks.

Atau contoh yang lebih sederhana:

S-> B("")
B(p)-> p 'a' p 'a' p
     | B(p 'b')

{bnSebuahbnSebuahbn|n0}

orang aneh
sumber
3

Saya belum pernah melihat formalisme ini disajikan (bahkan dalam sesuatu seperti Teknik Parsing Grune ), tergantung pada rincian tentang bagaimana Anda mendefinisikan dengan tepat "parameter harus pada dasarnya parser", itu tampak dapat dipetakan untuk van Wijngaarden dua tata bahasa level, yang memiliki kekuatan yang sama seperti tata bahasa struktur fase tidak terbatas (yaitu lebih kuat daripada konteks sensitif, Anda bisa menulis tata bahasa VW yang memberikan semua program penghentian).

Pemrogram
sumber
Koster dan kelompoknya mempelajari dua jenis tata bahasa tambahan, sejauh yang saya ketahui: 1) bentuk terbatas dari tata bahasa Van Wijngaarden, dimaksudkan untuk memungkinkan pengakuan yang lebih mudah; 2) bahasa CDL, bahasa deskripsi kompilator praktis tanpa manipulasi nilai imbuhan eksplisit tetapi dengan opsi untuk mendefinisikan aturan dalam bahasa target (mis. Assembler), menjadikannya Turing lengkap.
reinierpost