Bagaimana saya harus menentukan tata bahasa untuk parser?

Saya telah memprogram selama bertahun-tahun, tetapi satu tugas yang masih memakan waktu sangat lama adalah menentukan tata bahasa untuk parser, dan bahkan setelah upaya yang berlebihan ini, saya tidak pernah yakin bahwa tata bahasa yang saya buat itu bagus ( dengan ukuran "baik" yang masuk akal).

Saya tidak berharap bahwa ada algoritma untuk mengotomatiskan proses menentukan tata bahasa, tapi saya berharap ada cara untuk menyusun masalah yang menghilangkan banyak dugaan dan coba-coba pendekatan saya saat ini.

Pikiran pertama saya adalah membaca tentang parser, dan saya telah melakukan beberapa hal, tetapi semua yang saya baca tentang subjek ini menggunakan tata bahasa sebagai sesuatu yang diberikan (atau cukup sepele sehingga seseorang dapat menentukannya dengan inspeksi), dan berfokus pada masalah menerjemahkan tata bahasa ini menjadi parser. Saya tertarik dengan masalah ini sebelumnya: cara menentukan tata bahasa di tempat pertama.

Saya terutama tertarik pada masalah menentukan tata bahasa yang secara formal mewakili kumpulan contoh konkret (positif dan negatif). Ini berbeda dengan masalah mendesain sintaks baru . Terima kasih untuk Macneil karena menunjukkan perbedaan ini.

Saya tidak pernah benar-benar menghargai perbedaan antara tata bahasa dan sintaksis, tetapi sekarang saya mulai melihatnya, saya bisa mempertajam klarifikasi pertama saya dengan mengatakan bahwa saya terutama tertarik pada masalah menentukan tata bahasa yang akan menegakkan sintaks yang telah ditentukan: kebetulan dalam kasus saya, dasar untuk sintaks ini biasanya kumpulan contoh positif dan negatif.

Bagaimana tata bahasa ditentukan untuk parser? Apakah ada buku atau referensi di luar sana yang merupakan standar de-facto untuk menggambarkan praktik terbaik, metodologi desain, dan informasi bermanfaat lainnya tentang menentukan tata bahasa untuk pengurai? Poin apa, ketika membaca tentang tata bahasa parser, yang harus saya fokuskan?

Dari file sampel Anda perlu mengambil keputusan berdasarkan seberapa banyak Anda ingin menggeneralisasi dari contoh-contoh itu. Misalkan Anda memiliki tiga sampel berikut: (masing-masing adalah file terpisah)

f() {}
f(a,b) {b+a}
int x = 5;

Anda dapat dengan mudah menentukan dua tata bahasa yang akan menerima sampel ini:

Grammar One Trivial:

start ::= f() {} | f(a,b) {b+a} | int x = 5;

Tata Bahasa Trivial Dua:

start ::= tokens
tokens ::= token tokens | <empty>
token ::= identifier | literal | { | } | ( | ) | , | + | = | ;

Yang pertama sepele karena hanya menerima tiga sampel. Yang kedua sepele karena menerima semua yang mungkin bisa menggunakan tipe token tersebut. [Untuk diskusi ini saya akan berasumsi bahwa Anda tidak terlalu peduli tentang desain tokenizer: Sangat mudah untuk menganggap pengidentifikasi, angka, dan tanda baca sebagai token Anda, dan Anda bisa meminjam token yang ditetapkan dari bahasa scripting apa pun yang Anda inginkan. seperti juga.]

Jadi, prosedur yang harus Anda ikuti adalah mulai dari tingkat atas dan memutuskan "berapa banyak dari setiap contoh yang ingin saya izinkan?" Jika konstruksi sintaksis masuk akal untuk mengulang beberapa kali, seperti methods di kelas, Anda akan menginginkan aturan dengan formulir ini:

methods ::= method methods | empty

Yang lebih baik dinyatakan dalam EBNF sebagai:

methods ::= {method}

