Grammaires non contextuelles

Cours · informatique (MP2I/MPI), chapitre 30 · MP2I et MPI · le début du chapitre, la suite sur Adloun

Un arbre de syntaxe : la grammaire décompose l'expression 2 + 3 × 4 en respectant la priorité des opérations.

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.

Exercices du chapitre

Quel langage cette grammaire engendre-t-elle ? corrigé
Compter les arbres d'analyse corrigé
Écrire une grammaire – et vérifier qu'elle n'est pas ambiguë corrigé
Le sinon pendant, et sa réparation corrigé
La récursivité à gauche, et ce que la réécriture coûte corrigé
Ce que protège le dernier contrôle de l'analyseur corrigé

La suite du cours · Tous les exercices du chapitre