#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
idioma_recursif.py — Automate récursif reconnaissant les termes
d'un langage algébrique.

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

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

L'automate est l'ensemble de règles de production :

    { |-- a,  |-- b,  |-- f(.),  |-- g(.,.),  |-- h(.,.,.) }

Chaque point "." désigne un terme quelconque du langage et constitue
un appel récursif de l'automate lui-même.
"""

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]

    motif = re.compile(r"([A-Za-z_][A-Za-z_0-9]*)\s*(\((\s*\.\s*(,\s*\.\s*)*)\))?")

    signature = {}
    pos = 0
    while pos < len(interieur):
        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)
        arite = 0 if m.group(2) is None else m.group(2).count(".")
        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 récursif
# ----------------------------------------------------------------------

class Echec(Exception):
    """Levée quand aucune règle de production ne s'applique."""


class AutomateRecursif:
    """
    Automate récursif : une règle |-- s(., ..., .) par symbole s de
    la signature. Le symbole lu sélectionne la règle ; chaque point
    de la règle est un appel récursif de l'automate.
    """

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

    # -- découpage en lexèmes -----------------------------------------------
    def _lexemes(self, chaine: str) -> list:
        motif = re.compile(r"[A-Za-z_][A-Za-z_0-9]*|[(),]")
        lexemes, pos = [], 0
        while pos < len(chaine):
            if chaine[pos] in " \t\n":
                pos += 1
                continue
            m = motif.match(chaine, pos)
            if not m:
                raise Echec(f"caractère illisible {chaine[pos]!r}")
            lexemes.append(m.group(0))
            pos = m.end()
        return lexemes

    # -- l'automate proprement dit -------------------------------------------
    def _terme(self, lexemes: list, i: int) -> int:
        """
        Reconnaît un terme à partir de la position i.
        Retourne la position atteinte, ou lève Echec.
        """
        if i >= len(lexemes):
            raise Echec("fin d'entrée : un terme était attendu")
        symbole = lexemes[i]
        if symbole not in self.signature:
            raise Echec(f"symbole {symbole!r} étranger à la signature")
        i += 1
        n = self.signature[symbole]

        if n == 0:                                 # règles |-- a, |-- b
            return i

        i = self._attendre(lexemes, i, "(")        # règles |-- s(., ..., .)
        for k in range(n):
            i = self._terme(lexemes, i)            # le point "." : récursion
            if k < n - 1:
                i = self._attendre(lexemes, i, ",")
        return self._attendre(lexemes, i, ")")

    @staticmethod
    def _attendre(lexemes: list, i: int, lexeme: str) -> int:
        if i >= len(lexemes) or lexemes[i] != lexeme:
            trouve = lexemes[i] if i < len(lexemes) else "fin d'entrée"
            raise Echec(f"{lexeme!r} attendu, {trouve!r} trouvé")
        return i + 1

    # -- reconnaissance -------------------------------------------------------
    def reconnait(self, chaine: str) -> bool:
        """True si `chaine` est un terme du langage, False sinon."""
        try:
            lexemes = self._lexemes(chaine)
            fin = self._terme(lexemes, 0)
            return fin == len(lexemes)             # toute l'entrée est consommée
        except Echec:
            return False

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

    def __repr__(self):
        regles = ", ".join(
            f"|--{s}" if n == 0 else f"|--{s}({','.join(['.'] * n)})"
            for s, n in self.signature.items()
        )
        return "{" + regles + "}"


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

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

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


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

SYNOPSIS = """
======================================================================
 idioma_recursif — automate récursif pour un langage algébrique
======================================================================
 Le langage est présenté par ses générateurs entre < et > :

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

 L'automate associé est l'ensemble de règles de production :

     { |--a, |--b, |--f(.), |--g(.,.), |--h(.,.,.) }

 Le symbole lu sélectionne la règle à appliquer ; chaque point "."
 désigne un terme quelconque et constitue un appel récursif de
 l'automate. Une chaîne est reconnue si l'appel initial réussit en
 consommant exactement toute l'entrée.

 idioma_recursif(présentation) retourne cet automate A ;
 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_recursif(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}")