Grammaires sans contexte versus grammaires sensibles au contexte?

Un détail important ici est que les grammaires ne sont pas accepter chaînes; ils création chaînes. Les grammaires sont des descriptions de langues qui fournissent un moyen de générer toutes les chaînes possibles contenues dans la langue. Pour indiquer si une chaîne particulière est contenue dans la langue, vous utiliserez un reconnaissance, une sorte d'automate qui traite d'une chaîne donnée et dit "oui" ou "non."

libre de tout contexte grammaire (CFG) est une grammaire où (comme vous l'avez noté) chaque production a la forme a → w, où A est un non-terminal et w est une chaîne de terminaux et de non-terminaux. Officieusement, un CFG est une grammaire où n'importe quel nonterminal peut être étendu à n'importe quelle de ses productions à n'importe quel moment. La langue d'une grammaire est l'ensemble des chaînes de terminaux qui peuvent être dérivés du symbole de départ.

-sensible grammaire (CSG) est une grammaire où chaque la production a la forme wAx → wyx, où w et x sont des chaînes de terminaux et non-terminaux et y est également une chaîne de terminaux. En d'autres termes, les productions donnent des règles disant "Si vous voyez un dans un contexte donné, vous pouvez remplacer A par la chaîne y." Il est regrettable que ces grammaires soient appelées "grammaires sensibles au contexte" parce que cela signifie que "sans contexte" et" sensibles au contexte " ne sont pas opposés, et cela signifie qu'il y a certaines classes de grammaires qui pourraient être tenir compte d'un grand nombre d'informations contextuelles, mais qui ne sont pas officiellement considérées comme sensibles au contexte.

pour déterminer si une chaîne est contenue dans un CFG ou un CSG, il y a plusieurs approches. Tout d'abord, vous pourriez construire un reconnaisseur pour la grammaire donnée. Pour CFGs, le automate à pile (PDA) est un type d'automate qui accepte précisément les langues sans contexte, et il existe une construction simple pour transformer n'importe quel CFG en PDA. Pour l' sensible au contexte des grammaires, l'automate vous utilisez est appelé linéaire bornée automate (LBA).

cependant, ces approches, si elles sont traitées naïvement, ne sont pas très efficaces. Pour déterminer si une chaîne est contenue dans le langage D'un CFG, il existe des algorithmes beaucoup plus efficaces. Par exemple, beaucoup de grammaires peuvent avoir LL (k) ou LR (k) analyseurs construit pour eux, ce qui vous permet (en temps linéaire) décider si une chaîne est contenue dans la grammaire. Toutes les grammaires peuvent être interprétées en utilisant le Earley l'analyseur, qui en O (n ³) peut déterminer si une chaîne de longueur n est contenue dans la grammaire (il est intéressant de noter qu'elle peut analyser N'importe quel CFG non ambigu en O(n²), et avec lookaheads peuvent Parser n'importe quelle LR(k) grammaire dans O(n) temps!). Si vous étiez purement intéressé par la question "la chaîne x est-elle contenue dans la langue générée par grammar G?"puis l'un de ces les approches seraient excellentes. Si vous voulez savoir comment la chaîne x a été générée (en trouvant un arbre d'analyse), vous pouvez adapter ces approches pour fournir également cette information. Cependant, l'analyse des CSG est, en général, PSPACE-complète, de sorte qu'il n'y a pas d'algorithmes connus d'analyse des CSG qui fonctionnent dans le pire des cas de temps polynomial. Il y a cependant certains algorithmes qui, dans la pratique, ont tendance à fonctionner rapidement. Les auteurs de Techniques D'Analyse: Un Guide Pratique (voir ci-dessous) ont mis ensemble une page fantastique contenant toutes sortes d'algorithmes d'analyse, dont un qui analyse les langages sensibles au contexte.

si vous êtes intéressé à en apprendre davantage sur l'analyse, pensez à vérifier l'excellent livre"L'Analyse Des Techniques: Un Guide Pratique, Deuxième Édition " par Grune et Jacobs, qui traite de toutes sortes d'algorithmes d'analyse pour déterminer si une chaîne est contenue dans une grammaire et, si oui, comment elle est généré par l'algorithme d'analyse.

Espérons que cette aide!

Comme l'a dit avant, une Grammaire n'accepte pas une chaîne, mais c'est simplement un moyen pour générer des mots spécifiques d'une Langue que vous analysez. En fait, la grammaire comme règle générative dans la théorie du langage formel à la place de l'automate d'état fini font ce que vous dites, la reconnaissance de chaînes spécifiques. En particulier, vous avez besoin d'un automate énumérable récursif pour reconnaître les langues de Type 1( les langues sensibles au contexte dans la hiérarchie de Chomsky ). Une grammaire pour un la langue spécifique ne vous accorde que le droit de spécifier la propriété de toutes les chaînes qui s'assemblent à l'ensemble des chaînes de la langue CS. J'espère que mon explication a été claire.

Un moyen facile de montrer qu'une grammaire accepte une chaîne de caractères est de montrer les règles de production de cette chaîne.