#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
idioma.py — Reconnaissance des termes d'un langage algébrique.

Un langage est présenté par ses générateurs entre crochets angulaires :

    L = <a, b, f(.), g(.,.), h(.,.,.)>

  - un symbole sans suffixe est une constante (arité 0) ;
  - le suffixe (.)     indique une arité 1 (unaire)  ;
  - le suffixe (.,.)   indique une arité 2 (binaire) ;
  - le suffixe (.,.,.) indique une arité 3 (ternaire), etc.

La fonction idioma(spec) retourne un AUTOMATE À PILE capable de
reconnaître si une chaîne est un terme bien formé du langage.
"""

import re


# ----------------------------------------------------------------------
#  1. Analyse de la présentation  <a, b, f(.), g(.,.), ...>
# ----------------------------------------------------------------------

def analyse_signature(spec: str) -> dict:
    """
    Extrait de la présentation la signature du langage :
    un dictionnaire { symbole : arité }.

    >>> analyse_signature("<a,b,f(.), g(.,.),h(.,.,.)>")
    {'a': 0, 'b': 0, 'f': 1, 'g': 2, 'h': 3}
    """
    spec = spec.strip()
    if not (spec.startswith("<") and spec.endswith(">")):
        raise ValueError("La présentation doit être encadrée par < et >.")
    interieur = spec[1:-1]

    # Un générateur : identificateur, éventuellement suivi de (., ., ...)
    motif = re.compile(r"([A-Za-z_][A-Za-z_0-9]*)\s*(\((\s*\.\s*(,\s*\.\s*)*)\))?")

    signature = {}
    pos = 0
    while pos < len(interieur):
        # sauter espaces et virgules de séparation
        while pos < len(interieur) and interieur[pos] in " ,\t\n":
            pos += 1
        if pos >= len(interieur):
            break
        m = motif.match(interieur, pos)
        if not m:
            raise ValueError(f"Générateur illisible à partir de : {interieur[pos:]!r}")
        symbole = m.group(1)
        if m.group(2) is None:
            arite = 0                       # constante
        else:
            arite = m.group(2).count(".")   # nombre de points = arité
        if symbole in signature and signature[symbole] != arite:
            raise ValueError(f"Le symbole {symbole!r} est déclaré avec deux arités.")
        signature[symbole] = arite
        pos = m.end()
    if not signature:
        raise ValueError("La présentation ne contient aucun générateur.")
    return signature


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

class AutomateTermes:
    """
    Automate à pile reconnaissant les termes clos d'une signature.

    Principe : la pile contient les attentes de l'automate.
    On empile initialement l'attente d'un TERME ; la lecture d'un
    symbole d'arité n remplace cette attente par la séquence
        '(' TERME ',' TERME ... ')'
    (rien du tout si n = 0). La chaîne est reconnue si, l'entrée
    épuisée, la pile est vide.
    """

    TERME = "«terme»"          # symbole de pile : on attend un terme

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

    # -- lexème par lexème -------------------------------------------------
    def _lexemes(self, chaine: str):
        motif = re.compile(r"\s*([A-Za-z_][A-Za-z_0-9]*|\(|\)|,)")
        pos = 0
        while pos < len(chaine):
            if chaine[pos] in " \t\n":
                pos += 1
                continue
            m = motif.match(chaine, pos)
            if not m:
                yield ("ERREUR", chaine[pos])
                return
            lex = m.group(1)
            pos = m.end()
            yield ("SYMBOLE" if lex not in "(),," else lex, lex)

    # -- reconnaissance ----------------------------------------------------
    def reconnait(self, chaine: str, trace: bool = False) -> bool:
        """Retourne True si `chaine` est un terme du langage."""
        pile = [self.TERME]
        lexemes = list(self._lexemes(chaine))

        def montre(etape, lu):
            if trace:
                print(f"    lu={lu!r:<8} pile={pile}")

        if trace:
            print(f"    pile initiale : {pile}")

        i = 0
        while i < len(lexemes):
            genre, lex = lexemes[i]
            if genre == "ERREUR":
                return False
            if not pile:
                return False                      # entrée en trop
            attendu = pile.pop()

            if attendu == self.TERME:
                # il faut lire un symbole de la signature
                if genre != "SYMBOLE" or lex not in self.signature:
                    return False
                n = self.signature[lex]
                if n > 0:
                    # empiler ')' TERME (',' TERME)*  '('   — ordre inverse
                    a_empiler = [")"]
                    for k in range(n):
                        a_empiler.append(self.TERME)
                        if k < n - 1:
                            a_empiler.append(",")
                    a_empiler.append("(")
                    pile.extend(a_empiler)
            else:
                # attendu est un lexème de ponctuation précis
                if lex != attendu:
                    return False
            montre(attendu, lex)
            i += 1

        return not pile                            # tout consommé, rien en attente

    # -- confort -----------------------------------------------------------
    def __call__(self, chaine: str) -> bool:
        return self.reconnait(chaine)

    def __repr__(self):
        gens = ", ".join(
            s if n == 0 else f"{s}({','.join('.' * 1 for _ in range(n))})"
            for s, n in self.signature.items()
        )
        return f"AutomateTermes<{gens}>"


# ----------------------------------------------------------------------
#  3. La fonction demandée
# ----------------------------------------------------------------------

def idioma(spec: str) -> AutomateTermes:
    """
    Construit et retourne l'automate reconnaissant les termes du
    langage présenté par `spec`.

    >>> A = idioma("<a,b,f(.), g(.,.),h(.,.,.)>")
    >>> A("g(a, f(b))")
    True
    >>> A("f(a, b)")
    False
    """
    return AutomateTermes(analyse_signature(spec))


# ----------------------------------------------------------------------
#  4. Programme principal
# ----------------------------------------------------------------------

SYNOPSIS = """
======================================================================
 idioma — reconnaissance des termes d'un langage algébrique
======================================================================
 Un langage est présenté par ses générateurs entre < et > :

     <a, b, f(.), g(.,.), h(.,.,.)>

   . un symbole nu est une constante        (arité 0)
   . f(.)      est un opérateur unaire      (arité 1)
   . g(.,.)    est un opérateur binaire     (arité 2)
   . h(.,.,.)  est un opérateur ternaire    (arité 3)

 idioma(présentation) retourne un automate à pile A tel que
 A("terme") vaut True si et seulement si le terme est bien formé.
======================================================================
"""

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

    presentation = "<a,b,f(.), g(.,.),h(.,.,.)>"
    print(f"Présentation du langage : {presentation}")
    A = idioma(presentation)
    print(f"Automate construit      : {A}\n")

    essais = [
        "a",                      # constante seule
        "f(a)",                   # unaire
        "g(a, f(b))",             # composition
        "h(f(f(a)), b, g(a,a))",  # terme profond
        "f(a, b)",                # mauvaise arité
        "g(a)",                   # mauvaise arité
        "c",                      # symbole inconnu
        "f(a",                    # parenthèse manquante
        "g(a, b) b",              # entrée en trop
    ]

    print("Essais de reconnaissance :")
    for t in essais:
        verdict = "accepté " if A(t) else "rejeté  "
        print(f"   {verdict} : {t}")

    print("\nExemple avec trace de la pile pour g(a, f(b)) :")
    A.reconnait("g(a, f(b))", trace=True)