2. Structure d'une grammaire

Une grammaire à structure de phrase G permet de caractériser un langage L(G), qui est un ensemble de phrases (ou mots), appelé le langage engendré par la grammaire. Une telle grammaire ressemble à une définition rationnelle, en plus riche, plus expressif. Elle repose sur :

  1. La connaissance d'un vocabulaire terminal (noté VT) dont chaque élément est appelé symbole terminal. Ce vocabulaire correspond à l'alphabet pour les langages rationnels et les symboles terminaux aux symboles de l'alphabet. Nous avons donc L(G) ⊆ VT*. Dans ce cours, nous ne considérerons que les vocabulaires terminaux composés de symboles (lettres, chiffres, caractères spéciaux comme '+', '-', ';'...). En compilation, ce vocabulaire est un ensemble d'unités lexicales (identificateurs réservé ou non, paramètres, nom, opérateurs...).
  2. La connaissance d'un vocabulaire non terminal (noté VN) dont chaque élément est appelé symbole non terminal. Les symboles non terminaux peuvent être vus comme les nouveaux symboles des définitions rationnelles (utilisés comme membres gauches des règles). Ils ont toutefois un rôle un peu plus large. Ils n'appartiennent pas au vocabulaire de base (terminaux) et sont destinés à être éliminés, remplacés pour former les mots du langage.
  3. Des règles permettant de déterminer quelles séquences de VT* sont légales. Ces règles ressemblent à celles des définitions rationnelles mais sont plus souples et plus générales.


Grammaire

Une grammaire formelle, appelée aussi grammaire de Chomsky, G est une description de la forme des symboles et des phrases d'un langage noté L(G). Elle est définie par un quadruplet G = (VT, VN, S, R) où :

  • VT est un ensemble fini non vide : le vocabulaire terminal ou alphabet ;
    L(G) ⊆ VT*
  • VN est un ensemble fini non vide : le vocabulaire non terminal (on parle aussi de variable ou de catégorie syntaxique) ; On a VT ∩ VN = ∅ et on note V=VT ∪ VN le vocabulaire de la grammaire ;
  • S ∈ VN est un symbole non terminal particulier appelé l'axiome ;
  • R est un ensemble de règles, appelées règles de production (ou règles de réécriture), de la forme α → β avec α ∈ V+ et β ∈ V*.

Une règle de production α → β se lit "α peut être remplacé par β". α est appelé "partie gauche" et β "partie droite" de la règle. On peut également écrire des règles de la forme α → β1 | β2 | ... | βn avec n ≥ 1 et pour tout 1 ≤ i ≤ n, βi ∈ V* pour abréger n règles ayant α en partie gauche, de la forme α → βi .

Quelques exemples de grammaires :

Intuitivement, la grammaire G0 définit le langage L(G0)={0n1n | n ≥ 1} sur le vocabulaire terminal (ou alphabet) A={0,1}. En effet, de façon informelle :

  1. Appliquer une règle va consister à remplacer dans un mot une occurrence du membre gauche de la règle par le membre droit correspondant. Sur l'exemple, à partir de 0X1, on peut obtenir 00X11 en appliquant R2 (le lieu du remplacement étant signalé par les lettres en orange et la nouvelle chaîne est soulignée), ce que l'on peut noter :
    0X1 =R2⇒ 00X11.
  2. On considérera l'ensemble des mots que l'on peut atteindre en prenant l'axiome S comme mot de départ et en appliquant les règles un nombre fini de fois. Sur l'exemple, on peut ainsi atteindre (entre autres) les mots "0X1" (par S =R1⇒ 0X1), "00X11" (par S =R1⇒ 0X1=R2⇒ 00X11) et "01" (par S=R1⇒0X1=R3⇒01); remarquons que l'on peut également atteindre S, par l'application successive de 0 règles. Les mots ainsi accessibles sont appelés "formes sententielles" et les suites d'applications de règles, "dérivations".
  3. Les mots du langage caractérisé par la grammaire sont les mots accessibles (au sens du point précédent) qui ne sont composés que de symboles terminaux. Sur l'exemple, parmi les mots de L(G0), il y a "01" (S=R1⇒0X1=R3⇒01), mais aussi "0011" (S=R1⇒0X1=R2⇒ 00X11=R3⇒0011), et "000111" ...

On démontrera rigoureusement plus loin que L(G0) est exactement {anbn | n ≥ 1}. Auparavant, nous donnons les définitions rigoureuses correspondant aux idées que nous venons de présenter intuitivement.


Formes sententielles et langage d'une grammaire

Soit G = (VT,VN, S, R) une grammaire et V=VT∪ VN, alors :

  • l'ensemble des formes sententielles (ou proto-phrases) de G est défini récursivement par :

    • L'axiome "S" est une forme sententielle de G.
    • Pour tous v, x, y, z ∈ V*, si "xyz" est une forme sententielle de G et si y → v ∈ R, alors "xvz" est une forme sententielle de G.
  • Le langage engendré par G est L(G)={x ∈ V* | x est une forme sententielle de G et x ∈ VT*}.

Une forme sententielle est donc un mot sur V. Les formes sententielles ne contenant aucun symbole non terminal sont donc les phrases de L(G). Par ailleurs, la définition par induction des formes sententielles est la base de la notion d'application de règles que nous avons évoquée ci-dessus. Nous précisons ce point dans la section suivante.

mardi, 25/11/03 16:34