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

Question

Próbuję zrozumieć kontekstowych gramatyk, i rozumiem dlaczego języki jak

1. {WW | w jest ciągiem}
2. {a ⁿ b ⁿ c ⁿ | a, b, c są symbolami}

kontekst nie są wolne, ale to, co chciałbym wiedzieć, czy to język podobny do rachunku bez typu lambda jest kontekstowa. Chciałbym zobaczyć przykład prostego, ale nie-zabawki (uważam powyższe przykłady zabawek), przykład gramatyki kontekstowej, która może, dla niektórych reguł produkcji, np. Powiedzieć, czy jakiś ciąg symboli jest obecnie w zasięgu (np. przy tworzeniu bryły funkcji). Czy gramatyki kontekstowe są na tyle potężne, że niezdefiniowane/niezadeklarowane/zmienne nie są błędami składniowymi (a nie semantycznymi)?

Answer 1

Tak, gramatyki kontekstowe (CSG) są na tyle potężne, że sprawdzają niezdefiniowane/niezadeklarowane/niezwiązane zmienne, ale niestety nie znamy żadnego wydajnego algorytmu do analizy ciągów CSG.

Prawdziwym przykładem języka kontekstowego jest język programowania C. Funkcja, taka jak zadeklaruj zmienne jako pierwsza, a następnie użyj ich później, uczyń język w języku C context-sensitive language (CSL). (Nie wiem o nieoptymowanym rachunku lambda).

A ponieważ nie znamy żadnego algorytmu analizy liniowej dla CSL (lub CSG). To jest powód, dla którego projektujemy kompilator, używamy CFG (i jego algorytmu parsowania) tylko do sprawdzania składni, ponieważ znamy wydajne algorytmy analizowania CFG (jeśli jest w ograniczonej formie). Kompilatory najpierw analizują funkcję bez kontekstu, a następnie w sposób problematyczny obsługują funkcje kontekstowe (na przykład sprawdzają każdą użytą zmienną w tabeli symboli, jeśli jest ona zdefiniowana, w przeciwnym razie generuje błąd).

Gramatura kontekstowa jest również używana w natural-language processing (NLP). Większość języków naturalnych to przykłady języków kontekstowych. (Nie jestem pewien co do języka Sanskrit).

postaram się wytłumaczyć z głupie ale prosty przykład (jest to tylko pomysł, można go ulepszyć):

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

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

Teraz, przy użyciu tej gramatyki, możemy wygenerować kilka poprawnych wypowiedzi, ale niektóre też są złe. Na przykład,

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

Ale

   Grijesh am  working  [wrong statement] 

Powód: wartość < napięta> zależy wartość < rzeczownik> (na przykład I <TENSE> --> I am) i stąd gramatyka nie generuje odpowiednie sprawozdania w Język angielski.

Właściwie nie możemy napisać gramatyki bezkontekstowej dla pełnego angielskiego!

_{Być może zauważyłeś, że każdy translator języka naturalnego lub moduł sprawdzania poprawności gramatycznej nie działa poprawnie (spróbuj z długimi instrukcjami).Ponieważ ten problem jest objęty kontekstowym algorytmem analizy.}

---

mającej: Można oglądać Dr. Arun Kumar's lectures. _{W pewnym wykładzie wyjaśnia dokładnie, czym jesteś zainteresowany.}