Jaki jest rzeczywisty przypadek użycia gramatyki Chomsky'ego typu I (kontekstowej)

Ostatnio dobrze się bawiłem, badając rozwój parserów językowych w kontekście ich dopasowania do hierarchii Chomsky'ego.

Jaki jest dobry (nie teoretyczny) przykład gramatyki kontekstowej?

language-design parsing grammar Evan Plaice
źródło

Czy język programowania się liczy?

Martin York,

@LokiAstari Oczywiście.

Evan Plaice,

Wydaje mi się, że języki programowania się liczą, ale nie stanowią dobrego rozwiązania, ponieważ złożoność wrażliwości na kontekst jest zwykle zastępowana gramatyką bezkontekstową z analizą semantyczną.

Frank

@Frank Wydaje mi się, że moim problemem jest to, że tak naprawdę nie potrafię zrozumieć, czym są języki kontekstowe bez zastosowania ich w niektórych rzeczywistych zastosowaniach.

Evan Plaice,

Istnieje kilka języków ludzkich, które mogą nie wymagać rekurencyjnie wyliczalnych analizatorów składni języka, a zatem należą do zestawu języków typu 1 (wrażliwy na kontekst). cs.virginia.edu/~evans/cs3102/?p=138

Odpowiedzi:

Dobre pytanie. Chociaż, jak wspomniano w komentarzach, wiele języków programowania jest wrażliwych na kontekst, jednak wrażliwość na kontekst często nie jest rozwiązywana w fazie analizowania, ale w późniejszych fazach - to znaczy, nadzbiór języka jest analizowany przy użyciu gramatyki bezkontekstowej, a niektóre z tych drzew są później filtrowane.

Nie oznacza to jednak, że te języki nie uwzględniają kontekstu , dlatego oto kilka przykładów:

Haskell pozwala definiować funkcje używane jako operatory, a także określać priorytet i asocjatywność tych operatorów. Innymi słowy, nie można zbudować poprawnego drzewa analizy dla wyrażenia operatora, takiego jak:

a @@ b @@ c ## d ## e

chyba że już przeanalizowałeś deklaracje pierwszeństwa / asocjatywności dla @@i ##:

infixr 8 @@
infixr 6 ##

Drugim przykładem jest Bencode , język danych, który poprzedza treść swoją długością:

<length>:<contents>

Problem z tym formatem polega na tym, że prawie niemożliwe jest parsowanie bez czegoś kontekstowego, ponieważ jedynym sposobem na określenie rozmiarów „pola” jest ... parsowanie łańcucha.

Trzecim przykładem jest XML, zakładając, że dowolne nazwy znaczników są dozwolone: nazwy znaczników otwierających muszą mieć pasujące znaczniki zamknięcia:

<hi>
 <bye>
 the closing tag has to match bye
 </bye>
</hi> <!-- has to match "hi" -->

źródło

Ciekawy. Wiedziałem o XML. Podejrzewam, że napędem specyfikacji XHTML 1.0 było odejście od interpreterów HTML w „dziwacznych trybach”, które obsługują kontekstowe wyjątki od czystszego bezkontekstowego XML.

Evan Plaice,

@EvanPlaice Jestem zdezorientowany twoim komentarzem - „czysty XML” jest zależny od kontekstu, jak pokazałem w moim przykładzie.

@MattFenwick Myślę, że twój przykład XML nie pokazuje prawdziwego powodu, dla którego XML nie jest pozbawiony kontekstu. Powodem jest to, że dozwolone są dowolne nazwy znaczników. Gdyby dozwolony był tylko określony zestaw tagów, XML byłby pozbawiony kontekstu.

Honza Brabec

@HonzaBrabec masz rację - domyślnie założyłem, że dozwolone są dowolne nazwy znaczników. Powinienem był wyraźnie stwierdzić to założenie. Dziękujemy za zwrócenie na to uwagi!

Tak długo, jak wiem, Gramatyki kontekstowe są wykorzystywane w przetwarzaniu języka naturalnego, tylko . Tłumacze języków programowania i kompilatory nie próbują analizować gramatyki bezkontekstowej ze względu na złożoność (nawet jeśli w przeszłości podjęto jakąś próbę).

Może znajdziesz przykład rzeczywistego wykorzystania w jednej z tych bibliotek:

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

http://opennlp.sourceforge.net/projects.html

http://nltk.org/

http://nlp.stanford.edu/nlp/javadoc/javanlp/

AlexBottoni
źródło

A co z „trybem dziwactwa” HTML i preprocesorami kodu, nie liczą się?

Evan Plaice,

Gramatyki wrażliwe na kontekst są czasami używane w opisach semantyki języka programowania. Być może najbardziej wszechstronnym zastosowaniem gramatyk kontekstowych była definicja języka Algol68. Używał dwupoziomowego, wolnego od kontekstu gramatyka (patrz http://en.wikipedia.org/wiki/Two-level_grammar ) do opisania zarówno składni, jak i semantyki programów Algol68.

Kilku moich kolegów używało gramatyki van Wijngaarden do kierowania ich implementacją Algol68 (patrz http://en.wikipedia.org/wiki/FLACC ).

BobDalgleish
źródło