Ini mungkin akan menjadi jelas ketika Anda hanya ingin nol atau satu contoh (yang berarti bahwa konstruk adalah opsional, seperti extendsklausa untuk kelas Java), atau ketika Anda ingin mengizinkan satu atau lebih contoh (seperti dengan penginisialisasi variabel dalam deklarasi ). Anda harus memperhatikan masalah-masalah seperti mengharuskan pemisah antara elemen (seperti ,dalam daftar argumen), membutuhkan terminator setelah setiap elemen (seperti dengan ;untuk memisahkan pernyataan), atau tidak memerlukan pemisah atau terminator (seperti kasusnya) dengan metode di kelas).

Jika bahasa Anda menggunakan ekspresi aritmatika, akan mudah bagi Anda untuk menyalin dari aturan prioritas bahasa yang ada. Yang terbaik adalah tetap berpegang pada sesuatu yang terkenal, seperti aturan ekspresi C, daripada memilih sesuatu yang eksotis, tetapi hanya asalkan semua yang lain sama.

Selain masalah prioritas (apa yang diuraikan satu sama lain) dan masalah pengulangan (berapa banyak setiap elemen yang harus terjadi, bagaimana mereka dipisahkan?), Anda juga perlu memikirkan urutan: Haruskah sesuatu selalu muncul sebelum hal lain? Jika satu hal dimasukkan, haruskah yang lain dikecualikan?

Pada titik ini, Anda mungkin tergoda untuk secara tata bahasa menegakkan beberapa aturan, aturan seperti jika Personusia ditentukan, Anda tidak ingin mengizinkan tanggal lahir mereka juga ditentukan. Meskipun Anda dapat membuat tata bahasa Anda untuk melakukannya, Anda mungkin menemukan lebih mudah untuk menegakkan ini dengan pass "semantic check" setelah semuanya diuraikan. Ini membuat tata bahasa lebih sederhana dan, menurut saya, membuat pesan kesalahan yang lebih baik ketika aturan dilanggar.

Di mana saya bisa belajar cara menentukan tata bahasa untuk pengurai?

Untuk sebagian besar generator parser, biasanya beberapa varian dari Backus-Naur 's <nonterminal> ::= expressionFormat. Saya akan melanjutkan dengan asumsi bahwa Anda menggunakan sesuatu seperti itu dan tidak mencoba membuat parser dengan tangan. Jika Anda bisa menghasilkan parser untuk format di mana Anda telah diberikan sintaks (Saya sudah memasukkan contoh masalah di bawah ini), menentukan tata bahasa bukan masalah Anda.

Apa yang saya pikir Anda menentang adalah meramalkan sintaks dari serangkaian sampel, yang benar-benar lebih pengenalan pola daripada parsing. Jika Anda harus menggunakan itu, itu berarti siapa pun yang memberikan data Anda tidak dapat memberikan Anda sintaks karena mereka tidak memiliki pegangan yang baik pada formatnya. Jika Anda memiliki pilihan untuk mendorong kembali dan memberi tahu mereka untuk memberikan definisi formal kepada Anda, lakukanlah. Tidak adil bagi mereka untuk memberikan Anda masalah yang tidak jelas jika Anda dapat dianggap bertanggung jawab atas konsekuensi dari pengurai berdasarkan pada sintaksis yang diterima yang menerima input buruk atau menolak input yang baik.

... Saya tidak pernah yakin bahwa tata bahasa yang saya kemukakan baik (dengan ukuran "baik" yang masuk akal).

"Bagus" dalam situasi Anda harus berarti "mengurai yang positif dan menolak yang negatif." Tanpa spesifikasi formal lainnya dari sintaksis file input Anda, sampel hanya kasus uji Anda dan Anda tidak dapat melakukan lebih baik dari itu. Anda bisa meletakkan kaki Anda dan mengatakan bahwa hanya contoh-contoh positif yang baik dan tolak yang lain, tetapi itu mungkin tidak sesuai dengan apa yang Anda coba capai.

Dalam keadaan yang lebih waras, menguji tata bahasa sama seperti menguji hal lain: Anda harus membuat cukup kasus uji untuk menjalankan semua varian nonterminal (dan terminal, jika dihasilkan oleh lexer).

Contoh Masalah

Tulis tata bahasa yang akan mem-parsing file teks yang berisi daftar sebagaimana didefinisikan oleh aturan di bawah ini:

