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?

terminology context-free formal-grammars

— Shady Atef
źródło

Co rozumiesz przez „naprawdę”? Jakie wyjaśnienia przeczytałeś, a czego nie rozumiesz? IIRC, każdy w połowie przyzwoity podręcznik na ten temat wyjaśni, co one oznaczają.

— Raphael

Oto odpowiedni przykład. Rozważ słowo „przeczytaj”. To pojedyncze słowo, które ma dwa zupełnie różne znaczenia. Jeden to czas teraźniejszy „czytać”, drugi to czas przeszły „czytam”. Jeśli zobaczyłeś słowo „przeczytaj” w jednym tekście, nie możesz jednoznacznie określić, które z dwóch znaczeń ono reprezentuje, bez spojrzenia na kontekst. Dlatego angielski jest zależny od kontekstu, ponieważ nie można przeanalizować każdego tokenu (słowa) bez uwzględnienia go w kontekście. Gramatyka kontekstowa to taka, w której znaczenie każdego tokena można jednoznacznie wydedukować z pojedynczego tokena, który go reprezentuje.

— Alexander - Przywróć Monikę

Odpowiedzi:

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ć:

ZA \to α

$A \rightarrow \alpha$

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ć:

β ZA γ \to β α γ

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

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.

— PieCot
źródło

Dziękuję za Twoją odpowiedź. Ale dla mnie dziwne jest to, że podobne pytanie zostało zadane na temat matematyki SE.

— Shady Atef

Pamiętaj, że i nie muszą być częścią wyniku produkcji. Można je również zastąpić inną sekwencją, jak widać w odpowiedzi Davida Richerby'ego.

β

$\beta$

γ

$\gamma$

— Frozn

@Frozn AFAIK podana tutaj jest standardową definicją zgodnie z hierarchią Chmosky. Jasne, istnieją gramatyki mocniejsze niż wrażliwe na kontekst, które pozwalają na dowolny rodzaj produkcji, ale standardowe gramatyki wrażliwe na kontekst nie.

— Bakuriu

@Frozn: Bakariu ma rację, tutaj mówimy o gramatyce zdefiniowanej zgodnie z hierarchią Chomsky'ego, która opiera się na coraz bardziej restrykcyjnych warunkach w regułach produkcji. W szczególności gramatyki bezkontekstowe są gramatykami typu 2, podczas gdy gramatyczne kontekstowe są typu 1. Jednak gramatyki typu 0 mają reguły produkcji, które nie są ograniczone żadnymi ograniczeniami, a zatem nazywane są nieograniczonymi systemami przepisywania. Tutaj możesz znaleźć krótki opis hierarchii Chomsky'ego z kilkoma przykładami.

— PieCot

β A γ \to δ

$\beta A\gamma \rightarrow \delta$

| β A γ | \leq | δ |

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

$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
źródło

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.

— André Souza Lemos
źródło