Dapatkah seseorang memberikan contoh sederhana namun non-mainan dari tata bahasa konteks-sensitif?

12

Saya mencoba memahami tata bahasa konteks-sensitif.

Saya mengerti mengapa bahasa disukai

$\{ww \mid w \in A^*\}$

$\{a^n b^n c^n \mid n\in\mathbb{N}\}$

bukan konteks bebas, tetapi apa yang ingin saya ketahui jika bahasa yang mirip dengan kalkulus lambda yang tidak diketik adalah peka konteks.

Saya ingin melihat contoh sederhana, tetapi bukan mainan (saya perhatikan contoh mainan di atas), contoh tata bahasa yang peka konteks yang dapat, untuk beberapa aturan produksi, misalnya, mengetahui ada atau tidaknya serangkaian simbol berada dalam ruang lingkup saat ini (misalnya saat memproduksi tubuh fungsi).

Apakah tata bahasa sensitif konteks cukup kuat untuk membuat variabel yang tidak terdefinisi / tidak dideklarasikan / tidak terikat sebagai kesalahan sintaksis (bukan semantik)?

formal-grammars programming-languages lambda-calculus context-sensitive BlueBomber
sumber

1

hampir semua bahasa pemrograman nyata adalah konteks-sensitif (dalam arti umum, yaitu menggabungkan kedua chomsky tipe-0 dan tipe-I tata bahasa di bawah "konteks-sensitif"). Misalnya variabel perlu dideklarasikan sebelum digunakan, pengidentifikasi harus unik semua ini memerlukan konteks (st disebut sebagai konteks semantik, tetapi dapat menyesatkan) cs.purdue.edu/homes/hosking/502/notes/04-semantics.pdf

Nikos M .

Nah, "konteks-sensitif" adalah istilah standar untuk tata bahasa tipe-1.

reinierpost

8

Ya, saya percaya ini mungkin, tetapi tidak, saya tidak mau secara eksplisit membangun tata bahasa yang peka konteks. Saya akan menjelaskan jawaban saya, dengan membagi pertanyaan menjadi dua bagian berbeda.

(1) Bagaimana contoh bukan mainan itu? Itu harus mencerminkan deklarasi variabel. Proposal saya tentang bahasa seperti itu, disarikan dari pemrograman yang sebenarnya akan menjadi sesuatu seperti ini. Alfabet adalah . $\{a,b,;,(,)\}$ Bahasa itu peka konteks.

{w_{1}; w_{2}; \dots; w_{n} (x_{1}; x_{2}; \dots; x_{m}) ∣ w_{i}, x_{j} \in {a, b}^{*}, each x_{j} is equal to some w_{i}}

$\{ w_1;w_2;\dots;w_n(x_1;x_2;\dots;x_m) \mid w_i,x_j\in\{a,b\}^*, \mbox{ each }x_j\mbox{ is equal to some }w_i \}$

(2) Untuk menunjukkan itu benar-benar adalah konteks-sensitif saya akan menggunakan formalisme lain. Itu dari mesin Turing dengan penggunaan linier tape-nya: LBA automaton yang linier. Saya dapat memprogram untuk melakukan pencocokan pola / I akan berturut-turut mempertimbangkan setiap dan mencoba untuk mencocokkan dengan tepat , huruf demi huruf. LBA setara dengan tata bahasa yang sensitif terhadap konteks, tetapi jauh lebih mudah untuk diprogram. $x_j$ $w_j$

Hendrik Jan
sumber

Terima kasih atas kirimannya. Saya kurang terbiasa dengan LBA seperti sekarang, jadi saya kurang yakin dengan poin (2). Pada poin (1), saya mencoba melihat bagaimana membuat aturan yang akan menghasilkan, di mana nama variabel diharapkan sebagai ekspresi, hanya satu dari variabel dalam lingkup saat ini. Saya tidak perlu melihat keseluruhan, CSG formal, tetapi hanya penjelasan informal akan bekerja. Saya tidak bisa membayangkan bagaimana melakukannya dengan nama variabel multi-simbol, yang merupakan penggunaan konteks yang berbeda dari, misalnya, menggunakan konteks non-terminal tunggal untuk mengarahkan perjanjian nomor subjek-kata kerja dalam derivasi kalimat ~ bahasa Inggris.

