Méthode. Un analyseur lexical est un automate fini: il n'a aucune mémoire non bornée. Or l'énoncé demande trois comptages indexés par des chaînes arbitraires (login, navigateur, IP). La solution tient donc en deux parties: le lexer reconnaît et extrait les champs (travail fini, faisable par un AFD), et une table de symboles externe fait office de mémoire associative (travail de comptage, hors du modèle fini). C'est exactement la frontière du cours entre reconnaissance et mémorisation.

Pourquoi des conditions de démarrage. Le lexer ne peut pas décider avec une seule règle globale: la ligne contient deux champs entre guillemets (le référent et le navigateur) qui se ressemblent, et le premier doit être ignoré. Il faut donc savoir où l'on en est dans la ligne. Les conditions de démarrage (%x) donnent cet état supplémentaire sans sortir du modèle fini — elles se compilent en dupliquant l'automate par contexte. Ici, cinq états suffisent: INITIAL (avant l'IP), CHAMPS (identité, date, requête), NUM (les deux champs numériques), REFERENT (le champ à ignorer), AGENT (le navigateur).

1%{2#include <stdio.h>3#include <stdlib.h>4#include <string.h>5 6/* ---- table de symboles : association chaine -> compteur ---- */7typedef struct { char *cle; int valeur; } entree;8typedef struct { entree *t; int n, cap; } table_t;9 10static void table_init(table_t *T) { T->t = NULL; T->n = 0; T->cap = 0; }11 12/* Renvoie un pointeur sur le compteur associe a `cle`, en le creant si besoin. */13static int *table_acces(table_t *T, const char *cle) {14  int i;

Points de rédaction qui rapportent des points.

1. Deux champs entre guillemets, un seul à retenir. C'est le piège central de l'exercice. Le référent et le navigateur ont la même forme lexicale (une chaîne entre guillemets), et le référent vient en premier. Une règle unique <CHAMPS>\"{NAV}[^"\n]*\" attraperait le référent "http://vlaminck/" (qui commence par une lettre) et n'atteindrait jamais le navigateur: le compteur nav serait faux, sans aucun message d'erreur. Il faut donc compter les champs: deux champs numériques après la requête, puis le référent, puis le navigateur. C'est à cela que servent les états NUM, REFERENT et AGENT.
2. Pourquoi une condition de démarrage et pas une règle plus précise. On pourrait écrire une regex qui capture la ligne entière d'un coup. Mais l'énoncé demande de commenter les structures de données et les fonctions utilisées: la découpe en champs par états est ce qui rend le programme lisible et testable champ par champ. C'est aussi le style attendu dans un vrai lexer, où l'on garde un état par contexte syntaxique.
3. Le nom sans la version. Le séparateur est le / de Mozilla/4.73: on copie jusqu'au premier / (ou espace, ou fin de champ). Tester par préfixe serait faux (Opera et OperaMini sont deux navigateurs distincts).
4. Extraction du login. L'énoncé impose au plus 8 lettres. La borne k < 8 dans la boucle de copie matérialise cette contrainte; sans elle, un chemin /~abcdefghijkl/ produirait un login de 12 caractères, et la statistique serait indexée sur une clé que l'énoncé n'autorise pas.
5. Une table de symboles, pas trois compteurs. L'énoncé dit « une ou plusieurs tables de symboles »: la clé est une chaîne quelconque, l'accès doit être dynamique. Une recherche linéaire suffit pour un TP; en production on passerait à une table de hachage, mais l'interface (table_acces renvoyant un int *) ne change pas.
6. Un détail du fonds local. Dans la copie PDF archivée du sujet, le champ navigateur des lignes 7 et 9 se lit 0pera/5.0 et 0pera/7.0 — avec un zéro initial, et non la lettre O. Si le fichier de log contient réellement ce caractère, la classe [A-Za-z] de la règle NAV ne matche pas le champ, et le navigateur est compté à tort. Il faut décider explicitement: soit le log est propre (Opera), soit la règle doit accepter un premier caractère quelconque hors espace et hors guillemet. Sur un sujet d'examen, signaler ce cas rapporte des points; le passer sous silence le fait perdre.
7. Compilation. flex access.l && cc lex.yy.c -lfl -o stats && ./stats < /var/log/access.log.

Vérification. Faites tourner le programme sur l'extrait de l'énoncé (9 lignes) et contrôlez chaque table séparément:

• IP: 193.51.25.77 → 6 (lignes 1 à 6), 193.51.24.15 → 3 (lignes 7 à 9);
• login (pages personnelles seulement): hpc → 2 (lignes 1 et 2), touati → 1 (ligne 3), dupont → 2 (lignes 7 et 8), samual → 1 (ligne 9);
• navigateur: Mozilla → 6 (lignes 1, 2, 4, 5, 6 et 8), Opera → 2 (lignes 7 et 9), IE → 1 (ligne 3).

Un écart sur une seule de ces valeurs localise l'erreur. Les deux causes les plus fréquentes: le référent compté comme navigateur (état REFERENT oublié), et un login tronqué par une borne mal placée. Le total des trois tables navigateur doit faire 9, comme celui des IP.

Méthode: lire la grammaire comme un constructeur de types. Chaque non-terminal correspond à une opération de construction de type:

• basic_type produit un type de base (INT, FLOAT, VOID);
• declarator : '*' direct_declarator produit un pointeur vers le type engendré par direct_declarator;
• direct_declarator : IDENTIFIER produit un type « encore inconnu », porteur d'un nom;
• direct_declarator : direct_declarator '(' parameter_list ')' produit une fonction dont le type de retour est celui du direct_declarator de gauche et dont les paramètres sont ceux de droite;
• direct_declarator : '(' declarator ')' ne construit rien: c'est un groupement, il ne sert qu'à fixer la lecture.

Un type est donc soit un atome (type de base), soit un constructeur à un argument (pointeur), soit un constructeur à deux arguments (fonction: retour + liste de paramètres). D'où une structure récursive:

1typedef enum { BASE_INT, BASE_FLOAT, BASE_VOID } base_t;2typedef enum { GENRE_BASE, GENRE_PTR, GENRE_FUNC } genre_t;3 4typedef struct type_s type_t;5 6typedef struct param_s {7  char        *nom;      /* le nom du paramètre, pour les messages d'erreur */8  type_t      *type;     /* son type */9  struct param_s *suiv;  /* liste chaînée: l'ordre des paramètres compte */10} param_t;11 12struct type_s {13  genre_t  genre;        /* BASE, PTR ou FUNC */14  base_t   base;         /* si genre == GENRE_BASE */

Pourquoi cette forme et pas une autre. Un type est un arbre, pas une chaîne de caractères: int * et int ** sont deux types différents, int (*f)(void) et int *f(void) aussi. Le champ genre est le discriminant (l'équivalent d'un tag de variante); cible porte l'information structurelle; params porte la liste ordonnée des paramètres. Les types de base sont au fond de la récursion, ce qui explique la règle declaration : basic_type declarator de la grammaire: la base n'est connue qu'à la toute fin de l'analyse, on la « bouche » alors dans le trou laissé par la feuille IDENTIFIER.

Déclaration float p(float a, int *b). On lit: p est une fonction retournant float, prenant un float nommé a et un pointeur vers int nommé b.

1FUNC  cible = BASE(FLOAT)2      params ─┬─ { nom = "a", type = BASE(FLOAT) }3              └─ { nom = "b", type = PTR( cible = BASE(INT) ) } ─── suivant = NULL

Sous forme d'initialisation C:

1type_t *t_a  = type_base(BASE_FLOAT);2type_t *t_b  = type_ptr(type_base(BASE_INT));3param_t *pa  = cons_param("a", t_a, NULL);4param_t *pb  = cons_param("b", t_b, pa);5type_t  *t_p = type_fonction(type_base(BASE_FLOAT), pb);

Déclaration float *foo(float (*hook)(float a), int b). C'est le cas qui piège: foo est une fonction qui retourne un pointeur sur float, et dont le premier paramètre est un pointeur sur fonction. On lit de l'intérieur vers l'extérieur, en suivant la règle de la « spirale »:

1FUNC  cible = PTR( cible = BASE(FLOAT) )      ← foo retourne float *2      params ─┬─ { nom = "hook",3              │   type = PTR( cible = FUNC  cible = BASE(FLOAT)4              │                            params = { nom = "a", type = BASE(FLOAT) } ) }5              └─ { nom = "b", type = BASE(INT) }

Autrement dit: hook n'est pas une fonction, c'est un pointeur vers une fonction. Le GENRE_FUNC n'est jamais atteint directement depuis un paramètre; il est toujours derrière un GENRE_PTR. Cette distinction est précisément ce que vérifie la question 2.5 (voir exercice 5).

Erreur classique. Représenter le type par une chaîne ("float*") et compter les *. Cela marche sur les exemples simples et échoue dès qu'un pointeur de fonction apparaît: float (*hook)(float) et float *hook(float) s'écrivent presque pareil et désignent deux choses différentes. Le type doit être un arbre.

2.2 — le %union. Les attributs transportés par la grammaire sont exactement les valeurs produites par les règles:

• basic_type transporte un type de base (base_t), pas un type_t *: à ce stade on ne sait encore rien de la structure;
• declaration, declarator, direct_declarator transportent un arbre de type (type_t *);
• parameter_list et parameter transportent une liste de paramètres (param_t *);
• IDENTIFIER transporte une chaîne (le nom), et INT/FLOAT/VOID sont des mots-clés sans valeur, donc sans attribut.

1%union {2  base_t   base;     /* basic_type */3  type_t  *type;     /* declaration, declarator, direct_declarator */4  param_t *params;   /* parameter_list, parameter */5  char    *nom;      /* IDENTIFIER */6}7 8%token <nom>  IDENTIFIER9%token <base> INT FLOAT VOID10 11%type  <base>   basic_type12%type  <type>   declaration declarator direct_declarator13%type  <params> parameter_list parameter

Deux remarques de rédaction. D'une part, basic_type n'est pas de type type_t *: mélanger les deux obligerait à allouer un nœud pour chaque mot-clé et rendrait la règle declaration inutilement coûteuse. D'autre part, les terminaux INT, FLOAT, VOID portent bien un attribut <base>: c'est l'action de basic_type qui le lit, comme le montre l'exercice suivant.

2.3 — l'interface de la table des symboles. Trois opérations suffisent, et il faut les typer correctement: la table est hétérogène du point de vue de l'appelant (elle rend un type ou un booléen), d'où trois signatures distinctes plutôt qu'une fonction polymorphe.

1/* Insère (nom, type) si absent. Renvoie 1 si l'insertion a eu lieu,2   0 si l'identificateur était déjà déclaré. */3int      table_stocker (table_t *t, const char *nom, type_t *type);4 5/* Teste la présence d'un identificateur. */6int      table_contient(table_t *t, const char *nom);7 8/* Lit le type associé à un identificateur déjà présent.9   Précondition: table_contient(t, nom) est vrai. */10type_t  *table_lire    (table_t *t, const char *nom);

Le point à justifier: table_stocker renvoie un entier, non void. La question 2.5 demande justement de détecter les redéclarations, et c'est ce code de retour qui le permet sans parcourir la table une seconde fois.

Le point délicat: le type de base arrive après le déclarateur. La règle est declaration : basic_type declarator. En analyse ascendante (yacc), declarator est réduit avant basic_type: au moment où l'on construit le nœud de declarator, la base est encore inconnue. La solution standard est de laisser un trou dans la feuille IDENTIFIER, puis de le boucher au moment de la réduction de declaration. On ajoute donc un champ type_t *base_a_boucher (ou, plus simplement, on mémorise le nom de l'identificateur dans une variable globale pendant la réduction de direct_declarator : IDENTIFIER, ce qui suffit ici puisque la grammaire n'a qu'une déclaration en cours à la fois).

1/* Règle 1 : la base comble le trou laissé par la feuille IDENTIFIER. */2declaration3    : basic_type declarator4        { $$ = $2; type_boucher_base($2, $1); }5    ;6 7basic_type8    : INT   { $$ = BASE_INT;   }9    | FLOAT { $$ = BASE_FLOAT; }10    | VOID  { $$ = BASE_VOID;  }11    ;12 13/* '*' devant un déclarateur = un pointeur vers ce déclarateur. */14declarator

Justifications à écrire sur la copie.

1. declarator : '*' direct_declarator enveloppe le type de droite dans un GENRE_PTR. L'ordre est contre-intuitif: dans float *foo(...), le * est à gauche de foo mais c'est le type de retour de foo qui devient un pointeur, pas foo lui-même. C'est type_fonction($1, $3) qui construit FUNC(cible = $1), et $1 vaut alors PTR(FLOAT): la lecture est correcte.
2. direct_declarator : '(' declarator ')' ne fait rien d'autre que propager $2. Les parenthèses ne créent pas de type: elles forcent seulement la dérivation, exactement comme dans les expressions arithmétiques où (a+b)*c et a+b*c ont des arbres différents mais les mêmes nœuds.
3. parameter : declaration réutilise la règle complète, ce qui autorise récursivement les pointeurs de fonction en paramètre — c'est ce qui rend float (*hook)(float a) analysable.
4. La table des symboles n'est pas remplie ici: elle l'est dans declarator_list (exercice suivant), car c'est seulement là qu'on connaît le nom complet et qu'on peut détecter les collisions.

1declarator_list2    : declarator_list declarator { enregistrer($2); }3    | declarator                 { enregistrer($1); }4    ;

avec

1static void enregistrer(type_t *t)2{3  char *nom = declarateur_nom(t);4 5  /* (1) redéclaration ? */6  if (table_contient(&table, nom)) {7    erreur("identificateur %s deja declare", nom);8    return;                       /* on n'ecrase pas l'ancien type */9  }10 11  /* (2) fonction retournant une fonction, ou fonction en parametre ? */12  if (contient_fonction_imbriquee(t)) {13    erreur("%s : une fonction ne peut ni retourner ni prendre une fonction", nom);14    return;

et le parcours qui implémente la vérification (2):

1/* Renvoie 1 si le type contient une fonction « nue » la ou c'est interdit. */2static int contient_fonction_imbriquee(const type_t *t)3{4  if (!t || t->genre == GENRE_BASE) return 0;5 6  if (t->genre == GENRE_PTR)                 /* un pointeur sur fonction est licite */7    return contient_fonction_imbriquee(t->cible);8 9  /* genre == GENRE_FUNC */10  if (t->cible && t->cible->genre == GENRE_FUNC)   /* retour = fonction : interdit */11    return 1;12 13  for (param_t *p = t->params; p; p = p->suiv)14    if (p->type && p->type->genre == GENRE_FUNC)   /* parametre = fonction nue : interdit */

Pourquoi la récursion sur GENRE_PTR est indispensable. C'est le cœur de l'exercice. float *foo(float (*hook)(float a), int b) est valide: hook est un paramètre dont le type est PTR(FUNC(...)), et un pointeur sur fonction est une valeur parfaitement légitime en C. En revanche float f(float g(float)) — un paramètre de type FUNC(...) sans pointeur — est invalide: on ne peut pas passer une fonction « nue » en argument. La fonction de vérification doit donc s'arrêter (et renvoyer 0) dès qu'elle traverse un GENRE_PTR, et ne signaler l'erreur que sur un GENRE_FUNC atteint sans pointeur intermédiaire.

Formulation générale du C réel. Cette contrainte n'est pas propre à l'exercice: la norme C interdit les types fonction retournant fonction et fonction prenant une fonction en paramètre, mais autorise les pointeurs correspondants. C'est pourquoi la grammaire de déclarateurs impose le passage par declarator (qui peut produire un *) pour les paramètres de type fonction.

Erreur classique. Écrire if (t->cible->genre == GENRE_FUNC) return 1; sans distinguer GENRE_PTR de GENRE_FUNC en tête de fonction: la vérification rejette alors float (*hook)(float), qui est licite. Tester la correction sur les deux déclarations de l'exercice 2 est le moyen le plus rapide de détecter ce bug.

3.1 — l'arbre. Attention aux parenthèses et aux priorités. Les opérateurs * et / sont plus prioritaires que + et -, et tous sont associatifs à gauche. En appliquant ces règles, la structure de la partie gauche est (((a+b)*(c+d))/(a-c))*(b+d) puis + a puis + (b*e), et la racine de l'expression entière est le * extérieur:

1*                                                      (racine)2├── +3│   ├── +4│   │   ├── *5│   │   │   ├── /6│   │   │   │   ├── *7│   │   │   │   │   ├── + (a+b)8│   │   │   │   │   └── + (c+d)9│   │   │   │   └── - (a-c)10│   │   │   └── + (b+d)11│   │   └── a12│   └── * (b*e)13└── /14    ├── *

3.2 — les nombres de Sethi-Ullman (nombres d'Ershov). Règle de décoration: une feuille reçoit le nombre 1; pour un nœud interne dont les sous-arbres gauche et droit portent les nombres $l$ et $r$,

$\text{nombre}(n) = \begin{cases} l+1 & \text{si } l = r \\ \max(l,r) & \text{si } l \neq r \end{cases}$

Le nombre obtenu à la racine est le nombre minimal de registres nécessaires pour évaluer l'expression sans code de vidage. Intuition: si les deux sous-arbres demandent le même nombre de registres, il faut en plus conserver le résultat du premier pendant l'évaluation du second; si l'un en demande strictement moins, ce résultat « tient » dans les registres déjà occupés par le plus gourmand.

Décoration, de bas en haut:

1* [4]2├── + [3]3│   ├── + [3]4│   │   ├── * [3]5│   │   │   ├── / [3]6│   │   │   │   ├── * [3]      ← 2,2 ⇒ 37│   │   │   │   │   ├── + [2] (a+b)8│   │   │   │   │   └── + [2] (c+d)9│   │   │   │   └── - [2] (a-c)10│   │   │   └── + [2] (b+d)11│   │   └── a [1]12│   └── * [2] (b*e)13└── / [3]14    ├── * [3]                  ← 2,2 ⇒ 3

À la racine, les deux fils portent $l = r = 3$, donc le nombre est $3+1 = 4$.

$\boxed{\text{nombre minimal de registres} = 4}$

Vérification de deux nœuds au passage: (a+b)*(c+d) a deux fils de nombre 2 ⇒ 3. ((a+b)*(c+d))/(a-c) a des fils de nombres 3 et 2, donc $\max(3,2) = 3$: la division n'exige pas de registre supplémentaire, le sous-arbre gauche gardant la main.

3.3 — code trois adresses optimal (4 registres). La règle de génération découle de la décoration: on évalue d'abord le fils de plus grand nombre, puis l'autre, puis on combine. Si $l \ge r$, le sous-arbre droit est évalué avec un registre de moins, puisque le registre du résultat gauche est déjà occupé.

1; ---- partie gauche : (a+b)*(c+d)/(a-c)*(b+d) + a + b*e ----2R0 = a3R1 = b4R0 = R0 + R1          ; R0 = a+b5R1 = c6R2 = d7R1 = R1 + R2          ; R1 = c+d8R0 = R0 * R1          ; R0 = (a+b)*(c+d)9R1 = a10R2 = c11R1 = R1 - R2          ; R1 = a-c12R0 = R0 / R1          ; R0 = (a+b)*(c+d)/(a-c)13R1 = b14R2 = d

33 instructions, 4 registres, aucun spill. Le nombre de registres effectivement utilisés simultanément ne dépasse jamais 4, et il atteint 4 exactement dans la partie droite (R1, R2, R3 occupés plus R0 qui conserve la partie gauche): c'est le nœud racine qui impose la borne.

Point de méthode. Le code optimal n'est pas « le plus court »: il est celui qui minimise le nombre de registres simultanément vivants, et Sethi-Ullman est prouvé optimal pour les arbres sans re-matérialisation. Deux erreurs classiques: évaluer systématiquement le fils gauche en premier (ici c'est correct à la racine, mais faux dès que $l < r$, cas qui se produit dans la partie droite si l'on écrit la division dans l'autre sens), et oublier qu'un nœud dont les deux fils ont des nombres différents ne coûte pas de registre supplémentaire.

Le nombre d'Ershov de la racine vaut 4: avec 3 registres, au moins un spill est inévitable, et un seul suffit. La stratégie découle de l'arbre: les deux sous-arbres de la racine demandent chacun 3 registres. On évalue donc entièrement la partie gauche avec les 3 registres disponibles, on la vide en mémoire, puis on évalue la partie droite — qui tient dans 3 registres — et on recharge pour combiner.

1; ---- partie gauche : 3 registres suffisent (Ershov = 3) ----2R0 = a3R1 = b4R0 = R0 + R15R1 = c6R2 = d7R1 = R1 + R28R0 = R0 * R19R1 = a10R2 = c11R1 = R1 - R212R0 = R0 / R113R1 = b14R2 = d

Bilan: 35 instructions (33 + 1 écriture mémoire + 1 lecture), 2 accès mémoire de spill, 3 registres. Le coût est minimal: le spill est placé à la frontière de la racine, c'est-à-dire à l'endroit exact où la pression sur les registres atteint 4.

Pourquoi ce spill est optimal. Le nombre d'Ershov de la racine vaut 4, donc toute allocation à 3 registres doit vider au moins une valeur; une seule valeur est suffisante, car les deux sous-arbres de la racine ont un nombre d'Ershov de 3 et tiennent donc chacun dans les 3 registres. Placer le spill ailleurs (par exemple à l'intérieur de la partie droite, où le nœud * a deux fils de nombre 2) n'apporterait rien et coûterait un accès mémoire supplémentaire.

Vérification. Le résultat doit être identique au code à 4 registres sur un jeu de valeurs: prendre $a=1$, $b=2$, $c=3$, $d=4$, $e=5$, $x_1=6$, $x_2=7$, $y_2=8$ et exécuter les deux codes à la main. Toute divergence signale un spill mal placé (typiquement une valeur écrasée entre l'écriture et la relecture).

1.1 — $G_0$ est ambiguë. La règle $E \to E + E$ est doublement récursive à droite et à gauche, et elle est la seule à traiter $+$: le mot H + B + G admet deux arbres de dérivation distincts, correspondant à $(H+B)+G$ et à $H+(B+G)$. Il suffit d'exhiber ces deux arbres pour conclure — c'est ce qu'on attend, pas un argument de comptage.

1   E                E2  /|\              /|\3 E + E            E + E4/|\   |          |   /|\5H + B G          H  B + G

Sémantiquement les deux arbres donnent le même chemin (l'addition des déplacements est associative), mais la grammaire est ambiguë au sens syntaxique: un mot a plusieurs arbres. C'est un défaut de la grammaire, pas du langage.

1.2 — arbre de dérivation de 3 × (H + 5 × B).

1        E2       /|\3      N × E4      |    |5      C   (E)6      |   /|\7      3  E + E8         |    \9         H    N × E10              |    |11              C    B12              |13              5

1.3 — grammaire non ambiguë $G_1$. L'ambiguïté vient de ce qu'une seule règle traite à la fois les opérateurs de priorités différentes. On la supprime en stratifiant la grammaire, exactement comme pour les expressions arithmétiques du cours:

$E \longrightarrow T + E \mid T \qquad T \longrightarrow N \times T \mid F \qquad F \longrightarrow H \mid B \mid G \mid D \mid (E)$ $N \longrightarrow N\,C \mid C \qquad C \longrightarrow 0 \mid 1 \mid \dots \mid 9$

Justification de la non-ambiguïté, en trois arguments:

• Un $E$ est une suite de $T$ séparés par des +, et un $T$ ne contient jamais de + au niveau supérieur: la décomposition de H + B + G en $T + E$ est donc unique (le premier + non parenthésé). La récursion à droite fixe l'associativité à droite, sans créer de choix.
• Un $T$ est soit un facteur, soit N × T où $N$ est une suite de chiffres. Comme $N$ est maximal (la règle $N \to NC$ force à absorber tous les chiffres), le découpage N × ... est unique.
• $F$ est atomique: aucun choix interne.

On vérifie sur les deux cas qui départagent $G_0$ et $G_1$: 3 × G + B se lit (3 × G) + B (la partie $T$ s'arrête avant le +), et 3 × (H + 5 × B) exige les parenthèses pour répéter une somme — ce qui est bien la sémantique annoncée par l'énoncé.

1.4 — nombre de mouvements élémentaires. Attribut n, synthétisé sur $E$, $T$, $F$, plus un attribut v (valeur entière du nombre) synthétisé sur $N$ et $C$.

Tous les attributs sont synthétisés: aucune information ne descend de la racine vers les feuilles. Sur l'exemple de l'énoncé, 3 × (4 × G + D) donne $3 \times (4 \times 1 + 1) = 15$.

1.5 — coordonnées finales. Deux attributs dx et dy, synthétisés sur $E$, $T$, $F$.

Sur G + H + D + B: $(-1,0) + (0,1) + (1,0) + (0,-1) = (0,0)$, conforme à l'énoncé. La répétition $k$ fois se traite par une simple multiplication, ce qui est bien la sémantique de N × E.

1.6 — abscisse maximale. C'est la question qui distingue les étudiants: le maximum dépend de où l'on commence, donc il semble exiger un attribut hérité (l'abscisse courante). Une solution plus élégante n'utilise que des attributs synthétisés, en transportant le déplacement:

• dx: déplacement horizontal total du sous-chemin (synthétisé);
• mx: abscisse maximale relativement au point de départ du sous-chemin (synthétisé).

Trois points à justifier:

1. Concaténation. La trajectoire de $T + E_1$ parcourt d'abord $T$ (maximum relatif T.mx) puis $E_1$ décalé de T.dx (maximum relatif T.dx + E1.mx). Le maximum est donc max(T.mx, T.dx + E1.mx).
2. Répétition. $k$ copies de la même unité démarrent aux abscisses $0, dx, 2dx, \dots, (k-1)dx$. Chaque copie atteint au plus $mx$ relativement à son départ, donc le maximum global est $mx + \max(0, (k-1)dx)$: si $dx > 0$ la dernière copie est la plus à droite, sinon c'est la première.
3. Cas de base. Pour G, la trajectoire visite $0$ puis $-1$: l'abscisse maximale est $0$, pas $-1$. Pour D, elle vaut $1$. C'est le point où l'on oublie facilement de compter le point de départ.

Sur l'exemple D + H + G + B de l'énoncé: $D$ donne (dx=1, mx=1); la queue $H+G+B$ donne dx = 0, mx = 0; d'où mx = max(1, 1+0) = 1, conforme à l'énoncé. Aucun attribut hérité n'est nécessaire — c'est la raison pour laquelle on transporte le déplacement.

3.1 — traduction. Un parcours post-ordre de l'arbre: opérandes d'abord, opérateur ensuite.

• (3 + 5) × (6 + 7) devient 3□5 + 6□7 + ×.
• 3 + (5 × 6) + 7: l'associativité à gauche donne (3 + (5 × 6)) + 7, donc 3□5□6□× + 7□ +.

3.2 — grammaire non ambiguë. Le point clé: une expression postfixée valide est un mot où tout préfixe strict contient plus d'opérandes que d'opérateurs, et le mot entier contient exactement un opérande de plus que d'opérateurs. Cette propriété se traduit directement en grammaire, en distinguant « un nombre » de « une expression complète »:

$E \longrightarrow N \mid E\,E\,O \qquad O \longrightarrow + \mid \times \mid - \mid /$ $N \longrightarrow C\,\square \mid C\,N \qquad C \longrightarrow 0 \mid 1 \mid \dots \mid 9$

Justification de la non-ambiguïté — c'est le cœur de la question:

• $N$ est non ambigu: N → C N | C □ place le □ en dernière position, et la lecture d'un nombre est donc déterminée par la position de son marqueur de fin.
• $E \to E\,E\,O$ est non ambigu: dans un mot postfixé valide, le dernier symbole est nécessairement l'opérateur racine, et le découpage E E est alors unique. En effet le premier symbole est un nombre; soit $p$ la longueur du plus court préfixe qui soit une expression complète (il existe, et il est unique puisqu'un préfixe valide se termine par un opérateur ou un □). Alors $E_1$ est exactement ce préfixe, et $E_2$ est le reste. Aucun autre découpage ne peut fonctionner, car tout autre choix laisserait un des deux facteurs invalide.

Autrement dit, la notation postfixée est un code uniquement décodable: la position des opérateurs détermine l'arbre sans aucune convention de priorité. C'est précisément pour cette raison que les compilateurs l'utilisent comme représentation intermédiaire avant la génération de code à pile (voir la page Génération de code).

3.3 — actions sémantiques. Attribut s, synthétisé, de type chaîne, sur $E$, $N$ et $C$. On produit une forme infixée entièrement parenthésée, ce qui garantit que la chaîne obtenue est elle-même non ambiguë.

Sur 22□45□37 + ×: la sous-expression 45□37 + produit "(45+37)", puis l'expression complète produit "(22(45+37)×)". Si l'on veut la forme infixée minimale (sans parenthèses superflues), il faut un attribut supplémentaire de priorité, et les actions deviennent conditionnelles — c'est le sujet classique de la « jolie impression » d'un arbre. La forme parenthésée est celle attendue ici, car elle est correcte sans information supplémentaire.

Vérification. La chaîne produite doit se reparser en une expression infixée équivalente. Sur 3□5□6□× + 7□ +, les actions donnent "((3(5×6))+7)": en évaluant par le parcours post-ordre de l'arbre d'origine, on retrouve $3 + 5 \times 6 + 7 = 40$. Toute divergence indique une inversion des opérandes dans la règle $E \to E_1 E_2 O$ — l'erreur la plus fréquente sur cet exercice.