À gauche, à droite, et l'arbre

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 30 — Grammaires non contextuelles

Énoncé

Donner la dérivation à gauche et la dérivation à droite du mot acbacbc. Comparer les arbres.

Corrigé

À gauche — on remplace toujours le non-terminal le plus à gauche :

$S \Rightarrow T S \Rightarrow a S b S \Rightarrow a c b S \Rightarrow a c b T S \Rightarrow a c ba S b S \Rightarrow a c ba c b S \Rightarrow a c ba c b c .$

À droite — toujours le plus à droite :

$S \Rightarrow T S \Rightarrow T T S \Rightarrow T T c \Rightarrow T a S b c \Rightarrow T a c b c \Rightarrow a S ba c b c \Rightarrow a c ba c b c .$

Les deux arbres sont identiques. Sept étapes de chaque côté, les mêmes sept règles appliquées — dans un ordre différent. On applique $S \to T S$ , deux fois $T \to a S b$ , trois fois $S \to c$ , et une fois de plus $S \to T S$ .

Ce qu'il faut en retenir, et c'est le point de l'exercice. À un arbre correspond exactement une dérivation gauche et exactement une dérivation droite. Chercher l'ambiguïté en comparant deux dérivations n'a donc aucun sens : il faut comparer les arbres, ou — ce qui revient au même et se programme — comparer les dérivations à gauche.

Et une conséquence pratique. Un analyseur par descente récursive lit le mot de gauche à droite et applique les règles dans l'ordre de la dérivation gauche. C'est pourquoi c'est cette dérivation-là qui sert de référence.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.