Description du fichier de spécification EBNF

Un fichier de spécification de type EBNF est constitué de sections qui comportent la ligne nom: suivi de son contenu (nom est le nom de la section). Les sections valides de base sont :

• tokens et blanks qui décrivent la partie lexicale:
  tokens contient les tokens (ou lexèmes) que le lexeur peut reconnaitre. blanks contient les tokens que le lexeur doit ignorer. Les descriptions des tokens se font à l'aide d'expressions rationnelles. on peut assigner des types Java aux tokens (pour les traitements sémantiques).
• starts, error, versions and productions qui décrivent la grammaire:
  starts donne les axiomes de la grammaire (le non terminal de départ). error donne le terminal utilisé dans la grammaire pour le recouvrement d'erreurs. versions permet d'indiquer des nom de versions de la grammaire et leur chronologie. productions donne les différentes productions de la grammaire.

Il existe d'autres sections contenant, notamment, les priorités, la déclaration d'import de classes Java.

Avant de décrire en détail le fichier EBNF, nous donnons un exemple classique de calculatrice. Le fichier EBNF pour une telle grammaire serait:

tokens:
  value= "[0-9]+"
  plus= '\+'
  minus= '-'
  mult= '\*'
  div= '\/'
  lpar= '\('
  rpar= '\)'
  semicolon= ';'
blanks:
  space= '[ \t\r\n]'
starts:
  expr
productions:
  expr = expr 'plus' term {p0}
			| expr 'minus' term {p1}
			| term {p2}
			;
  term = term 'mult' factor {p3}
			| term 'div' factor {p4}
			| factor {p5};
  factor = 'minus' factor {p6} 
			| 'lpar' expr 'lpar' {p7}
			| 'value' {p8} 
			;
		

Les règles de reconnaissance de tokens sont sous la forme d'expressions rationnelles. Elles sont décrites dans la rubrique tokens. Chaque règle est décrite par un nom et une expression rationnelle. Le nom et l'expression rationnelle sont séparés par le symbole '='. L'expression rationnelle se trouve entre deux guillemets ou entre deux quotes. Par exemple, la règle ci-dessous indique que la règle nommée 'value' reconnaît les nombres entiers positifs ou nuls.

	value="[0-9]+"
			

L'ordre des règles est important. Le lexeur teste les règles les unes après les autres. Il garde le token reconnu par la règle ayant le "longest match". Si deux règles reconnaissent le même plus long token, alors, parmi ces deux règles, ce sera celle définie en premier dans l'EBNF qui sera sélectionnée. Supposons que l'on a les deux règles suivantes:

	id='[a-zA-Z]+'
	int='int'
			

Si la chaîne "int" est repérée par le lexeur, elle le sera par la règle nommée id.

Pour rendre le lexeur plus souple, il est possible de lui indiquer des léxèmes à ignorer. Ces séquences sont décrites sous la forme de règles (nom de règle plus expression rationnelle) qu'il suffira de placer dans la section blanks. Cette section se situe après la section 'tokens'. Supposons que l'on a :

	blanks:
		space= '[ \t\r\n]'
			

Lorsque que le lexeur repérera une séquence décrite par la règle space (i.e. un espace, une tabulation ou un retour à la ligne), elle sera ignorée.

Certains symboles doivent être déspécialisés pour être reconnu. Par exemple, la règle ci-dessous reconnaît une suite de +.

			  regle='\++'
			

Voici une liste (non exhaustive) des symboles spéciaux: /\*+[]

Voici quelques symboles particuliers :

• '\n' => retour à la ligne
• '\t' => tabulation

ATTENTION : la section 'productions' est obligatoire, même si elle a un contenu vide (le cas où l'on ne veut générer qu'un lexeur). Si 'productions' est vide, la section 'starts' ne doit pas exister.

La description des productions de la grammaire se trouve dans la section productions. Les productions sont regroupées selon le non-terminal de la partie gauche. Les différentes parties droites sont séparées par le symbole "|". Chaque production peut avoir un nom qui se trouve entre parenthèse après la définition de la partie droite. Le nommage d'une production est conseillé dans le cadre de projets.
La section starts contient le symbole non-terminal initial.

Certaines grammaires ont des conflits (selon la méthode de parsing que l'on veut utiliser). Il est possible de régler ce problème en donnant des priorités. Par exemple, dans l'exemple ci-dessous, la grammaire reconnaissant les expressions arithmériques entières possède des conflits LR.

Les priorités sont définies dans la section priorities de l'ebnf. Chaque priorité a un nom et on lui assigne deux valeurs: un degré de priorité (entier) et une règle d'associativité (left,right,nonassoc). Dans l'exemple, la priorité nommée plus_minus a pour degré de priorité 1 et a pour règle d'associativité à gauche (left). Ces priorités sont ensuite affectées aux différentes opérations :

• pour les décalages, les priorités sont celles des tokens
• pour les réductions, les priorités sont celles des productions

L'affectation d'une priorité se fait simplement en mettant le nom de la priorité entre crochets après la définition du token ou de la production visée. Dans l'exemple, s'il y a conflit entre un décalage par '+' (priorité plus_moins: 1 left) et une réduction par expr -> expr '*' expr (priorité star: 2 left), la réduction est choisie car 2 est supérieur à 1. Par contre, s'il y a conflit entre un décalage par '*' (priorité star: 2 left) et une réduction par expr -> expr '+' expr (priorité plus_moins: 1 left), le décalage est choisi. Par ailleurs, s'il y a conflit entre un décalage par '+' (priorité plus_moins: 1 left) et une réduction par expr -> expr '-' expr de même degré de priorité, la réduction est choisie par la règle de l'associativité à gauche (left) de la priorité de la réduction.

Quand elle n'est pas spécifiée, la priorité d'une production est calculée en fonction des terminaux qui la composent.

Il est possible de typer les différents tokens et non-terminaux pour réaliser une analyse sémantique. Dans l'exemple ci-dessous, le token value a le type de base int. Le non-terminal expr est un ExprContent, classe Java qui a été importée dans la section imports du fichier EBNF.

Il est souvent préférable de séparer la partie syntaxique de la partie sémantique (typage). Pour cela, on utilise deux fichiers EBNF comme montré ci-dessous.

Notez que, même si elles ne sont pas remplies, les sections tokens et productions sont obligatoires ! La section typage permet d'indiquer le type des différents symboles. Les terminaux doivent être mis entre simple quotes.

Il est possible de rajouter des commentaires sur une ligne comme en Java ou C :

	// ceci est un commentaire
			

ATTENTION : Les noms utilisés doivent être différents des mots-clés de Java.