Corrigé Mines-Ponts 2025 Informatique I MPI — Partie 4 (Q30 à Q34) : Analyse syntaxique : grammaire et automate

Sujet officiel du concours Mines-Ponts, session 2025, épreuve Informatique I MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

On veut une fonction analyse qui lit un tableau associatif écrit sous la forme \{id:5,valeur:12,ok:0\} : une accolade ouvrante, une liste non vide de couples clef:valeur séparés par des virgules, une accolade fermante ; la clef est une suite finie non vide de lettres de a à z, la valeur un entier non signé sans zéro non significatif, et ni l'une ni l'autre ne peut manquer. La notation $x ∣ \dots ∣ y$ désigne la disjonction des symboles de $x$ à $y$ (chiffres ou lettres), et l'on dispose des règles

$N \to 0 ∣ \dots ∣ 9, M \to 1 ∣ \dots ∣ 9, L \to a ∣ \dots ∣ z .$

Q30. Écrire la règle de production $C$ d'une clef. Q31. Écrire la règle de production $V$ d'une valeur.
On considère la grammaire d'axiome $T$ :

$T \to {S}, S \to K ∣ K, S, K \to C : V .$

Q32. \{id:5,valeur:12,ok:0\} appartient-il au langage engendré ? Le cas échéant, dessiner un arbre de dérivation. Même question pour \{james:007\}.
Q33. Décrire (schéma ou table) un automate déterministe, sans transition vide, reconnaissant le langage de $T$ ; les transitions peuvent être étiquetées par des disjonctions de lettres ou de chiffres.
Q34. Vérifier, en donnant les étapes, que \{code:102\}, \{v:0\} et \{a:1,b:2\} sont reconnues ; dans quel état est l'automate sur \{james:007\} ?

Corrigé

Q30. Une clef est une lettre, éventuellement suivie d'une clef :

$C \to L ∣ L C .$

Par récurrence sur $n ⩾ 1$ , $C$ engendre exactement les mots de $n$ lettres minuscules, chacun par une seule dérivation (la règle choisie est dictée par la présence ou non d'une lettre suivante).

Q31. Il faut traiter le zéro à part : une valeur est soit 0, soit un chiffre non nul suivi d'une suite quelconque, éventuellement vide, de chiffres :

$V \to 0 ∣ M R, R \to N R ∣ ε .$

$R$ engendre toutes les suites finies de chiffres, $V$ engendre donc 0 et les écritures décimales sans zéro de tête, c'est-à-dire exactement les entiers non signés sans zéro non significatif. La grammaire n'est pas ambiguë : le premier caractère décide entre $0$ et $M R$ , la présence d'un chiffre suivant entre $N R$ et $ε$ .

Ce que le correcteur attend : le cas de 0 séparé. Une règle comme $V \to N ∣ N V$ accepte 007 ; le jury a aussi refusé les règles « non déterministes », c'est-à-dire celles où deux productions d'un même non-terminal commencent par le même symbole, comme la variante sans $ε$ $V \to 0 ∣ M ∣ M R$ (deux règles débutent par $M$ ). Avec la règle $R \to ε$ , autorisée par le programme, chaque choix de production est dicté par le prochain caractère lu : c'est la version la plus sûre.

Q32. Le mot \{id:5,valeur:12,ok:0\} appartient au langage. $T \to {S}$ donne les accolades ; $S \to K, S$ deux fois puis $S \to K$ donnent les trois couples ; chaque $K \to C : V$ se dérive avec Q30 et Q31 (id, valeur, ok sont des clefs, 5, 12, 0 des valeurs). Voici l'arbre de dérivation complet (terminaux en couleur, lus de gauche à droite) :

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →