Grammaire récursive - Recursive grammar

En informatique , une grammaire est appelée de manière informelle une grammaire récursive si elle contient des règles de production qui sont récursives , ce qui signifie que développer un non-terminal selon ces règles peut éventuellement conduire à une chaîne qui inclut à nouveau le même non-terminal. Sinon, cela s'appelle une grammaire non récursive .

Par exemple, une grammaire pour un langage sans contexte est laissée récursive s'il existe un symbole non terminal A qui peut être soumis aux règles de production pour produire une chaîne avec A (comme symbole le plus à gauche). Tous les types de grammaires de la hiérarchie Chomsky peuvent être récursifs et c'est la récursivité qui permet la production d'ensembles infinis de mots.

Propriétés

Une grammaire non récursive ne peut produire qu'un langage fini; et chaque langue finie peut être produite par une grammaire non récursive. Par exemple, une grammaire linéaire ne produit qu'un seul mot.

Une grammaire récursive sans contexte qui ne contient aucune règle inutile produit nécessairement un langage infini. Cette propriété constitue la base d'un algorithme qui peut tester efficacement si une grammaire sans contexte produit un langage fini ou infini.

Les références