Co oznacza „bezkontekstowy” w znaczeniu „gramatyki bezkontekstowej”?

Biorąc pod uwagę ilość materiału, który próbuje wyjaśnić, czym jest gramatyka bezkontekstowa (CFG), zaskoczyło mnie, że bardzo niewiele (w mojej próbce, mniej niż 1 na 20) wyjaśnia, dlaczego takie gramatyki nazywane są „kontekstowo” wolny". Moim zdaniem, nikomu się to nie udaje.

Moje pytanie brzmi: dlaczego gramatyki bezkontekstowe nazywane są bezkontekstowymi? Jaki jest „kontekst”? Miałem intuicję, że kontekstem mogą być inne konstrukcje językowe otaczające obecnie analizowany konstrukt, ale wydaje się, że tak nie jest. Czy ktoś mógłby podać dokładne wyjaśnienie?

Oznacza to, że wszystkie reguły produkcji mają po lewej stronie jeden nie-terminal .

Na przykład ta gramatyka, która rozpoznaje ciągi pasujących nawiasów („()”, „() ()”, „(()) ()”, ...) jest pozbawiona kontekstu:

S → SS
S → (S)
S → ()

Lewa strona każdej reguły składa się z jednego nieterminala (w tym przypadku jest to zawsze S, ale może być ich więcej).

Rozważmy teraz inną gramatykę, która rozpoznaje ciągi znaków {a ^ nb ^ nc ^ n: n> = 1} (np. „Abc”, „aabbcc”, „aaabbbccc”):

S  → abc
S  → aSBc
cB → WB
WB → WX
WX → BX
BX → Bc
bB → bb

Jeśli nieterminalny Bjest poprzedzony znakiem terminala / literału c, przepisujesz ten termin na, WBale jeśli poprzedza go b, rozwijasz się do bbniego. Przypuszczalnie o tym wspomina wrażliwość kontekstowa gramatyk kontekstowych.

Język bezkontekstowy można rozpoznać jako automat z funkcją opuszczania . Podczas gdy maszyna stanów skończonych nie korzysta z pamięci dyskowej, tzn. Jej decyzja opiera się tylko na jej aktualnym stanie i danych wejściowych, automat push-down ma również do dyspozycji stos i może podejmować decyzje u góry stosu.

Aby zobaczyć, jak to działa, możesz przeanalizować zagnieżdżone nawiasy, przesuwając od lewej do prawej i popychając lewy nawias na stos za każdym razem, gdy go napotkasz, i wyskakując za każdym razem, gdy napotkasz prawy nawias. Jeśli nigdy nie spróbujesz wyskoczyć z pustego stosu, a stos jest pusty na końcu łańcucha, łańcuch jest prawidłowy.

W przypadku języka kontekstowego PDA nie wystarczy. Będziesz potrzebował automatu z ograniczeniem liniowym, który przypomina maszynę Turinga, której taśma nie jest nieograniczona (chociaż ilość dostępnej taśmy jest proporcjonalna do wejścia). Zauważ, że dość dobrze opisuje to komputery - lubimy myśleć o nich jak o maszynach Turinga, ale w prawdziwym świecie nie można pobrać dowolnie większej ilości pamięci RAM w trakcie programu. Jeśli nie jest dla ciebie oczywiste, w jaki sposób LBA jest silniejszy niż PDA, LBA może emulować PDA, używając części taśmy jako stosu, ale może również użyć taśmy w inny sposób.

(Jeśli zastanawiasz się, co może rozpoznać maszyna skończona, odpowiedzią są wyrażenia regularne. Ale nie wyrażenia regularne na sterydach z grupami przechwytywania i spoglądaniem wstecz / spoglądaniem w przyszłość w językach programowania; mam na myśli te, które możesz zbudować z operatorami takimi jak [abc], |, *, +, i ?. Widać, że abbbzpasuje do wyrażenia regularnego ab*ztylko poprzez utrzymanie aktualnej pozycji w łańcuchu i regex, nie wymaga stosu).

Pozostałe odpowiedzi są dość długie, nawet jeśli są dokładne i poprawne. To jest krótka wersja.

Jeśli masz ciąg znaków (terminale i nieterminale) i chcesz zastąpić nieterminal w ciągu, gramatyka bezkontekstowa pozwala to zrobić niezależnie od znaków otaczających nieterminal.

Rozważ następujące zasady (małe litery to terminale, wielkie litery to nieterminale):

A -> a
AB -> a

W pierwszej regule możesz zastąpić A niezależnie od tego, co się wokół niej pojawi (kontekst). W drugiej regule nie można zastąpić, Achyba że następuje po niej B. Chociaż w tym przypadku oba nieterminale zostaną zastąpione, ważne jest, aby nieterminale otaczające Asprawę. Nie można zastąpić BAz alub Bz a: tylko Apo której następuje Bponieważ zamówienia, kontekst od nieterminali jest ważne. Oznacza to kontekst kwestii nieterminalnych w drugiej regule, dzięki czemu jest wrażliwy na kontekst, podczas gdy pierwsza reguła jest pozbawiona kontekstu.

