#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
idioma_sortes.py — Systèmes de langages algébriques multi-sortes.

Plusieurs langages sont définis simultanément, chacun présenté par
ses générateurs ; les opérateurs déclarent le langage attendu à
chaque position d'argument :

    L = <a, b, f(H), g(H,L)>
    H = <e, j(H,H), k(H,L,H)>

Un point "." en position d'argument désigne le langage en cours de
définition : g(H,.) équivaut à g(H,L) dans la présentation de L.

Les automates associés sont mutuellement récursifs :

    automate L : { |--a, |--b, |--f(H), |--g(H,L) }
    automate H : { |--e, |--j(H,H), |--k(H,L,H) }

Chaque position d'argument est un appel récursif de l'automate du
langage désigné. Un opérateur est complètement désigné par le couple
(langage, nom) : un f de L et un f de H sont distincts.
"""

import re


# ----------------------------------------------------------------------
#  1. Analyse d'un système de présentations
# ----------------------------------------------------------------------

def analyse_presentation(presentation: str):
    """
    Analyse une présentation  "L = <a, b, f(H), g(H,L)>"  et retourne
    le couple (nom_du_langage, {opérateur: profil}) où le profil est
    le tuple des langages attendus aux positions d'argument
    (tuple vide pour une constante). Le point "." y désigne le
    langage en cours de définition.

    >>> analyse_presentation("L = <a, b, f(H), g(H,.)>")
    ('L', {'a': (), 'b': (), 'f': ('H',), 'g': ('H', 'L')})
    """
    m = re.match(r"\s*([A-Za-z_][A-Za-z_0-9]*)\s*=\s*<(.*)>\s*$",
                 presentation, re.DOTALL)
    if not m:
        raise ValueError(f"Présentation illisible : {presentation!r}")
    langage, interieur = m.group(1), m.group(2)

    motif = re.compile(
        r"([A-Za-z_][A-Za-z_0-9]*)\s*"                       # nom d'opérateur
        r"(\(\s*([A-Za-z_][A-Za-z_0-9]*|\.)"                 # premier argument
        r"(\s*,\s*([A-Za-z_][A-Za-z_0-9]*|\.))*\s*\))?")     # suivants

    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 : "
                             f"{interieur[pos:]!r}")
        operateur = m.group(1)
        if m.group(2) is None:
            profil = ()                                       # constante
        else:
            args = re.findall(r"[A-Za-z_][A-Za-z_0-9]*|\.", m.group(2))
            profil = tuple(langage if arg == "." else arg for arg in args)
        if operateur in signature and signature[operateur] != profil:
            raise ValueError(f"L'opérateur {langage}.{operateur} est "
                             f"déclaré avec deux profils.")
        signature[operateur] = profil
        pos = m.end()
    if not signature:
        raise ValueError(f"Le langage {langage} n'a aucun générateur.")
    return langage, signature


def analyse_systeme(*presentations):
    """
    Analyse un système de présentations et vérifie sa cohérence :
    tout langage mentionné en argument est défini, et chaque langage
    est habité (au moins un terme fini y existe).

    Retourne { langage : { opérateur : profil } }.
    """
    systeme = {}
    for p in presentations:
        langage, signature = analyse_presentation(p)
        if langage in systeme:
            raise ValueError(f"Le langage {langage} est présenté deux fois.")
        systeme[langage] = signature

    # -- tout langage mentionné doit être défini ------------------------------
    for langage, signature in systeme.items():
        for operateur, profil in signature.items():
            for arg in profil:
                if arg not in systeme:
                    raise ValueError(
                        f"{langage}.{operateur} attend un terme du langage "
                        f"{arg!r}, qui n'est pas défini dans le système.")

    # -- chaque langage doit être habité (point fixe croissant) ---------------
    habites = set()
    progres = True
    while progres:
        progres = False
        for langage, signature in systeme.items():
            if langage in habites:
                continue
            for profil in signature.values():
                if all(arg in habites for arg in profil):
                    habites.add(langage)
                    progres = True
                    break
    vides = set(systeme) - habites
    if vides:
        raise ValueError(f"Langage(s) vide(s), aucun terme constructible : "
                         f"{sorted(vides)}")
    return systeme


# ----------------------------------------------------------------------
#  2. Le système d'automates mutuellement récursifs
# ----------------------------------------------------------------------

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


class AutomateSortes:
    """
    Système d'automates mutuellement récursifs, un par langage.

    La reconnaissance d'un terme du langage S lit un symbole, cherche
    l'opérateur (S, symbole) — le couple qui désigne complètement
    l'opérateur — puis, pour chaque position d'argument de son profil,
    appelle récursivement l'automate du langage attendu à cette
    position.
    """

    def __init__(self, systeme: dict):
        self.systeme = {lg: dict(sig) for lg, sig in systeme.items()}

    # -- découpage en lexèmes --------------------------------------------------
    @staticmethod
    def _lexemes(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 du langage `langage` ----------------------------------------
    def _terme(self, langage: str, lexemes: list, i: int) -> int:
        if i >= len(lexemes):
            raise Echec(f"fin d'entrée : un terme de {langage} était attendu")
        symbole = lexemes[i]
        signature = self.systeme[langage]
        if symbole not in signature:                # l'opérateur est désigné
            raise Echec(f"{symbole!r} n'est pas un "        # par (langage, nom)
                        f"opérateur du langage {langage}")
        i += 1
        profil = signature[symbole]

        if not profil:                              # constante : |--s
            return i

        i = self._attendre(lexemes, i, "(")
        for pos, arg in enumerate(profil):
            i = self._terme(arg, lexemes, i)        # appel récursif de
            if pos < len(profil) - 1:               # l'automate du langage
                i = self._attendre(lexemes, i, ",") # attendu à cette position
        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, langage: str, chaine: str) -> bool:
        """True si `chaine` est un terme du langage `langage`."""
        if langage not in self.systeme:
            raise ValueError(f"Langage inconnu : {langage!r}")
        try:
            lexemes = self._lexemes(chaine)
            fin = self._terme(langage, lexemes, 0)
            return fin == len(lexemes)
        except Echec:
            return False

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

    # -- l'automate d'un langage, vu comme fonction d'une seule variable -----------
    def automate(self, langage: str):
        """Retourne l'automate du langage : une fonction chaine -> bool."""
        if langage not in self.systeme:
            raise ValueError(f"Langage inconnu : {langage!r}")
        return lambda chaine: self.reconnait(langage, chaine)

    def __repr__(self):
        lignes = []
        for langage, signature in self.systeme.items():
            regles = ", ".join(
                f"|--{op}" if not profil else f"|--{op}({','.join(profil)})"
                for op, profil in signature.items())
            lignes.append(f"automate {langage} : {{{regles}}}")
        return "\n".join(lignes)


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

