Grammaire non contextuelle

En linguistique et en informatique, une grammaire non contextuelle, grammaire hors-contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de production (ou simplement production) est de la forme

$X\to w$

où $X$ est un symbole non terminal et $w$ est une chaîne composée de terminaux et/ou de non-terminaux. Le terme « non contextuel » provient du fait qu'un non terminal $X$ peut être remplacé par $w$ , sans tenir compte du contexte où il apparaît. Un langage formel est non contextuel (ou hors-contexte, ou encore algébrique) s'il existe une grammaire non contextuelle qui l'engendre.

Les grammaires algébriques sont suffisamment puissantes pour décrire la partie principale de la syntaxe de la plupart des langages de programmation, avec au besoin quelques extensions ; la syntaxe de la majorité des langages de programmation est en général spécifiée à l'aide de grammaires non contextuelles. On doit y ajouter des contraintes sémantiques par d'autres méthodes.

Les grammaires algébriques sont suffisamment simples pour permettre la création d'analyseurs syntaxiques efficaces (contrairement aux grammaires contextuelles). Un tel analyseur a pour tâche de déterminer, pour une chaîne donnée, si et comment elle peut être engendrée à partir de la grammaire. L'analyseur d'Earley est un exemple d'un tel algorithme. Les analyseurs LR et les analyseurs LL opèrent en temps linéaire, et sont employés dans la pratique. En revanche, ils ne permettent d'analyser que des familles plus restrictives de grammaires algébriques.

La forme normale de Backus (Backus Naur form) est la notation la plus communément utilisée pour décrire une grammaire non contextuelle décrivant un langage de programmation.

Définition

Une grammaire algébrique $G$ est composée

d'un alphabet fini $V$ de symboles non terminaux ou variables
d'un alphabet fini $A$ , disjoint de $V$ , de symboles terminaux ou lettres terminales
d'un élément $S$ de $V$ appelé l'axiome
d'un ensemble fini $\mathcal {P}\subset V\times (V\cup A)^*$ de règles de dérivations ou productions.

Une règle $(X,\alpha)\,$ est en général écrite sous la forme $X\to\alpha$ . La variable $X$ et le mot $α$ sont appelés respectivement le membre gauche et le membre droit de la règle. On étend cette notation et on écrit $u\to v$ lorsque $v$ résulte de $u$ par le remplacement, dans $u$ , d'un membre gauche de règle (qui est donc une variable) par son membre droit, donc s'il existe des mots $x, y$ et une règle $X\to\alpha$ telle que $u = x X y$ et $v = x α y$ . On note $\xrightarrow*$ la fermeture réflexive et transitive de cette relation. Lorsque $u\xrightarrow* v$ , on dit que $u$ dérive en $v$ .

Le langage engendré par la grammaire $G$ , noté $L (G)$ , est l'ensemble des mots terminaux (ne contenant plus de variables) qui dérivent de l'axiome $S$ , soit

$L(G)=\{w\in A^*\mid S\xrightarrow*w\}.$

Exemples

Exemple 1

Voici une grammaire algébrique simple :

$S \to aSb \mid\varepsilon$

La barre verticale sert à grouper les règles qui on le même symbole non terminal en membre gauche, et $ε$ dénote le mot vide. Cette grammaire engendre le langage : $\{ a^n b^n \mid n \ge 0 \}$ qui n'est pas un langage rationnel.

Exemple 2

Voici une grammaire algébrique qui engendre les expressions arithmétiques en trois variables $x$ , $y$ et $z$ , correctement parenthésées :

$S \to x \mid y \mid z \mid S + S \mid S - S \mid S * S \mid S/S \mid (S)$

Cette grammaire peut par exemple engendrer $(x + y) * x - z * y / (x + x)$ .

Exemple 3

La grammaire suivante engendre le langage composé des mots en $a$ et en $b$ , et dont le nombre de $a$ est différent du nombre de $b$ :

$S \to U \mid V$

$U \to TaU \mid TaT$

$V \to TbV \mid TbT$

$T \to aTbT \mid bTaT \mid \varepsilon$

