# -*- coding: utf-8 -*-
"""
nuevo_idioma — génère un automate reconnaisseur de termes
==========================================================

Usage :
    A = nuevo_idioma("<a,b,f(.), g(.,.), h(.,.,.)>")
    A.reconoce("h(b, g(a,b), f(f(a)))")   # -> True
    A.reconoce("g(a)")                     # -> False

Le langage des termes étant algébrique (context-free) et non rationnel
(parenthésage arbitrairement profond), le reconnaisseur est un
automate à pile déterministe (PDA) construit à partir de la signature.
"""

import re


# ---------------------------------------------------------------------------
# 1. Analyse de la signature  "<a, b, f(.), g(.,.), h(.,.,.)>"
# ---------------------------------------------------------------------------

def _parse_signature(sig: str) -> dict:
    """Retourne un dictionnaire {symbole: arité}."""
    sig = sig.strip()
    if not (sig.startswith("<") and sig.endswith(">")):
        raise ValueError("La signature doit être entre crochets <...>")
    interieur = sig[1:-1]

    arites = {}
    # Un générateur :  nom  éventuellement suivi de (., ., ..., .)
    motif = re.compile(r"\s*([A-Za-z_]\w*)\s*(\(\s*\.(?:\s*,\s*\.)*\s*\))?\s*")
    pos = 0
    while pos < len(interieur):
        m = motif.match(interieur, pos)
        if not m:
            raise ValueError(f"Signature mal formée près de : {interieur[pos:]!r}")
        nom, parens = m.group(1), m.group(2)
        arite = parens.count(".") if parens else 0
        if nom in arites:
            raise ValueError(f"Symbole déclaré deux fois : {nom}")
        arites[nom] = arite
        pos = m.end()
        if pos < len(interieur):
            if interieur[pos] != ",":
                raise ValueError(f"Virgule attendue près de : {interieur[pos:]!r}")
            pos += 1
    if not arites:
        raise ValueError("Signature vide")
    return arites


# ---------------------------------------------------------------------------
# 2. Lexeur : découpe un terme en lexèmes
# ---------------------------------------------------------------------------

_LEX = re.compile(r"\s*(?:([A-Za-z_]\w*)|([(),]))")

def _lexer(texte: str):
    """Génère la suite des lexèmes ; lève ValueError sur caractère illégal."""
    pos = 0
    while pos < len(texte):
        m = _LEX.match(texte, pos)
        if not m:
            reste = texte[pos:].strip()
            if not reste:          # espaces terminaux
                return
            raise ValueError(f"Caractère illégal près de : {reste!r}")
        yield m.group(1) or m.group(2)
        pos = m.end()


# ---------------------------------------------------------------------------
# 3. L'automate à pile
# ---------------------------------------------------------------------------

TERME = "⟨T⟩"   # symbole de pile : « on attend ici un terme »


class AutomateTermes:
    """Automate à pile déterministe reconnaissant les termes de la signature."""

    def __init__(self, arites: dict):
        self.arites = dict(arites)

    # -- transition élémentaire ---------------------------------------------
    def _pas(self, pile, lexeme):
        """Consomme un lexème, met à jour la pile. Retourne False si blocage."""
        if not pile:
            return False                      # entrée trop longue
        attendu = pile.pop()

        if attendu == TERME:
            arite = self.arites.get(lexeme)
            if arite is None:
                return False                  # symbole inconnu ou ponctuation
            if arite > 0:
                # on attend ensuite :  ( T , T , ... , T )
                # empilé en ordre inverse pour que '(' soit au sommet
                seq = [")"]
                for i in range(arite):
                    seq.append(TERME)
                    if i < arite - 1:
                        seq.append(",")
                seq.append("(")
                pile.extend(seq)
            return True

        # attendu est un lexème littéral : '(' ',' ')'
        return lexeme == attendu

    # -- reconnaissance ------------------------------------------------------
    def reconoce(self, terme: str, trace: bool = False) -> bool:
        pile = [TERME]
        try:
            for lex in _lexer(terme):
                if trace:
                    print(f"  lexème {lex!r:6}  pile = {pile}")
                if not self._pas(pile, lex):
                    if trace:
                        print("  ✗ blocage")
                    return False
        except ValueError:
            return False
        ok = not pile
        if trace:
            print(f"  fin d'entrée, pile = {pile}  ->  {'✓ accepté' if ok else '✗ refusé'}")
        return ok

    def __repr__(self):
        gen = ", ".join(f"{s}/{a}" for s, a in self.arites.items())
        return f"AutomateTermes⟨{gen}⟩"


# ---------------------------------------------------------------------------
# 4. Le constructeur demandé
# ---------------------------------------------------------------------------

def nuevo_idioma(signature: str) -> AutomateTermes:
    """Construit l'automate reconnaisseur associé à la signature donnée."""
    return AutomateTermes(_parse_signature(signature))


# ---------------------------------------------------------------------------
# 5. Auto-test
# ---------------------------------------------------------------------------

SYNOPSIE = """\
================================================================
 nuevo_idioma — boîte à outils pour langages algébriques
================================================================
 nuevo_idioma(sig)          construit l'automate reconnaisseur
                            à partir d'une signature, p. ex.
                            "<a, b, f(.), g(.,.), h(.,.,.)>"
                            ( "(.)"=unaire, "(.,.)"=binaire, ... )

 A.reconoce(terme)         -> True / False
 A.reconoce(t, trace=True) affiche pas à pas la pile du PDA
 repr(A)                    résume la signature (symbole/arité)
================================================================
"""

if __name__ == "__main__":
    print(SYNOPSIE)

    A = nuevo_idioma("<a, b, f(.), g(.,.), h(.,.,.)>")
    print(A)

    positifs = [
        "a",
        "f(b)",
        "g(a, f(a))",
        "h(b, g(a,b), f(f(a)))",
        "  f(  g( a , b ) )  ",
    ]
    negatifs = [
        "",              # vide
        "c",             # symbole inconnu
        "f",             # arité non respectée
        "f(a,b)",        # trop d'arguments
        "g(a)",          # pas assez d'arguments
        "h(a,b,)",       # argument manquant
        "f(a))",         # parenthèse en trop
        "a b",           # deux termes juxtaposés
        "f(a) x",        # résidu après un terme valide
    ]

    print("\n-- termes valides --")
    for t in positifs:
        r = A.reconoce(t)
        print(f"  {t!r:35} -> {r}")
        assert r

    print("\n-- termes invalides --")
    for t in negatifs:
        r = A.reconoce(t)
        print(f"  {t!r:35} -> {r}")
        assert not r

    print("\n-- trace détaillée sur h(a, f(b), b) --")
    A.reconoce("h(a, f(b), b)", trace=True)

    print("\nTous les tests passent ✓")