Grammaires non contextuelles

Cours complet · informatique (MP2I/MPI), chapitre 30 · MP2I et MPI

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

30.1 Au-delà des automates

Le chapitre chap:automates s'est achevé sur une limite précise : un automate fini n'a qu'une mémoire bornée, et ne peut donc pas reconnaître ${a^{k} b^{k}}$ . Or c'est exactement ce dont on a besoin pour décrire un langage de programmation : les parenthèses doivent s'équilibrer, et leur nombre n'est pas borné.

Les grammaires lèvent cette limite. Le programme en donne l'usage : « les grammaires formelles ont pour principal intérêt de définir des syntaxes structurées, en particulier celles des langages informatiques (langage de programmation, langage de requête, langage de balisage) ».

AttentionCe qui est explicitement hors programme

Le B.O. les nomme : « sont hors programme : les automates à pile, les grammaires syntagmatiques générales, la hiérarchie de Chomsky ». Et pour l'analyse : « on ne parle pas d'analyseur LL ou lr. On ne présente pas de théorie générale de l'analyse syntaxique. »

On apprend donc à écrire une grammaire, à dériver un mot, à construire un arbre d'analyse et à écrire un analyseur ad hoc par descente récursive. Rien de plus.

30.2 Grammaires

Définition 30.1Grammaire non contextuelle

Une grammaire non contextuelle est la donnée :

d'un ensemble de symboles terminaux — les lettres du mot final ;
d'un ensemble de symboles non-terminaux — les catégories intermédiaires ;
d'un symbole initial, non-terminal ;
de règles de production $A \to α$ , où $A$ est un non-terminal et $α$ une suite de symboles.

Le programme fixe les notations : $\to$ pour la production, $\Rightarrow$ pour la dérivation immédiate — remplacer un non-terminal par le membre droit d'une de ses règles — et $\Rightarrow^{*}$ pour une suite de dérivations.

Le langage engendré est l'ensemble des mots de terminaux dérivables du symbole initial. Un langage est non contextuel s'il est engendré par une telle grammaire.

Important« Non contextuelle » veut dire quelque chose de précis

Le membre gauche d'une règle est un seul non-terminal. On peut donc remplacer $A$ par $α$ quel que soit son voisinage — sans regarder le contexte. C'est cette restriction qui rend l'analyse praticable, et c'est elle qui donne son nom à la classe.

Exemple 30.2La grammaire qui bat les automates

$S \to a S b ∣ ε$

Une dérivation : $S \Rightarrow a S b \Rightarrow aa S bb \Rightarrow aabb$ . Le langage engendré est ${a^{k} b^{k} : k \geq 0}$ — celui-là même dont le lemme de l'étoile a établi qu'aucun automate fini ne le reconnaît.

La grammaire y arrive parce que la récursivité de $S$ « mémorise » implicitement le nombre de $a$ , dans la profondeur de la dérivation. Là où l'automate n'avait que ses états, la grammaire dispose d'une structure imbriquée sans limite.

Exemple 30.3Une expression arithmétique

Le programme demande de « montrer comment définir une expression arithmétique ou une formule de la logique propositionnelle par une grammaire ».

$E T F \to \to \to E + T ∣ T T \times F ∣ F (E) ∣ n$

Les trois niveaux $E$ , $T$ , $F$ ne sont pas décoratifs : ils encodent la priorité des opérateurs. Comme un $+$ ne peut apparaître qu'au niveau $E$ , qui est plus haut que $T$ , l'arbre place nécessairement le $\times$ plus bas — donc plus près des feuilles, donc évalué d'abord. La priorité n'est écrite nulle part : elle est dans la forme de la grammaire.

Proposition 30.4Tout langage régulier est non contextuel

Le programme demande cette « non contextualité des langages réguliers ».

Démonstration

Soit un automate déterministe $(Q, Σ, δ, q_{0}, F)$ . On prend un non-terminal $A_{q}$ par état, $A_{q_{0}}$ comme symbole initial, et les règles

$A_{q} \to a A_{δ (q, a)} pour chaque transition, A_{q} \to ε pour q \in F .$

Une dérivation reproduit exactement une exécution de l'automate : la grammaire engendre donc le même langage.

iRemarqueL'inclusion est stricte

${a^{k} b^{k}}$ est non contextuel et n'est pas régulier : les langages non contextuels forment donc une classe strictement plus large. Le programme s'arrête là — la hiérarchie de Chomsky, qui poursuit cette échelle, est hors programme.

30.3 Arbre d'analyse et ambiguïté

Définition 30.5Arbre d'analyse

L'arbre d'analyse d'une dérivation a le symbole initial pour racine, un nœud par application de règle, et les terminaux pour feuilles — lues de gauche à droite, elles donnent le mot.

C'est l'arbre du chapitre chap:arbres, et c'est l'objet que produit un compilateur avant toute autre chose.

Définition 30.6Dérivation à gauche, à droite

Une dérivation est à gauche si l'on remplace toujours le non-terminal le plus à gauche, à droite dans l'autre cas. Un même arbre d'analyse correspond à exactement une dérivation gauche et une dérivation droite : c'est l'ordre des remplacements qui change, pas leur résultat.

Définition 30.7Ambiguïté, équivalence faible

Une grammaire est ambiguë s'il existe un mot admettant deux arbres d'analyse distincts. Deux grammaires sont faiblement équivalentes si elles engendrent le même langage — sans que leurs arbres coïncident.

AttentionL'ambiguïté n'est pas un défaut esthétique : elle change le sens

