# Laboratoire facultatif — Des tokens à un arbre d'expression

## Ce que les tokens ne disent pas encore

Dans ce laboratoire, notre lexer reconnaît les nombres et les opérateurs. Il ne choisit
pas l'ordre des calculs : `1 + 2 * 3` doit valoir 7, tandis que
`(1 + 2) * 3` vaut 9. Aujourd'hui, nous allons construire un arbre qui rend
cet ordre explicite, puis l'évaluer.

Le socle accepte les entiers non signés, `+`, `*` et les parenthèses.
Les espaces, tabulations, sauts de ligne et retours chariot sont permis entre les symboles.
Le lexer reconnaît aussi `-` et `/`, mais le parser du socle les refuse :
nous pourrons les ajouter en approfondissement. Le moins unaire, comme
`-3`, n'appartient pas au langage étudié ici.

Ce notebook facultatif étudie un langage arithmétique réduit aux entiers,
indépendant du langage à flottants d'AP2. Il permet de reprendre le parser
en détail. Il se sauvegarde dans `entrainement/`, sans rendu supplémentaire.
Ce notebook est autonome : le lexer est fourni ci-dessous. Aucun fichier
AP2, aucune image et aucune bibliothèque à installer ne sont nécessaires.
Nous reprenons la progression de la démo « Un peu de parsing », sans son
préambule sur le langage : les clauses et la récursion sont déjà nos outils.

Les cellules à compléter contiennent `nil`. Procédez dans l'ordre E1 à E5
et relancez la cellule du module après chaque modification. Les vérifications
intermédiaires ne passent qu'une fois les étapes indiquées complétées.
Les boucles et messages des vérifications sont fournis ; vous n'avez pas
à apprendre leur syntaxe pour résoudre les exercices.

## Le lexer du laboratoire, fourni

`Lexer.lex/1` renvoie `{:ok, tokens}` ou
`{:error, :symbole_inconnu, texte_restant}`. Une erreur conserve le suffixe
à partir du premier symbole inconnu, y compris s'il contient de l'Unicode.
Les signes sont reconnus avant les nombres : un `-` est un opérateur,
jamais une partie du token entier. `Enum.reverse/1` remet simplement les
tokens dans l'ordre de lecture à la fin du parcours.

Évaluez cette cellule sans la modifier :

```elixir
defmodule Lexer do
  def lex(texte) do
    parcourir(texte, [])
  end

  def parcourir("", tokens) do
    {:ok, Enum.reverse(tokens)}
  end

  def parcourir(" " <> reste, tokens) do
    parcourir(reste, tokens)
  end

  def parcourir("\t" <> reste, tokens) do
    parcourir(reste, tokens)
  end

  def parcourir("\n" <> reste, tokens) do
    parcourir(reste, tokens)
  end

  def parcourir("\r" <> reste, tokens) do
    parcourir(reste, tokens)
  end

  def parcourir("+" <> reste, tokens) do
    parcourir(reste, [:plus | tokens])
  end

  def parcourir("-" <> reste, tokens) do
    parcourir(reste, [:minus | tokens])
  end

  def parcourir("*" <> reste, tokens) do
    parcourir(reste, [:multiply | tokens])
  end

  def parcourir("/" <> reste, tokens) do
    parcourir(reste, [:divide | tokens])
  end

  def parcourir("(" <> reste, tokens) do
    parcourir(reste, [:lparen | tokens])
  end

  def parcourir(")" <> reste, tokens) do
    parcourir(reste, [:rparen | tokens])
  end

  def parcourir(texte, tokens) do
    ajouter_nombre(Integer.parse(texte), texte, tokens)
  end

  def ajouter_nombre({nombre, reste}, _texte, tokens) do
    parcourir(reste, [{:int, nombre} | tokens])
  end

  def ajouter_nombre(:error, texte, _tokens) do
    {:error, :symbole_inconnu, texte}
  end
end
```

