434 lines
14 KiB
Markdown
434 lines
14 KiB
Markdown
# 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
|
|
|
|
```mermaid
|
|
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`
|
|
|
|
```mermaid
|
|
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`
|
|
|
|
```mermaid
|
|
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 :**
|
|
```python
|
|
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`.
|