Avec la grammaire simplifiée $E \to E + E ∣ E \times E ∣ n$ , le mot $2 + 3 \times 4$ admet deux arbres : l'un évalue $14$ , l'autre $20$ . La grammaire ne dit pas lequel est correct — c'est ce qui rend une grammaire ambiguë inutilisable pour un compilateur.

La grammaire à trois niveaux de la section précédente engendre le même langage — elle lui est faiblement équivalente — et n'est pas ambiguë. C'est tout l'objet de ses niveaux.

Exemple 30.8Le « sinon pendant », que le programme demande

Le dangling else :

$I \to si c alors I ∣ si c alors I sinon I ∣ a$

Sur l'instruction


si c1 alors si c2 alors a sinon a

le sinon peut se rattacher au premier si ou au second : deux arbres, deux comportements différents à l'exécution.

Comment les vrais langages tranchent : par une règle extérieure à la grammaire — « le sinon se rattache au si le plus proche » — ou par une grammaire remaniée qui interdit le cas litigieux. C'est aussi pourquoi tant de langages exigent un marqueur de fin explicite (fi, end, des accolades) : l'ambiguïté disparaît alors par construction.

30.4 Analyse syntaxique par descente récursive

ImportantCe que demande le programme, exactement

« On peut présenter au tableau un algorithme ad hoc d'analyse syntaxique par descente récursive (algorithme top-down) pour un langage de balisage fictif — par exemple, la grammaire de symbole initial $S$ et de règles de production $S \to T S ∣ c$ , $T \to a S b$ sur l'alphabet ${a, b, c}$ . »

C'est cette grammaire précise qu'on traite.

Méthode : Une fonction par non-terminal

Le principe de la descente récursive tient en une phrase : on écrit une fonction par non-terminal, et le corps de la fonction est la règle.


(* Analyseur pour S -> T S | c  et  T -> a S b, sur l'alphabet {a, b, c}.
   pos est la position courante dans le mot ; les fonctions l'avancent.
   Lèvent Echec si le mot n'appartient pas au langage. *)
exception Echec

let analyser mot =
  let n = String.length mot in
  let pos = ref 0 in
  let lire c =
    if !pos < n && mot.[!pos] = c then incr pos else raise Echec
  in
  let rec s () =
    if !pos < n && mot.[!pos] = 'a' then begin t (); s () end   (* S -> T S *)
    else lire 'c'                                              (* S -> c   *)
  and t () =
    lire 'a'; s (); lire 'b'                                   (* T -> a S b *)
  in
  s ();
  if !pos <> n then raise Echec        (* tout le mot doit être consommé *)

ImportantPourquoi une seule lettre suffit à choisir la règle

La fonction s choisit entre ses deux règles en regardant un seul caractère : si c'est un a, la seule règle possible est $S \to T S$ , car $T$ commence forcément par a ; sinon ce doit être $S \to c$ .

Cette propriété — un caractère d'avance suffit à décider — est ce qui rend la descente récursive possible. Le programme interdit d'en faire la théorie (« on ne parle pas d'analyseur LL ou lr »), mais l'idée pratique est là : la structure du code est celle de la grammaire, et la récursivité du langage porte la récursivité de la structure.

AttentionUne grammaire récursive à gauche fait boucler l'analyseur

La règle $E \to E + T$ traduite littéralement donne :


let rec e () = e (); lire '+'; t ()     (* NE TERMINE JAMAIS *)

La fonction s'appelle elle-même sans avoir consommé un seul caractère : il n'y a pas de variant, donc pas de terminaison — c'est exactement le défaut du chapitre chap:recursivite.

La grammaire des expressions arithmétiques, si commode pour les priorités, est donc inutilisable telle quelle en descente récursive. On la réécrit en itératif :


let rec e () = t (); while pointe_sur '+' do lire '+'; t () done

La grammaire la plus élégante n'est pas toujours celle qu'on analyse. C'est une contrainte réelle de l'écriture des compilateurs.

iRemarqueLe lien avec les types inductifs

Le programme demande de « faire le lien avec la définition par induction de certaines structures de données (listes, arbres, formules de logique propositionnelle) ». Il est exact : une grammaire non contextuelle est une définition inductive, et l'arbre d'analyse est la valeur du type correspondant.

$E \to E + T ∣ T ⟷ type e = Plus of e * t | Simple of t$

Écrire un analyseur, c'est passer d'un mot — la syntaxe concrète — à une valeur du type inductif — la syntaxe abstraite. Le chapitre chap:arbres évaluait déjà ces arbres ; ce chapitre montre d'où ils viennent.

30.5 Ce qu'il faut retenir

ImportantGrammaires : cinq points

Une grammaire non contextuelle a un seul non-terminal en membre gauche : on remplace sans regarder le contexte.
Elle dépasse les automates parce que la récursivité lui donne une mémoire non bornée : $S \to a S b ∣ ε$ engendre ${a^{k} b^{k}}$ .
L'arbre d'analyse porte la structure. Les niveaux $E$ , $T$ , $F$ encodent la priorité des opérateurs — elle n'est écrite nulle part ailleurs.
Une grammaire ambiguë donne deux arbres pour un mot, donc deux sens : $2 + 3 \times 4$ vaut $14$ ou $20$ . Le « sinon pendant » en est le cas classique.
La descente récursive écrit une fonction par non-terminal. Elle échoue sur les grammaires récursives à gauche — faute de variant — et l'on réécrit alors la règle en boucle.

Continuer sur Adloun : animation, QCM, fiches, exercices