$T$ produit les mots ayant le même nombre de $a$ et de $b$ , $U$ produit les mots avec plus de $a$ que de $b$ , et $V$ produit les mots ayant moins de $a$ que de $b$ .

Exemple 4

Les langages de Dyck ou langages de parenthésages corrects sont des langages algébriques.

Un autre exemple

Les grammaires non contextuelles ne sont pas limitées aux langages formels en mathématiques. Le linguiste indien Pānini décrivit le sanskrit avec une grammaire non contextuelle.

Dérivations et arbres de dérivation

Il existe deux manières de décrire comment un mot a été engendré à partir d'une grammaire donnée, la première consiste à lister la suite des applications des règles, la deuxième synthétise cette liste en un arbre, appelé arbre de dérivation.

La première méthode liste la suite des mots (en commençant par le symbole de départ, l'axiome, et en finissant par le mot recherché). Les mots intermédiaires, contenant des variables, sont parfois appelés proto-phrases (sentential forms en anglais) ou mot du langage étendu. En plus de ces mots, on liste les règles appliquées pour passer d'un mot au suivant. Si de plus on utilise la stratégie consistant à « toujours remplacer le non-terminal le plus à gauche », alors il suffit en fait de donner la liste des règles appliquées. La dérivation obtenue s'appelle une dérivation gauche du mot. Par exemple, pour la grammaire suivante :

$(1)\quad S \to S + S$

$(2)\quad S\to a$

la chaîne « $a + a + a$ » admet une dérivation gauche représentée par la liste [ (1), (1), (2), (2), (2) ]. De manière analogue, une dérivation droite est la liste des règles employées lorsque l'on remplace systématiquement le non-terminal le plus à droite en premier. Dans l'exemple précédent, une dérivation droite est [ (1), (2), (1), (2), (2)].

La distinction entre dérivation gauche et dérivation droite est importante en pratique car elle permet dans la plupart des analyseurs syntaxiques de tenir compte des priorités des opérations. Les analyseurs LL produisent des dérivations gauches, et les analyseurs LR des dérivations droite (en fait des réductions, c'est-à-dire déterminent d'abord la dernière règle appliquée).

Une dérivation impose de plus une structure hiérarchique de la chaîne dérivée. La structure de la chaîne « a + a + a », par exemple, est, pour une dérivation gauche :

S→S+S (1)

S→S+S+S (1)

S→a+S+S (2)

S→a+a+S (2)

S→a+a+a (2)

{ { { a }_S + { a }_S }_S + { a }_S }_S

où { ... }_S indique une sous-chaîne reconnue comme appartenant à S. Cette hiérarchie peut aussi être vue comme un arbre :

           S
          /|\
         / | \
        /  |  \
       S   +   S
      /|\      |
     / | \     |
    S  +  S    a 
    |     |
    a     a

Cet arbre est appelé arbre de dérivation, arbre d'analyse ou arbre de syntaxe concrète (en opposition à l'arbre syntaxique abstrait) de la chaîne. La dérivation gauche présentée plus haut et la dérivation droite définissent le même arbre de dérivation. Ceci est normal car les deux dérivations sont deux parcours en profondeur de l'arbre de dérivation, le premier obtenu en choisissant le nœud le plus à gauche, le deuxième en choisissant le nœud le plus à droite. Il y a bijection entre les dérivations gauches et les dérivations droites.

Dans notre exemple, il y a une autre dérivation gauche possible

S→ S + S (1)

S→ a + S (2)

S→ a + S + S (1)

S→ a + a + S (2)

S→ a + a + a (2)

qui définit l'arbre syntaxique suivant :

           S 
          /|\
         / | \
        /  |  \
       S   +   S
       |      /|\
       |     / | \
       a    S  +  S
            |     |
            a     a

Une grammaire est ambiguë lorsque au moins un mot engendré par la grammaire possède au moins deux arbres de dérivation distincts, sinon, c'est une grammaire inambiguë ou non ambiguë. Un langage est inambigu ou non ambigu s'il possède une grammaire inambiguë. Il est appelé inhéremment ambigu si toutes les grammaires qui l'engendrent sont ambiguës.

