MOïRA est une méthode et un outil destinés à intégrer de façon optimale le traitement des données textuelles dans une application.

Cette page décrit la façon d'écrire une grammaire selon le formalisme MOïRA.

Contenu de cette page :
 

Le formalisme BNF standard
Le formalisme BNF étendu de Moïra
Analyse syntaxique. Grammaire déterministe

Retour à MOïRA

MOïRA utilise un mode de description proche du modèle grammatical traditionnel BNF (Backus-Naur Form).
Le formalisme BNF a été conçu à la fin des années 50 par John Backus pour définir rigoureusement le langage ALGOL, ancêtre des langages structurés.

Comme pour une langue naturelle, la syntaxe d'un langage formel est définie par une grammaire Une grammaire est un mécanisme fini capable de produire toutes les phrases d'un langage et seulement celles-là.

Une grammaire est constituée d'une liste de productions décrivant les règles grammaticales applicables au vocabulaire de ce langage. Le vocabulaire est constitué de deux types de symboles :

• Les terminaux du langage : mots résevés (if, else, while, for), séparateurs (•, ;) qui sont les entités élémentaires apparaissant dans un texte. Ils constituent l'alphabet du langage.
• Les non-terminaux ou symboles auxilliaires qui permettent de nommer les différentes constructions autorisées par la grammaire. Ils sont aussi appelés noms de règles ou métanoms et se notent entre < > : <affectation>, <instruction>, <bloc>, ...

Par exemple, la règle suivante : "Une phrase type se compose d'un sujet, d'un verbe et d'un complément et se termine par un point", s'écrit en BNF :
 

Un test en C posséde 2 syntaxes : une syntaxe simple et une syntaxe complète avec  bloc else.
 

Le formalisme BNF standard pour décrire des listes d'instructions est assez lourd :
 

Pour cette raison, on a dû améliorer le formalisme pour aboutir au BNF étendu.

Retour au début

On a pu remarquer la lourdeur de certaines productions : Si l'on doit définir la totalité d'un langage par une grammaire, on aimerait disposer d'une plus grande concision et d'une plus grande lisibilité.

On considère les réels, entiers, identifieurs comme des terminaux du langage, terminaux ayant une forme variable mais bien définie. On nomme ces constructions les expressions régulières lexicales du langage. On les note au moyen d'un identifieur précédé du métacaractère % : %entier, %reel,%identifieur et %chaine.

 L'alternative symbolysée par une barre | (prononcer "ou")  qui permet de regrouper les règles ayant même partie gauche dans une seule production.
 

L'itération ou la liste qui existe en deux types : l'itération 0 à n symbolysée par { }* et l'itération 1 à n symbolysée par { }+ . On rangera aussi dans cette catégorie la phase facultative notée entre crochets  [ ] .
 

Les listes font souvent apparaître des séparateurs. Par exemple le point-virgule séparateur d'instructions  ou la virgule séparatrice des indices d'un tableau. MOïRA permet d'accoler au méta-caractère d'itération ( le "*" ou le "+") le séparateur de la liste.
 

Enfin, on peut aussi faire disparaître les métacaractères < >, à condition de prévoir un mécanisme permettant de distinguer les mots réservés et les non-terminaux. Sur un document on peut souligner ou afficher les mots-clés en caractères gras. Certains constructeurs syntaxiques (par exemple YACC) imposent de déclarer préalablement les mots réservés. La solution de MOïRA consiste à adopter les majuscules pour les mots réservés et les minuscules pour les non-terminaux. Notons que cette convention ne concerne que la grammaire  et pas le texte analysé.
 

En résumé :
 

Les notations en italique sont des spécificités de MOïRA.

Retour au début

L'analyse syntaxique consiste à vérifier si un texte est conforme à la grammaire utilisée pour spécifier ce texte.
Prenons une grammaire décrivant des expressions arithmétiques.
 

Soit le texte :

On dit qu'une phrase est conforme à la grammaire si on peut retrouver l'ensemble des règles qui ont abouti à cette phrase en partant de l'axiome. On peut représenter ces dérivations de façon arborescente :
 

Arbre de dérivation

La racine de l'arbre de dérivation est l'axiome (première règle de la grammaire), ses feuilles sont des terminaux.

En suivant les règles de la grammaire fournie sur le dernier exemple, on peut remarquer que cette représentation arborescente n'est pas unique : Comme la première règle de décomposition d'une expression est symétrique, on peut tout à fait décomposer l'expression située à gauche, soit celle située à droite de l'opérateur. Il en ressort que l'arbre syntaxique associé à la phrase "A+B*C" selon cette grammaire n'est pas unique.  On dit alors que la grammaire est ambigüe :
 
 

Arbre obtenu en dérivant l'élément récursif à gauche de la règle :	Arbre obtenu en dérivant l'élément récursif à droite de la règle
express ::= express oper var | var	express ::= var oper express | var

Une grammaire ambigüe met  l'analyeur syntaxique dans une situation imposssible. En effet un traitement algoritmique se doit d'être déterministe pour d'effectuer un traitement sémantique correct. Dans le cas contraire, la sémantique risque  d'être aléatoire.

Comment lever une telle ambigüité ?. Dans ce cas précis l'ambigüité provient d'une récursivité double, elle est donc levée si l'on choisit de faire apparaître la récursivité à gauche ou la récursivité à droite.

Prenons une grammaire récursive à gauche :
 

Dans ce cas, l'arbre de dérivation est unique, puisque l'on ne peut dériver que l'expression de gauche :
 

On pourrait fort bien imaginer une forme récursive à droite. Par exemple :
 

En fait la récursivité à gauche est bien plus intéressante du point de vue formel que la récursivité à droite, car elle correspond au sens conventionnel des calculs : la partie gauche d'une opération correspond au total déja calculé, et la partie droite à l'élément en cours de calcul. Autre exemple : la phrase A-B-C doit être sémantiquement équivalente à (A-B)-C et non à l'expression A-(B-C). Or c'est cette seconde interprétation qui serait fournie par une grammaire récursive à droite.

On remarque que tous les opérateurs étant décrits au même niveau, c'est le premier rencontré sur la phrase à analyser qui décide de l'ordre des opérations. Si l'on évalue l'expression selon l'ordre des opérations établi par cet arbre de dérivation, on voit que l'on aboutit à un résultat ne correspondant pas aux priorités classiques d'opérateurs : en effet A+B*C est conventionnellement reconnu comme équivalent à A+(B*C) et non à (A + B) * C.
Si l'on désire évaluer l'expression, on a donc deux possibilités :

• Soit rétablir l'ordre de priorité des opérateurs, après l'analyse syntaxique, c'est à dire au niveau sémantique. Une sorte de "bricolage" en quelque sorte.
• Soit faire apparaître les priorités au niveau de la grammaire on obtient  la grammaire des expressions algébriques :

Ainsi avec cette dernière grammaire le texte :
 

est structuré de façon cohérente avec l'ordre des calculs :
 

On voit  que, pour un langage donné, il existe plusieurs grammaires possibles. Le fait de faire apparaître plusieurs priorités d'opérateurs, ou de définir une grammaire non ambigüe, peut ressembler superflu au départ, mais ce travail permet d'une part d'utiliser les outils d'analyse syntaxique existant, et surtout de simplifier le travail sémantique qui va suivre.

Retour au début