Aby lepiej zrozumieć rozróżnienie i terminologię, dobrym pomysłem jest zestawienie języka bezkontekstowego, takiego jak ⁿ b ^n, z językiem kontekstowym, takim jak ⁿ b ⁿ c ⁿ . (Notacja: a, b i c są tutaj literałami, a wykładnik n oznacza powtarzanie literałów n razy , powiedzmy n > 0). Na przykład, aabbclub aabbbccnie jest w tym drugim języku, podczas gdy aabbccjest.

Akceptorem dla języka bezkontekstowych ⁿ b ⁿ może zawrzeć parę ai bbez względu na to, co znajduje się wokół niego (czyli niezależnie od kontekstu, w którym pojawia ab) i będzie ona działać prawidłowo, przyjmując tylko ciągi w języku i odrzucania czegokolwiek innego, tzn. gramatyka jest S -> aSb | ab. Zauważ, że po lewej stronie produkcji nie ma żadnych zacisków . (Istnieją dwie reguły produkcji, ale piszemy je tylko zwięźle.) Akceptant może w zasadzie podjąć lokalną decyzję bez kontekstu.

W przeciwieństwie do tego, nie można zrobić czegoś takiego w przypadku języka kontekstowego a ⁿ b ⁿ c ⁿ , ponieważ w tym drugim przypadku należy w jakiś sposób pamiętać kontekst, w którym się znajdowałeś, tj. Liczbę skurczów ab, aby dopasować je do skurczów bc. Gramatyka tego drugiego języka to

S -> abc | aBSc
Ba -> aB
Bb -> bb

Zauważ, że masz dwa terminale i nie-terminale po lewej w ostatnich dwóch regułach. Terminale po lewej stronie są kontekstem, w którym terminale nieterminalne mogą być rozszerzane.

Bootnote dotyczące terminologii „kontrakt” kontra „rozwinąć” itd .: chociaż gramatyki formalne są [formalnie, hah] generatywne, sposób, w jaki są one faktycznie implementowane w parserach, jest w rzeczywistości redukcjonistyczny, tzn. W zasadzie kontaktujesz wszystko z nieterminalnym stosowanie reguł „w odwrotnej kolejności”, dlatego nawet pierwsza podana powyżej gramatyka nie jest praktyczna w programie (dałoby to słynny konflikt redukcji przesunięcia, ponieważ nie możesz zdecydować, którą regułę zastosować), ale dwie powyższe gramatyki wystarczają do zilustrowania rozróżnienia między bezkontekstowym i wrażliwym na kontekst. Kwestia dwuznaczności w gramatyce bezkontekstowej jest raczej skomplikowana i nie jest tak naprawdę tematem tego pytania, więc nie powiem tutaj więcej, zwłaszcza że okazuje się, że Wikipedia ma porządny artykuł na ten temat. W przeciwieństwie do artykułów na temat bezkontekstowego, a zwłaszcza na temat języka kontekstowego, są! @ # $ @! # $, Szczególnie jeśli jesteś nowy w temacie ... Myślę, że to więcej na mojej liście TODO.

Powyższe odpowiedzi podają całkiem dobrą definicję tego, co to jest. Zobaczmy, czy mogę to wyrazić własnymi słowami, tak abyś miał 23 wyjaśnienia zamiast 20. Cała gramatyka, każda gramatyka, polega na ustaleniu, czy dane zdanie jest zdaniem w danym języku. Jednak tak naprawdę używamy gramatyki i analizowania, aby dowiedzieć się, co to zdanie oznacza. To jest jak stare schematy zdania, które mogłeś, ale nie musiałeś, powtórzyć na lekcji angielskiego w szkole. Zdanie składa się z części podmiotowej i predykatowej, część tematyczna ma rzeczownik i może niektóre przymiotniki, część predykatowa ma czasownik, a może rzeczownik rzeczowy, z kilkoma przymiotnikami itp.

Gdyby istniała gramatyka języka angielskiego (i nie sądzę, by istniała, nie w sensie informatyki), wówczas obowiązywałyby ją zasady następującej formy, zwane produkcjami.

Sentence -> SubjectPart PredicatePart
SubjectPart -> Adjective Noun

itp...

Następnie możesz napisać program i przekazać mu dowolne zdanie, a program może użyć gramatyki, aby dowiedzieć się, która część zdania to każde słowo i jaki mają związek ze sobą.

Jeśli w każdej produkcji jest tylko jedna rzecz po lewej stronie, oznacza to, że ilekroć widzisz prawą stronę w zdaniu, możesz zastępować po lewej stronie. Na przykład za każdym razem, gdy widziałeś rzeczownik przymiotnikowy, możesz powiedzieć „That's a SubjectPart”, nie zwracając uwagi na nic poza tym wyrażeniem.

Jednak angielski (nawet uproszczony opis angielskiego, który podałem powyżej) jest zależny od kontekstu. „Przymiotnik” nie zawsze jest podmiotem, może być wyrażeniem rzeczownikowym w predykacie. To zależy od kontekstu. Rozwińmy nieco naszą pseudo-angielską gramatykę:

