Sheerka/docs/FEAT-021-sya-concepts-parser-fr.md

SyaConceptsParser

Purpose

SyaConceptsParser parse des séquences de concepts avec paramètres (variables). Il complète SimpleConceptsParser qui, lui, ne gère que les concepts sans paramètres.

Exemples de concepts reconnus :

• a plus b → reconnaît 1 plus 2, x plus y plus z, etc.
• if a then b end → reconnaît if x > 0 then print x end
• a long named concept b → reconnaît 1 long named concept 2

Le cas fondamental visé est la composition de concepts : 1 plus 2 times 3, où times doit être évalué avant plus. C'est ce problème de précédence que résout le Shunting Yard Algorithm.

---

Le Shunting Yard Algorithm (SYA)

Algorithme de Dijkstra (1961) qui convertit une expression en notation infixe (1 + 2 * 3) en notation polonaise inverse (RPN : 1 2 3 * +), en respectant la précédence des opérateurs.

Principe

Deux structures : un stack d'opérateurs et une queue de sortie.

Entrée : 1  +  2  *  3

         ┌──────────────────────────────────────────────┐
Token    │ Action                  Stack      Sortie    │
─────────┼──────────────────────────────────────────────┤
1        │ → sortie               []         [1]        │
+        │ → stack                [+]        [1]        │
2        │ → sortie               [+]        [1, 2]     │
*        │ prec(*) > prec(+)      [+, *]     [1, 2]     │
         │ → stack (pas de pop)              [1, 2]     │
3        │ → sortie               [+, *]     [1, 2, 3]  │
fin      │ vider stack            []         [1, 2, 3, *, +] │
└──────────────────────────────────────────────────────┘

RPN : 1 2 3 * +  ≡  1 + (2 * 3)

Règle de pop

Quand on empile un opérateur op, on dépile d'abord tout opérateur top tel que : précédence(top) >= précédence(op)

Cela garantit que les opérateurs de haute précédence sont évalués en premier.

---

Adaptation dans Sheerka

Le SYA original travaille sur des tokens atomiques (chiffres, +, *). Sheerka l'adapte pour travailler sur des concepts qui :

1. S'identifient par plusieurs tokens — un concept comme if a then b end contient plusieurs mots-clés (if, then, end) entrelacés avec des paramètres. L'algorithme original reconnaît un opérateur en un seul token.

2. Peuvent contenir N paramètres — un opérateur binaire a exactement 2 opérandes. Un concept Sheerka peut en avoir 0, 1, 2 ou plus.

3. Les paramètres peuvent eux-mêmes être des concepts — dans 1 plus 2 times 3, le paramètre b de plus est le résultat du concept times. La récursion est gérée par l'imbrication des workflows.

Correspondance SYA ↔ Sheerka

SYA original	Sheerka
Opérateur (+, *)	ConceptToRecognize (concept avec paramètres)
Opérande (nombre, variable)	UnrecognizedToken ou ConceptToken
Stack d'opérateurs	state_context.stack
Queue de sortie	state_context.parameters
Précédence	InitConceptParsing.must_pop()
Résultat RPN	MetadataToken dans state_context.result

Différences structurelles

Reconnaissance multi-tokens — là où SYA lit un token pour identifier *, Sheerka doit lire long named concept (3 tokens) pour identifier le concept a long named concept b. La classe ReadConcept gère cette lecture séquentielle.

Structure expected — le concept if a then b end est décomposé en segments :

[("if ", 0), (" then ", 1), (" end", 1)]
 ────────     ──────────     ──────────
 keyword      keyword        keyword
 0 params     1 param        1 param
 avant        avant          avant

Chaque segment indique combien de paramètres précèdent ce groupe de tokens, et quels tokens consommer pour valider ce segment.

Précédence non encore implémentée — must_pop() retourne toujours False. La composition de concepts n'est donc pas encore active. C'est la prochaine étape d'implémentation.

---

Architecture

Deux workflows interdépendants

