Do czego odnosi się „kontekst” w „gramatyce bezkontekstowej”?

Istnieje wiele definicji online na temat gramatyki bezkontekstowej, ale nic, co znalazłem, nie zaspokoi mojego głównego problemu:

Z jakiego kontekstu jest wolny?

Aby to zbadać, przejrzałem „gramatykę wrażliwą na kontekst”, ale nadal nie udało mi się znaleźć o co chodzi w „kontekście”.

Czy ktoś może wyjaśnić, do czego contextodnosi się to określenie?

terminology context-free formal-grammars

— CodyBugstein
źródło

Uważam, że wyjaśnienie wikipedii jest całkiem dobre - „Formalna gramatyka jest uważana za„ bezkontekstową ”, gdy jej reguły produkcji można zastosować bez względu na kontekst nieterminala. Bez względu na otaczające go symbole, pojedynczy nieterminal po lewej stronie zawsze może być zastąpiony przez prawą stronę. ” - można go przeformułować i uprościć, aby stać się „zwykłym angielskim”, ale sedno tego wydaje mi się dość jasne.

— jkff

@ jkff Wspaniale jest, że wyjaśnienie jest dobre, ale wciąż nie rozumiem, co tak naprawdę oznacza „kontekst”. Muszę zobaczyć przykład, w którym jest kontekst i gdzie nie ma kontekstu. Wydaje mi się, że każda gramatyka, którą widziałem, ma kontekst

— CodyBugstein

Czy nie jest to jasne z definicji?

— Raphael

Jak na ironię, w tej definicji brakuje istotnego fragmentu kontekstu , więc właśnie dodałem zdanie, aby to wyjaśnić.

— reinierpost

Przykład: w C ++ 11 overridemoże być nazwą zmiennej lub słowem kluczowym, w zależności od tego, gdzie jest używana (tj. Od jej kontekstu). Jeśli zostanie użyte po deklaracji metody, jest słowem kluczowym. W przeciwnym razie tak nie jest. To jest przykład gramatyki kontekstowej.

— Thomas Eding

Odpowiedzi:

Masz rację, zawsze istnieje pewien kontekst. Nie sądzę, że można zrozumieć, co oznacza „kontekst” w „bezkontekstowym” bez zrozumienia produkcji.

Produkcja jest regułą substytucyjną. Mówi, że aby wygenerować ciągi w języku, możesz zastąpić to, co jest po lewej stronie, tym, co jest po prawej stronie:

A -> xy

Oznacza to, że abstrakcyjną sekwencję A można zastąpić znakiem „x”, a następnie znakiem „y”. Możesz także mieć bardziej złożone produkcje:

zA -> xy

Oznacza to, że znak „z”, po którym następuje abstrakcyjna sekwencja A, można zastąpić znakami „x” i „y”.

Produkcja bezkontekstowa oznacza po prostu, że po lewej stronie jest tylko jedna rzecz. Pierwszy przykład jest pozbawiony kontekstu, ponieważ A można zastąpić „x” i „y” bez względu na to, co nastąpi przed nim lub po nim. Jednak w drugim przykładzie znak „z” musi pojawić się przed literą A, a następnie kombinację można zastąpić literą „x” i „y”, więc występuje pewien kontekst.

Gramatyka bezkontekstowa jest więc po prostu gramatyką zawierającą wyłącznie produkcje bezkontekstowe.

Drugi przykład jest w rzeczywistości przykładem nieograniczonej produkcji. Istnieje inna kategoria, która znajduje się między kontekstową a nieograniczoną, zwana „wrażliwą na kontekst”. Przykładem produkcji kontekstowej jest:

zA -> zxy

Różnica polega na tym, że to, co znajduje się przed literą A (i po) po lewej stronie, musi zostać zachowane po prawej stronie. To faktycznie oznacza, że tylko A jest podstawione, ale można je zastąpić tylko w odpowiednim kontekście.

— Vaughn Cato
źródło

Dziękuję, to ogromna pomoc! Nigdy nie widziałem jeszcze przykładu gramatyki z więcej niż jedną zmienną po lewej stronie, jak pokazałeś. Myślę, że dlatego nie mogłem zobaczyć, jaki był „kontekst”. Dziękuję

— CodyBugstein

Być może prostszym kontekstowym przykładem byłoby zA -> zxy: A nadal jest zastępowane przez xy, ale dopiero po z.

— MSalters

Bardziej szczegółowo, ta odpowiedź mówi o nieograniczonej gramatyce , podczas gdy @MSalters wskazuje, że gramatyka wrażliwa na kontekst byłaby lepszym przykładem znaczenia kontekstu.

@MSalters: Masz rację. Zmodyfikowałem swoją odpowiedź. Trudno mi było wymyślić sposób dodania tych szczegółów do mojego opisu bez zabarwienia bardziej złożonego, więc ostatecznie skończyłem na dodaniu więcej szczegółów na końcu.

— Vaughn Cato

Zastanów się nad regułą i powiedzmy, że masz formę a następnie redukcja do β nie zależy od tego, czym są α i δ. Dzięki temu jest pozbawiony kontekstu, ponieważ nie zależy od otaczającego kontekstu.

A \to β

$A \rightarrow \beta$

α A δ

$αAδ$

— iLoveCamelCase
źródło

Co to jest beta? Czy to jest terminal czy zmienna? Czy potrafisz wyjaśnić „formę sentymentalną”? Czy to oznacza, że nie można go dalej wyprowadzić?

— CodyBugstein

Beta może być wszystkim, tylko A-> beta jest regułą. Sentencjalna forma oznacza, że biorąc pod uwagę twój symbol początkowy przy użyciu reguł gramatyki, przekształcamy go w wynik. Ten wynik nazywa się formą sentymentalną. Po każdym użyciu każdej reguły otrzymujemy nowy formularz sentymentu.

— iLoveCamelCase

@Imray Musisz spojrzeć na formalne definicje gramatyki i gramatyki bezkontekstowej. Nie ma skrótu do zrozumienia obiektów formalnych .

— Raphael

@Imray A zdaniowymi forma jest łańcuch zacisków i nie końcowych symboli, który wynika z pewnik (zwany także początkowy symboli ) na podstawie gramatyki zasad (zwany również produkcji ). Formę sentymentalną można przekształcić w inną, stosując regułę do jednego z jej nieterminalnych symboli. Gdy nie ma żadnych terminali, formą sentencji jest zdanie , tzn. Ciąg lub słowo w języku zdefiniowanym lub wygenerowanym przez gramatykę. Terminologia pochodzi od lingwistów, którzy byli kiedyś głównymi autorami tej części formalnej teorii języka.

— babou

Myślałem, że forma sentymentalna nie może zawierać żadnych zmiennych - muszą to być tylko terminale.

— CodyBugstein