```elixir
Lexer.lex("1 + 2 * 3")
# {:ok, [{:int, 1}, :plus, {:int, 2}, :multiply, {:int, 3}]}
```

## E1 — Construire et évaluer deux arbres (30 min)

Un *arbre syntaxique abstrait* (AST) représente les opérations imbriquées.
Une feuille est un entier. Un nœud est un tuple :
`{:plus, gauche, droite}` ou `{:multiply, gauche, droite}`.
Les deux derniers éléments sont eux-mêmes des arbres.

Pour `1 + 2 * 3`, la racine est une addition et sa branche droite est la
multiplication. Pour `(1 + 2) * 3`, la racine est une multiplication.
Complétez ces deux valeurs avant d'écrire l'évaluateur :

```elixir
arbre_priorite = nil
arbre_parentheses = nil
{arbre_priorite, arbre_parentheses}
```

Vérification des arbres, fournie :

```elixir
if arbre_priorite != {:plus, 1, {:multiply, 2, 3}} do
  raise "La multiplication doit être la branche droite de l'addition."
end
if arbre_parentheses != {:multiply, {:plus, 1, 2}, 3} do
  raise "Avec ces parenthèses, l'addition doit être une branche de la multiplication."
end
IO.puts("E1 : structures des deux arbres vérifiées")
```

Complétez `CalculAST.eval/1` : pour une opération, évaluez les deux branches
puis combinez leurs valeurs. Pour une feuille, renvoyez l'entier.
L'évaluateur reçoit uniquement un AST bien formé ; sa dernière clause
suppose donc que la valeur reçue est un entier.

```elixir
defmodule CalculAST do
  def eval({:plus, gauche, droite}) do
    nil
  end

  def eval({:multiply, gauche, droite}) do
    nil
  end

  def eval(nombre) do
    nil
  end
end
```

```elixir
for {arbre, attendu} <- [
  {42, 42}, {{:plus, 2, 3}, 5},
  {{:plus, 1, {:multiply, 2, 3}}, 7},
  {{:multiply, {:plus, 1, 2}, 3}, 9}
] do
  if CalculAST.eval(arbre) != attendu do
    raise "Évaluez chaque branche avant d'appliquer l'opération."
  end
end
IO.puts("E1 : évaluation récursive vérifiée")
```

Dans une cellule de texte, expliquez ce que portent les tuples, puis
tracez l'évaluation de `{:multiply, {:plus, 1, 2}, 3}`.

## E2 — Lire un entier et conserver le reste (30 min)

Notre parser va descendre dans trois niveaux. Cette grammaire décrit les
formes qu'il accepte ; ici `*` après un groupe signifie « répéter zéro ou
plusieurs fois », tandis que `"*"` désigne le signe de multiplication :

```text
expr   := term ("+" term)*
term   := factor ("*" factor)*
factor := entier | "(" expr ")"
```

`expr` lit les additions ; pour obtenir chaque terme, elle appelle `term`,
qui lit d'abord les multiplications. `factor` lit un entier ou une expression
parenthésée. Ainsi, nous construisons la multiplication avant de l'utiliser
dans une addition. Les parenthèses peuvent relancer `expr` depuis `factor`.

Chaque fonction interne renvoie `{:ok, arbre, tokens_restants}` ou une
erreur `{:error, raison, tokens_restants}`. Seule `Parser.parse/1` impose
la consommation complète : son succès est `{:ok, arbre}`.

Le squelette suivant contient le parcours et les cas d'erreur. Commencez
par **les trois emplacements E2** : la feuille entière, puis les deux fins
de parcours `expr_suite/2` et `term_suite/2`. Une fin de parcours conserve
l'arbre courant et le reste ; elle ne jette aucun token.

### Lire un `case` dans le code fourni