Un exemple de langage inhéremment ambigu est le langage:

$\{a^nb^nc^m\mid n,m\ge0\}\cup\{a^nb^mc^m\mid n,m\ge0\}$

Dans toutes les grammaires, les mots $a n b n c n$ ont deux dérivations distinctes. La preuve se fait au moyen du lemme d'Ogden.

Dans l'analyse syntaxique de mots engendrés par une grammaire ambiguë, il faut faire usage de techniques d'analyse non-déterministe et/ou de techniques adaptées (backtracking, règles de désambiguïsation,...)

Formes normales

Un langage algébrique peut être engendré par des grammaires algébriques de formes variées. Deux grammaires sont dites équivalentes lorsqu'elles engendrent le même langage.

Grammaire réduite et propre

Une grammaire réduite est une grammaire où toute variable est utile, c'est-à-dire figure dans au moins une dérivation d'un mot du langage. On peut toujours réduire une grammaire, c'est-à-dire supprimer, de manière effective, les variables inutiles.
Une grammaire est propre lorsque aucun membre droit de règle n'est égal au mot vide ou à une variable. On peut rendre une grammaire propre, à condition que le langage engendré ne contient pas le mot vide, ou alors autoriser la seule $ε$ -règle $S\to\varepsilon$ , où $S$ est l'axiome, avec la condition supplémentaire que $S$ ne figure dans aucun membre droit de règle.

Forme normale de Chomsky

Une grammaire est en forme normale de Chomsky si toutes ses règles sont de l'une des trois formes

$X\to YZ$

$X\to a$

où $X, Y, Z$ sont des variables, et $a$ est une lettre. Toute grammaire peut être mise en forme normale de Chomsky, au mot vide près. Cette forme normale sert par exemple dans la définition d'un algorithme d'analyse syntaxique: c'est l'algorithme CYK. Il permet de décider, en temps polynomial, si un mot est dans le langage généré par cette grammaire.

Forme normale de Greibach

Une grammaire est en forme normale de Greibach si les membres droits de toutes ses règles commencent par une lettres, et ne sont suivies éventuellement que par des variables. Par exemple, la grammaire

$s\to aSS\mid b$

qui engendre le langage de Lukasiewicz est en forme normale de Greibach. La forme quadratique de Greibach impose de plus qu'il y au plus deux variables dans chaque membre droit de règle (ce qui est le cas ici). Toute grammaire peut être mises sous forme quadratique de Greibach, au mot vide près.

La forme normale de Greibach bilatère est une forme bilatère de la forme normale de Greibach: les membres droits des règles sont soit des lettres terminales, soit commencent et finissent par des lettres terminales et ne contiennent au plus deux variables. Toute grammaire peut être mise sous forme normale bilatère^[1]

Grammaires étendues

On rencontre, surtout dans les applications, une forme de grammaires étendues: les membres droits des règles peuvent être des expressions rationnelles. Il en est ainsi dans la forme normale de Backus étendue. Plus précisément, notons $P (X)$ l'ensemble des membres droits de règles dont le membre gauche est $X$ .

Dans la définition usuelle des grammaires algébriques, les ensembles $P (X)$ sont finis pour toute variable $X$ .
Dans les grammaires étendues, les ensembles $P (X)$ sont des langages rationnels qui sont donnés par des expressions régulières.
Dans une généralisation de ces grammaires, les ensembles $P (X)$ sont eux-mêmes des langages algébriques.

On peut montrer que les deux extensions des grammaires engendrent toujours des langages algébriques.

Notes

↑ Ce résultat a été prouvé par G. Hotz. Une preuve et un exemple détaillé sont donnés dans Autebert, Berstel Boasson (1997)

Bibliographie

Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008 (ISBN 978-2-7117-2077-4)

Jean-Michel Autebert et Luc Boasson, Transductions rationnelles : Application aux Langages Algébriques, Masson, 1988 (ISBN 978-2-225-81504-1)

Jean-Michel Autebert, Langages algébriques, Masson, 1987 (ISBN 978-2-225-81087-9)

Jean-Michel Autebert, Jean Berstel et Luc Boasson, « Context-free languages and pushdown automata », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 1 : Word, Language, Grammar, Springer Verlag, 1997 (ISBN 978-3540604204)

