#!/usr/bin/env python3 """Automates de langages algébriques à opérateurs partagés et règles-motifs.""" from __future__ import annotations from dataclasses import dataclass, field from itertools import product import math import random import re from typing import Iterator, Mapping ID = re.compile(r"[^\W\d]\w*|_\w*", re.UNICODE) VAR = re.compile(r"([^\W\d]\w*|_\w*?)([1-9]\d*)", re.UNICODE) QUALIFIE = re.compile(r"([^\W\d]\w*|_\w*)_([^\W\d]\w*|_\w*)", re.UNICODE) @dataclass(frozen=True) class Arbre: """Terme concret gardant l'identité canonique de chaque opérateur. ``contexte`` indique le langage dans lequel le sous-terme a été produit. ``affichage`` est calculé seulement pour les résultats destinés à l'utilisateur et n'intervient ni dans l'égalité ni dans le hachage. """ nom: str arguments: tuple["Arbre", ...] = () cle_operateur: tuple[str | None, str] | None = None contexte: str | None = field(default=None, compare=False, hash=False) affichage: str | None = field(default=None, compare=False, hash=False) rendu_complet: str | None = field(default=None, compare=False, hash=False) @property def taille(self) -> int: return 1 + sum(a.taille for a in self.arguments) @property def profondeur(self) -> int: return 0 if not self.arguments else 1 + max(a.profondeur for a in self.arguments) def __str__(self) -> str: if self.rendu_complet is not None: return self.rendu_complet nom = self.affichage or self.nom if not self.arguments: return nom return f"{nom}({','.join(map(str, self.arguments))})" @dataclass(frozen=True) class Operateur: """Objet opérateur canonique du système. ``proprietaire`` vaut le nom du langage qui a introduit l'opérateur, ou ``None`` lorsque l'opérateur est une pièce extérieure à tous les langages du système. """ proprietaire: str | None nom: str arite: int | None arite_minimale: int = 0 @property def est_piece(self) -> bool: return self.proprietaire is None @property def est_variadique(self) -> bool: return self.arite is None def accepte_arite(self, arite: int) -> bool: return arite >= self.arite_minimale if self.est_variadique else arite == self.arite def profil_arite(self) -> str: if self.est_variadique: return f"{self.arite_minimale}..∞" return str(self.arite) @property def nom_long(self) -> str | None: if self.proprietaire is None: return None return f"{self.proprietaire}_{self.nom}" @property def identite(self) -> tuple[str | None, str]: return self.proprietaire, self.nom @dataclass(frozen=True) class Trou: langage: str cle: str # même clé => même sous-terme @dataclass(frozen=True) class Motif: operateur: Operateur | None = None arguments: tuple["Motif", ...] = () trou: Trou | None = None @property def est_trou(self) -> bool: return self.trou is not None def texte(self, langage_courant: str) -> str: if self.est_trou: assert self.trou is not None return self.trou.langage if self.trou.cle.startswith("@") else self.trou.cle assert self.operateur is not None nom = self.operateur.nom if not self.arguments: return nom return f"{nom}({','.join(a.texte(langage_courant) for a in self.arguments)})" @dataclass(frozen=True) class Regle: langage: str motif: Motif ordre: int arite_variable_minimale: int | None = None langage_variable: str | None = None @property def operateur(self) -> Operateur | None: """Opérateur racine, ou None pour une règle d'inclusion H|--L.""" return self.motif.operateur def texte(self) -> str: if self.arite_variable_minimale is not None: assert self.motif.operateur is not None base = ["."] * self.arite_variable_minimale suffixe = "..." if self.langage_variable == self.langage else f"{self.langage_variable}.." contenu = ",".join(base + [suffixe]) return f"|--{self.motif.operateur.nom}({contenu})" return "|--" + self.motif.texte(self.langage) class SystemeLangages: def __init__(self, presentations: Mapping[str, str]): if not presentations: raise ValueError("Aucun langage n'est défini.") self.langages = tuple(presentations) for langage in self.langages: if not ID.fullmatch(langage): raise ValueError(f"Nom de langage incorrect : {langage!r}.") # Analyse syntaxique préalable de toutes les déclarations. brutes: dict[str, list[Arbre]] = {} for langage, presentation in presentations.items(): texte = presentation.strip() if not (texte.startswith("<") and texte.endswith(">")): raise ValueError(f"La présentation de {langage} doit être entre chevrons.") contenu = texte[1:-1].strip() if not contenu: raise ValueError(f"Le langage {langage} est vide.") brutes[langage] = [parse_arbre(x) for x in separer(contenu)] # 1er passage : chaque déclaration courte crée l'opérateur propre # au langage courant. Un nom long X_f désigne explicitement # l'opérateur f de X et peut l'importer dans un autre langage. self._operateurs_par_identite: dict[tuple[str | None, str], Operateur] = {} self._operateurs_par_long: dict[str, Operateur] = {} self._membres: dict[str, set[Operateur]] = {l: set() for l in self.langages} self._pieces: set[Operateur] = set() for langage in self.langages: for racine in brutes[langage]: if not racine.arguments and racine.nom in self.langages: continue if racine.nom == "." or VAR.fullmatch(racine.nom): raise ValueError( "Une règle entière ne peut pas être un trou anonyme " "ou une variable liée ; utilisez le nom d'un langage." ) variadique = extraire_arite_variadique(racine, langage, self.langages) variadique_min = None if variadique is None else variadique[0] arite_fixe = None if variadique is not None else len(racine.arguments) op = self._resoudre_ou_creer_racine( langage, racine.nom, arite_fixe, variadique_min or 0 ) self._membres[langage].add(op) # Un alias X_f désigne l'unique opérateur nommé f membre de X. # Si X possède son opérateur natif X.f, celui-ci est prioritaire. for langage_membre, membres in self._membres.items(): par_nom: dict[str, list[Operateur]] = {} for op in membres: par_nom.setdefault(op.nom, []).append(op) for nom, ops in par_nom.items(): natif = self._operateurs_par_identite.get((langage_membre, nom)) if natif in ops: self._operateurs_par_long[f"{langage_membre}_{nom}"] = natif elif len(ops) == 1: self._operateurs_par_long[f"{langage_membre}_{nom}"] = ops[0] # 2e passage : les symboles internes déjà déclarés sont résolus ; # les symboles inconnus rencontrés seulement à l'intérieur des motifs # deviennent des pièces extérieures à tous les langages. self._regles: dict[str, tuple[Regle, ...]] = {} for langage in self.langages: regles: list[Regle] = [] vus: set[tuple[Motif, int | None]] = set() for ordre, arbre in enumerate(brutes[langage]): variadique = extraire_arite_variadique(arbre, langage, self.langages) variadique_min = None if variadique is None else variadique[0] langage_variable = None if variadique is None else variadique[1] arbre_motif = arbre if variadique is not None: arbre_motif = Arbre(arbre.nom, arbre.arguments[:-1]) motif = self._convertir_motif(arbre_motif, langage, compteur=[0], est_racine=True) signature_regle = (motif, variadique_min, langage_variable) if signature_regle in vus: continue vus.add(signature_regle) regles.append(Regle(langage, motif, ordre, variadique_min, langage_variable)) self._regles[langage] = tuple(regles) self._cache: dict[tuple[str, int], tuple[Arbre, ...]] = {} self._min_taille = self._calculer_min_tailles() non_productifs = [l for l, n in self._min_taille.items() if math.isinf(n)] if non_productifs: raise ValueError("Langages non productifs : " + ", ".join(non_productifs)) self._min_profondeur = self._calculer_min_profondeurs() # ------------------------------------------------------------------ # Description # ------------------------------------------------------------------ def regles(self, langage: str) -> tuple[str, ...]: self._check(langage) return tuple(r.texte() for r in self._regles[langage]) def cles_regles(self, langage: str) -> tuple[str, ...]: """Clés complètes utilisables pour pondérer chaque règle. Exemple : ``L|--g(L1,L1)``. """ self._check(langage) return tuple(f"{langage}{r.texte()}" for r in self._regles[langage]) def operateurs(self, langage: str) -> tuple[str, ...]: """Noms courts des objets opérateurs appartenant au langage.""" self._check(langage) return tuple(sorted(op.nom for op in self._membres[langage])) def pieces(self) -> tuple[str, ...]: """Noms courts des pièces du système n'appartenant à aucun langage.""" return tuple(sorted(op.nom for op in self._pieces)) def meme_operateur(self, nom1: str, nom2: str) -> bool: """Teste l'identité de deux désignations courtes ou longues.""" return self._resoudre_nom_operateur(nom1) is self._resoudre_nom_operateur(nom2) def _nom_affiche(self, op: Operateur, contexte: str | None) -> str: """Choisit le nom court seulement lorsqu'il est non ambigu. Dans un contexte donné, le nom court est conservé s'il se résout précisément vers cet opérateur. Sinon le nom long de l'opérateur est nécessaire. Les pièces extérieures gardent toujours leur nom simple. """ if op.est_piece or contexte is None: return op.nom try: resolu = self._resoudre_nom_operateur(op.nom, contexte) except ValueError: resolu = None if resolu is op: return op.nom return op.nom_long or op.nom def _preparer_affichage(self, arbre: Arbre, contexte: str | None = None) -> Arbre: """Construit une copie munie de noms non ambigus pour l'affichage.""" # Tous les noms d'un terme sont écrits dans le contexte syntaxique # du terme complet. Cela force un nom long pour un sous-terme importé # dont le nom court serait interprété autrement par le parseur parent. contexte_effectif = contexte if contexte is not None else arbre.contexte if arbre.cle_operateur is None: nom_affiche = arbre.nom else: op = self._operateurs_par_identite.get(arbre.cle_operateur) nom_affiche = arbre.nom if op is None else self._nom_affiche(op, contexte_effectif) return Arbre( arbre.nom, tuple(self._preparer_affichage(a, contexte_effectif) for a in arbre.arguments), arbre.cle_operateur, contexte=contexte_effectif, affichage=nom_affiche, ) def _avec_contexte_racine(self, arbre: Arbre, contexte: str) -> Arbre: """Change seulement le contexte d'affichage de la racine. C'est nécessaire pour une règle d'inclusion comme ``H|--L`` : l'arbre interne vient de L, mais sa racine est présentée comme un terme de H. Les contextes de ses sous-termes restent inchangés. """ return Arbre( arbre.nom, arbre.arguments, arbre.cle_operateur, contexte=contexte, affichage=arbre.affichage, ) # ------------------------------------------------------------------ # Reconnaissance # ------------------------------------------------------------------ def reconnait(self, langage: str, expression: str) -> bool: try: arbre = self._canonicaliser_arbre(parse_arbre(expression), langage) return self._reconnait_arbre(langage, arbre, set()) except (SyntaxError, ValueError): return False def expliquer(self, langage: str, expression: str) -> tuple[bool, str]: try: arbre = self._canonicaliser_arbre(parse_arbre(expression), langage) except (SyntaxError, ValueError) as e: return False, str(e) if self._reconnait_arbre(langage, arbre, set()): return True, f"Terme reconnu dans {langage}, taille {arbre.taille}, profondeur {arbre.profondeur}." return False, f"L'expression n'est pas engendrée par les règles de {langage}." def analyser(self, langage: str, expression: str) -> Arbre: arbre = self._canonicaliser_arbre(parse_arbre(expression), langage) if not self._reconnait_arbre(langage, arbre, set()): raise SyntaxError(f"Terme non reconnu dans {langage} : {expression!r}.") return self._preparer_affichage(arbre, langage) def _canonicaliser_arbre(self, arbre: Arbre, langage: str) -> Arbre: # Les variables muettes restent inchangées. if not arbre.arguments and VAR.fullmatch(arbre.nom): return arbre contexte_resolution = ( None if self._decomposer_nom_long(arbre.nom) is not None else langage ) op = self._resoudre_nom_operateur(arbre.nom, contexte_resolution) if not op.accepte_arite(len(arbre.arguments)): if op.est_variadique: raise SyntaxError( f"L'opérateur {arbre.nom!r} attend au moins " f"{op.arite_minimale} argument(s)." ) raise SyntaxError(f"L'opérateur {arbre.nom!r} est d'arité {op.arite}.") return Arbre( op.nom, tuple(self._canonicaliser_arbre(a, langage) for a in arbre.arguments), op.identite, contexte=langage, ) def _reconnait_arbre(self, langage: str, arbre: Arbre, pile: set[tuple[str, Arbre]]) -> bool: self._check(langage) variable = VAR.fullmatch(arbre.nom) if not arbre.arguments and variable and variable.group(1) == langage: return True cle = (langage, arbre) if cle in pile: return False pile = pile | {cle} return any(self._accorde_regle(r, arbre, pile) for r in self._regles[langage]) def _accorde_regle(self, regle: Regle, arbre: Arbre, pile) -> bool: if regle.arite_variable_minimale is None: return self._accorde(regle.motif, arbre, {}, pile) motif = regle.motif assert motif.operateur is not None if motif.operateur.identite != arbre.cle_operateur: return False minimum = regle.arite_variable_minimale assert minimum is not None and regle.langage_variable is not None if len(arbre.arguments) < minimum: return False # Les arguments de base correspondent aux points précédant le suffixe. # Les arguments supplémentaires sont tous du type répété indiqué. env: dict[str, Arbre] = {} for sous_motif, sous_arbre in zip(motif.arguments, arbre.arguments[:minimum]): if not self._accorde(sous_motif, sous_arbre, env, pile): return False return all( self._reconnait_arbre(regle.langage_variable, a, pile) for a in arbre.arguments[minimum:] ) def _accorde(self, motif: Motif, arbre: Arbre, env: dict[str, Arbre], pile) -> bool: if motif.est_trou: assert motif.trou is not None t = motif.trou if t.cle in env: return env[t.cle] == arbre if not self._reconnait_arbre(t.langage, arbre, pile): return False env[t.cle] = arbre return True assert motif.operateur is not None if ( motif.operateur.identite != arbre.cle_operateur or len(motif.arguments) != len(arbre.arguments) ): return False copie = dict(env) for sous_motif, sous_arbre in zip(motif.arguments, arbre.arguments): if not self._accorde(sous_motif, sous_arbre, copie, pile): return False env.clear() env.update(copie) return True def _ordonner_pour_trou( self, langage: str, arbres: tuple[Arbre, ...] ) -> tuple[Arbre, ...]: """Place d'abord les termes dont la racine a son nom court local. L'ordre propre du langage reste inchangé à la racine. En revanche, lorsqu'un trou attend un terme de H, les opérateurs propres à H sont essayés avant les opérateurs homonymes importés. """ def priorite(arbre: Arbre) -> int: if arbre.cle_operateur is None: return 0 op = self._operateurs_par_identite.get(arbre.cle_operateur) if op is None: return 0 try: return 0 if self._resoudre_nom_operateur(op.nom, langage) is op else 1 except ValueError: return 1 return tuple( arbre for _, arbre in sorted( enumerate(arbres), key=lambda item: (priorite(item[1]), item[0]) ) ) # ------------------------------------------------------------------ # Énumération par taille, sans répétition # ------------------------------------------------------------------ def termes_de_taille(self, langage: str, taille: int) -> Iterator[str]: for arbre in self._termes_taille(langage, taille): yield str(self._preparer_affichage(arbre, langage)) def termes(self, langage: str, taille_minimale: int = 1, taille_maximale: int | None = None) -> Iterator[str]: self._check(langage) taille = max(1, taille_minimale) while taille_maximale is None or taille <= taille_maximale: yield from self.termes_de_taille(langage, taille) taille += 1 def _termes_taille(self, langage: str, taille: int) -> tuple[Arbre, ...]: if taille < 1: return () cle = (langage, taille) if cle in self._cache: return self._cache[cle] resultat: list[Arbre] = [] vus: set[Arbre] = set() for regle in self._regles[langage]: if regle.arite_variable_minimale is not None: op = regle.operateur assert op is not None total_arguments = taille - 1 if total_arguments < 0: continue # À taille fixée, l'arité maximale est total_arguments, car # chaque argument a une taille au moins égale à 1. On parcourt # les arités décroissantes : h(a,a) précède h(h(a)). for arite in range(total_arguments, regle.arite_variable_minimale - 1, -1): if arite == 0: if total_arguments == 0: arbre = Arbre(op.nom, (), op.identite, contexte=regle.langage) if arbre not in vus: vus.add(arbre); resultat.append(arbre) continue for tailles_args in compositions_positives(total_arguments, arite): minimum = regle.arite_variable_minimale assert minimum is not None and regle.langage_variable is not None types_arguments = ( [regle.langage] * minimum + [regle.langage_variable] * (arite - minimum) ) groupes = [ self._ordonner_pour_trou( type_argument, self._termes_taille(type_argument, n) ) for type_argument, n in zip(types_arguments, tailles_args) ] if any(not groupe for groupe in groupes): continue for choix in product(*groupes): arbre = Arbre(op.nom, tuple(choix), op.identite, contexte=regle.langage) if arbre not in vus: vus.add(arbre); resultat.append(arbre) continue infos, fixe = analyser_trous(regle.motif) variables = list(infos) multiplicites = [infos[k][1] for k in variables] for tailles in solutions_ponderees(taille - fixe, multiplicites): groupes = [ self._ordonner_pour_trou( infos[k][0], self._termes_taille(infos[k][0], n) ) for k, n in zip(variables, tailles) ] if any(not groupe for groupe in groupes): continue for choix in product(*groupes): arbre = instancier(regle.motif, dict(zip(variables, choix)), regle.langage) arbre = self._avec_contexte_racine(arbre, regle.langage) if arbre not in vus: vus.add(arbre) resultat.append(arbre) self._cache[cle] = tuple(resultat) return self._cache[cle] # ------------------------------------------------------------------ # Génération aléatoire # ------------------------------------------------------------------ def terme_aleatoire(self, langage: str, probabilites=None, *, profondeur_maximale=12, arite_maximale=5, seed=None, rng=None) -> str: self._check(langage) if seed is not None and rng is not None: raise ValueError("Utilisez seed ou rng, pas les deux.") generateur = rng or random.Random(seed) poids = self._poids(probabilites) arbre = self._aleatoire(langage, profondeur_maximale, arite_maximale, poids, generateur) return str(self._preparer_affichage(arbre, langage)) def termes_aleatoires(self, langage: str, probabilites=None, *, profondeur_maximale=12, arite_maximale=5, seed=None) -> Iterator[str]: self._check(langage) generateur = random.Random(seed) poids = self._poids(probabilites) while True: arbre = self._aleatoire(langage, profondeur_maximale, arite_maximale, poids, generateur) yield str(self._preparer_affichage(arbre, langage)) def _aleatoire(self, langage: str, profondeur: int, arite_maximale: int, poids, rng: random.Random) -> Arbre: admissibles = [ r for r in self._regles[langage] if self._min_profondeur_regle(r) <= profondeur ] if not admissibles: raise ValueError( f"Profondeur {profondeur} insuffisante pour produire {langage}." ) # Les poids portent désormais sur les règles complètes, et non # uniquement sur leur opérateur racine. Deux règles commençant # par le même opérateur peuvent donc avoir des poids distincts. ws = [poids.get(r, 0.0) for r in admissibles] if sum(ws) <= 0: ws = [1.0] * len(admissibles) regle = rng.choices(admissibles, weights=ws, k=1)[0] if regle.arite_variable_minimale is not None: if arite_maximale < regle.arite_variable_minimale: raise ValueError( f"arite_maximale={arite_maximale} est inférieure à " f"l'arité minimale {regle.arite_variable_minimale}." ) op = regle.operateur assert op is not None borne_arite = ( regle.arite_variable_minimale if profondeur <= 0 else arite_maximale ) arite = rng.randint(regle.arite_variable_minimale, borne_arite) assert regle.langage_variable is not None types_arguments = ( [regle.langage] * regle.arite_variable_minimale + [regle.langage_variable] * (arite - regle.arite_variable_minimale) ) arguments = tuple( self._aleatoire(type_argument, profondeur - 1, arite_maximale, poids, rng) for type_argument in types_arguments ) arbre = Arbre(op.nom, arguments, op.identite, contexte=langage) else: arbre = self._instancier_aleatoire( regle.motif, {}, profondeur, arite_maximale, poids, rng, langage ) return self._avec_contexte_racine(arbre, langage) def _instancier_aleatoire(self, motif: Motif, env, profondeur, arite_maximale, poids, rng, contexte) -> Arbre: if motif.est_trou: assert motif.trou is not None if motif.trou.cle not in env: env[motif.trou.cle] = self._aleatoire(motif.trou.langage, profondeur, arite_maximale, poids, rng) return env[motif.trou.cle] assert motif.operateur is not None if profondeur < 0: raise ValueError("Profondeur maximale dépassée.") return Arbre( motif.operateur.nom, tuple(self._instancier_aleatoire(a, env, profondeur - 1, arite_maximale, poids, rng, contexte) for a in motif.arguments), motif.operateur.identite, contexte=contexte, ) # ------------------------------------------------------------------ # Résolution des opérateurs et conversion des motifs # ------------------------------------------------------------------ def _resoudre_ou_creer_racine(self, langage: str, nom_ecrit: str, arite: int | None, arite_minimale: int = 0) -> Operateur: qualifie = self._decomposer_nom_long(nom_ecrit) if qualifie is not None: origine, nom = qualifie if origine not in self.langages: raise ValueError(f"Langage inconnu dans {nom_ecrit!r}.") cle = (origine, nom) op = self._operateurs_par_identite.get(cle) if op is None: # Si le langage d'origine ne possède pas d'opérateur natif # de ce nom mais en a déjà importé exactement un, son alias # long origine_nom désigne cet opérateur importé. candidats = [o for o in self._membres[origine] if o.nom == nom] if len(candidats) == 1: op = candidats[0] elif len(candidats) > 1: raise ValueError( f"Le nom long {nom_ecrit!r} est ambigu : {origine} " f"contient plusieurs opérateurs nommés {nom!r}." ) else: op = Operateur(origine, nom, arite, arite_minimale) self._enregistrer_operateur(op) else: nom = nom_ecrit cle = (langage, nom) op = self._operateurs_par_identite.get(cle) if op is None: op = Operateur(langage, nom, arite, arite_minimale) self._enregistrer_operateur(op) if op is None: raise AssertionError("Résolution interne impossible.") else: self._verifier_profil_arite(op, arite, arite_minimale, nom_ecrit) return op def _enregistrer_operateur(self, op: Operateur) -> None: self._operateurs_par_identite[op.identite] = op if op.nom_long is not None: self._operateurs_par_long[op.nom_long] = op if op.est_piece: self._pieces.add(op) @staticmethod def _verifier_profil_arite( op: Operateur, arite: int | None, arite_minimale: int, designation: str ) -> None: compatible = (op.arite == arite and op.arite_minimale == arite_minimale) # Un opérateur déjà déclaré variadique peut aussi porter des règles # particulières d'arité fixe comprises dans son profil. if op.est_variadique and arite is not None and op.accepte_arite(arite): compatible = True if not compatible: attendu = op.profil_arite() recu = f"{arite_minimale}..∞" if arite is None else str(arite) raise ValueError( f"L'opérateur {designation!r} est utilisé avec les profils " f"d'arité {attendu} et {recu}." ) @staticmethod def _verifier_arite(op: Operateur, arite: int, designation: str) -> None: if not op.accepte_arite(arite): raise ValueError( f"L'opérateur {designation!r} est utilisé avec une arité {arite}, " f"mais son profil est {op.profil_arite()}." ) def _resoudre_nom_operateur(self, nom: str, langage: str | None = None) -> Operateur: """Résout un nom selon son identité et le langage de contexte.""" if nom in self._operateurs_par_long: op = self._operateurs_par_long[nom] if langage is not None and op not in self._membres[langage]: raise ValueError( f"L'opérateur {nom!r} n'appartient pas au langage {langage}." ) return op qualifie = self._decomposer_nom_long(nom) if qualifie is not None: origine, court = qualifie op = self._operateurs_par_identite.get((origine, court)) if op is None: raise ValueError(f"Opérateur inconnu : {nom!r}.") if langage is not None and op not in self._membres[langage]: raise ValueError( f"L'opérateur {nom!r} n'appartient pas au langage {langage}." ) return op if langage is None: candidats_globaux = [ op for op in self._operateurs_par_identite.values() if op.nom == nom and not op.est_piece ] # Plusieurs langages peuvent contenir le même objet importé : # on déduplique par identité d'objet. uniques = list(dict.fromkeys(candidats_globaux)) if len(uniques) == 1: return uniques[0] if len(uniques) > 1: raise ValueError( f"Le nom court {nom!r} est ambigu dans le système; " "utilisez un nom long." ) if langage is not None: candidats = [op for op in self._membres[langage] if op.nom == nom] natif = self._operateurs_par_identite.get((langage, nom)) if natif in candidats: return natif if len(candidats) == 1: return candidats[0] if len(candidats) > 1: raise ValueError( f"Le nom court {nom!r} est ambigu dans {langage}; " "utilisez un nom long." ) # Un opérateur provenant d'un autre langage peut apparaître # comme pièce dans un motif. Si aucun opérateur local homonyme # n'existe et que le nom est globalement non ambigu, le nom court # reste accepté dans le terme affiché. globaux = [ op for op in self._operateurs_par_identite.values() if op.nom == nom and not op.est_piece ] globaux = list(dict.fromkeys(globaux)) if len(globaux) == 1: return globaux[0] pieces = [op for op in self._pieces if op.nom == nom] if len(pieces) == 1: return pieces[0] raise ValueError(f"Opérateur inconnu dans ce contexte : {nom!r}.") def _convertir_motif(self, arbre: Arbre, courant: str, compteur: list[int], *, est_racine=False) -> Motif: if not arbre.arguments: if arbre.nom == "." or arbre.nom in self.langages: langage = courant if arbre.nom == "." else arbre.nom compteur[0] += 1 return Motif(trou=Trou(langage, f"@{compteur[0]}")) variable = VAR.fullmatch(arbre.nom) if variable and variable.group(1) in self.langages: return Motif(trou=Trou(variable.group(1), arbre.nom)) try: # Un nom long peut désigner une pièce provenant d'un autre # langage sans que cet opérateur devienne membre du langage # courant. Un nom court, lui, est résolu dans le contexte courant. contexte = None if self._decomposer_nom_long(arbre.nom) else courant op = self._resoudre_nom_operateur(arbre.nom, contexte) except ValueError: # Un nom qualifié prétend désigner l'opérateur d'un langage : # il ne peut donc pas créer implicitement une pièce extérieure. if self._decomposer_nom_long(arbre.nom) is not None: raise cle_piece = (None, arbre.nom) op = self._operateurs_par_identite.get(cle_piece) if op is None: op = Operateur(None, arbre.nom, len(arbre.arguments)) self._enregistrer_operateur(op) self._verifier_arite(op, len(arbre.arguments), arbre.nom) if est_racine: self._membres[courant].add(op) return Motif(op, tuple(self._convertir_motif(a, courant, compteur) for a in arbre.arguments)) @staticmethod def _decomposer_nom_long(nom: str) -> tuple[str, str] | None: m = QUALIFIE.fullmatch(nom) return None if m is None else (m.group(1), m.group(2)) # ------------------------------------------------------------------ # Mesures minimales et poids # ------------------------------------------------------------------ def _calculer_min_tailles(self) -> dict[str, float]: mins = {l: math.inf for l in self.langages} changement = True while changement: changement = False for langage, regles in self._regles.items(): for regle in regles: if regle.arite_variable_minimale is not None: m = regle.arite_variable_minimale # L'arité supplémentaire peut être nulle : seuls les # m arguments de base du langage courant sont obligatoires. if m == 0: valeur = 1 elif math.isfinite(mins[langage]): valeur = 1 + m * mins[langage] else: continue else: infos, fixe = analyser_trous(regle.motif) if not all(math.isfinite(mins[s]) for s, _ in infos.values()): continue valeur = fixe + sum(mult * mins[s] for s, mult in infos.values()) if valeur < mins[langage]: mins[langage] = valeur changement = True return mins def _calculer_min_profondeurs(self) -> dict[str, float]: d = {l: math.inf for l in self.langages} changement = True while changement: changement = False for langage, regles in self._regles.items(): for regle in regles: if regle.arite_variable_minimale is not None: m = regle.arite_variable_minimale valeur = 0 if m == 0 else (1 + d[langage] if math.isfinite(d[langage]) else math.inf) if valeur < d[langage]: d[langage] = valeur changement = True continue def profondeur(m: Motif) -> float: if m.est_trou: assert m.trou is not None return d[m.trou.langage] if not m.arguments: return 0 valeurs = [profondeur(a) for a in m.arguments] if any(math.isinf(v) for v in valeurs): return math.inf return 1 + max(valeurs) valeur = profondeur(regle.motif) if valeur < d[langage]: d[langage] = valeur changement = True return d def _min_profondeur_regle(self, regle: Regle) -> float: if regle.arite_variable_minimale is not None: if regle.arite_variable_minimale == 0: return 0 return 1 + self._min_profondeur[regle.langage] return self._min_profondeur_motif(regle.motif) def _min_profondeur_motif(self, motif: Motif) -> float: if motif.est_trou: assert motif.trou is not None return self._min_profondeur[motif.trou.langage] if not motif.arguments: return 0 return 1 + max(self._min_profondeur_motif(a) for a in motif.arguments) def _poids(self, probabilites): """Normalise les poids en un dictionnaire ``Regle -> poids``. Désignations acceptées : - ``"L|--g(L1,L1)"`` : une règle précise ; - ``("L", "g(L1,L1)")`` : la même règle précise ; - ``"H|--L"`` ou ``("H", "L")`` : une règle d'inclusion de tous les termes de L dans H ; - ``"g"``, ``"L_g"`` ou ``("L", "g")`` : toutes les règles dont la racine est cet opérateur. Une désignation de règle précise remplace la pondération générale éventuellement attribuée auparavant à son opérateur. """ toutes_regles = tuple( regle for langage in self.langages for regle in self._regles[langage] ) if probabilites is None: return {regle: 1.0 for regle in toutes_regles} sortie = {regle: 0.0 for regle in toutes_regles} def poids_valide(valeur) -> float: if ( not isinstance(valeur, (int, float)) or isinstance(valeur, bool) or not math.isfinite(float(valeur)) or valeur < 0 ): raise ValueError("Poids invalide.") return float(valeur) for cle, valeur_brute in probabilites.items(): valeur = poids_valide(valeur_brute) regles_cibles: list[Regle] # Couple (langage, motif ou opérateur). if isinstance(cle, tuple): if len(cle) != 2 or not all(isinstance(x, str) for x in cle): raise ValueError( "Une clé tuple doit être (langage, règle_ou_opérateur)." ) langage, designation = cle self._check(langage) designation = designation.strip() if designation.startswith("|--"): designation = designation[3:] exactes = [ r for r in self._regles[langage] if r.motif.texte(langage) == designation ] if exactes: regles_cibles = exactes else: op = self._resoudre_nom_operateur( f"{langage}_{designation}" if "_" not in designation else designation ) regles_cibles = [ r for r in toutes_regles if r.operateur is not None and r.operateur is op ] elif isinstance(cle, str): designation = cle.strip() # Forme complète : L|--g(L1,L1), éventuellement L:|--... if "|--" in designation: gauche, motif = designation.split("|--", 1) langage = gauche.rstrip(":").strip() self._check(langage) motif = motif.strip() regles_cibles = [ r for r in self._regles[langage] if r.motif.texte(langage) == motif ] if not regles_cibles: raise ValueError( f"Règle inconnue : {langage}|--{motif}." ) else: designation_op = ( designation.replace(".", "_", 1) if "." in designation else designation ) op = self._resoudre_nom_operateur(designation_op) regles_cibles = [ r for r in toutes_regles if r.operateur is not None and r.operateur is op ] else: raise TypeError("Clé de poids incorrecte.") if not regles_cibles: raise ValueError(f"Aucune règle ne correspond à {cle!r}.") for regle in regles_cibles: sortie[regle] = valeur if sum(sortie.values()) <= 0: raise ValueError("Au moins un poids doit être strictement positif.") return sortie def _check(self, langage: str) -> None: if langage not in self._regles: raise ValueError(f"Langage inconnu : {langage!r}.") def extraire_arite_variadique( arbre: Arbre, langage: str, langages: tuple[str, ...], ) -> tuple[int, str] | None: """Retourne ``(arité minimale, type répété)`` d'une règle multi-aire. Formes admises : - ``h(...)`` : zéro ou plusieurs arguments du langage courant ; - ``h(.,.,...)`` : au moins deux arguments du langage courant ; - ``h(A..)`` : zéro ou plusieurs arguments du langage A ; - ``h(.,A..)`` : un argument de base du langage courant, puis zéro ou plusieurs arguments du langage A. """ marqueurs: list[tuple[int, str]] = [] for i, argument in enumerate(arbre.arguments): if argument.arguments: continue if argument.nom == "...": marqueurs.append((i, langage)) elif argument.nom.endswith("..") and argument.nom != "...": type_repete = argument.nom[:-2] if type_repete in langages: marqueurs.append((i, type_repete)) else: raise ValueError( f"Type répété inconnu dans {argument.nom!r} : {type_repete!r}." ) if not marqueurs: return None if len(marqueurs) != 1 or marqueurs[0][0] != len(arbre.arguments) - 1: raise ValueError("Le suffixe multi-aire doit être l'unique dernier argument.") position, type_repete = marqueurs[0] base = arbre.arguments[:position] if any(a.arguments or a.nom not in {".", langage} for a in base): raise ValueError( "Avant le suffixe multi-aire, seuls des trous indépendants '.' " "ou le nom du langage courant sont autorisés." ) return len(base), type_repete def compositions_positives(total: int, parties: int) -> Iterator[tuple[int, ...]]: if parties == 0: if total == 0: yield () return if parties == 1: if total >= 1: yield (total,) return for premier in range(1, total - parties + 2): for suite in compositions_positives(total - premier, parties - 1): yield (premier,) + suite def analyser_trous(motif: Motif): info: dict[str, tuple[str, int]] = {} fixe = 0 def rec(m: Motif): nonlocal fixe if m.est_trou: assert m.trou is not None t = m.trou if t.cle in info and info[t.cle][0] != t.langage: raise ValueError(f"Variable {t.cle} utilisée avec deux langages.") info[t.cle] = (t.langage, info.get(t.cle, (t.langage, 0))[1] + 1) else: fixe += 1 for a in m.arguments: rec(a) rec(motif) return info, fixe def instancier(motif: Motif, env: Mapping[str, Arbre], contexte: str | None = None) -> Arbre: if motif.est_trou: assert motif.trou is not None return env[motif.trou.cle] assert motif.operateur is not None return Arbre( motif.operateur.nom, tuple(instancier(a, env, contexte) for a in motif.arguments), motif.operateur.identite, contexte=contexte, ) def solutions_ponderees(total: int, poids: list[int]) -> Iterator[tuple[int, ...]]: if not poids: if total == 0: yield () return premier = poids[0] for n in range(1, total // premier + 1): for suite in solutions_ponderees(total - premier * n, poids[1:]): yield (n,) + suite def parse_arbre(texte: str) -> Arbre: s = re.sub(r"\s+", "", texte) if not s: raise SyntaxError("Expression vide.") def rec(i: int) -> tuple[Arbre, int]: if s.startswith("...", i): nom, i = "...", i + 3 elif i < len(s) and s[i] == ".": nom, i = ".", i + 1 else: m = ID.match(s, i) if not m: raise SyntaxError(f"Identificateur attendu à la position {i + 1}.") nom, i = m.group(), m.end() if s.startswith("..", i): nom, i = nom + "..", i + 2 arguments: list[Arbre] = [] if i < len(s) and s[i] == "(": i += 1 if i < len(s) and s[i] == ")": raise SyntaxError("Liste d'arguments vide.") while True: argument, i = rec(i) arguments.append(argument) if i < len(s) and s[i] == ",": i += 1 continue if i < len(s) and s[i] == ")": i += 1 break raise SyntaxError(f"Virgule ou ')' attendue à la position {i + 1}.") return Arbre(nom, tuple(arguments)), i arbre, position = rec(0) if position != len(s): raise SyntaxError(f"Texte inattendu à la position {position + 1}.") return arbre def separer(texte: str) -> list[str]: resultat: list[str] = [] debut = 0 profondeur = 0 for i, caractere in enumerate(texte): if caractere == "(": profondeur += 1 elif caractere == ")": profondeur -= 1 elif caractere == "," and profondeur == 0: resultat.append(texte[debut:i].strip()) debut = i + 1 if profondeur < 0: raise ValueError("Parenthèses déséquilibrées.") if profondeur: raise ValueError("Parenthèses déséquilibrées.") resultat.append(texte[debut:].strip()) if any(not x for x in resultat): raise ValueError("Déclaration vide.") return resultat def _analyser_definition_langage(definition: str) -> tuple[str, str]: """Analyse une chaîne de la forme ``L=<...>``.""" if not isinstance(definition, str): raise TypeError( "Chaque langage doit être transmis sous forme de chaîne, " "par exemple 'L='." ) texte = definition.strip() if not texte: raise ValueError("Une définition de langage est vide.") if "=" not in texte: raise ValueError( f"Signe '=' absent dans {definition!r}. " "Format attendu : 'L='." ) nom, presentation = texte.split("=", 1) nom = nom.strip() presentation = presentation.strip() if not ID.fullmatch(nom): raise ValueError(f"Nom de langage incorrect : {nom!r}.") if not (presentation.startswith("<") and presentation.endswith(">")): raise ValueError( f"La présentation de {nom} doit être placée entre chevrons : " f"'{nom}=<...>'." ) return nom, presentation @dataclass(frozen=True) class SyntaxeAlternative: """Syntaxe externe associée à un nom court d'opérateur.""" genre: str priorite: int = 0 sens: str = "-" debut: str = "" fin: str = "" class SystemeLangagesSyntaxe(SystemeLangages): """Ajoute une couche de syntaxe externe sans modifier les arbres internes.""" def __init__(self, presentations: Mapping[str, str], syntaxes=None): super().__init__(presentations) self._syntaxes = self._normaliser_syntaxes(syntaxes or {}) self._valider_syntaxes() self._aliases_par_operateur = self._construire_aliases() self._tokens_prefixes = self._tokens_genre("prefixe") self._tokens_postfixes = self._tokens_genre("postfixe") self._tokens_infixes = self._tokens_genre("infixe") self._syntaxes_delimitees = tuple( sorted( ((nom, syn) for nom, syn in self._syntaxes.items() if syn.genre == "delimite"), key=lambda item: (-len(item[1].debut), item[1].debut), ) ) self._tokens_atomes = self._construire_tokens_atomes() def _normaliser_syntaxes(self, syntaxes): if not isinstance(syntaxes, Mapping): raise TypeError("syntaxes doit être un dictionnaire indexé par nom court.") resultat = {} for nom, valeur in syntaxes.items(): if not isinstance(nom, str) or not nom: raise ValueError("Chaque clé de syntaxes doit être un nom court non vide.") if isinstance(valeur, str): genre = valeur.lower() if genre not in {"prefixe", "postfixe"}: raise ValueError(f"Syntaxe inconnue pour {nom!r}: {valeur!r}.") resultat[nom] = SyntaxeAlternative(genre) elif isinstance(valeur, (tuple, list)) and len(valeur) == 3: genre, second, troisieme = valeur genre = str(genre).lower() if genre == "infixe": priorite, sens = second, troisieme if not isinstance(priorite, int) or isinstance(priorite, bool) or not 0 <= priorite <= 255: raise ValueError(f"Priorité invalide pour {nom!r}; entier attendu entre 0 et 255.") if sens not in {"+", "-"}: raise ValueError(f"Sens invalide pour {nom!r}; utilisez '+' ou '-'.") resultat[nom] = SyntaxeAlternative("infixe", priorite, sens) elif genre == "delimite": debut, fin = second, troisieme if not isinstance(debut, str) or not debut or not isinstance(fin, str) or not fin: raise ValueError(f"Les délimiteurs de {nom!r} doivent être deux chaînes non vides.") if debut == fin: raise ValueError(f"Les délimiteurs de début et de fin de {nom!r} doivent être distincts.") resultat[nom] = SyntaxeAlternative("delimite", debut=debut, fin=fin) else: raise ValueError( f"Le triplet de {nom!r} doit commencer par 'infixe' ou 'delimite'." ) elif isinstance(valeur, Mapping): genre = str(valeur.get("type", valeur.get("genre", ""))).lower() if genre in {"prefixe", "postfixe"}: resultat[nom] = SyntaxeAlternative(genre) elif genre == "infixe": priorite = valeur.get("priorite") sens = valeur.get("sens") if not isinstance(priorite, int) or isinstance(priorite, bool) or not 0 <= priorite <= 255: raise ValueError(f"Priorité invalide pour {nom!r}.") if sens not in {"+", "-"}: raise ValueError(f"Sens invalide pour {nom!r}.") resultat[nom] = SyntaxeAlternative("infixe", priorite, sens) elif genre == "delimite": debut = valeur.get("debut") fin = valeur.get("fin") if not isinstance(debut, str) or not debut or not isinstance(fin, str) or not fin: raise ValueError(f"Les délimiteurs de {nom!r} doivent être deux chaînes non vides.") if debut == fin: raise ValueError(f"Les délimiteurs de début et de fin de {nom!r} doivent être distincts.") resultat[nom] = SyntaxeAlternative("delimite", debut=debut, fin=fin) else: raise ValueError(f"Syntaxe inconnue pour {nom!r}.") else: raise ValueError(f"Description de syntaxe incorrecte pour {nom!r}.") return resultat def _ops_de_nom(self, nom): return list(dict.fromkeys(op for op in self._operateurs_par_identite.values() if op.nom == nom)) def _valider_syntaxes(self): sens_par_priorite = {} for nom, syntaxe in self._syntaxes.items(): ops = self._ops_de_nom(nom) if not ops: raise ValueError(f"Aucun opérateur de nom court {nom!r} dans le système.") for op in ops: if syntaxe.genre == "delimite": if not op.est_variadique: raise ValueError(f"La syntaxe délimitée exige une arité variable pour {nom!r}.") else: if op.est_variadique: raise ValueError(f"La syntaxe {syntaxe.genre} de {nom!r} exige une arité fixe.") if syntaxe.genre == "prefixe" and (op.arite or 0) <= 0: raise ValueError(f"La syntaxe préfixe exige une arité strictement positive pour {nom!r}.") if syntaxe.genre == "postfixe" and op.arite != 1: raise ValueError(f"La syntaxe postfixe exige l'arité 1 pour {nom!r}.") if syntaxe.genre == "infixe" and op.arite != 2: raise ValueError(f"La syntaxe infixe exige l'arité 2 pour {nom!r}.") profils = {(op.arite, op.arite_minimale) for op in ops} if len(profils) != 1: raise ValueError(f"Tous les opérateurs courts {nom!r} doivent avoir le même profil d'arité.") if syntaxe.genre == "infixe": ancien = sens_par_priorite.get(syntaxe.priorite) if ancien is not None and ancien != syntaxe.sens: raise ValueError( f"Deux opérateurs infixes de priorité {syntaxe.priorite} ont des sens différents." ) sens_par_priorite[syntaxe.priorite] = syntaxe.sens # Les délimiteurs de début identifient la syntaxe délimitée : ils # doivent donc être distincts. Plusieurs syntaxes peuvent en revanche # partager le même délimiteur final. debuts_vus: dict[str, str] = {} noms_operateurs = {op.nom for op in self._operateurs_par_identite.values()} for nom, syntaxe in self._syntaxes.items(): if syntaxe.genre != "delimite": continue debut, fin = syntaxe.debut, syntaxe.fin # Le début peut exceptionnellement être exactement le nom court # de l'opérateur auquel la syntaxe est associée, mais pas le nom # d'un autre opérateur. if re.search(r"\s", debut): raise ValueError( f"Le délimiteur de début de {nom!r} ne doit pas contenir d'espace." ) if debut in noms_operateurs and debut != nom: raise ValueError( f"Le délimiteur de début {debut!r} de {nom!r} est le nom d'un autre opérateur." ) ancien = debuts_vus.get(debut) if ancien is not None and ancien != nom: raise ValueError( f"Le délimiteur de début {debut!r} est déjà utilisé par {ancien!r}." ) debuts_vus[debut] = nom # Le délimiteur final peut être commun à plusieurs syntaxes. Le # caractère espace unique est autorisé comme cas particulier. if fin != " " and re.search(r"\s", fin): raise ValueError( f"Le délimiteur final de {nom!r} ne peut contenir d'espace, sauf s'il vaut exactement ' '." ) if fin in noms_operateurs: raise ValueError( f"Le délimiteur final {fin!r} de {nom!r} est déjà un nom d'opérateur." ) def _construire_aliases(self): d = {} for op in self._operateurs_par_identite.values(): aliases = {op.nom} if not op.est_piece: for langage, membres in self._membres.items(): if op in membres: aliases.add(f"{langage}_{op.nom}") if op.nom_long: aliases.add(op.nom_long) d[op.identite] = tuple(sorted(aliases, key=lambda x: (-len(x), x))) return d def _tokens_genre(self, genre): noms = [nom for nom, syn in self._syntaxes.items() if syn.genre == genre] return tuple(sorted(noms, key=lambda x: (-len(x), x))) def _construire_tokens_atomes(self): tokens = [] for op in self._operateurs_par_identite.values(): if op.accepte_arite(0): tokens.extend((alias, op) for alias in self._aliases_par_operateur[op.identite]) return tuple(sorted(tokens, key=lambda x: (-len(x[0]), x[0]))) def syntaxes(self): return dict(self._syntaxes) def _match_token(self, s, pos, tokens): for token in tokens: if s.startswith(token, pos): return token return None def _parse_alternatif(self, expression: str, langage: str) -> Arbre: # Un espace peut être un délimiteur final significatif. Dans ce cas, # on conserve la chaîne originale et on ignore les espaces seulement # hors de la fermeture d'une syntaxe délimitée. Sinon, on garde le # comportement compact historique en supprimant les blancs. espace_significatif = any( syn.genre == "delimite" and syn.fin == " " for syn in self._syntaxes.values() ) s = expression if espace_significatif else re.sub(r"\s+", "", expression) if not s or (espace_significatif and not s.strip()): raise SyntaxError("Expression vide.") def saute_blancs(pos): if not espace_significatif: return pos while pos < len(s) and s[pos].isspace(): pos += 1 return pos # Priorités internes : postfixe > préfixe > infixe (0..255). PREC_PREFIXE = 1000 def op_depuis_token(token, contexte): return self._resoudre_nom_operateur(token, contexte) def parse_primaire(pos): pos = saute_blancs(pos) if pos < len(s) and s[pos] == '(': arbre, fin = parse_expr(pos + 1, 0) if fin >= len(s) or s[fin] != ')': raise SyntaxError(f"Parenthèse fermante attendue à la position {fin + 1}.") return arbre, fin + 1 # Syntaxe délimitée d'un opérateur multi-aire. Le délimiteur # remplace le nom de l'opérateur et ses parenthèses. for nom_court, syn in self._syntaxes_delimitees: if s.startswith(syn.debut, pos): op = op_depuis_token(nom_court, langage) i = pos + len(syn.debut) args = [] while not s.startswith(syn.fin, i): if i >= len(s): raise SyntaxError( f"Délimiteur final {syn.fin!r} attendu pour {nom_court!r}." ) avant = i arg, i = parse_expr(i, 0, syn.fin == " ") if i <= avant: raise SyntaxError(f"Argument attendu à la position {i + 1}.") args.append(arg) i += len(syn.fin) if not op.accepte_arite(len(args)): raise SyntaxError( f"{nom_court!r} attend au moins {op.arite_minimale} argument(s), " f"mais {len(args)} ont été lus." ) return Arbre(op.nom, tuple(args), op.identite, contexte=langage), i # Appel canonique nom(...), conservé comme syntaxe de secours. aliases = [] for op in self._operateurs_par_identite.values(): for alias in self._aliases_par_operateur[op.identite]: aliases.append((alias, op)) for alias, op in sorted(aliases, key=lambda x: (-len(x[0]), x[0])): if s.startswith(alias + '(', pos): i = pos + len(alias) + 1 args = [] if i < len(s) and s[i] == ')': i += 1 else: while True: arg, i = parse_expr(i, 0) args.append(arg) i = saute_blancs(i) if i < len(s) and s[i] == ',': i = saute_blancs(i + 1) continue if i < len(s) and s[i] == ')': i += 1 break raise SyntaxError(f"Virgule ou ')' attendue à la position {i + 1}.") return Arbre(op.nom, tuple(args), op.identite, contexte=langage), i # Préfixe : l'arité fixe indique combien d'expressions lire. for token in self._tokens_prefixes: if s.startswith(token, pos): op = op_depuis_token(token, langage) args = [] i = pos + len(token) assert op.arite is not None for _ in range(op.arite): arg, i = parse_expr(i, PREC_PREFIXE) args.append(arg) return Arbre(op.nom, tuple(args), op.identite, contexte=langage), i # Variable muette typée. m = VAR.match(s, pos) if m: return Arbre(m.group()), m.end() # Générateur d'arité zéro. Le plus long alias est essayé d'abord. for token, op in self._tokens_atomes: if s.startswith(token, pos): return Arbre(op.nom, (), op.identite, contexte=langage), pos + len(token) raise SyntaxError(f"Terme attendu à la position {pos + 1}.") def parse_expr(pos, min_prec, arret_espace=False): pos = saute_blancs(pos) gauche, pos = parse_primaire(pos) if not (arret_espace and pos < len(s) and s[pos] == " "): pos = saute_blancs(pos) # Tous les postfixes sont plus prioritaires que préfixes et infixes. while True: token = self._match_token(s, pos, self._tokens_postfixes) if token is None: break op = op_depuis_token(token, langage) gauche = Arbre(op.nom, (gauche,), op.identite, contexte=langage) pos += len(token) if not (arret_espace and pos < len(s) and s[pos] == " "): pos = saute_blancs(pos) while True: trouve = None for token in self._tokens_infixes: if s.startswith(token, pos): syn = self._syntaxes[token] if syn.priorite >= min_prec: trouve = (token, syn) break if trouve is None: break token, syn = trouve op = op_depuis_token(token, langage) pos = saute_blancs(pos + len(token)) prochain_min = syn.priorite + 1 if syn.sens == '-' else syn.priorite droite, pos = parse_expr(pos, prochain_min, arret_espace) gauche = Arbre(op.nom, (gauche, droite), op.identite, contexte=langage) return gauche, pos arbre, fin = parse_expr(0, 0) fin = saute_blancs(fin) if fin != len(s): raise SyntaxError(f"Texte inattendu à la position {fin + 1}: {s[fin:]!r}.") return arbre def _lire_expression(self, expression, langage): if not self._syntaxes: return parse_arbre(expression) try: return self._parse_alternatif(expression, langage) except (SyntaxError, ValueError): return parse_arbre(expression) def reconnait(self, langage: str, expression: str) -> bool: try: arbre = self._canonicaliser_arbre(self._lire_expression(expression, langage), langage) return self._reconnait_arbre(langage, arbre, set()) except (SyntaxError, ValueError): return False def expliquer(self, langage: str, expression: str) -> tuple[bool, str]: try: arbre = self._canonicaliser_arbre(self._lire_expression(expression, langage), langage) except (SyntaxError, ValueError) as e: return False, str(e) if self._reconnait_arbre(langage, arbre, set()): return True, f"Terme reconnu dans {langage}, taille {arbre.taille}, profondeur {arbre.profondeur}." return False, f"L'expression n'est pas engendrée par les règles de {langage}." def analyser(self, langage: str, expression: str) -> Arbre: arbre = self._canonicaliser_arbre(self._lire_expression(expression, langage), langage) if not self._reconnait_arbre(langage, arbre, set()): raise SyntaxError(f"Terme non reconnu dans {langage} : {expression!r}.") prepare = self._preparer_affichage(arbre, langage) rendu = self.formater(arbre, langage) return Arbre( prepare.nom, prepare.arguments, prepare.cle_operateur, contexte=prepare.contexte, affichage=prepare.affichage, rendu_complet=rendu, ) def _nom_externe(self, arbre, contexte): if arbre.cle_operateur is None: return arbre.nom op = self._operateurs_par_identite.get(arbre.cle_operateur) return arbre.nom if op is None else self._nom_affiche(op, contexte) def formater(self, arbre: Arbre, langage: str | None = None) -> str: contexte = langage or arbre.contexte def rec(a, parent_prec=-1, cote=None, parent_syn=None): nom = self._nom_externe(a, contexte) syn = self._syntaxes.get(a.nom) if syn is None or a.cle_operateur is None: if not a.arguments: return nom, 3000 contenu = ','.join(rec(x)[0] for x in a.arguments) return f"{nom}({contenu})", 3000 if syn.genre == 'delimite': contenu = ''.join(rec(x)[0] for x in a.arguments) return syn.debut + contenu + syn.fin, 3000 if syn.genre == 'prefixe': morceaux = [] for x in a.arguments: tx, px = rec(x, 1000, 'arg', syn) if px < 1000: tx = f"({tx})" morceaux.append(tx) return nom + ''.join(morceaux), 1000 if syn.genre == 'postfixe': tx, px = rec(a.arguments[0], 2000, 'gauche', syn) if px < 2000: tx = f"({tx})" return tx + nom, 2000 # Infixe p = syn.priorite tg, pg = rec(a.arguments[0], p, 'gauche', syn) td, pd = rec(a.arguments[1], p, 'droite', syn) if pg < p or (pg == p and syn.sens == '+'): tg = f"({tg})" if pd < p or (pd == p and syn.sens == '-'): td = f"({td})" texte = tg + nom + td return texte, p return rec(arbre)[0] def termes_de_taille(self, langage: str, taille: int) -> Iterator[str]: for arbre in self._termes_taille(langage, taille): yield self.formater(arbre, langage) def terme_aleatoire(self, langage: str, probabilites=None, *, profondeur_maximale=20, arite_maximale=6, seed=None, rng=None) -> str: # Reprend l'algorithme parent mais récupère l'arbre avant formatage. self._check(langage) if profondeur_maximale < 0 or arite_maximale < 0: raise ValueError("Les bornes doivent être positives ou nulles.") if seed is not None and rng is not None: raise ValueError("Indiquez seed ou rng, pas les deux.") generateur = rng if rng is not None else random.Random(seed) poids = self._poids(probabilites) arbre = self._aleatoire(langage, profondeur_maximale, arite_maximale, poids, generateur) return self.formater(arbre, langage) def termes_aleatoires(self, langage: str, probabilites=None, *, profondeur_maximale=20, arite_maximale=6, seed=None): rng = random.Random(seed) poids = self._poids(probabilites) while True: arbre = self._aleatoire(langage, profondeur_maximale, arite_maximale, poids, rng) yield self.formater(arbre, langage) def Idioma(*definitions: str, syntaxes=None) -> SystemeLangages: """ Construit un système de langages algébriques. Chaque argument est une chaîne de la forme ``Nom=``. """ if not definitions: raise ValueError( "Idioma attend au moins une définition, par exemple " "Idioma('L=')." ) presentations: dict[str, str] = {} for definition in definitions: nom, presentation = _analyser_definition_langage(definition) if nom in presentations: raise ValueError(f"Le langage {nom!r} est défini plusieurs fois.") presentations[nom] = presentation return SystemeLangagesSyntaxe(presentations, syntaxes=syntaxes) def idiomas(presentations: Mapping[str, str]) -> SystemeLangages: """Ancienne interface, conservée uniquement pour compatibilité.""" return SystemeLangagesSyntaxe(presentations) def afficher_synopsis() -> None: print(r''' ================================================================================ IDIOMA — AUTOMATES DE LANGAGES ALGÉBRIQUES À OPÉRATEURS PARTAGÉS ================================================================================ 1. CONSTRUCTION D'UN SYSTÈME DE LANGAGES ----------------------------------------- Chaque langage est transmis comme un argument séparé de la fonction Idioma : S = Idioma( "L=", "H=", ) La syntaxe générale d'un argument est : "NomDuLangage=" Exemple avec deux langages mutuellement récursifs : S = Idioma( "L=", "H=", ) L'ordre des arguments est conservé. Il intervient notamment lorsqu'un nom court crée pour la première fois un opérateur canonique partagé par plusieurs langages. 2. TROUS INDÉPENDANTS ET LANGAGE COURANT ---------------------------------------- Dans la présentation d'un langage, un point représente un terme quelconque de ce même langage : "L=" équivaut à : "L=" Deux occurrences non numérotées sont indépendantes. La règle g(L,L) peut donc produire g(a,f(a)) aussi bien que g(a,a). Un nom de langage placé comme argument représente lui aussi un trou indépendant : f(H) attend un terme quelconque de H ; g(H,L) attend successivement un terme de H et un terme de L. 3. VARIABLES LIÉES DANS LES RÈGLES-MOTIFS ----------------------------------------- Un nom de langage suivi d'un entier strictement positif est une variable liée : "L=" Les deux occurrences de L1 doivent recevoir exactement le même terme : g(a,a) est reconnu ; g(f(a),f(a)) est reconnu ; g(a,f(a)) est rejeté. Les variables liées peuvent apparaître dans des sous-motifs : S = Idioma( "K=", "H=", ) Cette règle peut produire g(a,r(a)) ou g(f(a),r(f(a))), mais jamais g(f(a),r(a)). Les expressions reconnues peuvent également contenir des variables muettes : L1, L2, L3, ... H1, H2, H3, ... Une variable muette est acceptée seulement lorsqu'un terme de son langage est attendu. Elle n'est ni un générateur, ni un terme clos énuméré au hasard. 4. OPÉRATEURS MULTI-AIRES TYPÉS -------------------------------- Un suffixe multi-aire peut préciser le langage de tous les arguments répétés. Le premier point de ``...`` est alors remplacé par le nom du langage : S = Idioma( "L=", "A=", ) La règle : L|--h(A..) signifie que h reçoit zéro, un ou plusieurs arguments, tous appartenant à A : h h(A_a) h(A_a,b) h(c,A_a,b) Lorsque le nom court d'un opérateur est ambigu, l'affichage utilise son nom long. Dans cet exemple, A_a est nécessaire pour distinguer la constante a de A de la constante a de L. Les constantes b et c peuvent rester courtes puisqu'elles ne sont pas ambiguës dans L. La règle distincte : L|--h(L,L) provient de h(.,.) et accepte exactement deux termes de L. Ainsi : h(a,a) est reconnu par h(.,.) ; h(A_a,b) est reconnu par h(A..) ; h(a,A_a) est rejeté par les deux règles. Les formes suivantes sont admises : h(...) zéro ou plusieurs arguments du langage courant ; h(A..) zéro ou plusieurs arguments de A ; h(.,...) au moins un argument du langage courant ; h(.,A..) un argument de base du langage courant, puis zéro ou plusieurs arguments de A ; h(.,.,A..) deux arguments de base du langage courant, puis zéro ou plusieurs arguments de A. Pour la génération aléatoire, ``arite_maximale`` borne le nombre total d'arguments d'une règle multi-aire. Chaque argument supplémentaire est produit par l'automate du langage indiqué après le suffixe typé. 5. OPÉRATEURS, PIÈCES ET NOMS LONGS ----------------------------------- La racine de chaque règle est un opérateur générateur appartenant au langage présenté. Un opérateur qui apparaît seulement à l'intérieur d'une règle peut être une pièce extérieure à tous les langages du système. Exemple : S = Idioma("L=") Dans ce système : a et g sont les opérateurs générateurs de L ; r est une pièce du système S ; r n'appartient à aucun langage. La pièce r peut participer à la forme des termes de L, par exemple g(a,r(a)), mais elle ne constitue pas à elle seule une règle génératrice de L. Une même pièce peut apparaître dans plusieurs motifs. Son nom et son arité doivent rester identiques dans tout le système. Une pièce n'a pas de nom long, puisqu'elle n'a aucun langage propriétaire. Le nom long d'un opérateur est : NomDuLangage_NomDeLOpérateur Exemple : S = Idioma( "L=", "H=", ) Dans ce système : L_a et a désignent le même opérateur ; H_f et f désignent le même opérateur ; H_r et r désignent le même opérateur. Les termes sont toujours affichés avec le nom court canonique : L_a s'affiche a ; H_f(a) s'affiche f(a) ; g(a,H_r(a)) s'affiche g(a,r(a)). Deux règles devenues identiques après résolution des alias ne produisent pas de répétition. Par exemple : S = Idioma("L=") n'énumère f(a) qu'une seule fois. 6. INCLUSION DIRECTE D'UN LANGAGE DANS UN AUTRE ------------------------------------------------ Un langage peut contenir directement tous les termes d'un autre langage : S = Idioma( "L=", "H=", ) Les règles de H sont alors : H|--L H|--f(H) La règle H|--L signifie que tout terme de L est aussi reconnu comme terme de H. Elle n'ajoute aucun opérateur ni aucun symbole à l'arbre : S.reconnait("H", "a") # True S.reconnait("H", "g(a,a)") # True S.reconnait("H", "f(a)") # True Cette inclusion est une règle complète et possède son propre poids : poids = { "L|--a": 8, "L|--g(L,L)": 1, "H|--L": 4, "H|--f(H)": 2, } S.terme_aleatoire( "H", probabilites=poids, profondeur_maximale=8, seed=123, ) Le poids de H|--L règle la fréquence avec laquelle la génération de H délègue la production d'un terme au langage L. 7. CONSULTER LES LANGAGES ET LES RÈGLES --------------------------------------- S.langages retourne les noms des langages dans l'ordre de leur déclaration. S.regles("L") retourne les règles de production de L. S.operateurs("L") retourne les noms courts des opérateurs appartenant à L. S.pieces() retourne les noms courts des pièces extérieures à tous les langages. S.meme_operateur("a", "L_a") S.meme_operateur("f", "H_f") permet de vérifier que deux désignations représentent le même opérateur. 8. RECONNAISSANCE D'UN TERME ---------------------------- S.reconnait("L", "g(a,r(a))") renvoie True ou False. reconnu, message = S.expliquer("L", "g(a,r(a))") renvoie le résultat accompagné d'une explication. terme = S.analyser("L", "g(a,r(a))") renvoie l'arbre syntaxique canonique ou lève SyntaxError si le terme n'est pas reconnu. Propriétés utiles de l'arbre : str(terme) forme canonique du terme ; terme.taille nombre total d'occurrences d'opérateurs et de feuilles ; terme.profondeur profondeur de l'arbre syntaxique. 8. ÉNUMÉRATION DES TERMES CLOS ------------------------------ Tous les termes d'une taille exactement égale à 5 : list(S.termes_de_taille("L", 5)) Tous les termes de taille 1 à 7 : list(S.termes("L", taille_maximale=7)) Tous les termes de taille 3 à 7 : list(S.termes("L", taille_minimale=3, taille_maximale=7)) Les vingt premiers termes d'une énumération potentiellement infinie : from itertools import islice list(islice(S.termes("L"), 20)) L'énumération se fait par taille croissante et élimine les doublons syntaxiques. Les variables muettes L1, L2, ... ne sont pas énumérées, car ce ne sont pas des éléments générateurs. 10. GÉNÉRATION ALÉATOIRE ----------------------- Générer un terme aléatoire de L : terme = S.terme_aleatoire("L", seed=123) Limiter la profondeur : terme = S.terme_aleatoire( "L", profondeur_maximale=8, seed=123, ) Donner des poids relatifs aux règles de production : S = Idioma("L=") poids = { "L|--a": 8, "L|--g(L1,L1)": 3, "L|--g(L,r(L))": 1, } terme = S.terme_aleatoire( "L", probabilites=poids, profondeur_maximale=8, seed=123, ) Les deux règles commençant par g reçoivent ici des poids différents. Les clés complètes disponibles peuvent être consultées avec : S.cles_regles("L") qui retourne : ( "L|--a", "L|--g(L1,L1)", "L|--g(L,r(L))", ) Une règle précise peut aussi être désignée par un couple : poids = { ("L", "a"): 8, ("L", "g(L1,L1)"): 3, ("L", "g(L,r(L))"): 1, } Une clé réduite au nom d'un opérateur reste autorisée : poids = {"a": 8, "g": 2} Dans ce cas, le poids 2 est attribué à chacune des règles dont l'opérateur racine est g. Une clé de règle complète peut ensuite surcharger ce poids : poids = { "a": 8, "g": 2, "L|--g(L,r(L))": 0.5, } Les noms longs et les couples d'opérateurs restent également utilisables pour pondérer toutes les règles ayant cet opérateur pour racine : poids = { "L_a": 5, "H.f": 2, ("H", "r"): 1, } La somme des poids n'a pas besoin d'être égale à 1. Les règles non mentionnées reçoivent un poids nul. Si, à cause de la limite de profondeur, toutes les règles admissibles ont un poids nul, le choix devient uniforme entre ces règles afin de garantir la terminaison. Créer une suite aléatoire reproductible : G = S.termes_aleatoires( "L", probabilites=poids, profondeur_maximale=8, seed=123, ) from itertools import islice list(islice(G, 10)) Lorsqu'une variable liée apparaît plusieurs fois dans une règle, son terme est choisi une seule fois puis réutilisé à l'identique dans toutes ses occurrences. 11. EXÉCUTION DU FICHIER ----------------------- Lancer directement : python automates_langages_multisortes.py Le programme affiche cette synopsis puis exécute une batterie de tests non interactifs couvrant : - la nouvelle syntaxe Idioma("L=<...>", "H=<...>") ; - les opérateurs partagés et leurs noms longs ; - la reconnaissance typée ; - les variables muettes et les variables liées ; - l'énumération sans répétition ; - la génération aléatoire reproductible ; - les pièces extérieures à tous les langages ; - les opérateurs multi-aires typés comme h(A..) ; - le rejet des définitions et arités incohérentes. ================================================================================ ''') def tests() -> None: S = Idioma( "L=", "H=", ) assert S.langages == ("L", "H") assert S.operateurs("L") == ("a", "b", "f", "g") assert S.operateurs("H") == ("a", "f", "r") assert S.meme_operateur("a", "L_a") assert S.meme_operateur("f", "H_f") assert S.reconnait("L", "a") assert S.reconnait("H", "a") assert S.reconnait("L", "f(a)") assert S.reconnait("H", "f(a)") assert S.reconnait("L", "L_f(a)") assert S.reconnait("L", "H_f(a)") assert S.reconnait("H", "L_f(a)") assert S.reconnait("H", "H_f(a)") assert S.reconnait("L", "L_a") assert S.reconnait("H", "H_a") assert S.reconnait("L", "g(a,r(a))") A = Idioma("L=", "H=") assert A.operateurs("L") == ("a", "f") assert A.reconnait("L", "f(a)") assert A.reconnait("L", "L_f(a)") assert A.reconnait("L", "H_f(a)") assert str(A.analyser("L", "L_f(a)")) == "f(a)" D = Idioma("L=") termes = list(D.termes("L", taille_maximale=5)) assert termes.count("f(a)") == 1 assert len(termes) == len(set(termes)) C = Idioma("L=", "H=") assert C.reconnait("L", "a") and C.reconnait("H", "a") P = Idioma("L=", "H=") assert P.meme_operateur("f", "L_f") assert P.reconnait("L", "f(a)") and P.reconnait("H", "f(a)") assert "L_f(a)" not in list(P.termes("H", taille_maximale=4)) # Un opérateur peut appartenir à plusieurs langages sans propriétaire # exclusif. Tous les noms longs correspondants sont des alias identiques. M = Idioma( "L=", "H=", "K=", ) assert M.operateurs("L") == ("a", "f") assert M.operateurs("H") == ("a", "f") assert M.operateurs("K") == ("a", "f") assert M.meme_operateur("L_f", "H_f") assert M.meme_operateur("H_f", "K_f") assert M.reconnait("K", "H_f(a)") assert M.reconnait("K", "K_f(L_a)") assert str(M.analyser("K", "H_f(L_a)")) == "f(a)" V = Idioma("L=") assert V.reconnait("L", "g(a,a)") assert V.reconnait("L", "g(L2,L2)") assert not V.reconnait("L", "g(a,f(a))") assert not V.reconnait("L", "g(L1,L2)") for definition in ("L", "L=a", "="): try: Idioma(definition) except (TypeError, ValueError): pass else: raise AssertionError(f"Définition incorrecte acceptée : {definition!r}") try: Idioma("L=", "L=") except ValueError: pass else: raise AssertionError("Un langage défini deux fois aurait dû être rejeté.") X = Idioma("L=") assert X.operateurs("L") == ("a", "g") assert X.pieces() == ("r",) assert X.reconnait("L", "g(a,r(a))") assert not X.reconnait("L", "r(a)") assert "g(a,r(a))" in list(X.termes("L", taille_maximale=4)) try: Idioma("L=") except ValueError: pass else: raise AssertionError("Une pièce utilisée avec deux arités aurait dû être rejetée.") poids = {"a": 4, "b": 4, "f": 2, "g": 1, "r": 2} for seed in range(50): t = S.terme_aleatoire( "L", poids, profondeur_maximale=8, seed=seed, ) assert S.reconnait("L", t), t assert S.terme_aleatoire("L", poids, seed=123) == S.terme_aleatoire( "L", poids, seed=123 ) # Pondération distincte de deux règles ayant le même opérateur racine. R = Idioma("L=") assert R.cles_regles("L") == ( "L|--a", "L|--g(L1,L1)", "L|--g(L,r(L))", ) seulement_diagonale = { "L|--a": 8, "L|--g(L1,L1)": 3, "L|--g(L,r(L))": 0, } termes_diagonaux = [ R.terme_aleatoire( "L", seulement_diagonale, profondeur_maximale=7, seed=i ) for i in range(100) ] assert all("r(" not in terme for terme in termes_diagonaux) seulement_r = { "L|--a": 8, "L|--g(L1,L1)": 0, "L|--g(L,r(L))": 3, } termes_r = [ R.terme_aleatoire( "L", seulement_r, profondeur_maximale=7, seed=i ) for i in range(100) ] assert all(terme == "a" or "r(" in terme for terme in termes_r) # Règle d'inclusion directe H|--L, pondérable séparément. I = Idioma("L=", "H=") assert I.regles("H") == ("|--L", "|--f(H)") assert I.cles_regles("H") == ("H|--L", "H|--f(H)") assert I.reconnait("H", "a") assert I.reconnait("H", "g(a,a)") assert I.reconnait("H", "f(a)") seulement_inclusion = { "L|--a": 10, "L|--g(L,L)": 0, "H|--L": 10, "H|--f(H)": 0, } assert all( I.terme_aleatoire( "H", seulement_inclusion, profondeur_maximale=6, seed=i ) == "a" for i in range(50) ) seulement_f = { "L|--a": 10, "L|--g(L,L)": 0, "H|--L": 0, "H|--f(H)": 10, } termes_f = [ I.terme_aleatoire( "H", seulement_f, profondeur_maximale=5, seed=i ) for i in range(50) ] assert all(t.startswith("f(") for t in termes_f) # Opérateurs multi-aires. U = Idioma("L=") assert U.regles("L") == ("|--a", "|--h(...)") assert U.reconnait("L", "h") assert U.reconnait("L", "h(a)") assert U.reconnait("L", "h(a,a,a)") assert U.reconnait("L", "h(h(a),a)") # Puisque h est lui-même un terme d'arité zéro, h(h) est aussi un terme. assert U.reconnait("L", "h(h)") premiers_u = list(U.termes("L", taille_maximale=3)) assert premiers_u[:6] == ["a", "h", "h(a)", "h(h)", "h(a,a)", "h(a,h)"] U1 = Idioma("L=") assert not U1.reconnait("L", "h") assert U1.reconnait("L", "h(a)") assert U1.reconnait("L", "h(a,a)") UT = Idioma("L=", "A=") assert UT.regles("L") == ("|--a", "|--h(A..)", "|--h(L,L)") assert UT.reconnait("L", "h") assert UT.reconnait("L", "h(A_a)") assert UT.reconnait("L", "h(A_a,A_b,A_c)") assert not UT.reconnait("L", "h(f(a))") # La règle binaire interne accepte deux termes de L, y compris h lui-même. assert UT.reconnait("L", "h(a,h)") for graine in range(20): terme = UT.terme_aleatoire( "L", profondeur_maximale=4, arite_maximale=4, seed=graine ) assert UT.reconnait("L", terme), terme U2 = Idioma("L=") assert not U2.reconnait("L", "h") assert not U2.reconnait("L", "h(a)") assert U2.reconnait("L", "h(a,a)") assert U2.reconnait("L", "h(a,a,a)") for graine in range(30): terme = U2.terme_aleatoire( "L", profondeur_maximale=4, arite_maximale=4, seed=graine ) assert U2.reconnait("L", terme), terme # Deux déclarations courtes homonymes créent deux opérateurs distincts. D = Idioma("L=", "H=") assert D.reconnait("L", "L_f(a)") assert D.reconnait("H", "H_f(a)") assert not D.reconnait("H", "L_f(a)") assert not D.reconnait("L", "H_f(a)") # Couche de syntaxe alternative : stockage interne canonique. ALT = Idioma( "L=", syntaxes={ "h": "prefixe", "p": "postfixe", "m": ("infixe", 100, "-"), }, ) assert ALT.reconnait("L", "habp") is False # postfixe sans opérande assert ALT.reconnait("L", "a m b") # m(a,b) assert ALT.reconnait("L", "ap") # p(a) assert ALT.reconnait("L", "h(a,b,p(a))") # canonique encore accepté assert str(ALT.analyser("L", "h(a,b,p(a))")) == "habap" assert "amb" in list(ALT.termes("L", taille_maximale=3)) DROITE = Idioma( "L=", syntaxes={"imp": ("infixe", 10, "+")}, ) assert DROITE.reconnait("L", "aimpbimpc") assert str(DROITE.analyser("L", "imp(a,imp(b,c))")) == "aimpbimpc" assert str(DROITE.analyser("L", "imp(imp(a,b),c)")) == "(aimpb)impc" DEL = Idioma( "L=", "H=", syntaxes={"f": ("delimite", "|", ">")}, ) assert DEL.reconnait("L", "|abab>") assert DEL.reconnait("H", "|cdcd>") assert not DEL.reconnait("L", "|ac>") assert str(DEL.analyser("L", "f(a,b,a,b)")) == "|abab>" assert str(DEL.analyser("H", "f(c,d,c,d)")) == "|cdcd>" assert DEL.reconnait("L", "||a>>") # f(f(a)) # Deux syntaxes délimitées peuvent partager leur délimiteur final. DEL_COMMUN = Idioma( "L=", syntaxes={ "f": ("delimite", "f", ">"), "g": ("delimite", "g", ">"), }, ) assert DEL_COMMUN.reconnait("L", "faa>") assert DEL_COMMUN.reconnait("L", "gaa>") assert str(DEL_COMMUN.analyser("L", "f(a,a)")) == "faa>" assert str(DEL_COMMUN.analyser("L", "g(a,a)")) == "gaa>" # Le délimiteur final peut être le caractère espace. DEL_ESPACE = Idioma( "L=", syntaxes={"f": ("delimite", "|", " ")}, ) assert DEL_ESPACE.reconnait("L", "|ab ") assert str(DEL_ESPACE.analyser("L", "f(a,b)")) == "|ab " print("Tous les tests non interactifs ont réussi.") if __name__ == "__main__": afficher_synopsis() tests()