`case resultat do` choisit une branche d'après la forme d'une valeur.
À gauche de `->`, nous retrouvons les motifs connus ; à droite se trouve
le calcul à effectuer. `erreur -> erreur` conserve le résultat d'erreur.
Les branches sont examinées dans l'ordre, comme les clauses de fonction.
Vous n'avez pas à modifier les branches de propagation des erreurs.

```elixir
defmodule Parser do
  # L'entrée publique exige que tous les tokens soient consommés.
  def parse(tokens) do
    case expr(tokens) do
      {:ok, arbre, []} -> {:ok, arbre}
      {:ok, _arbre, reste} -> {:error, :tokens_restants, reste}
      erreur -> erreur
    end
  end

  # Une expression commence par un terme, puis accepte des additions.
  def expr(tokens) do
    case term(tokens) do
      {:ok, gauche, reste} -> expr_suite(gauche, reste)
      erreur -> erreur
    end
  end

  def expr_suite(gauche, [:plus | suite]) do
    case term(suite) do
      {:ok, droite, reste} ->
        # E3 : construire le nouveau nœud d'addition.
        arbre = nil
        expr_suite(arbre, reste)
      erreur -> erreur
    end
  end

  def expr_suite(gauche, reste) do
    # E2 : succès avec l'arbre construit et les tokens non consommés.
    nil
  end

  # Un terme commence par un facteur, puis accepte des multiplications.
  def term(tokens) do
    case factor(tokens) do
      {:ok, gauche, reste} -> term_suite(gauche, reste)
      erreur -> erreur
    end
  end

  def term_suite(gauche, [:multiply | suite]) do
    case factor(suite) do
      {:ok, droite, reste} ->
        # E3 : construire le nouveau nœud de multiplication.
        arbre = nil
        term_suite(arbre, reste)
      erreur -> erreur
    end
  end

  def term_suite(gauche, reste) do
    # E2 : succès avec l'arbre construit et les tokens non consommés.
    nil
  end

  def factor([{:int, nombre} | reste]) do
    # E2 : la feuille de notre AST est l'entier lui-même.
    nil
  end

  def factor([:lparen | suite]) do
    # E4 : fourni, à tracer et à expliquer.
    case expr(suite) do
      {:ok, arbre, [:rparen | reste]} -> {:ok, arbre, reste}
      {:ok, _arbre, reste} -> {:error, :parenthese_fermante_attendue, reste}
      erreur -> erreur
    end
  end

  def factor(tokens) do
    {:error, :facteur_attendu, tokens}
  end
end
```

Après avoir complété E2, évaluez la cellule du module puis ces vérifications :

```elixir
if Parser.factor([{:int, 12}, :plus, {:int, 3}]) != {:ok, 12, [:plus, {:int, 3}]} do
  raise "Un facteur entier consomme un token et conserve tous les autres."
end
if Parser.parse([{:int, 12}]) != {:ok, 12} do
  raise "Les fins de term et expr doivent conserver l'arbre entier."
end
if Parser.parse([{:int, 12}, {:int, 3}]) != {:error, :tokens_restants, [{:int, 3}]} do
  raise "Un second entier sans opérateur ne doit pas disparaître."
end
IO.puts("E2 : feuille, fins de parcours et reste vérifiés")
```

Pourquoi `factor` peut-il réussir avec un reste, alors que `parse` le refuse ?
Quelle est la différence entre consommer un entier et reconnaître une
expression entière ?

## E3 — Faire respecter la priorité (40 min)

Revenez aux **deux emplacements E3** du même module. Dans `expr_suite`,
construisez un nœud d'addition avec `gauche` et `droite`. Dans `term_suite`,
construisez le nœud de multiplication. Le nouvel arbre devient l'argument
du prochain appel : il accumule la partie de l'expression déjà reconnue.

Les appels de lecture sont fournis. Observez surtout que l'addition appelle
`term(suite)` pour lire toute la multiplication qui pourrait suivre.

