Qu'est-ce qu'une grammaire sans contexte ?

Question

Quelqu'un peut-il m'expliquer ce qu'est une grammaire sans contexte ? Après avoir consulté l'entrée Wikipédia, puis l'entrée Wikipédia sur la grammaire formelle, je suis complètement et totalement déconcerté. Quelqu'un pourrait-il avoir l'amabilité de m'expliquer ce que sont ces choses ?

Je me pose cette question car je souhaite étudier l'analyse syntaxique, et aussi, en parallèle, les limites d'un moteur de regex.

Je ne sais pas si ces termes sont directement liés à la programmation ou s'ils relèvent plutôt de la linguistique en général. Si c'est le cas, je m'en excuse, peut-être cela pourrait-il être déplacé si c'est le cas ?

Answer 1

Une grammaire libre de contexte est une grammaire qui satisfait à certaines propriétés. En informatique, les grammaires décrivent des langages ; plus précisément, elles décrivent des langages formels.

Un langage formel n'est qu'un ensemble (terme mathématique désignant une collection d'objets) de chaînes (séquences de symboles... très similaire à l'utilisation du mot "chaîne" en programmation). Un exemple simple de langage formel est l'ensemble de toutes les chaînes binaires de longueur trois, {000, 001, 010, 011, 100, 101, 110, 111}.

Les grammaires fonctionnent en définissant les transformations que vous pouvez effectuer pour construire une chaîne de caractères dans le langage décrit par une grammaire. Les grammaires indiquent comment transformer un symbole de départ (généralement S) en une chaîne de symboles. Une grammaire pour le langage donné précédemment est la suivante :

S -> BBB
B -> 0
B -> 1

La façon d'interpréter cela est de dire que S peut être remplacée par BBB y B peut être remplacé par 0, et B peut être remplacé par 1. Ainsi, pour construire la chaîne 010, nous pouvons faire S -> BBB -> 0BB -> 01B -> 010 .

Une grammaire sans contexte est simplement une grammaire dans laquelle la chose que vous remplacez (à gauche de la flèche) est un seul symbole "non terminal". Un symbole non terminal est un symbole que vous utilisez dans la grammaire et qui ne peut pas apparaître dans vos chaînes finales. Dans la grammaire ci-dessus, "S" et "B" sont des symboles non terminaux, et "0" et "1" sont des symboles "terminaux". Les grammaires comme

S -> AB
AB -> 1
A -> AA
B -> 0

ne sont pas libres de contexte puisqu'ils contiennent des règles telles que AB -> 1 qui ont plus d'un symbole non terminal à gauche.

Answer 2

La théorie du langage est liée à la théorie de l'informatique. Il s'agit de l'aspect plus philosophique de l'informatique, qui consiste à décider quels programmes sont possibles, ou seront jamais possibles à écrire, et quel type de problèmes il est impossible d'écrire un algorithme pour les résoudre.

Une expression régulière est une façon de décrire un langage régulier. Un langage régulier est un langage qui peut être déterminé par un automate fini déterministe.

Vous devriez lire l'article sur les machines à états finis : http://en.wikipedia.org/wiki/Finite_state_machine

Et les langues régulières : http://en.wikipedia.org/wiki/Regular_language

Toutes les langues régulières sont des langues sans contexte, mais il existe des langues sans contexte qui ne sont pas régulières. Un langage sans contexte est l'ensemble de toutes les chaînes de caractères acceptées par un grammaire sans contexte ou une automate Pushdown qui est une machine à états finis avec une seule pile : http://en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_Context-free_Languages

Il existe des langages plus compliqués qui nécessitent une machine de Turing (tout programme possible que vous pouvez écrire sur votre ordinateur) pour décider si une chaîne de caractères est dans le langage ou non.

La théorie des langages est également très liée au problème P vs. NP, ainsi qu'à d'autres questions intéressantes.

Mon livre d'introduction à l'informatique de troisième année expliquait assez bien ce genre de choses : Introduction à la théorie de l'informatique. Par Michael Sipser. Mais il m'a coûté environ 160 dollars à l'achat et il n'est pas très grand. Peut-être que tu peux trouver un exemplaire d'occasion ou un exemplaire dans une bibliothèque ou quelque chose comme ça, ça pourrait t'aider.

EDIT :

Les limites des expressions régulières et des classes de langage supérieures ont fait l'objet de nombreuses recherches au cours des 50 dernières années environ. Vous pourriez être intéressé par le lemme de pompage pour les langages réguliers. Il s'agit d'un moyen de prouver qu'un certain langage n'est pas régulier :

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

Si un langage n'est pas régulier, il peut être sans contexte, ce qui signifie qu'il peut être décrit par une grammaire sans contexte, ou il peut même appartenir à une classe de langage supérieure. Vous pouvez prouver qu'il n'est pas sans contexte à l'aide du lemme de pompage pour les langages sans contexte, qui est similaire à celui des expressions régulières.

Un langage peut même être indécidable, ce qui signifie que même une machine de Turing (programme que votre ordinateur peut exécuter) ne peut être programmée pour décider si une chaîne de caractères doit être acceptée comme faisant partie du langage ou rejetée.

Je pense que la partie qui vous intéresse le plus est la machine à états finis (à la fois déterministe et déterministe) pour voir quels langages une expression régulière peut décider, et le lemme de pompage pour prouver quels langages ne sont pas réguliers.

En fait, une langue n'est pas régulière si elle a besoin d'une certaine forme de mémoire ou de capacité à compter. Le langage des parenthèses correspondantes n'est pas régulier, par exemple, parce que la machine doit se souvenir si elle a ouvert une parenthèse pour savoir si elle doit en fermer une.

Le langage de toutes les chaînes utilisant les lettres a et b et contenant au moins trois b est un langage régulier : a ba ba ba

Le langage de toutes les chaînes utilisant les lettres a et b et contenant plus de b que de a n'est pas régulier.

Il ne faut pas non plus croire que tous les langages finis sont réguliers, par exemple :

Le langage de toutes les chaînes de moins de 50 caractères utilisant les lettres a et b et contenant plus de b que de a est régulier, puisqu'il est fini, nous savons qu'il pourrait être décrit comme (b|abb|bab|bba|aabbb|abb|...) ect jusqu'à ce que toutes les combinaisons possibles soient répertoriées.