Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Grammaire hors-contexte

En linguistique et en informatique, une Grammaire hors-contexte est une grammaire formelle dans laquelle chaque règle de production est de la forme

V → w

où V est un symbole non-terminal et w est une chaîne composée de terminaux et/ou de non-terminaux. Le terme « hors-contexte » provient du fait qu'un non-terminal V peut toujours être remplacé par w, sans prendre en compte son contexte. Un langage formel est hors-contexte s'il existe une grammaire hors-contexte qui le génère.

Les grammaires hors-contexte sont suffisamment puissantes pour décrire la syntaxe des langages de programmation ; la syntaxe de la majorité des langages de programmation est en fait spécifiée à l'aide de grammaires hors-contexte. Ces grammaires sont cependant suffisamment simples pour permettre la création de parseurs efficaces qui, pour une chaîne donnée, déterminent si et comment elle peut être générée à partir de la grammaire. Voir le parseur d'Earley pour un exemple d'un tel algorithme. Les parseurs LR et les parseurs LL sont des méthodes pour analyser des sous-ensembles plus restrictifs de grammaires hors-contexte.

La BNF (Backus Naur form) est la notation la plus communément utilisée pour décrire une grammaire hors-contexte.

Exemples

Exemple 1

Voilà une grammaire hors-contexte simple :

S → aSb | ε

où | sépare différentes options pour le même non-terminal, et où ε correspond à la chaîne vide. Cette grammaire génère le langage : qui n'est pas régulier.

Exemple 2

Voilà une grammaire hors-contexte pour les expressions algébriques à trois variables (x, y et z), correctement parenthèsées :

S → x | y | z | S + S | S - S | S * S | S/S | (S)

Cette grammaire peut par exemple générer la chaîne « ( x + y ) * x - z * y / ( x + x ) ».

Exemple 3

Cette grammaire décrit le langage consistant en toutes les chaînes contenant seulement des a et des b, et dont le nombre de a est différent du nombre de b :

S → U | V

U → TaU | TaT

V → TbV | TbT

T → aTbT | bTaT | ε

T génère toutes les chaînes ayant le même nombre de a et de b, U génère toutes les chaînes avec plus de a que de b, et V génère toutes les chaînes ayant moins de a que de b.

Autres exemples

Les grammaires hors-contextes ne sont pas limitées aux langages formels en mathématiques. Le linguiste indien Panini décrivit le sanskrit avec une grammaire hors-contexte.

Dérivations et arbres syntaxiques

Il existe deux manières de décrire comment une chaîne a été générée à partir d'une grammaire donnée. La plus simple est de lister les chaînes consécutives de symboles (en commençant par le symbole de départ et en finissant par la chaîne) ainsi que les règles appliquées pour passer d'une chaîne à la suivante. Si nous utilisons de plus une stratégie comme « toujours remplacer en premier le non-terminal le plus à gauche », alors, pour les grammaires hors-contexte, la liste des règles appliquées est suffisante. Cela s'appelle la dérivation gauche d'une chaîne. Par exemple, pour la grammaire suivante :

(1) S → S + S

(2) S → 1

la chaîne « 1 + 1 + 1 » a pour dérivation gauche la liste [ (1), (1), (2), (2), (2) ]. De manière analogue, la dérivation droite est la liste des règles lorsque nous remplaçons systématiquement le non-terminal le plus à droite en premier. Dans l'exemple précédent, la dérivation droite est [ (1), (2), (1), (2), (2)].

La distinction entre dérivation gauche et dérivation droite est importante car elle permet dans la plupart des parseurs de déterminer l'ordre dans lequel les parties d'un programme seront executées. Voir par exemple les parseurs LL et les Parseur LR.

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

S→S+S (1)

S→S+S+S (1)

S→1+S+S (2)

S→1+1+S (2)

S→1+1+1 (2)

{ { { 1 }_S + { 1 }_S }_S + { 1 }_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 '1'
 | |
 '1' '1'

Cet arbre est appelé arbre syntaxique concret (voir aussi arbre syntaxique abstrait) de la chaîne. Dans ce cas, la dérivation gauche présentée plus haut et la dérivation droite définissent le même arbre syntaxique. Il y a cependant une autre dérivation gauche possible

S→ S + S (1)

S→ 1 + S (2)

S→ 1 + S + S (1)

S→ 1 + 1 + S (2)

S→ 1 + 1 + 1 (2)

qui définit l'arbre syntaxique suivant :

 S 
 /|\
 / | \
 / | \
 S '+' S
 | /|\
 | / | \
 '1' S '+' S
 | |
 '1' '1'

Si pour certaines chaînes du langage d'une grammaire, il y a plus d'un arbre syntaxique, alors la grammaire est dite grammaire ambigue. De telle grammaires sont habituellement difficiles à parser car le parseur ne peut pas toujours décider quelle règle grammaticale appliquer.

Formes normales

Toute grammaire hors-contexte qui ne génère pas la chaîne vide peut être transformée en une forme normale de Chomsky équivalente ou une forme normale de Greibach équivalente. « Équivalente » signifie ici que les deux grammaires génèrent le même langage.

Vu la relative simplicité des règles de production des grammaires en forme normale de Chomsky, cette forme a des implications à la fois théoriques et pratiques. Par exemple, étant donnée une grammaire hors-contexte, on peut utiliser la forme normale de Chomsky pour construire un algorithme qui décide, en temps polynomial, si une chaîne est dans le langage généré par cette grammaire : c'est l'algorithme CYK.

Propriétés des langages hors-contexte

• L'union et la concaténation de deux langages hors-contexte est un langage hors-contexte ; leur intersection ne l'est pas nécessairement.
• L'inverse d'un langage hors-contexte est un langage hors-contexte ; son complémentaire ne l'est pas nécessairement.
• Tout langage régulier est hors-contexte car il peut être décrit par une grammaire régulière.
• L'intersection d'un langage hors-contexte et d'un langage régulier est toujours hors-contexte.