Apa yang dimaksud dengan kasus penggunaan dunia nyata menggunakan tata bahasa Chomsky Type-I (konteks-sensitif)

9

Saya telah bersenang-senang akhir-akhir ini mengeksplorasi pengembangan parser bahasa dalam konteks bagaimana mereka cocok dengan Hierarki Chomsky.

Apa contoh dunia nyata yang baik (yaitu tidak teoretis) dari tata bahasa yang peka konteks?

language-design parsing grammar Evan Plaice
sumber
8
Apakah bahasa pemrograman dihitung?
Martin York
@LokiAstari Tentu saja.
Evan Plaice
2
Saya kira bahasa pemrograman diperhitungkan, tetapi tidak menghasilkan solusi yang baik, karena kompleksitas sensitivitas konteks biasanya diganti oleh tata bahasa bebas konteks dengan analisis semantik.
Frank
@ Sejujurnya saya kira masalah saya adalah, saya tidak dapat benar-benar memahami apa bahasa yang peka konteks tanpa menerapkannya pada beberapa penggunaan di dunia nyata.
Evan Plaice
Ada beberapa bahasa manusia yang mungkin tidak memerlukan parser bahasa enumerable rekursif dan dengan demikian jatuh ke dalam tipe 1 (konteks senstive) set bahasa. cs.virginia.edu/~evans/cs3102/?p=138

Jawaban:

9

Pertanyaan bagus. Meskipun seperti yang disebutkan dalam komentar sangat banyak bahasa pemrograman yang peka konteks, sensitivitas konteks sering tidak diselesaikan dalam fase parsing tetapi dalam fase selanjutnya - yaitu, superset dari bahasa diuraikan menggunakan tata bahasa bebas konteks, dan beberapa pohon parse itu kemudian disaring.

Namun, itu tidak berarti bahwa bahasa-bahasa itu tidak peka terhadap konteks , jadi inilah beberapa contohnya:

Haskell memungkinkan Anda untuk mendefinisikan fungsi-fungsi yang digunakan sebagai operator, dan juga untuk menentukan prioritas dan asosiasi dari operator tersebut. Dengan kata lain, Anda tidak dapat membuat parse tree yang benar untuk ekspresi operator seperti:

a @@ b @@ c ## d ## e

kecuali Anda sudah menguraikan deklarasi presedensi / asosiatif untuk @@dan ##:

infixr 8 @@
infixr 6 ##

Contoh kedua adalah Bencode , bahasa data yang mengawali konten dengan panjangnya:

<length>:<contents>

Masalah dengan format ini adalah bahwa hampir tidak mungkin untuk mem-parsing tanpa sesuatu yang peka konteks, karena satu-satunya cara untuk mengetahui ukuran "bidang" adalah dengan ... mem-parsing string.

Contoh ketiga adalah XML, dengan asumsi nama tag sewenang-wenang diizinkan: nama tag pembuka harus memiliki tag penutup yang cocok:

<hi>
 <bye>
 the closing tag has to match bye
 </bye>
</hi> <!-- has to match "hi" -->

sumber
Menarik. Saya tahu tentang XML. Saya menduga penggerak di belakang spesifikasi XHTML 1.0 adalah untuk menjauhkan diri dari penerjemah HTML 'quirks mode' yang mendukung pengecualian konteks-sensitif ke XML bebas-konteks yang lebih bersih.
Evan Plaice
@ EvanPlaice Saya bingung dengan komentar Anda - "clean XML" peka konteks seperti yang saya tunjukkan dalam contoh saya.
4
@MattFenwick Saya pikir contoh XML Anda tidak menunjukkan alasan sebenarnya mengapa XML tidak bebas konteks. Alasannya adalah bahwa nama tag sewenang-wenang diizinkan. Jika hanya satu set tag tertentu diizinkan XML akan bebas konteks.
Honza Brabec
@HonzaBrabec Anda benar - secara implisit saya berasumsi bahwa nama tag yang sewenang-wenang diizinkan. Saya seharusnya secara eksplisit menyatakan asumsi itu. Terima kasih telah menunjukkan itu!
3

Selama aku tahu, tata bahasa konteks-sensitif yang digunakan dalam pengolahan bahasa alami, hanya . Memprogram penerjemah dan kompiler bahasa tidak mencoba untuk menguraikan tata bahasa bebas konteks karena kompleksitas (bahkan jika beberapa upaya telah dilakukan di masa lalu).

Mungkin, Anda dapat menemukan beberapa contoh penggunaan nyata di salah satu perpustakaan ini:

http://en.wikipedia.org/wiki/List_of_natural_language_processing_toolkits

http://opennlp.sourceforge.net/projects.html

http://nltk.org/

http://nlp.stanford.edu/nlp/javadoc/javanlp/

AlexBottoni
sumber
2
Bagaimana dengan 'quirks mode' HTML dan preprosesor kode, tidakkah mereka akan menghitung?
Evan Plaice
2

Tata bahasa sensitif konteks kadang-kadang digunakan dalam deskripsi semantik bahasa pemrograman. Mungkin penggunaan tata bahasa sensitif konteks yang paling komprehensif adalah definisi bahasa Algol68. Itu menggunakan grammer konteks gratis dua tingkat (lihat http://en.wikipedia.org/wiki/Two-level_grammar ) untuk menggambarkan sintaks dan semantik program Algol68.

Beberapa rekan saya menggunakan tata bahasa van Wijngaarden untuk mengarahkan implementasi Algol68 (lihat http://en.wikipedia.org/wiki/FLACC ).

BobDalgleish
sumber