{w w ∣ w \dots}

$\{ ww \mid w\dots\}$

{w w | w . . .}

$\{ww | w ... \}$

3

{w w}

$\{ ww \}$

L R

$LR$

L w R w

$LwRw$

L

$L$

a

$a$

M_{a}

$M_a$

w

$w$

M_{a} b \to b M_{a}

$M_ab \to bM_a$

R

$R$

M_{a} R \to R a

$M_aR \to Ra$

13

$[n]$

Banyak bahasa NP-hard lainnya juga di CSL dengan alasan yang sama, seperti CLIQUE.

Ada juga bahasa yang cukup alami di CSL yang bahkan lebih sulit.

Namun, saya tidak mengetahui adanya cara untuk mengekspresikan CSL yang sewenang-wenang sebagai tata bahasa yang sensitif terhadap konteks (CSG), selain menggunakan konstruksi Landweber dalam Teorema 3 dari makalahnya. Dalam konstruksi ini, CSG menggambarkan kebalikan dari operasi otomat-linear yang mengakui CSL. Produksi CSG menggambarkan bagaimana kondisi mesin tertentu dihasilkan dari satu gerakan yang memungkinkan. CSG semacam itu adalah terjemahan langsung dari automaton ke dalam tata bahasa, sehingga tidak harus sesuai dengan fitur bahasa seperti kemampuan untuk mendeklarasikan variabel, tetapi sebaliknya akan dihambat oleh rincian automaton.

Jika Anda bersikeras menggunakan CSG daripada CSL, dan jika pertanyaan Anda sebenarnya adalah tentang ingin melihat CSG untuk bahasa yang melibatkan pelingkupan variabel terbatas, maka jawaban Hendrik Jan tampaknya merupakan awal yang baik.

András Salamon
sumber

9

Ya, tata bahasa konteks-sensitif (CSG) cukup kuat untuk melakukan pengecekan variabel tidak terdefinisi / tidak dideklarasikan, tetapi sayangnya kami tidak tahu algoritma yang efisien untuk mengurai string CSG.

Contoh nyata dari bahasa konteks-sensitif adalah bahasa pemrograman C. Sebuah fitur seperti mendeklarasikan variabel terlebih dahulu dan kemudian menggunakannya kemudian membuat bahasa-C bahasa konteks-sensitif (CSL). ( Saya tidak tahu tentang kalkulus lambda yang tidak diketik ).

Dan karena kita tidak tahu algoritma penguraian linear untuk CSL (atau CSG). Itulah alasan dalam desain kompiler, kami menggunakan CFG (dan algoritma parsingnya saja) untuk memeriksa sintaks karena kami tahu algoritma yang efisien untuk mengurai CFG (jika dalam bentuk terbatas). Compiler pertama-tama mengurai fitur bebas konteks dan kemudian menangani fitur sensitif konteks dengan cara yang problematis (misalnya, memeriksa variabel apa pun yang digunakan dalam tabel simbol jika itu didefinisikan. Jika tidak, ia menghasilkan kesalahan).

Tata bahasa konteks-sensitif juga digunakan dalam pemrosesan bahasa alami (NLP). Dan sebagian besar bahasa alami adalah contoh bahasa konteks-sensitif. (Saya tidak yakin dengan bahasa Sanskerta ).

Saya akan mencoba menjelaskannya dengan contoh yang konyol tapi sederhana (itu hanya sebuah ide, Anda dapat memperbaikinya):

NOUN     -->  { BlueBomber, Grijesh, I, We}
TENSE    -->  { am, was, is, were}
VERB     -->  { going, eating, working}

SENTENCE --> <NOUN> <TENSE> <VERB>

Sekarang, menggunakan tata bahasa ini, kita dapat menghasilkan beberapa pernyataan yang benar, tetapi ada juga yang salah. Sebagai contoh,

