# Laboratoire facultatif — Un lexer arithmétique

## Écrire un lexer avec les briques d'AP1

Dans ce laboratoire indépendant, nous construisons un *lexer* : une fonction qui lit
un texte et produit une liste de *tokens*, c'est-à-dire des étiquettes pour
les opérateurs, les parenthèses et les nombres. Par ex., `"12 + 3"`
deviendra `[{:int, 12}, :plus, {:int, 3}]`.

Ce notebook est autonome. Nous réutilisons les fonctions, les clauses,
la récursion, les accumulateurs et les préfixes `<>` d'AP1. Nous avançons
par étapes, avec des vérifications à chaque fois.

Ce laboratoire reprend un langage réduit aux **entiers** pour détailler
le parcours du lexer. Le langage principal d'AP2 utilise des flottants,
des variables et des conditionnelles dans les cinq ateliers numérotés d’AP2.
Vous pouvez choisir ce complément après le socle ; il n'ajoute aucun rendu.
Les durées indiquées sont des repères pour un travail facultatif.

Évaluez les cellules dans l'ordre. Remplacez les `nil` à compléter, puis
lancez les vérifications fournies. Si une vérification échoue, reprenez le
cas indiqué et réévaluez votre code. Dans les vérifications,
`for {texte, attendu} <- liste do … end` parcourt chaque couple de la liste,
et `if … do raise … end` arrête la cellule avec un message si un cas échoue.
Ce sont des outils fournis, que vous n'avez pas à réécrire.

## E1 — Reconnaître un opérateur isolé (15 min)

Commençons avec une chaîne qui contient exactement un opérateur.
`Operateur.lex/1` renvoie l'atome correspondant : `+` donne `:plus`,
`-` donne `:minus`, `*` donne `:multiply` et `/` donne `:divide`.
Complétez les trois clauses manquantes. La clause d'erreur est fournie.

```elixir
defmodule Operateur do
  def lex("+") do
    :plus
  end

  def lex("-") do
    nil
  end

  def lex("*") do
    nil
  end

  def lex("/") do
    nil
  end

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

Prédisez le résultat pour `"+-"`. Deux symboles reconnus séparément
forment-ils une entrée reconnue par cette fonction ?

```elixir
for {texte, attendu} <- [
  {"+", :plus}, {"-", :minus}, {"*", :multiply}, {"/", :divide},
  {"+-", {:error, :symbole_inconnu, "+-"}},
  {"", {:error, :symbole_inconnu, ""}},
  {"x", {:error, :symbole_inconnu, "x"}}
] do
  if Operateur.lex(texte) != attendu do
    raise "E1 : vérifiez la clause choisie pour #{inspect(texte)}."
  end
end
IO.puts("E1 : opérateurs isolés vérifiés")
```

Votre explication pour `"+-"` : …

## E2 — Parcourir plusieurs symboles (40 min)

Nous allons maintenant consommer un préfixe, puis poursuivre sur le reste.
`Symboles.lex/1` démarre le parcours avec la liste vide comme accumulateur.
Le résultat est `{:ok, tokens}` en cas de succès. En cas d'échec, il est
`{:error, :symbole_inconnu, reste}`, où `reste` commence au premier symbole
que nous n'avons pas reconnu.

À chaque opérateur, ajoutez son token en tête de `acc` avec `[token | acc]`.
Ajoutez aussi les parenthèses : `(` donne `:lparen` et `)` donne `:rparen`.
Les clauses fournies pour l’espace, la tabulation `"\t"`, le saut de
ligne `"\n"` et le retour chariot `"\r"` poursuivent le parcours sans
ajouter de token. Les fins de ligne Windows `"\r\n"` sont ainsi acceptées.

Comme nous ajoutons en tête, l'accumulateur est construit à l'envers :

```text
parcourir("+-*", [])
parcourir("-*",  [:plus])
parcourir("*",   [:minus, :plus])
parcourir("",    [:multiply, :minus, :plus])
```

L'appel fourni `Enum.reverse(acc)` remet la liste dans l'ordre une seule
fois, à la fin. Par ex., `Enum.reverse([3, 2, 1])` renvoie `[1, 2, 3]`.
Nous utilisons cette fonction comme un outil ; le reste du parcours repose
sur les clauses et la récursion.

Complétez les clauses marquées `nil`, y compris celle du symbole inconnu.

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

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

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

  def parcourir("-" <> reste, acc) do
    nil
  end

  def parcourir("*" <> reste, acc) do
    nil
  end

  def parcourir("/" <> reste, acc) do
    nil
  end

  def parcourir("(" <> reste, acc) do
    nil
  end

  def parcourir(")" <> reste, acc) do
    nil
  end

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

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

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

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

  def parcourir(texte, _acc) do
    nil
  end
end
```