def idioma_sortes(*presentations) -> AutomateSortes:
    """
    Construit le système d'automates mutuellement récursifs
    reconnaissant les termes d'un système de langages.

    >>> S = idioma_sortes("L = <a,b,f(H), g(H,L)>",
    ...                   "H = <e, j(H,H),k(H,L,H)>")
    >>> S("L", "g(e, a)")
    True
    >>> S("L", "f(a)")          # a est un terme de L, pas de H
    False
    """
    return AutomateSortes(analyse_systeme(*presentations))


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

SYNOPSIS = """
======================================================================
 idioma_sortes — langages algébriques multi-sortes mutuellement
                 récursifs
======================================================================
 Plusieurs langages sont présentés simultanément ; chaque opérateur
 déclare le langage attendu à chaque position d'argument :

     L = <a, b, f(H), g(H,L)>          (g(H,.) est aussi admis)
     H = <e, j(H,H), k(H,L,H)>

 Les automates associés sont mutuellement récursifs :

     automate L : { |--a, |--b, |--f(H), |--g(H,L) }
     automate H : { |--e, |--j(H,H), |--k(H,L,H) }

 Chaque position d'argument est un appel récursif de l'automate du
 langage désigné. Un opérateur est complètement désigné par le
 couple (langage, nom) : un f de L et un f de H sont distincts.

 idioma_sortes(présentation1, présentation2, ...) retourne le
 système S :
    - S("L", "terme")          reconnaissance dans le langage L ;
    - S.automate("L")          l'automate de L, seul, en fonction.
======================================================================
"""

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

    presentations = ("L = <a,b,f(H), g(H,L)>",
                     "H = <e, j(H,H),k(H,L,H)>")
    for p in presentations:
        print(f"Présentation : {p}")
    S = idioma_sortes(*presentations)
    print(f"\n{S}\n")

    essais = [
        # (langage, terme, commentaire)
        ("L", "a",                       "constante de L"),
        ("L", "f(e)",                    "f attend un terme de H"),
        ("L", "g(e, a)",                 "g attend H puis L"),
        ("L", "g(j(e,e), f(e))",         "composition croisée"),
        ("L", "f(k(e, g(e,b), e))",      "L dans H dans L"),
        ("L", "f(a)",                    "a est de L : mauvaise sorte"),
        ("L", "g(a, e)",                 "arguments intervertis"),
        ("L", "e",                       "e est de H, pas de L"),
        ("H", "e",                       "constante de H"),
        ("H", "j(e, k(e,a,e))",          "composition dans H"),
        ("H", "k(e, f(e), j(e,e))",      "k attend H, L, H"),
        ("H", "k(e, e, e)",              "l'argument médian doit être de L"),
        ("H", "a",                       "a est de L, pas de H"),
    ]

    print("Essais de reconnaissance :")
    for langage, terme, commentaire in essais:
        verdict = "accepté " if S(langage, terme) else "rejeté  "
        print(f"   {verdict} dans {langage} : {terme:<24} ({commentaire})")

    # -- un même nom d'opérateur dans deux langages -----------------------------
    print("\nDésignation complète (langage, nom) — un même nom, deux "
          "opérateurs :")
    D = idioma_sortes("M = <c, f(M)>", "N = <d, f(M,N)>")
    for langage, terme in [("M", "f(c)"), ("N", "f(c,d)"),
                           ("M", "f(c,d)"), ("N", "f(c)")]:
        verdict = "accepté " if D(langage, terme) else "rejeté  "
        print(f"   {verdict} dans {langage} : {terme}")
    print("   M.f est unaire, N.f est binaire : mêmes noms, opérateurs "
          "distincts.")