```elixir
for {texte, attendu} <- [
  {"1 + 2 * 3", {:plus, 1, {:multiply, 2, 3}}},
  {"2 * 3 + 4", {:plus, {:multiply, 2, 3}, 4}},
  {"12+3*4", {:plus, 12, {:multiply, 3, 4}}},
  {"1 + 2 + 3", {:plus, {:plus, 1, 2}, 3}},
  {"2 * 3 * 4", {:multiply, {:multiply, 2, 3}, 4}}
] do
  {:ok, tokens} = Lexer.lex(texte)
  if Parser.parse(tokens) != {:ok, attendu} do
    raise "Vérifiez l'arbre de #{inspect(texte)}, pas seulement sa valeur."
  end
end
IO.puts("E3 : priorités et association à gauche vérifiées")
```

Comparez les arbres de `1 + 2 + 3` et de `1 + (2 + 3)` à la main.
Leur valeur est identique, mais leur structure diffère. Notre parcours
associe les opérations successives à gauche : l'arbre déjà construit devient
la branche gauche du nœud suivant. Cette différence sera visible dans le
résultat si nous ajoutons plus tard la soustraction.

## E4 — Revenir des parenthèses et expliquer les erreurs (35 min)

La clause de `factor` qui reconnaît `:lparen` est fournie. Elle consomme
l'ouverture, appelle `expr` sur la suite, puis exige `:rparen` dans le
reste renvoyé. Le contenu devient directement l'arbre du facteur : les
parenthèses ont fixé sa structure, elles ne deviennent pas un nœud d'AST.

Avant d'exécuter, tracez sur papier les tokens consommés pour `(1 + 2) * 3`.
Qui consomme `:lparen` ? Qui conserve `:rparen` ? Qui finit par le consommer ?

```elixir
for {texte, attendu} <- [
  {"(1 + 2) * 3", {:ok, {:multiply, {:plus, 1, 2}, 3}}},
  {"((12))", {:ok, 12}},
  {"(1 + 2) * 3 + 4", {:ok, {:plus, {:multiply, {:plus, 1, 2}, 3}, 4}}},
  {"1 + (2 + 3)", {:ok, {:plus, 1, {:plus, 2, 3}}}},
  {"", {:error, :facteur_attendu, []}},
  {"1 +", {:error, :facteur_attendu, []}},
  {"1 + * 2", {:error, :facteur_attendu, [:multiply, {:int, 2}]}},
  {"(1 + 2", {:error, :parenthese_fermante_attendue, []}},
  {"()", {:error, :facteur_attendu, [:rparen]}},
  {"1)", {:error, :tokens_restants, [:rparen]}},
  {"1 2", {:error, :tokens_restants, [{:int, 2}]}},
  {"1 - 2", {:error, :tokens_restants, [:minus, {:int, 2}]}},
  {"4 / 2", {:error, :tokens_restants, [:divide, {:int, 2}]}}
] do
  {:ok, tokens} = Lexer.lex(texte)
  if Parser.parse(tokens) != attendu do
    raise "Vérifiez le résultat complet de #{inspect(texte)} et son reste."
  end
end
IO.puts("E4 : parenthèses, erreurs et tokens restants vérifiés")
```

Les erreurs de la cellule précédente ont un reste en **tokens**, car le
parser travaille sur des tokens. Une erreur du lexer garde du **texte** :
les deux étapes ne reçoivent pas la même donnée.

```elixir
for {texte, attendu} <- [
  {"1 + é", {:error, :symbole_inconnu, "é"}},
  {"12x + 3", {:error, :symbole_inconnu, "x + 3"}},
  {"1\t+\r\n2", {:ok, [{:int, 1}, :plus, {:int, 2}]}}
] do
  if Lexer.lex(texte) != attendu do
    raise "Une erreur lexicale doit conserver le suffixe fautif."
  end
end
IO.puts("E4 : distinction entre lexing et parsing vérifiée")
```

