Czy ktoś może podać prosty, ale nie zabawkowy przykład gramatyki kontekstowej?

12

Próbuję zrozumieć gramatyki kontekstowe.

Rozumiem, dlaczego języki lubią

$\{ww \mid w \in A^*\}$

$\{a^n b^n c^n \mid n\in\mathbb{N}\}$

nie są wolne od kontekstu, ale co chciałbym wiedzieć, jeśli język podobny do niepisanego rachunku lambda jest wrażliwy na kontekst.

Chciałbym zobaczyć przykład prostego, ale nie-zabawkowego (uważam powyższe przykłady zabawkowe), przykładu gramatyki kontekstowej, która może, dla niektórych reguł produkcji, np. Powiedzieć, czy jakiś ciąg symboli jest obecnie objęty zakresem (np. podczas tworzenia treści funkcji).

Czy gramatyki kontekstowe są wystarczająco mocne, aby uczynić niezdefiniowane / niezadeklarowane / niezwiązane zmienne błędem składniowym (a nie semantycznym)?

— BlueBomber
źródło

1

prawie wszystkie prawdziwe języki programowania są wrażliwe na kontekst (w ogólnym sensie, tj. łączą gramatykę chomsky'ego typu 0 i typu I w „wrażliwym na kontekst”). Na przykład zmienne muszą zostać zadeklarowane przed użyciem, identyfikatory powinny być unikalne, wszystkie wymagają kontekstu (zwane też kontekstem semantycznym, ale mogą wprowadzać w błąd) cs.purdue.edu/homes/hosking/502/notes/04-semantics.pdf

— Nikos M ,

Cóż, „kontekstowy” to standardowy termin dla gramatyki typu 1.

— reinierpost

8

Tak, uważam, że jest to możliwe, ale nie, nie jestem gotów wyraźnie skonstruować gramatyki kontekstowej. Wyjaśnię moją odpowiedź, dzieląc pytanie na dwie różne części.

(1) Jaki byłby nie-zabawkowy przykład? Powinien odzwierciedlać deklarację zmiennych. Moja propozycja takiego języka, wyabstrahowana z prawdziwego programowania, byłaby taka. Alfabet to . Ten język jest kontekstowy. $\{a,b,;,(,)\}$

{w_{1}; w_{2)}; \dots; w_{n} (x_{1}; x_{2)}; \dots; x_{m}) ∣ w_{ja}, x_{jot} \in {za, b}^{*}, każdy x_{jot} jest równy niektórym w_{ja}}

$\{ w_1;w_2;\dots;w_n(x_1;x_2;\dots;x_m) \mid w_i,x_j\in\{a,b\}^*, \mbox{ each }x_j\mbox{ is equal to some }w_i \}$

(2) Aby pokazać, że tak naprawdę jest kontekstowe, użyłbym innego formalizmu. Maszyna Turinga z liniowym wykorzystaniem taśmy: automat z ogranicznikiem liniowym LBA. Mogę zaprogramować, by dopasowywał wzór / rozważałbym kolejno każdy i próbował dopasować go do odpowiedniego , litera po literze. LBA są równoważne gramatyce kontekstowej, ale o wiele łatwiejsze do zaprogramowania. $x_j$ $w_j$

— Hendrik Jan
źródło

Dziękuję za post. Na razie mniej znam LBA, więc mniej przekonuje mnie punkt (2). W punkcie (1) staram się zobaczyć, jak konstruować reguły, które wygenerują, w których nazwa zmiennej jest oczekiwana jako wyrażenie, tylko jedna ze zmiennych w bieżącym zakresie. Nie muszę widzieć całego, formalnego CSG, ale zadziałałoby tylko nieformalne wyjaśnienie. Nie mogę sobie wyobrazić, jak to zrobić z nazwami zmiennych składających się z wielu symboli, co stanowi inne zastosowanie kontekstu niż np. Użycie pojedynczego kontekstu nieterminalnego do bezpośredniego uzgodnienia numeru podmiot-czasownik w pochodnej zdania w języku angielskim.

Z drugiej strony pochodzę z języka formalnego (a także nie jestem ojczystym językiem angielskim) i mam problem ze zrozumieniem tego, co dokładnie chcesz modelować / reprezentować. Przepraszam! W mojej wizji w tym kontekście jest npy tylko zabawkowym przykładem, ale jest częścią tego, co chcesz osiągnąć, mając pełne kopie tego samego łańcucha (nazwa zmiennej?)

{w w ∣ w \dots}

