Co to jest gramatyka bezkontekstowa?

Czy ktoś może mi wyjaśnić, czym jest gramatyka bezkontekstowa? Po przejrzeniu wpisu w Wikipedii, a następnie wpisu w Wikipedii dotyczącego gramatyki formalnej, jestem całkowicie zdezorientowany. Czy ktoś byłby tak miły i wyjaśniłby, czym są te rzeczy?

Zastanawiam się nad tym, ponieważ chcę zbadać analizę składniową, a także na marginesie, ograniczenie silnika regex.

Nie jestem pewien, czy te terminy są bezpośrednio związane z programowaniem, czy też są związane bardziej z językoznawstwem w ogóle. Jeśli tak jest, przepraszam, może można by to przenieść, jeśli tak?

Gramatyka bezkontekstowa to gramatyka spełniająca określone właściwości. W informatyce gramatyki opisują języki; w szczególności opisują języki formalne.

Język formalny to po prostu zbiór (termin matematyczny na zbiór obiektów) ciągów (sekwencji symboli ... bardzo podobny do użycia słowa „łańcuch” w programowaniu). Prostym przykładem języka formalnego jest zbiór wszystkich ciągów binarnych o długości trzy, {000, 001, 010, 011, 100, 101, 110, 111}.

Gramatyki działają poprzez definiowanie przekształceń, które możesz wykonać, aby skonstruować ciąg w języku opisanym przez gramatykę. Gramatyka powie, jak przekształcić symbol początkowy (zwykle S) w jakiś ciąg symboli. Gramatyka dla podanego wcześniej języka to:

S -> BBB
B -> 0
B -> 1

Sposobem na zinterpretowanie tego jest stwierdzenie, że Smożna go zastąpić BBBi Bzastąpić przez 0, a także Bprzez 1. Tak więc skonstruować łańcuch 010, możemy zrobić S -> BBB -> 0BB -> 01B -> 010.

Gramatyka bezkontekstowa to po prostu gramatyka, w której element, który zastępujesz (na lewo od strzałki), jest pojedynczym symbolem „nieterminalowym”. Symbol nieterminalny to dowolny symbol używany w gramatyce, który nie może pojawić się w końcowych napisach. W gramatyce powyżej „S” i „B” to symbole nieterminalne, a „0” i „1” to symbole „końcowe”. Gramatyki jak

S -> AB
AB -> 1
A -> AA
B -> 0

Nie są regularne, ponieważ zawierają reguły takie jak „AB -> 1”.

Teoria języka jest powiązana z teorią obliczeń. Jaka jest bardziej filozoficzna strona informatyki, o decydowaniu, które programy są możliwe lub które kiedykolwiek będzie można napisać, i jakiego rodzaju problemów nie da się napisać algorytmu do rozwiązania.

Wyrażenie regularne to sposób opisu języka regularnego. Język regularny to język, o którym decyduje deterministyczny automat skończony.

Powinieneś przeczytać artykuł o maszynach skończonych: http://en.wikipedia.org/wiki/Finite_state_machine

Oraz języki regularne: http://en.wikipedia.org/wiki/Regular_language

Wszystkie zwykłe języki są językami bezkontekstowymi, ale istnieją języki bezkontekstowe, które nie są normalne. Język wolny od kontekstu to zbiór wszystkich ciągów akceptowanych przez gramofon bezkontekstowy lub automat przesuwający, który jest maszyną skończoną z pojedynczym stosem: http://en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_Context-free_Languages

Istnieją bardziej skomplikowane języki, które wymagają maszyny Turinga (dowolnego możliwego programu, który możesz napisać na swoim komputerze), aby zdecydować, czy łańcuch jest w tym języku, czy nie.

Teoria języka jest również bardzo powiązana z problemem P vs. NP i kilkoma innymi interesującymi rzeczami.

Mój podręcznik Wprowadzenie do informatyki na trzecim roku był całkiem dobry w wyjaśnianiu tego zagadnienia: Wprowadzenie do teorii obliczeń. Michael Sipser. Ale kupienie nowego kosztowało mnie około 160 dolarów i nie jest zbyt duże. Może znajdziesz używaną kopię, kopię w bibliotece lub coś, co może ci pomóc.

EDYTOWAĆ:

Ograniczenia wyrażeń regularnych i wyższych klas językowych były badane mnóstwo w ciągu ostatnich 50 lat. Może zainteresuje Cię lemat o pompowaniu dla języków regularnych. Jest to sposób na udowodnienie, że określony język nie jest regularny:

http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

Jeśli język nie jest zwykły, może być bezkontekstowy, co oznacza, że ​​może być opisany przez gramofon bezkontekstowy lub może być nawet w wyższej klasie językowej, możesz udowodnić, że nie jest wolny od kontekstu, lemat o pompowaniu dla programu Context Free języki, które są podobne do języka dla wyrażeń regularnych.

Język może być nawet nierozstrzygalny, co oznacza, że ​​nawet maszyna Turinga (może programować twój komputer) nie może być zaprogramowana do decydowania, czy łańcuch powinien być akceptowany tak jak w języku, czy odrzucany.

Myślę, że najbardziej interesują cię maszyny skończone (zarówno deterministyczne, jak i deterministyczne), aby zobaczyć, jakie języki może zdecydować wyrażenie regularne, oraz lemat o pompowaniu, aby udowodnić, które języki nie są regularne.

Zasadniczo język nie jest normalny, jeśli potrzebuje jakiejś pamięci lub umiejętności liczenia. Język dopasowania nawiasów nie jest regularny, na przykład, ponieważ maszyna musi pamiętać, czy otworzyła nawias, aby wiedzieć, czy musi go zamknąć.

Językiem wszystkich ciągów znaków zawierających litery a i b, które zawierają co najmniej trzy b, jest język zwykły: a ba ba ba

Język wszystkich łańcuchów wykorzystujących litery a i b, które zawierają więcej b niż a, nie jest regularny.

Nie powinieneś też, aby wszystkie skończone języki były regularne, na przykład:

Język wszystkich łańcuchów krótszych niż 50 znaków, w których występują litery a i b, które zawierają więcej b niż a, jest regularny, ponieważ jest skończony, wiemy, że można go opisać jako (b | abb | bab | bba | aabbb | ababb |. ..) ect, aż zostaną wymienione wszystkie możliwe kombinacje.