Sentence -> SubjectPart PredicatePart
SubjectPart -> Adjective Noun
PredicatePart -> VerbPhrase ObjectNounPhrase
VerbPhrase ObjectNounPhrase -> VerbPhrase Adjective Noun

Możesz utworzyć „rzeczownik przymiotnikowy” w wyrażeniu ObjectNounPhrase, tylko jeśli występuje ono po wyrażeniu czasownikowym.

Zasadniczo, jeśli masz produkcję i możesz ją zastosować w dowolnym momencie, bez względu na to, co go otacza, jest on pozbawiony kontekstu.

Zawsze możesz łatwo stwierdzić, czy gramatyka jest pozbawiona kontekstu. Po prostu sprawdź, czy po lewej stronie strzałek jest więcej niż jeden symbol.

Każdy język może być opisany przez więcej niż jedną gramatykę. Jeśli jakaś gramatyka języka jest pozbawiona kontekstu, język jest pozbawiony kontekstu. W przypadku niektórych języków można udowodnić, że nie jest możliwa gramatyka bezkontekstowa. Przypuszczam, że może istnieć gramatyka bezkontekstowa dla uproszczonego pseudo-angielskiego podzbioru, który opisuję powyżej.

Jeśli chodzi o to, dlaczego ma to znaczenie, wymaga prostszego programu do parsowania gramatyki bezkontekstowej. Jak zauważono w innych odpowiedziach, nie wymaga pełnej mocy maszyny Turinga, aby parsować gramatykę bezkontekstową. Analizator składni LR (1) lookahead (który jest rodzajem maszyny wypychającej) dla konkretnej gramatyki bezkontekstowej może analizować dowolne zdanie w tej gramatyce w czasie i przestrzeni liniowej do długości zdania. Jeśli zdanie jest w języku, analizator składni utworzy drzewo struktury identyfikujące, co oznacza każdy symbol w zdaniu (lub przynajmniej jaką rolę odgrywa w strukturze). Jeśli zdania nie ma w gramatyce, parser zauważy i zatrzyma się na pierwszym symbolu, którego nie da się pogodzić z gramatyką i poprzedzającymi symbolami (na pierwszym „błędzie”).

Jeszcze lepsze jest to, że istnieją programy, w których możesz podać opis gramatyki oraz listę instrukcji dotyczących tego, co zrobić z każdą częścią (w pewnym sensie przypisując „znaczenie” do każdej produkcji), a program napisze parser dla Was. Program przeanalizuje zdanie, znajdzie strukturę i uruchomi instrukcje dla każdej części struktury. Ten rodzaj programu nazywa się generatorem analizatora składni lub kompilatorem-kompilatorem.

Ten rodzaj analizy języka został wymyślony do automatycznej analizy języka naturalnego (np. Angielskiego), ale okazuje się, że jest to najbardziej przydatne do analizy języków komputerowych. Projektant języka może napisać gramatykę, która przechwytuje jego nowy język, a następnie uruchomić go za pomocą generatora analizatora składni, aby uzyskać program, który analizuje jego język i tłumaczy, interpretuje, kompiluje, wykonuje itp., Jeśli chce.

W rzeczywistości w większości przypadków tak naprawdę nie można tego zrobić. Na przykład zrównoważone nawiasy są językiem bezkontekstowym, ale język, w którym wymagane jest zadeklarowanie wszystkich zmiennych przed ich użyciem, jest zależny od kontekstu. Analizator składni jest częścią kompilatora, ale wymagana jest dodatkowa logika w celu wymuszenia tych innych wymagań. Następnie musisz napisać gramatykę, która przechwytuje jak najwięcej twojego języka, uruchom go przez generator parsera, a następnie napisz kod, który egzekwuje pozostałe wymagania (moduł obsługi tabeli symboli itp.).

Zasadniczo nie używamy gramatyk kontekstowych, ponieważ są one znacznie słabiej obsługiwane. Nie wiem, czy istnieje odpowiednik generatora analizatora składni LR (k) dla języków kontekstowych. Tak, maszyna Turinga (lub maszyna związana liniowo) może parsować jedną, ale nie wiem, czy istnieje ogólny algorytm przekształcania gramatyki kontekstowej w program dla maszyny Turinga w tym sensie, że LR (1 ) generator tworzy tabele analizujące dla maszyny pushdown. Domyślam się, że tabele leżące u podstaw parsera byłyby wykładniczo większe. W każdym razie studenci CS (podobnie jak ja, w przeszłości) zwykle uczą się gramatyki bezkontekstowej i generatorów analizatora składni LR (1), takich jak YACC.

Gramatyki bezkontekstowe nie uwzględniają żadnego kontekstu dla reguł produkcji. Kontekstem są albo terminale, albo nie-terminale.

Tak więc: Gramatyki bezkontekstowe mają tylko jeden nie-terminal po lewej stronie reguł produkcji.