graph TD
    A[#tokens_wkf] -->|concept keyword found| B[#concept_wkf]
    B -->|concept fully parsed| A
    A -->|EOF| C[end]

Le parser démarre toujours dans #tokens_wkf. À chaque fois qu'un mot-clé correspondant au premier token d'un concept est détecté, un fork est créé et envoyé dans #concept_wkf. Une fois le concept reconnu, on revient dans #tokens_wkf pour continuer la lecture.

---

Workflow #tokens_wkf

stateDiagram-v2
    [*] --> start
    start --> prepare_read_tokens
    prepare_read_tokens --> read_tokens
    read_tokens --> read_tokens : no concept found (loop)
    read_tokens --> eof : EOF
    read_tokens --> concepts_found : concept keyword detected (fork)
    eof --> end : ManageUnrecognized
    concepts_found --> concept_wkf : ManageUnrecognized → #concept_wkf
    end --> [*]

PrepareReadTokens : initialise le buffer et mémorise buffer_start_pos.

ReadTokens : lit un token, consulte get_metadata_from_first_token. Si un concept peut démarrer à ce token → fork avec un clone du contexte où concept_to_recognize est renseigné. Le chemin principal continue à lire.

ManageUnrecognized("concepts found") : traite le buffer accumulé avant le mot-clé (via SimpleConceptsParser). Les tokens non reconnus deviennent UnrecognizedToken et sont ajoutés à parameters.

---

Workflow #concept_wkf

stateDiagram-v2
    [*] --> start
    start --> init_concept_parsing
    init_concept_parsing --> manage_parameters

    manage_parameters --> read_concept

    read_concept --> read_parameters : more segments
    read_concept --> finalize_concept : all segments done
    read_concept --> token_mismatch : token mismatch
    read_concept --> error_eof : unexpected EOF

    read_parameters --> manage_parameters : loop
    read_parameters --> finalize_concept : EOF

    finalize_concept --> tokens_wkf : #tokens_wkf
    token_mismatch --> end
    error_eof --> end
    end --> [*]

InitConceptParsing :

• Vérifie que le nombre de paramètres déjà collectés est suffisant
• Retire le premier token du segment (déjà consommé par ReadTokens)
• Applique le SYA : empile le concept sur le stack

ReadConcept : lit les tokens fixes du segment courant un par un. Si tous correspondent → pop(0) du segment et continue.

ReadParameters : lit UN token dans le buffer. Revient à ManageUnrecognized qui tente de le reconnaître via SimpleConceptsParser.

FinalizeConceptParsing :

• Dépile le concept du stack
• Calcule start (depuis le premier paramètre) et end (position courante)
• Crée un MetadataToken(concept.metadata, start, end, resolution_method, "sya")
• Vide stack et parameters
• Retourne à #tokens_wkf

---

Exemple pas à pas — "1 plus 2"

Concept défini : a plus b (variables a, b).

Tokens :

pos :  0    1      2       3    4    5
tok : "1"  " "  "plus"   " "  "2"  EOF

expected pour ce concept :

[([" ", "plus", " "], 1), ([], 1)]
   segment 0 → 1 param avant, lire " plus "
   segment 1 → 1 param avant, lire rien (concept se termine par un param)

Déroulé :

PrepareReadTokens  → buffer_start_pos = 0

ReadTokens "1"    → no concept, buffer = ["1"]
ReadTokens " "    → no concept, buffer = ["1", " "]
ReadTokens "plus" → concept "a plus b" trouvé !

  ┌── FORK ──────────────────────────────────────────────────────┐
  │ clone: buffer=["1"," "], pos=2, concept_to_recognize=CTR(+)  │
  └──────────────────────────────────────────────────────────────┘

ManageUnrecognized("concepts found")
  buffer = ["1"," "] → SimpleConceptsParser → not found
  parameters = [UT("1 ", start=0, end=1)]
  buffer_start_pos = 3
  → #concept_wkf

InitConceptParsing
  expected[0] = ([" ","plus"," "], 1)
  need 1 param → have 1 ✓
  strip leading WS → ["plus"," "]
  pop "plus" (déjà lu) → [" "]
  SYA: stack = [CTR(a_plus_b)]

ManageUnrecognized("manage parameters") : buffer vide → rien

ReadConcept : lit [" "] → pos 3 = " " ✓
  expected.pop(0) → remaining = [([], 1)]
  → "read parameters"

ReadParameters : lit "2" (pos 4)
  buffer = ["2"]
  → "manage parameters"

ManageUnrecognized("manage parameters")
  buffer = ["2"] → not a concept
  parameters = [UT("1 ", 0, 1), UT("2", 3, 3)]
  buffer_start_pos = 5

ReadConcept : expected = [([], 1)], lit 0 tokens
  expected.pop(0) → empty → "finalize concept"

FinalizeConceptParsing
  concept = stack.pop() = CTR(a_plus_b)
  start   = parameters[0].start = 0
  end     = parser_input.pos    = 4
  result.append(MetadataToken(metadata, 0, 4, "key", "sya"))
  → #tokens_wkf

ReadTokens → EOF → ManageUnrecognized("eof") → end

Résultat :

MultipleChoices([
    [MetadataToken(id="1001", start=0, end=4, resolution_method="key", parser="sya")]
])

---

Exemple — séquence "1 plus 2 3 plus 7"

Même concept a plus b. Le parser reconnaît deux concepts successifs dans un seul passage.

pos :  0    1      2       3    4    5    6    7      8       9    10   11
tok : "1"  " "  "plus"   " "  "2"  " "  "3"  " "  "plus"   " "  "7"  EOF

Après FinalizeConceptParsing du premier concept (pos=4), #tokens_wkf repart :

PrepareReadTokens   → buffer_start_pos = 5
ReadTokens " "      → buffer = [" "]
ReadTokens "3"      → buffer = [" ","3"]
ReadTokens " "      → buffer = [" ","3"," "]
ReadTokens "plus"   → fork

ManageUnrecognized  → UT(" 3 ", start=5, end=7), buffer_start_pos=9
...
FinalizeConceptParsing
  start = 5, end = 10
  result.append(MetadataToken(1001, 5, 10, "key", "sya"))

Résultat final (un seul path, deux concepts) :

MultipleChoices([
    [
        MetadataToken(1001, start=0,  end=4,  parser="sya"),
        MetadataToken(1001, start=5,  end=10, parser="sya"),
    ]
])

---

Exemple futur — composition "1 plus 2 times 3"

Note : cet exemple nécessite l'implémentation de must_pop(). Aujourd'hui must_pop() retourne toujours False.

Concepts : a plus b (basse précédence), a times b (haute précédence).

Comportement attendu après implémentation :

Expression :  1  plus  2  times  3

SYA avec précédence times > plus :

Token "1"      → parameters = [1]            stack = []
Token "plus"   → stack = [plus]              parameters = [1]
Token "2"      → parameters = [1, 2]        stack = [plus]
Token "times"  → prec(times) > prec(plus) → pas de pop
                  stack = [plus, times]      parameters = [1, 2]
Token "3"      → parameters = [1, 2, 3]     stack = [plus, times]

Finalize :
  pop "times" → MetadataToken(times, params=[2, 3])
  pop "plus"  → MetadataToken(plus,  params=[1, times_result])

Ce que must_pop() doit implémenter :

def must_pop(self, current_concept, top_of_stack_concept):
    return precedence(top_of_stack_concept) >= precedence(current_concept)

Sans cette règle, les deux concepts seraient traités de gauche à droite avec la même précédence, ce qui donnerait (1 plus 2) times 3 au lieu de 1 plus (2 times 3).

---

Structure expected en détail

Pour le concept if a then b end (clé "if __var__0 then __var__1 end") :

_get_expected_tokens("if __var__0 then __var__1 end")

→ [
    (["if", " "],        0),   # lire "if " avant le 1er param
    ([" ", "then", " "], 1),   # lire " then " avant le 2ème param
    ([" ", "end"],       1),   # lire " end" avant le 3ème... non, 1 param avant
  ]

Pendant le parsing, expected est modifié en place :

• InitConceptParsing retire le premier token du segment 0 (déjà lu par ReadTokens)
• ReadConcept consomme les tokens du segment courant puis fait pop(0)
• Quand expected est vide → FinalizeConceptParsing

---

Structures de données clés

StateMachineContext

StateMachineContext
├── parser_input         ParserInput       flux de tokens + curseur
├── other_parsers        [SimpleConceptsParser]
├── buffer               list[Token]       tokens en attente de classification
├── buffer_start_pos     int               position de début du buffer courant
├── concept_to_recognize ConceptToRecognize | None
├── stack                list[CTR]         SYA — stack d'opérateurs
├── parameters           list[UT|CT]       SYA — queue de sortie
├── result               list[MetadataToken]
└── errors               list

MetadataToken (sortie)

MetadataToken
├── metadata          ConceptMetadata   (id, name, key, variables, ...)
├── start             int               position du 1er token de l'expression
├── end               int               position du dernier token
├── resolution_method "key" | "name" | "id"
└── parser            "sya"

Positions dans "1 plus 2" :

"1 plus 2"
 0 1  2   3 4
 │ │  │   │ │
 1 _  plus _ 2

MetadataToken : start=0, end=4

---

Différences avec SimpleConceptsParser

	SimpleConceptsParser	SyaConceptsParser
Concepts ciblés	Sans paramètres	Avec paramètres
concept_wkf	2 états	8 états
Contenu de result	MetadataToken + UnrecognizedToken	MetadataToken uniquement
Paramètres	N/A	Collectés dans parameters
Parser tag	"simple"	"sya"
SYA	Non	Oui (précédence à implémenter)

---

Gestion des erreurs

Erreur	Cause	État atteint
UnexpectedToken	Token lu ≠ token attendu du concept	TokenMismatch → end
UnexpectedEof	Fin de l'entrée avant fin du concept	ErrorEof → end
NotEnoughParameters	Pas assez de params avant un segment	Exception levée

Les erreurs sont collectées depuis tous les paths et transmises à error_sink dans parse(). Un path avec erreurs est exclu de _select_best_paths.