Próbuję zrozumieć gramatyki kontekstowe.
Rozumiem, dlaczego języki lubią
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)?
Odpowiedzi:
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.{ w 1 ; w 2 ; … ; w n ( x 1 ; x 2 ; … ; x m ) ∣ w i , x j ∈ { a , b } ∗ , każdy x j jest równy pewnemu w i }{ , B , ; , ( , ) }
(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.w jxjot wjot
źródło
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.
źródło
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ć):
Teraz, korzystając z tej gramatyki, możemy wygenerować kilka poprawnych instrukcji, ale niektóre też są błędne. Na przykład,
Ale
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.
źródło
(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
źródło