• Sebuah daftar terdiri dari nol atau lebih hal-hal .
• Sebuah hal yang terdiri dari identifier , sebuah penjepit terbuka, sebuah item daftar dan penjepit penutupan.
• _Item_list_ terdiri dari nol item atau lebih .
• Sebuah Item constsis dari identifier , tanda sama, lain identifier dan titik koma.
• Sebuah identifier adalah urutan satu atau lebih karakter AZ, az, 0-9 atau garis bawah.
• Spasi diabaikan.

Contoh input (semuanya valid):

clank { foo = bar; baz = bear; }
clunk {
    quux =bletch;
    281_apple = OU812;
    He_Eats=Asparagus ; }

Jawaban oleh Macneil dan Blrfl sangat bagus. Saya hanya ingin menambahkan beberapa komentar tentang awal proses.

Sebuah sintaks adalah cara untuk mewakili program yang . Jadi sintaks bahasa Anda harus ditentukan oleh jawaban Anda untuk pertanyaan ini: Apa itu program?

Anda mungkin mengatakan bahwa program adalah kumpulan kelas. Oke, itu memberi kita

program ::= class*

sebagai titik awal. Atau Anda mungkin harus menulisnya

program ::= ε
         |  class program

Sekarang, apa itu kelas? Itu punya nama; spesifikasi superclass opsional; dan sekelompok konstruktor, metode, dan deklarasi lapangan. Juga, Anda memerlukan beberapa cara untuk mengelompokkan kelas menjadi satu unit (tidak ambigu), dan itu harus melibatkan beberapa konsesi untuk kemudahan penggunaan (misalnya, beri tag dengan kata yang dipesan class). Baik:

class ::= "class" identifier extends-clause? "{" class-member-decl * "}"

Itu satu notasi ("sintaks konkret") yang bisa Anda pilih. Atau Anda bisa dengan mudah memutuskan ini:

class ::= "(" "class" identifier extends-clause "(" class-member-decl* ")" ")"

atau

class ::= "class" identifier "=" "CLASS" extends-clause? class-member-decl* "END"

Anda mungkin sudah membuat keputusan ini secara implisit, terutama jika Anda memiliki contoh, tetapi saya hanya ingin menegaskan pokoknya: Struktur sintaksis ditentukan oleh struktur program yang diwakilinya. Itulah yang membuat Anda melewati "tata bahasa sepele" dari jawaban Macneil. Contoh program masih sangat penting. Mereka melayani dua tujuan. Pertama, mereka membantu Anda mengetahui, pada tingkat abstrak, apa program itu. Kedua, mereka membantu Anda memutuskan sintaksis konkret apa yang harus Anda gunakan untuk mewakili struktur bahasa Anda.

Setelah strukturnya turun, Anda harus kembali dan menangani masalah-masalah seperti membolehkan ruang kosong dan komentar, memperbaiki ambiguitas, dll. Ini penting, tetapi mereka sekunder dari keseluruhan desain, dan mereka sangat bergantung pada teknologi parsing yang Anda gunakan.

Akhirnya, jangan mencoba untuk mewakili segala sesuatu tentang bahasa Anda dalam tata bahasa. Misalnya, Anda mungkin ingin melarang beberapa jenis kode yang tidak dapat dijangkau (misalnya, pernyataan setelah a return, seperti di Jawa). Anda mungkin tidak boleh mencoba menjejalkannya ke dalam tata bahasa, karena Anda akan kehilangan banyak hal (whoops, bagaimana jika returnada dalam kawat gigi, atau bagaimana jika kedua cabang ifpernyataan kembali?) Atau Anda akan membuat tata bahasa Anda terlalu rumit untuk mengelola. Ini adalah batasan konteks-sensitif ; tuliskan sebagai pass terpisah. Contoh lain yang sangat umum dari batasan konteks-sensitif adalah sistem tipe. Anda bisa menolak ekspresi seperti 1 + "a"dalam tata bahasa, jika Anda bekerja cukup keras, tetapi Anda tidak bisa menolak 1 + x(di mana xmemiliki tipe string). Begituhindari pembatasan setengah matang dalam tata bahasa dan lakukan dengan benar sebagai izin terpisah.