SENTENCE --> <NOUN>   <TENSE>   <VERB>
             Grijesh    is       working       [Correct statement]

Tapi

             Grijesh    am       working       [wrong statement]

Alasan: nilai <TENSE> tergantung pada nilai <NOUN> (misalnya, I <TENNSE> --> I am) dan karenanya tata bahasa tidak menghasilkan pernyataan yang benar dalam bahasa Inggris.

Sebenarnya kita tidak bisa menulis tata bahasa bebas konteks untuk bahasa Inggris lengkap!

_{Anda mungkin telah memperhatikan, penerjemah bahasa alami atau pemeriksa tata bahasa tidak berfungsi dengan benar (coba dengan pernyataan panjang). Karena masalah ini datang di bawah algoritma parsing konteks-sensitif.}

REFERENSI : Anda dapat menonton kuliah Dr. Arun Kumar . _{Dalam beberapa kuliah ia menjelaskan dengan tepat apa yang Anda minati.}

Grijesh Chauhan
sumber

Terima kasih atas informasinya, niscaya akan bermanfaat bagi orang lain yang tertarik dengan topik yang sama, tetapi hanya sebagian yang berhubungan dengan apa yang akan saya tanyakan. Saya tidak khawatir dengan penguraian string yang dihasilkan oleh CSG, tetapi untuk melihat contoh sederhana - bahkan konyol - dari CSG formal yang menghasilkan abstraksi yang terbentuk dengan baik (tidak ada variabel yang tidak terikat dalam tubuh fungsi). Saya dapat membayangkan CSG untuk menghasilkan string "Bahasa Inggris" yang benar, karena satu simbol dapat mengarahkan perjanjian subjek / kata kerja, tetapi dengan abstraksi, variabel biasanya terdiri dari beberapa simbol.

1

@BlueBomber: terima kasih, saya pasti akan menjawab Anda, Malamnya di India..N Selamat tahun baru! :)

Grijesh Chauhan

Sepertinya saya hanya bisa melakukan itu beberapa kali, dan menurut (ini) [ meta.scicomp.stackexchange.com/questions/156/… , saya harus menghapus pertanyaan ini dan memposting ulang di tempat yang lebih tepat ...

@BlueBomber saya telah ditandai untuk menggeser, Anda juga dapat melakukannya.

Grijesh Chauhan

1

(memperluas komentar menjadi jawaban)

Tidak yakin ini adalah contoh yang Anda inginkan.

Hampir semua bahasa pemrograman yang sebenarnya adalah konteks-sensitif (dalam arti umum, yaitu conflating baik Chomsky jenis-0 dan tipe-I tata bahasa di bawah "konteks-sensitif", yang benar tentu saja karena tata bahasa terbatas yang bahkan lebih peka konteks dari konteks - Tata bahasa sensitif ).

Misalnya, "variabel harus dideklarasikan sebelum digunakan", "pengidentifikasi harus unik", semua ini memerlukan konteks (kadang-kadang disebut sebagai konteks semantik, tetapi itu bisa menyesatkan, karena itu tetap melibatkan fitur sintaksis) lihat contoh https: // www .cs.purdue.edu / homes / hosking / 502 / notes / 04-semantics.pdf

Pengertian bahwa contoh-contoh di atas adalah peka konteks (dalam arti tata bahasa / sintaksis serta semantik) adalah karena mereka berbicara tentang konteksnya (apa yang mendahului atau datang sesudahnya).

"Variabel sudah didefinisikan", adalah tentang konteks sebelumnya , penggunaan variabel. "Pengidentifikasi unik", adalah konteks untuk apa yang didahului atau datang setelah deklarasi pengenal, dan seterusnya ..

lihat juga Apakah JavaScript Bahasa Bebas Konteks? pada SO

Nikos M.
sumber

"Konteks-sensitif" berarti tipe-1.

reinierpost

Dapatkah seseorang memberikan contoh sederhana namun non-mainan dari tata bahasa konteks-sensitif?

Jawaban: