Co tak naprawdę oznacza bezkontekstowa gramatyka bezkontekstowa?

Przez jakiś czas studiowałem kompilatory i szukałem, co rozumie się przez „kontekst” w gramatyce i co to znaczy, że gramatyka jest „bezkontekstowa”, ale bez rezultatu.

Czy ktoś może w tym pomóc?

Kontekst można wyjaśnić w odniesieniu do reguł produkcji dozwolonych dla różnych gramatyk w hierarchii Chomsky'ego.

Jeśli wziąć pod uwagę gramatyki bezkontekstowe, ich reguły produkcji mają następującą postać:

Można więc zauważyć, że lewa część tego rodzaju reguł składa się tylko z jednego nieterminalnego symbolu; zatem podstawienie nieterminalnego symbolu ma miejsce bez uwzględnienia jego „kontekstu”, czyli innych symboli, w których jest on otoczony.

Z drugiej strony, jeśli weźmie się pod uwagę reguły produkcji gramatyk kontekstowych, mają one następującą postać:

gdzie jest nieterminalne, a , , to sekwencje nieterminalne i terminale.$A$$\alpha$$\beta$$\gamma$

W tym przypadku „kontekst” (tj. i ) nieterminalnego symbolu, który ma zostać podstawiony, wpływa na efekt podstawienia i jest częścią samej reguły.$\beta$$\gamma$

Więcej informacji można znaleźć w tej odpowiedzi na temat matematyki oraz w tej odpowiedzi na temat inżynierii oprogramowania.

$A\to\text{things}$$\text{stuff}\,A\,\text{more-stuff}\to\text{things}$$\mathrm{Expr}$x:=y+zf(y+z)return y+z

Mówiąc ogólnie, nawet zwykłe języki mogą mieć zależności kontekstowe, co oznacza, że ​​możesz określić - do pewnego stopnia - w jaki sposób symbole mogą pojawiać się w pobliżu innych symboli w ciągu należącym do tego języka.

Specyficzne dla gramatyki bezkontekstowej jest to, że gdy istnieje wiele sposobów na zastąpienie nieterminalnego symbolu, poprzez zastosowanie różnych reguł z tym samym nieterminalnym po prawej stronie, wybór reguły, która ma być stosowana, nigdy nie zależy od tego, co dzieje się wokół tego symbolu podczas procesu wyprowadzania.

Możesz myśleć o nich jako o bezkontekstowych językach pochodnych , w skrócie językach bezkontekstowych.