Voir aussi

v · d · m

Informatique théorique

Théorie du calcul

Calculabilité	Décidabilité et indécidabilité • Ensemble récursif • Problème de l'arrêt • Ensemble récursivement énumérable
Modèle de calcul	Automate fini •Transducteur fini •Automate sur les mots infinis •Automate à pile •Automate linéairement borné • Automate cellulaire • Machine de Turing • Thèse de Church
Modes de calcul	Concurrence • Parallèlisme • Théorie de l'ordonnancement
Mesure et échelle de complexité	Réduction polynomiale • Problème NP-complet

Logique, syntaxe et sémantique

Logique mathématique	Assistant de preuve • Calcul des prédicats • Correspondance de Curry-Howard • Fonction récursive • Lambda-calcul • Théorème d'incomplétude de Gödel • Théorie des types
Grammaire formelle et systèmes de réécriture	Compilation • Expression rationnelle • Grammaire formelle • Transduction rationnelle • Langage rationnel • Langage algébrique • Langage contextuel • Théorie des langages
Sémantique	Sémantique des langages de programmation • Sémantique dénotationnelle • Sémantique axiomatique • Sémantique opérationnelle
Spécifier, vérifier et concevoir des programmes	Interprétation abstraite • Méthodes formelles • Model checking

Algorithmique, complexité et mathématiques discrètes

Algorithmique	Algorithme génétique • Algorithme glouton • Algorithme probabiliste • Complexité algorithmique • Diviser pour régner • Heuristique • Programmation dynamique
Problèmes et algorithmes numériques	Algorithme du simplexe • Géométrie algorithmique • Algorithme d'Euclide • Test de primalité
Problèmes et algorithmes non-numériques	Algorithmes de la théorie des graphes • Arbre (structure de données) • Liste (informatique) • Table de hachage • Tas (informatique)
Théorie des graphes	Coloration de graphe • Problèmes de cheminement
Recherche opérationnelle	Optimisation • Optimisation combinatoire • Théorie de l'ordonnancement
Données et codage	Combinatoire des mots •Codage • Codage de l'information • Compression de données • Cryptage • Cryptanalyse • Cryptographie • Théorie de l'information

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Grammaire non contextuelle de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

Grammaire Non Contextuelle — En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de production (ou simplement… … Wikipédia en Français
Grammaire Indépendante du Contexte — Grammaire non contextuelle En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de… … Wikipédia en Français
Grammaire algébrique — Grammaire non contextuelle En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de… … Wikipédia en Français
Grammaire hors-contexte — Grammaire non contextuelle En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de… … Wikipédia en Français
Grammaire hors contexte — Grammaire non contextuelle En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de… … Wikipédia en Français
Grammaire indépendante du contexte — Grammaire non contextuelle En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de… … Wikipédia en Français
Grammaire d'arbres adjoints — La grammaire d arbres adjoints, grammaire TAG, ou légèrement sensible au contexte est un formalisme d analyse grammaticale introduit par A.K. Joshi et ses collègues[1] en 1975. Ce formalisme a été utilisé à différentes fins, et particulièrement… … Wikipédia en Français
Grammaire S-attribuée — Une grammaire S attribuée est une grammaire ne contenant que des attributs synthetisés où chaque attribut ne dépend que des attributs fils. Sommaire 1 Généralités 2 Méthodes d évaluation des attributs 2.1 Méthode à plusieurs passes … Wikipédia en Français
Grammaire Universelle — La grammaire universelle, sous sa forme actuelle, a été pensée par Noam Chomsky, elle a pour but de s appliquer à n importe quel langage humain, que ce soit sous sa forme écrite ou verbale. L origine de cette conception, reconnue par Chomsky,… … Wikipédia en Français
Grammaire Formelle — Une grammaire est un formalisme permettant de définir une syntaxe et donc un langage formel, c est à dire un ensemble de mots admissibles sur un alphabet donné. La notion de grammaire formelle est particulièrement utilisée en programmation… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Grammaire non contextuelle

Sommaire

Définition