$\{ ww \mid w\dots\}$

— Hendrik Jan

Dziękuję za odpowiedź!. to zabawkowy przykład i rozumiem, dlaczego nie jest bezkontekstowy, ale nadal nie intuicyjnie „widzę”, jak jest kontekstowy lub jak wygeneruje go CSG. Pozwólcie, że wyjaśnię to, czego nie rozumiem (jest co najmniej jedno pytanie uzupełniające, ale na razie to wystarczy): Jak CSG może użyć kontekstu zawierającego słowa zawierające wiele symboli, aby wygenerować jedno z tych słów ponownie w określonym produkcja? Z tego, co widziałem, generalnie CSG działają poprzez zamianę znaków podczas produkcji i używanie pojedynczych symboli do kierowania produkcją, ale nie słów zawierających wiele symboli.

{w w | w . . .}

$\{ww | w ... \}$

3

O. To dość konkretne pytanie. Bez podania gramatyki dla mogę powiedzieć kilka rzeczy. Gramatyka ma dwa „symbole graniczne” - . Podczas wyprowadzania ciąg wygląda jak . wytwarza się z alfabetu wraz z kopią że będzie „przenieść” na listach w produkcje (technicznie, który jest monotonia gramatyki, odpowiednik CS). Kiedy „posłaniec” osiągnie , zapisuje kopię litery . W ten sposób można skopiować dłuższe ciągi (wiele symboli).

{w w}

$\{ ww \}$

L R

$LR$

L w R w

$LwRw$

L

$L$

a

$a$

M_{a}

$M_a$

w

$w$

M_{a} b \to b M_{a}

$M_ab \to bM_a$

R

$R$

M_{a} R \to R a

$M_aR \to Ra$

— Hendrik Jan

13

Moim ulubionym przykładem języka kontekstowego (CSL) jest SAT . Twierdzenie Landwebera-Kurody mówi, że CSL = NSPACE . Każda instancja SAT ma certyfikat wielkości liniowej, więc SAT jest CSL. Zobacz moje pytanie Gramatyka kontekstowa dla SAT? do referencji i dyskusji. $[n]$

Wiele innych języków NP-trudnych jest również w CSL z tego samego powodu, takich jak CLIQUE.

Istnieją również dość naturalne języki w CSL, które są jeszcze trudniejsze.

Jednak nie znam żadnego sposobu wyrażenia arbitralnej CSL jako gramatyki kontekstowej (CSG), innej niż użycie konstrukcji Landwebera w Twierdzeniu 3 jego pracy. W tej konstrukcji CSG opisuje odwrotność działania automatu ograniczonego liniowo, który rozpoznaje CSL. Produkcje CSG opisują, w jaki sposób określony stan maszyny wynika z jednego możliwego ruchu. Taki CSG jest prostym tłumaczeniem automatu na gramatykę, więc niekoniecznie będzie on odpowiadał cechom językowym, takim jak możliwość deklarowania zmiennych, ale zamiast tego zostanie ugrzęznięty przez szczegóły automatu.

Jeśli nalegasz na CSG, a nie CSL, i jeśli twoje rzeczywiste pytanie dotyczy konkretnie chęci zobaczenia CSG dla języka, który wymaga ograniczonego zakresu zmiennych, odpowiedź Hendrika Jana wydaje się być dobrym początkiem.

— András Salamon
źródło

9

Tak, gramatyki kontekstowe (CSG) mają wystarczającą moc, aby sprawdzać zmienne niezdefiniowane / niezadeklarowane / niezwiązane, ale niestety nie znamy żadnego skutecznego algorytmu do analizowania ciągów CSG.

Prawdziwym przykładem języka kontekstowego jest język programowania C. Funkcja taka jak najpierw zadeklaruj zmienne, a następnie użyj ich później, aby język C był językiem kontekstowym (CSL). ( Nie wiem o nietypowym rachunku lambda ).

A ponieważ nie znamy żadnego liniowego algorytmu analizy dla CSL (lub CSG). Dlatego w projektowaniu kompilatora używamy CFG (i tylko jego algorytmu analizującego) do sprawdzania składni, ponieważ znamy wydajne algorytmy do analizowania CFG (jeśli jest w ograniczonej formie). Kompilatory najpierw analizują funkcję bezkontekstową, a następnie problematycznie obsługują funkcje kontekstowe (na przykład sprawdzają każdą używaną zmienną w tabeli symboli, jeśli jest zdefiniowana. W przeciwnym razie generuje błąd).