Expliquez le refus de `1 2` et de `1)`. Pour `(1 + 2`, quelle fermeture
manque-t-il ? Sur `1 + é`, pourquoi n'appelons-nous pas le parser ?

## E5 — Relier les trois étapes et faire le bilan (25 min)

Sur une entrée valide, nous pouvons maintenant enchaîner explicitement
les trois étapes. Cette cellule est fournie ; elle s'évalue une fois le
parser et l'évaluateur complétés :

```elixir
texte = "(12 + 3) * 4"
{:ok, tokens} = Lexer.lex(texte)
{:ok, arbre} = Parser.parse(tokens)
valeur = CalculAST.eval(arbre)
{tokens, arbre, valeur}
```

La valeur finale doit être `60`. Vérifiez aussi l'expression de la démo :

```elixir
{:ok, tokens_demo} = Lexer.lex("(1 + 2) * 3 + 4")
{:ok, arbre_demo} = Parser.parse(tokens_demo)
if CalculAST.eval(arbre_demo) != 13 do
  raise "L'expression de la démo doit valoir 13."
end
IO.puts("E5 : lexer, parser et évaluation reliés")
```
 Les appariements `{:ok, ...} = ...`
supposent ici une entrée valide ; pour les essais invalides, appelez
séparément le lexer ou le parser comme en E4, sans forcer un succès.

Ajoutez une cellule de code avec **deux expressions personnelles** :
choisissez une expression valide qui combine priorité et parenthèses,
puis une expression invalide. Indiquez les résultats attendus avant
d'exécuter les étapes utiles et de les vérifier.

Complétez ensuite cette cellule de texte :

1. Donnez les tokens, l'AST et la valeur de `1 + 2 * 3`. Qu'apporte chaque étape ?
2. Expliquez pourquoi `term` est appelé avant de construire un nœud d'addition.
3. Tracez les appels utiles sur `(1 + 2) * 3`, avec le reste à chaque retour.
4. Que représente `gauche` dans `expr_suite` ? Pourquoi les tokens ne sont-ils
   pas consommés de nouveau à l'infini ?
5. Décrivez une erreur ou une hésitation et la vérification qui vous a aidé.

Sauvegardez vos essais dans `entrainement/`. Les durées sont des repères
pour un travail facultatif ; ce laboratoire ne définit pas le déroulé AP3.

## Pour aller plus loin, facultatif

Dans une copie `ParserEtendu` et `CalculEtendu`, ajoutez d'abord `-` au même
niveau que `+`, puis `/` au même niveau que `*`. Gardez les modules du socle
pour relancer leurs vérifications, notamment celles qui refusent ces signes.
Le lexer les reconnaît déjà.

Vérifiez `10 - 3 - 2` : il doit valoir `5`, avec l'arbre
`{:minus, {:minus, 10, 3}, 2}`. Vérifiez aussi `12 / 3 / 2` : la division
Elixir `/` donne ici `2.0`. Définissez le comportement de votre extension
pour une division par zéro ; le moins unaire reste hors de ce contrat.
Vous pouvez aussi choisir de dessiner ou d'afficher la trace de construction
d'un arbre. L'extension reste facultative, comme l'ensemble du laboratoire.

## Sauvegarder

Conservez ce fichier dans `entrainement/`. Les étapes `ap3-01` à `ap3-04`
constituent la progression de compilation d'AP3. Je préciserai en cours
les notebooks à terminer pour le rendu unique du cycle. Ce laboratoire reste
un complément facultatif, que vous pouvez joindre pour un bonus.

Avant de conclure, relancez toutes les cellules depuis une session neuve.
Si une partie reste incomplète, conservez votre tentative et décrivez le
souci dans le bilan. Pour toute question, vous pouvez me contacter par email :
[aurelien.noce@minesparis.psl.eu](mailto:aurelien.noce@minesparis.psl.eu).