Vérification fournie :

```elixir
for {texte, attendu} <- [
  {"+-*/", {:ok, [:plus, :minus, :multiply, :divide]}},
  {" ( + ) * - / ", {:ok, [:lparen, :plus, :rparen, :multiply, :minus, :divide]}},
  {"+\t-\r\n*", {:ok, [:plus, :minus, :multiply]}},
  {"", {:ok, []}},
  {" \t\n", {:ok, []}},
  {"+x*", {:error, :symbole_inconnu, "x*"}},
  {"(é)", {:error, :symbole_inconnu, "é)"}},
  {"12+", {:error, :symbole_inconnu, "12+"}},
  {")(", {:ok, [:rparen, :lparen]}}
] do
  if Symboles.lex(texte) != attendu do
    raise "E2 : vérifiez les tokens, leur ordre et le reste pour #{inspect(texte)}."
  end
end
IO.puts("E2 : suite de symboles vérifiée")
```

Complétez cette cellule de texte :

1. Tracez les appels pour `Symboles.lex(" - + ")`, espaces compris.
2. Que représente `acc` ? Que renverrait le programme sans `Enum.reverse` ?
3. Pourquoi `"12+"` échoue-t-il ? Quelle brique manque-t-il ?
4. Pourquoi `")("` est-il accepté ? Notre lexer reconnaît des symboles ;
   il ne vérifie pas encore qu'ils forment une expression correcte.

## E3 — Reconnaître les nombres (35 min)