Również gramatyka kontekstowa jest używana w przetwarzaniu języka naturalnego (NLP). A większość języków naturalnych to przykłady języków kontekstowych. (Nie jestem pewien języka sanskrytu ).

Spróbuję to wytłumaczyć głupim, ale prostym przykładem (to tylko pomysł, możesz to ulepszyć):

NOUN     -->  { BlueBomber, Grijesh, I, We}
TENSE    -->  { am, was, is, were}
VERB     -->  { going, eating, working}

SENTENCE --> <NOUN> <TENSE> <VERB>

Teraz, korzystając z tej gramatyki, możemy wygenerować kilka poprawnych instrukcji, ale niektóre też są błędne. Na przykład,

SENTENCE --> <NOUN>   <TENSE>   <VERB>
             Grijesh    is       working       [Correct statement]

Ale

             Grijesh    am       working       [wrong statement]

Powód: wartość <TENSE> zależy od wartości <NOUN> (na przykład I <TENNSE> --> I am), a zatem gramatyka nie generuje poprawnych instrukcji w języku angielskim.

W rzeczywistości nie możemy napisać gramatyki bezkontekstowej dla pełnego języka angielskiego!

_{Być może zauważyłeś, że żaden tłumacz języka naturalnego lub moduł sprawdzania gramatyki nie działa poprawnie (spróbuj użyć długich instrukcji). Ponieważ ten problem jest objęty kontekstowym algorytmem analizy.}

ODNIESIENIE : Możesz obejrzeć wykłady dr. Aruna Kumara . _{W pewnym wykładzie wyjaśnia dokładnie, czym jesteś zainteresowany.}

— Grijesh Chauhan
źródło

Dziękuję za informację, niewątpliwie będzie pomocna dla osób zainteresowanych tym samym tematem, ale tylko częściowo wiąże się z tym, o co chciałbym prosić. Nie zajmuję się analizowaniem ciągu generowanego przez CSG, ale aby zobaczyć prosty - nawet głupiutki - przykład formalnego CSG, który generuje dobrze uformowane abstrakcje (brak niezwiązanych zmiennych w ciele funkcji). Mogę sobie wyobrazić, że CSG generuje prawidłowe „angielskie” ciągi, ponieważ pojedynczy symbol może kierować zgodą podmiotu / czasownika, ale przy abstrakcjach zmienne zazwyczaj składają się z wielu symboli.

1

@BlueBomber: dzięki Na pewno odpowiem, Jego noc w Indiach..N Szczęśliwego nowego roku! :)

— Grijesh Chauhan,

Wydaje się, że mogę to zrobić tylko ograniczoną liczbę razy i zgodnie z (tym) [ meta.scicomp.stackexchange.com/questions/156/… powinienem usunąć to pytanie i opublikować je w bardziej odpowiednim miejscu ...

@BlueBomber Zgłoszono zmianę, możesz też zrobić.

— Grijesh Chauhan

1

(rozszerzenie komentarzy w odpowiedź)

W każdym razie nie jestem pewien, czy jest to przykład.

Prawie wszystkie prawdziwe języki programowania są wrażliwe na kontekst (w ogólnym sensie, tj. Łączą gramatykę Chomsky'ego typu 0 i typu I z „wrażliwą na kontekst”, co oczywiście jest prawdą, ponieważ nieograniczone gramatyki są jeszcze bardziej wrażliwe na kontekst niż kontekst gramatyki wrażliwe ).

Na przykład „zmienne muszą zostać zadeklarowane przed użyciem”, „identyfikatory powinny być unikalne”, wszystkie one wymagają kontekstu (czasem określanego jako kontekst semantyczny, ale może to być mylące, ponieważ i tak obejmuje funkcje składniowe) patrz np. Https: // www .cs.purdue.edu / homes / hosking / 502 / notes / 04-semantics.pdf

Poczucie, że powyższe przykłady są kontekstowe (zarówno w sensie gramatycznym / syntaktycznym, jak i semantycznym) wynika z tego, że mówią o swoim kontekście (co poprzedza lub następuje).

„Zmienna już zdefiniowana” dotyczy kontekstu poprzedzającego , zastosowania zmiennej. „Unikalny identyfikator” jest kontekstem zarówno tego, co poprzedza deklarację identyfikatora, jak i następuje po niej, itd.

zobacz także Czy JavaScript jest językiem bezkontekstowym? Na tak

— Nikos M.
źródło

„Kontekstowy” oznacza typ 1.

— reinierpost