Qu'est-ce qu'un cas d'utilisation réel de l'utilisation d'une grammaire Chomsky Type-I (contextuelle)

9

Je me suis amusé récemment à explorer le développement des analyseurs de langage dans le contexte de leur intégration dans la hiérarchie de Chomsky.

Qu'est-ce qu'un bon exemple concret (c'est-à-dire non théorique) d'une grammaire contextuelle?

language-design parsing grammar Plie d'Evan
la source
8
Le langage de programmation compte-t-il?
Martin York
@LokiAstari Bien sûr.
Evan Plaice
2
Je suppose que les langages de programmation comptent, mais ne constituent pas une bonne solution, car la complexité de la sensibilité au contexte est normalement remplacée par une grammaire sans contexte avec une analyse sémantique.
Frank
@Frank Je suppose que mon problème est que je ne peux pas vraiment comprendre ce qu'est un langage contextuel sans l'appliquer à une utilisation réelle.
Evan Plaice
Il existe certaines langues humaines qui peuvent ne pas nécessiter d'analyseurs de langage récursivement énumérables et tombent donc dans l'ensemble de langues de type 1 (sensible au contexte). cs.virginia.edu/~evans/cs3102/?p=138

Réponses:

9

Bonne question. Bien que, comme mentionné dans les commentaires, de nombreux langages de programmation soient sensibles au contexte, cette sensibilité au contexte n'est souvent pas résolue dans la phase d'analyse mais dans les phases ultérieures - c'est-à-dire qu'un sur-ensemble du langage est analysé à l'aide d'une grammaire sans contexte, et certains de ces arbres d'analyse sont ensuite filtrés.

Cependant, cela ne signifie pas que ces langues ne sont pas contextuelles , voici donc quelques exemples:

Haskell vous permet de définir des fonctions qui sont utilisées comme opérateurs, ainsi que de définir la priorité et l'associativité de ces opérateurs. En d'autres termes, vous ne pouvez pas créer l'arborescence d'analyse correcte pour une expression d'opérateur comme:

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

sauf si vous avez déjà analysé les déclarations de priorité / associativité pour @@et ##:

infixr 8 @@
infixr 6 ##

Un deuxième exemple est le Bencode , un langage de données qui préfixe le contenu avec sa longueur:

<length>:<contents>

Le problème avec ce format est qu'il est à peu près impossible d'analyser sans quelque chose de contextuel, car la seule façon de déterminer les tailles de "champ" est de ... analyser la chaîne.

Un troisième exemple est XML, en supposant que les noms de balises arbitraires sont autorisés: les noms de balises d'ouverture doivent avoir des balises de fermeture correspondantes:

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

la source
Intéressant. Je connaissais XML. Je soupçonne que le lecteur derrière la spécification XHTML 1.0 devait s'éloigner des interpréteurs HTML en «mode excentrique» qui prennent en charge les exceptions contextuelles à un XML sans contexte plus propre.
Evan Plaice
@EvanPlaice Je suis confus par votre commentaire - "clean XML" est contextuel comme je l'ai montré dans mon exemple.
4
@MattFenwick Je pense que votre exemple XML ne montre pas la vraie raison pour laquelle XML n'est pas sans contexte. La raison en est que les noms de balises arbitraires sont autorisés. Si seul un ensemble spécifique de balises était autorisé, XML serait sans contexte.
Honza Brabec
@HonzaBrabec vous avez raison - j'ai implicitement supposé que les noms de balises arbitraires étaient autorisés. J'aurais dû énoncer explicitement cette hypothèse. Merci d'avoir fait remarquer cela!
3

Pour autant que je sache, les grammaires contextuelles sont utilisées uniquement dans le traitement du langage naturel . Les interprètes et les compilateurs de langages de programmation n'essaient pas d'analyser une grammaire sans contexte à cause de la complexité (même si une tentative a été faite dans le passé).

Peut-être, vous pouvez trouver un exemple d'utilisation réelle dans l'une de ces bibliothèques:

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
la source
2
Qu'en est-il du «mode excentrique» HTML et des préprocesseurs de code, ne compteraient-ils pas?
Evan Plaice
2

Des grammaires sensibles au contexte sont parfois utilisées dans les descriptions de la sémantique des langages de programmation. L'utilisation la plus complète des grammaires contextuelles était peut-être la définition du langage Algol68. Il a utilisé une grammaire sans contexte à deux niveaux (voir http://en.wikipedia.org/wiki/Two-level_grammar ) pour décrire à la fois la syntaxe et la sémantique des programmes Algol68.

Un couple de mes collègues a utilisé la grammaire van Wijngaarden pour diriger leur implémentation d'Algol68 (voir http://en.wikipedia.org/wiki/FLACC ).

BobDalgleish
la source