La fonction [Integer.parse/1](https://hexdocs.pm/elixir/Integer.html#parse/2)
lit un entier au début d'une chaîne. Elle renvoie `{nombre, reste}` en cas
de succès, et `:error` si elle ne peut pas commencer. Évaluez ces exemples :

```elixir
{
  Integer.parse("123+4"),
  Integer.parse("7"),
  Integer.parse("x+4")
}
```

Nous obtenons `{{123, "+4"}, {7, ""}, :error}`. Ainsi, il faut poursuivre
le parcours sur le reste après avoir ajouté `{:int, nombre}` aux tokens.

Le module `Lexer` reprend les clauses de E2, fournies ci-dessous pour
concentrer votre travail sur cette nouvelle étape. Sa dernière clause
appelle `Integer.parse`, puis transmet son résultat à `lire_nombre/3`.
Complétez les deux clauses de cette fonction : un motif pour le tuple de
succès, un motif pour l'atome d'échec. L'argument `texte` conserve le suffixe
original afin de pouvoir le rendre dans le résultat d'erreur.

Notre langage utilise des entiers décimaux **non signés**. Les clauses des
opérateurs sont placées avant la lecture des nombres : `"-3"` produit donc
`[:minus, {:int, 3}]`, et non un entier négatif. Nous ne traitons ni les
variables ni les nombres décimaux à virgule ou à point.

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

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

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

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

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

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

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

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

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

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

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

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

  def parcourir(texte, acc) do
    lire_nombre(Integer.parse(texte), texte, acc)
  end

  def lire_nombre({nombre, reste}, _texte, acc) do
    # Ajoutez {:int, nombre} en tête de acc, puis poursuivez sur reste.
    nil
  end

  def lire_nombre(:error, texte, _acc) do
    # Gardez tout le texte que Integer.parse n'a pas pu commencer à lire.
    nil
  end
end
```

Vérification fournie. Le lexer conserve l'ordre des tokens ; les
parenthèses sont reconnues mais leur équilibre n'est pas encore vérifié.

```elixir
for {texte, attendu} <- [
  {"12 + 34 * 5", {:ok, [{:int, 12}, :plus, {:int, 34}, :multiply, {:int, 5}]}},
  {"(1+2)*3+4", {:ok, [:lparen, {:int, 1}, :plus, {:int, 2}, :rparen, :multiply, {:int, 3}, :plus, {:int, 4}]}},
  {"20-3/2", {:ok, [{:int, 20}, :minus, {:int, 3}, :divide, {:int, 2}]}},
  {"-3", {:ok, [:minus, {:int, 3}]}},
  {"+12", {:ok, [:plus, {:int, 12}]}},
  {"0 007", {:ok, [{:int, 0}, {:int, 7}]}},
  {"12\t+\r\n3", {:ok, [{:int, 12}, :plus, {:int, 3}]}},
  {"", {:ok, []}},
  {"  ", {:ok, []}},
  {"1.5+2", {:error, :symbole_inconnu, ".5+2"}},
  {"12 + x * 3", {:error, :symbole_inconnu, "x * 3"}},
  {"12+é)", {:error, :symbole_inconnu, "é)"}},
  {"(1+2", {:ok, [:lparen, {:int, 1}, :plus, {:int, 2}]}},
  {"3 4 +", {:ok, [{:int, 3}, {:int, 4}, :plus]}}
] do
  if Lexer.lex(texte) != attendu do
    raise "E3 : vérifiez les tokens ou le suffixe d'erreur pour #{inspect(texte)}."
  end
end
IO.puts("E3 : lexer avec entiers vérifié")
```

## Bilan du laboratoire

Vous pouvez ensuite utiliser une liste de tokens pour faire fonctionner un
petit langage à pile, dans `ap2-pile.livemd`. Ce sera un atelier autonome,
à conserver dans `entrainement/`.

Pour approfondir, complétez cette cellule de texte et les cas personnels :

1. Tracez les appels de `Lexer.lex("12-3")`. Indiquez le texte restant et
   l'accumulateur, ainsi que le résultat de chaque appel à `Integer.parse`.
2. Sur `"12+é)"`, que contient le reste de l'erreur ? Pourquoi faut-il
   le conserver plutôt que de renvoyer la liste partielle de tokens ?
3. Quelle différence faites-vous entre reconnaître des tokens et vérifier
   une expression ? Appuyez-vous sur `"(1+2"` et sur `"3 4 +"`.
4. Ajoutez trois cas personnels dans une cellule de code : un avec un
   entier de plusieurs chiffres, un qui vérifie l'ordre des tokens,
   et un invalide. Écrivez les résultats attendus avant d'exécuter.
5. Décrivez une erreur ou une hésitation et la manière dont vous l'avez
   résolue. Conservez une tentative commentée si elle vous aide à l'expliquer.

## Sauvegarder

Conservez ce laboratoire dans `entrainement/`. Pour le rendu unique du cycle,
les notebooks et les cellules à rendre seront précisés en cours, selon notre
avancement. Vous pouvez joindre ce complément dans `AP2/` pour un bonus, sans
obligation supplémentaire. Si un bout de syntaxe Elixir vous manque, les
[fiches de référence](https://ap-2026.noce.fr/reference/) se consultent au besoin.

Pour toute question, vous pouvez me contacter par email :
[aurelien.noce@minesparis.psl.eu](mailto:aurelien.noce@minesparis.psl.eu).