Apa yang sebenarnya dimaksud dengan bebas konteks dalam tata bahasa bebas konteks?

Saya telah mempelajari kompiler untuk sementara waktu, dan saya telah mencari apa yang dimaksud dengan "konteks" dalam tata bahasa dan apa artinya bagi tata bahasa untuk menjadi "bebas konteks", tetapi tanpa hasil.

Jadi, adakah yang bisa membantu dengan ini?

terminology context-free formal-grammars Shady Atef
sumber

Apa yang Anda maksud dengan "sungguh"? Penjelasan mana yang telah Anda baca dan apa yang tidak Anda mengerti? IIRC, setiap buku teks setengah layak tentang masalah ini akan menjelaskan apa artinya.

Raphael

Inilah contoh yang bisa diterima. Pertimbangkan kata "baca". Ini satu kata yang memiliki dua arti yang sangat berbeda. Salah satunya adalah present tense "to read", yang lainnya adalah tense past "I read". Jika Anda melihat kata "baca" dalam selembar teks, Anda tidak dapat menyatukan dua makna yang diwakilinya, tanpa melihat konteksnya. Jadi, bahasa Inggris adalah konteks-sensitif, karena Anda tidak dapat menguraikan setiap token (kata) tanpa mempertimbangkannya dalam konteks. Tata bahasa konteks-sensitif adalah makna di mana setiap token tidak dapat direduksi secara jelas dari token tunggal yang mewakilinya.

Alexander - Pasang kembali Monica

Jawaban:

Konteksnya dapat dijelaskan sehubungan dengan aturan produksi yang diizinkan untuk tata bahasa yang berbeda dalam hierarki Chomsky.

Jika Anda mempertimbangkan tata bahasa bebas konteks, aturan produksinya memiliki formulir berikut:

A \to α

$A \rightarrow \alpha$

Jadi, Anda dapat mengamati bahwa bagian kiri dari aturan semacam ini hanya terdiri dari satu simbol non-terminal; dengan demikian, penggantian simbol non-terminal terjadi tanpa mempertimbangkan "konteksnya", yaitu simbol lain yang dikelilingi olehnya.

Di sisi lain, jika Anda mempertimbangkan aturan produksi tata bahasa yang sensitif terhadap konteks, mereka memiliki bentuk berikut:

β A γ \to β α γ

$\beta A \gamma \rightarrow \beta \alpha \gamma$

di mana adalah non-terminal dan , , adalah urutan non-terminal dan terminal. $A$ $\alpha$ $\beta$ $\gamma$

Dalam hal ini "konteks" (yaitu, dan ) dari simbol non-terminal yang akan diganti mempengaruhi efek substitusi dan itu adalah bagian dari aturan itu sendiri. $\beta$ $\gamma$

Anda dapat menemukan lebih banyak detail dalam jawaban ini untuk matematika dan jawaban ini untuk rekayasa perangkat lunak.

PieCot
sumber

Terima kasih atas jawabannya. Tetapi hal yang aneh bagi saya adalah bahwa pertanyaan serupa ditanyakan pada matematika SE.

Shady Atef

Perhatikan bahwa dan tidak perlu menjadi bagian dari hasil produksi. Mereka juga bisa diganti dengan beberapa urutan lain seperti yang dapat dilihat di jawaban @David Richerby.

β

$\beta$

γ

$\gamma$

Frozn

@Frozn AFAIK yang diberikan di sini adalah definisi standar sesuai dengan hierarki Chmosky. Tentu, ada tata bahasa yang lebih kuat daripada konteks-sensistif yang memungkinkan segala jenis produksi, tetapi tata bahasa konteks-sensitif standar tidak.

Bakuriu

@Frozn: Bakariu benar, di sini kita berbicara tentang tata bahasa yang didefinisikan sesuai dengan hierarki Chomsky, yang didasarkan pada kondisi yang semakin ketat pada aturan produksi. Secara khusus, tata bahasa bebas konteks adalah tipe-2 tata bahasa, sedangkan yang peka konteks adalah tipe-1. Namun, tata bahasa tipe-0 memiliki aturan produksi yang tidak dibatasi oleh batasan apa pun dan dengan demikian disebut sistem penulisan ulang yang tidak dibatasi. Di sini Anda dapat menemukan deskripsi singkat hierarki Chomsky dengan beberapa contoh.

PieCot

@ Bakuriu dan PieCot Baiklah terima kasih untuk itu, saya tahu hierarki Chomsky. Suatu ketika seseorang memperkenalkan tata bahasa monoton sebagai konteks-sensitif dan bersama-sama dengan tipe-0 dan tipe-1 dari hierarki Chomsky ini menghasilkan aturan umum selama.

β A γ \to δ

$\beta A\gamma \rightarrow \delta$

| β A γ | \leq | δ |

$|\beta A\gamma| \leq |\delta|$

Frozn

"Konteks" adalah teks di sekelilingnya. Tata bahasa bebas konteks bebas konteks dalam arti aturannya terlihat seperti , daripada . Sisi kiri aturan selalu merupakan simbol non-terminal tunggal. Artinya, aturan untuk memperluas simbol non-terminal tidak tergantung pada teks apa yang muncul di sekitar simbol itu (konteksnya), tetapi hanya bergantung pada simbol itu sendiri. Misalnya, dalam tata bahasa untuk bahasa pemrograman, istilah meluas ke jenis ekspresi yang sama apakah Anda sedang menulis tugas (misalnya, ), meneruskan argumen ke fungsi (misalnya, ) atau mengembalikan nilai dari suatu fungsi (misalnya, ). $A\to\text{things}$ $\text{stuff}\,A\,\text{more-stuff}\to\text{things}$ $\mathrm{Expr}$ x:=y+zf(y+z)return y+z

David Richerby
sumber

Secara umum, bahkan bahasa reguler dapat memiliki dependensi konteks, artinya Anda dapat menentukan - sampai batas tertentu - dengan cara apa simbol dapat muncul di sekitar simbol lain dalam string yang termasuk dalam bahasa tersebut.

Apa yang khusus untuk tata bahasa bebas konteks adalah bahwa ketika ada banyak cara untuk menggantikan simbol non-terminal, dengan menerapkan aturan yang berbeda dengan non-terminal yang sama di sisi kanan, pilihan aturan yang akan diterapkan tidak pernah bergantung pada apa sedang terjadi di sekitar simbol ini selama proses derivasi.

Anda dapat menganggap mereka sebagai bahasa derivasi bebas konteks, singkatnya bahasa bebas konteks.

André Souza Lemos
sumber