---

Définition de la notion de grammaire

---

Définition (Grammaire)

Une grammaire est un ensemble de règles de syntaxe qui décrivent quelles sont les constructions correctes, possibles dans le langage utilisé, à l'aide de l'alphabet utilisé (alphabet ou vocabulaire).

---

Il existe de nombreux types de grammaires, et encore bien plus de formalismes exprimés pour représenter cette grammaire.

Nous utiliseront ici un seul symbolisme, parmi les plus célèbres, pour représenter les grammaires : la formalisation BNF (Backus-Naur Form).

Le formalisme BNF

Dans la syntaxe BNF, une grammaire est constituée d'un ensemble de règles.

Chaque règle est constituée :

• d'un premier membre,
• suivi du symbole de réécriture (::=),
• suivi d'un second membre, qui peut être vide.

On utilise (et on distingue) des symboles terminaux et des symboles non-terminaux (ST et SNT).

Les symboles terminaux

---

Définition (Symbole terminal)

Un symbole terminal est un symbole qui peut intervenir réellement, effectivement, dans le texte analysé.

---

---

Exemple : Dans

  if (temps == beau)

if est un symbole terminal (on trouve le mot dans le programme).

---

Notation: Les symboles terminaux sont entourés par des guillemets : « ».

Les symboles non terminaux

---

Définition (Symbole non terminal)

Un symbole non terminal (SNT) est un symbole introduit par commodité, ou par nécessité, par le rédacteur de la grammaire. Il n'est pas présent en tant que tel dans le texte analysé.

---

Ce rédacteur (vous, par exemple) introduit des SNT pour décrire les parties du fichier d'entrée qui représentent entre eux un tout logique.

On peut ainsi simplifier l'écriture de la grammaire.

Notation : Les symboles non-terminaux sont entourés par des chevrons: $<$ $>$.

Les règles d'une grammaire

Définition

Les règles d'une grammaire sont ainsi constituées :

• Le premier membre d'une règle de grammaire est un SNT (la règle en constitue la définition).
• Le second membre est une famille ordonnée (éventuellement vide) de symboles, terminaux ou non.

Ainsi, chaque règle de la grammaire consiste en la définition d'un symbole non-terminal. Cette dernière est terminée quand tous les SNT ont reçu une définition.

Une règle s'écrit finalement sous la forme :

$<$SNT$>$::= suite (éventuellement vide) de ST et SNT

Premier exemple de grammaire

---

Exemple :

Voici un bout de grammaire (pour la définition d'une fonction en C) :

  <fct>   ::= <type> <nom> «(» <parametres> «)» <bloc>
  <type>  ::= «int»
          ::= «char» 

---

L'axiome de la grammaire

---

Définition (Axiome de la grammaire)

Parmi tous les SNT, l'un d'entre eux doit désigner l'ensemble du texte à analyser, on l'appelle axiome de la grammaire.

---

---

Exemple :

  <programme en C> ::= <entete> <suite de fonctions>

---

Fin de la grammaire

La grammaire est terminée quand tous les SNT ont reçu au moins une définition.

Exercices

---

Exercice : Les mots du langage $\mathcal L$ sont constitués d'un nombre éventuellement nul de $a$, suivi d'un $b$, suivi d'au moins un $c$.

Donner une grammaire BNF de ce langage.

---

Correction :

  <mot>     ::= <suite_a> 'b' <suite_c>
  <suite_a> ::= 'a' <suite_a>
            ::=
  <suite_c> ::= 'c' <fin_c>
  <fin_c>   ::= 'c' <fin_c>
            ::=

---

---

Exercice : Ecrire la grammaire, en syntaxe BNF, des formes propositionnelles. On rappelle que les opérateurs sont, par ordre de priorité croissante :

• Implication (le moins prioritaire) : on ne peut ni les répéter, ni les faire coexister, au même niveau dans une expression (par exemple, $a \Rightarrow b \Rightarrow c$ est incorrect).
• Disjonction et conjonction (au même niveau, prioritaires sur implication et équivalence) : on ne peut pas les mélanger : on peut écrire $a \lor b \lor c$, sans parenthèse, mais pas $a \lor b \land c$.
• Négation : prioritaire sur tous les autres. Elle peut être répétée. Il s'agit d'un opérateur unaire préfixé.

Les noms de variable commencent par un caractère alphabétique, suivi éventuellement d'un nombre quelconque de caractères alphanumériques ou de soulignements. Il n'y a pas de constantes dans les expressions.

Les opérateurs sont réalisés au clavier :

• les deux caractères consécutifs $->$, \/ et /\ pour l'implication, la disjonction et la conjonction
• le caractèr ~ pour la négation.

L'expression peut évidemment comporter des parenthèses, et ne peut être vide.

Consulter le site http://pltplp.net/lex-yacc/yacc.html.fr et implanter les fichiers lex et yacc permettant l'analyse lexicale et syntaxique d'une ligne contenant une formule propositionnelle.

---