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
źródło
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.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:
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:
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:
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.
źródło
zA -> zxy: A nadal jest zastępowane przez xy, ale dopiero po z.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.
źródło