#!/usr/bin/env python
# -*- coding: latin-1 -*-
#
##############################################################################
#
# metacomp 2.5beta3: a metacompiler for RLL(1) grammars
# Copyright (C) 2008 Juan Miguel Vilar and Andrés Marzal
#                    Universitat Jaume I, Castelló (Spain)
#
# This program is free software; you can redistribute it and/or
#  modify it under the terms of the GNU General Public License
#  as published by the Free Software Foundation; either version 2
#  of the License, or (at your option) any later version.
#
#  This program is distributed in the hope that it will be useful,
#  but WITHOUT ANY WARRANTY; without even the implied warranty of
#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#  GNU General Public License for more details.
#
#  You should have received a copy of the GNU General Public License
#  along with this program; if not, write to the Free Software
#  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
#
#  Any questions regarding this software should be directed to:
#
#   Juan Miguel Vilar
#   Departament de Llenguatges i Sistemes Informàtics
#   Universitat Jaume I
#   E12071 Castellón (SPAIN)
#
#   email: jvilar@lsi.uji.es
#
##############################################################################
#
# Fichero: gramatica.py
#

from sets import Set

# Funciones auxiliares:

def _gestion_orden(orden, nombre):
    orden[nombre]= orden.get(nombre, 0)+1
    return `orden[nombre]`

def _set_strlista(s):
    return "[ '%s' ]" % "', '".join(s,)

def _test_set(s):
    if len(s)==1:
        e= s.pop()
        s.add(e)
        return "mc_al.actual.cat== '%s'" % e
    else:
        return "mc_al.actual.cat in %s" % _set_strlista(s)

def _test_no_set(s):
    if len(s)==1:
        e= s.pop()
        s.add(e)
        return "mc_al.actual.cat!= '%s'" % e
    else:
        return "mc_al.actual.cat not in [ '%s' ]" % "', '".join(s,)


def clausura(eltos, ctos, influye):
    p= Set(eltos) # pendientes
    while p:
        e= p.pop()
        ce= ctos[e]
        for f in influye[e]:
            cf= ctos[f]
            l= len(cf)
            cf.update(ce)
            if l!= len(cf):
                p.add(f)

##############################################################################

class Regla:
    "Representación de las reglas"
    def __init__(self, izda, dcha, nl):
        self.nl= nl
        self.izda= izda
        self.dcha= dcha

        self.izda.reglasizda.append(self)

        def escribe_mi_nt(self, mi_nt= self.izda):
            self.mi_nt= mi_nt
        self.dcha.aplica_funcion(escribe_mi_nt)

        self.simbolos= []
        def averigua_simbolos(self, s=self.simbolos):
            if isinstance(self, NoTerminal) or isinstance(self, Terminal):
                s.append(self)
        self.dcha.aplica_funcion(averigua_simbolos)

    def __str__(self):
        return "%s -> %s ;" % (str(self.izda),str(self.dcha))

    def regla(self):
        return "%s -> %s ;" % (self.izda.regla(), self.dcha.regla())

    def aplica_funcion(self,f):
        self.izda.aplica_funcion(f)
        self.dcha.aplica_funcion(f)

class Pdcha:
    "Clase genérica para las partes derechas de las reglas"
    def __init__(self, anulable, nl):
        self.nl= nl
	self.esanulable= anulable
        self.misprimeros= Set()
        self.missiguientes= Set()
        self.misaceptables= None
        self.ninventario= None

    def regla(self):
        # Devuelve la regla como cadena, sin las acciones
        return str(self)

    def anulable(self):
        """Devuelve True si es anulable, False si no lo es y None si
        no se sabe"""
        return self.esanulable

    def influye_anulable(self, inf):
        """Añade self a cada uno de los elementos de inf que influyen
        para que self sea anulable."""
        pass

    def comprueba_anulable(self):
        """Intenta averiguar si self es ya anulable"""
        pass

    def primeros(self):
        # Devuelve los primeros de parte derecha
        return self.misprimeros

    def influye_primeros(self, inf, primeros):
        """Añade self.ninventario a los elementos de inf que influyen
        para los primeros de self. Asigna a primeros[self.ninventario]
        el conjunto propio de primeros."""
        primeros[self.ninventario]= self.misprimeros

    def siguientes(self):
        """Devuelve los siguientes de self"""
        return self.missiguientes

    def influye_siguientes(self, inf, siguientes):
        """Añade a inf las influencias del cálculo de siguientes que
        pueden encontrarse desde self. Asigna a
        siguientes[self.ninventario] el conjunto propio de siguientes."""
        siguientes[self.ninventario]= self.missiguientes

    def propaga_primeros_siguientes(self):
        """Propaga los primeros de un elemento a los siguientes de sus
        precedentes. Se aplica en secuencias y clausuras."""
        pass

    def aceptables(self):
        """Devuelve la unión de los primeros con los siguientes si es anulable"""
        return self.misaceptables

    def prepara_aceptables(self):
        if self.anulable():
            self.misaceptables= self.primeros().union(self.siguientes())
        else:
            self.misaceptables= self.primeros().copy()

    def genera_codigo(self, traza):
        """ Genera el código de la regla. Solo se usa para los no terminales
            traza: genera código para escribir la traza (arbol o traza)."""
        return ""

    def genera_codigo_interno(self, pizda, orden, garantizados, traza, esPuro):
        """Genera la parte del código de esta pdcha.
            pizda: parte izquierda de la regla que se está tratando
            ordenT: diccionarios para controlar la numeración de terminales y
              no terminales.
            garantizados: conjunto de terminales que pueden llegar a este punto.
              Son siempre aceptables. None si no se sabe.
            traza: formato de la traza ("A" arbol, "t" traza).
            esPuro: cierto si se está generando un analizador sintáctico puro."""
        return ""

    def aplica_funcion(self,f):
        # Aplica la función f sobre sí mismo y sus descendientes
        f(self)

    def recursividad_izquierda(self, nt):
        """Devuelve True si el nt tiene recursividad a izquierdas, False si no"""
        return True

class NoTerminal(Pdcha):
    "Representa los no terminales"
    def __init__(self, nombre, nl):
        self.nombre= nombre
        self.reglasizda= [] # reglas en las que este no terminal aparece
        		    # en la parte izquierda
        self.reglasdcha= [] # reglas en las que este no terminal aparece
        		    # en la parte derecha
        self.traterror= None
        Pdcha.__init__(self, None, nl)

    def influye_anulable(self, inf):
        for r in self.reglasizda:
            n= r.dcha.ninventario
            inf[n].append(self)

    def comprueba_anulable(self):
        for r in self.reglasizda:
            if r.dcha.anulable():
                self.esanulable= True
                break

    def influye_primeros(self, inf, primeros):
        yo= self.ninventario
        for r in self.reglasizda:
            inf[r.dcha.ninventario].append(yo)
        primeros[self.ninventario]= self.misprimeros

    def influye_siguientes(self, inf, siguientes):
        yo= self.ninventario
        for r in self.reglasizda:
            inf[yo].append(r.dcha.ninventario)
        siguientes[self.ninventario]= self.missiguientes

    def __str__(self):
        return "<%s>" % self.nombre

    def tratamientoError(self,tratamiento):
        self.traterror= tratamiento

    def genera_codigo(self, traza, esPuro= None):
        c= []
        if esPuro:
            c.append("def mc_analiza_%s(self):" % self.nombre)
        else:
            c.append("def mc_analiza_%s(self, %s):" % (self.nombre,self.nombre))
        indent="  "
        # La traza:
        if traza=="t":
            c.append(indent+"global indentacion_traza")
            c.append(indent+"""mc_traza("> %s %%s\\n" %% self.mc_al.actual)""" % self)
            c.append(indent+"indentacion_traza= indentacion_traza+2")
        elif traza=="A":
            c.append(indent+"global indentacion_traza")
            c.append(indent+r"""mc_traza('("%s" "línea: %%d"\n' %% self.mc_al.actual.nlinea)""" % self)
            c.append(indent+"indentacion_traza= indentacion_traza+2")
        # Hacemos accesible el analizador léxico:
        c.append(indent+"mc_al= self.mc_al")
        # Comprobamos el tratamiento de errores:
        if self.traterror and not esPuro:
            c.append(indent+"self.mc_reintento.append(1)")
            c.append(indent+"mc_reintentar= self.mc_reintentar")
            c.append(indent+"while self.mc_reintento[-1]:")
            c.append(indent+"  self.mc_reintento[-1]= 0")
            c.append(indent+"  try:")
            indent="      "
        c.append(indent+"if not %s:" % _test_set(self.misaceptables))
        if traza:
          c.append(indent+'  mc_traza("Error, no se encuentra ningún primero de %s.\\n")' % self)
        c.append(indent+"  mc_error('%s', %s)" % (self, _set_strlista(self.misaceptables)))
        eselse= 0
        cadif= "if"
        n=0
        for r in self.reglasizda:
            n= n+1
            if len(self.reglasizda)> 1:
                if n== len(self.reglasizda):
                    c.append(indent+"else:")
                else:
                    c.append(indent+ cadif+ " %s:" % _test_set(r.dcha.aceptables()))
                cadif="elif"
                indent= indent+"  "
            # La traza:
            if traza=="t":
                c.append(indent+"""mc_traza("Aplico regla: "+"""+ `r.regla()` +"""+"\\n")""")
            if not esPuro:
                # Generamos los atributos y los alias:
                orden= {}
                for s in r.simbolos:
                    _gestion_orden(orden, s.nombre)
                    if isinstance(s, NoTerminal):
                        nto= s.nombre+`orden[s.nombre]`
                        if orden[s.nombre]== 1 and s!= self:
                            c.append(indent+"%s= %s= Atributos()" % (s.nombre, nto))
                        else:
                            c.append(indent+"%s= Atributos()" % nto)
            # Generamos el código de la regla:
            c2= r.dcha.genera_codigo_interno(self, {}, r.dcha.aceptables(), traza, esPuro)
            for i in c2:
                c.append(indent+i)
            if len(self.reglasizda)> 1:
                indent= indent[:-2]
        # Más traza, para avisar de que nos vamos
        if traza=="t":
            c.append(indent+"""indentacion_traza = indentacion_traza-2""")
            c.append(indent+"""mc_traza("< %s\\n")""" % self)
        elif traza=="A":
            c.append(indent+"""indentacion_traza = indentacion_traza-2""")
            c.append(indent+"""mc_traza(")\\n")""")
        if self.traterror and not esPuro:
            c.append("    except mc_error_sintaxis, (mc_nt, mc_t):")
            indent= "      "
            for i in self.traterror:
                c.append(indent+i)
            c.append("  self.mc_reintento.pop()")
        return c

    def genera_codigo_interno(self, pizda, orden, garantizados, traza, esPuro):
        c=[]
        if not esPuro:
            atr= self.nombre+_gestion_orden(orden, self.nombre)
            c.append("self.mc_analiza_%s(%s)" % (self.nombre,atr))
            c.append("%s_= %s" % (self.nombre, atr))
        else:
            c.append("self.mc_analiza_%s()" % self.nombre)
        return c

    def aplica_funcion(self,f):
        f(self)

    def recursividad_izquierda(self, nt):
        return self==nt

    def comprueba_conflictos_globales(self, salida):
        vistos={}
        for r in self.reglasizda:
            for t in r.dcha.aceptables():
                if vistos.has_key(t):
                    salida.write("Aviso: hay un conflicto entre las regla de la línea %d:\n"
                                 "    %s\n"
                                 "  y la de la línea %d\n"
                                 "    %s\n"
                                 "  al ver el símbolo %s. Se tomará la primera.\n"
                                 % (vistos[t].nl, vistos[t].regla(), r.nl, r.regla(), t))
                else:
                    vistos[t]= r
            r.dcha.comprueba_conflictos(salida)

    def comprueba_conflictos(self, salida):
        pass

class Terminal(Pdcha):
    "Representa los terminales que no son la cadena vacía"
    def __init__(self, nombre, directo, error, nl):
        self.nombre= nombre
        self.directo= directo
        self.error= error
        Pdcha.__init__(self, False, nl)
        self.misprimeros.add(self.nombre)

    def __str__(self):
        if self.directo:
            return '"%s"' % self.nombre[1:]
        else:
            return self.nombre

    def genera_codigo_interno(self, pizda, orden, garantizados, traza, esPuro ):
        c= []
        if garantizados and len(garantizados)==1 and self.nombre in garantizados:
            indent=""
        else:
            indent="  "
            c.append("if mc_al.actual.cat == '%s':" % self.nombre)
        if traza=="t":
            c.append("""%smc_traza('Reconocido el terminal "%s"\\n')""" % (indent,self.nombre))
        elif traza=="A":
            c.append("""%smc_traza('("%s"\\n')""" % (indent,repr(self.nombre.replace('"','""'))[1:-1]))
            c.append("""%smc_traza(' "Lexema: %%s"\\n' %% mc_al.actual.lexema.replace('"','""'))""" % indent)
            c.append("""%smc_traza(' "Línea: %%d"\\n' %% mc_al.actual.nlinea)""" % indent)
            c.append("""%smc_traza(')\\n')""" % indent) #'<- para el font-lock
        if not esPuro and not self.directo:
            n= self.nombre+_gestion_orden(orden, self.nombre)
            if orden[self.nombre]== 1 and pizda.nombre!= self.nombre:
                c.append("%s%s= %s= %s_= mc_al.actual" % (indent,self.nombre, n, self.nombre))
            else:
                c.append("%s%s= %s_= mc_al.actual" % (indent,n, self.nombre))
        c.append("%smc_al.avanza()" % indent)
        if traza=="t":
            c.append("""%smc_traza('Leído el terminal "%%s"\\n' %% self.mc_al.actual)""" % indent)
        if indent=="  ":
            c.append("else:")
            if traza:
                c.append("""%smc_traza('Error no es un "%s"\\n')"""%(indent, self.nombre))
            if not self.error:
                c.append("  mc_error('%s', ['%s'])" % (pizda, self.nombre))
            else:
                for l in self.error:
                    c.append("  "+l)
        return c

    def aplica_funcion(self,f):
        f(self)

    def recursividad_izquierda(self,nt):
        return False

    def comprueba_conflictos(self,salida):
        pass

class Vacia(Pdcha):
    "Representa el terminal cadena vacía"
    def __init__(self, nl):
        Pdcha.__init__(self, True, nl)

    def __str__(self):
        return ""

    def genera_codigo_interno(self, pizda, orden, garantizado, traza, esPuro):
        c= []
        if traza=="t":
            c.append("mc_traza('Reconocida una cadena vacía\\n')")
        elif traza=="A":
            c.append("""mc_traza('("")\\n')""")
        else:
            c.append("pass")
        return c

    def aplica_funcion(self,f):
        f(self)

    def recursividad_izquierda(self,nt):
        return False

    def comprueba_conflictos(self,salida):
        pass

class Accion(Vacia):
    "Acción en una regla"
    def __init__(self, cod, nl):
        self.cod= cod
        Pdcha.__init__(self, True, nl)

    def __str__(self):
        return "@%s@" % self.cod

    def regla(self):
        return ""

    def genera_codigo_interno(self, pizda, orden, garantizado, traza, esPuro):
        if esPuro:
            return ["pass"]
        else:
            return [self.cod]

class Secuencia(Pdcha):
    "Parte derecha consistente en una secuencia de elementos"
    def __init__(self, l, nl):
        self.l= l
        Pdcha.__init__(self, None, nl)

    def influye_anulable(self, inf):
        for pd in self.l:
            n= pd.ninventario
            inf[n].append(self)

    def comprueba_anulable(self):
        self.esanulable= True
        for pd in self.l:
            if pd.anulable()== False:
                self.esanulable= False
                break

    def influye_primeros(self, inf, primeros):
        yo= self.ninventario
        for pd in self.l:
            inf[pd.ninventario].append(yo)
            if not pd.anulable():
                break
        primeros[self.ninventario]= self.misprimeros

    def influye_siguientes(self, inf, siguientes):
        yo= self.ninventario
        if self.l:
            for npd in range(len(self.l)-1, -1, -1):
                pd= self.l[npd]
                inf[yo].append(pd.ninventario)
                if not pd.anulable():
                    break
        siguientes[self.ninventario]= self.missiguientes

    def propaga_primeros_siguientes(self):
        ac=Set()
        if self.l:
            for npd in range(len(self.l)-1, -1, -1):
                pd= self.l[npd]
                pd.missiguientes.update(ac)
                if pd.anulable():
                    ac.update(pd.primeros())
                else:
                    ac= pd.primeros().copy()

    def __str__(self):
        r=[]
        for i in self.l:
            r.append(str(i))
        return " ".join(r)

    def regla(self):
        r=[]
        for i in self.l:
            if i.regla():
                r.append(i.regla())
        return " ".join(r)

    def genera_codigo_interno(self, pizda, orden, garantizados, traza, esPuro):
        c=[]
        g= garantizados
        if traza=="t":
            c.append("""mc_traza('> Analizando %s\\n')""" % self.regla())
            c.append("""indentacion_traza= indentacion_traza+2""")
        for i in self.l:
            c= c+ i.genera_codigo_interno(pizda, orden, g, traza, esPuro)
            if not isinstance(i,Vacia):
                g= None
        if traza=="t":
            c.append("""indentacion_traza= indentacion_traza-2""")
            c.append("""mc_traza('< Fin de %s\\n')""" % self.regla())
        return c

    def aplica_funcion(self,f):
        f(self)
        for i in self.l:
            i.aplica_funcion(f)

    def recursividad_izquierda(self,nt):
        for i in self.l:
            if i.recursividad_izquierda(nt):
                return True
            if not i.anulable():
                return False
        return False

    def comprueba_conflictos(self,salida):
        for i in self.l:
            i.comprueba_conflictos(salida)

class Opcional(Pdcha):
    "Parte derecha representando la aparición o no de una parte"

    def __init__(self, pd, nl):
        self.pd= pd
        Pdcha.__init__(self, True, nl)

    def __str__(self):
        return "( %s )?" % str(self.pd)

    def regla(self):
        return "( %s )?" % self.pd.regla()

    def influye_primeros(self, inf, primeros):
        inf[self.pd.ninventario].append(self.ninventario)
        primeros[self.ninventario]= self.misprimeros

    def influye_siguientes(self, inf, siguientes):
        inf[self.ninventario].append(self.pd.ninventario)
        siguientes[self.ninventario]= self.missiguientes

    def genera_codigo_interno(self, pizda, orden, garantizados, traza, esPuro):
        c=[]
        g= self.pd.primeros()
        if traza=="t":
            c.append("""mc_traza('> Analizando %s\\n')""" % self.regla())
        c.append("if %s:" % _test_set(g))
        for l in self.pd.genera_codigo_interno(pizda, orden, g, traza, esPuro):
            c.append("  "+l)
        c.append("elif %s:" % _test_no_set(self.missiguientes))
        if traza:
            c.append("  mc_traza('Error, no podemos asumir que esté vacía.\\n')")
        c.append("  mc_error('%s', %s)" % (pizda, _set_strlista(self.misaceptables)))
        if traza=="t":
            c.append("else:")
            c.append("  mc_traza('Se supone que no está\\n')")
        return c

    def aplica_funcion(self,f):
        f(self)
        self.pd.aplica_funcion(f)

    def recursividad_izquierda(self,nt):
        return self.pd.recursividad_izquierda(nt)

    def comprueba_conflictos(self, salida):
        if self.pd.anulable():
            for t in self.missiguientes:
                if not t in self.primeros():
                    salida.write("Aviso: hay un conflicto en la parte opcional de la línea %d:\n"
                                 "   %s\n"
                                 "  con el símbolo %s. En ese caso, no entraré.\n"
                                 % (self.nl, self.regla(), t))
        for t in self.primeros():
            if t in self.missiguientes:
                salida.write("Aviso: hay un conflicto en la parte opcional de la línea %d:\n"
                             "   %s\n"
                             "  con el símbolo %s. En ese caso, desplazaré.\n"
                             % (self.nl, self.regla(), t))
        self.pd.comprueba_conflictos(salida)

class Disyuncion(Pdcha):
    "Parte derecha para representar multiples opciones"
    def __init__(self, l, nl, traterror= None):
        self.l= l
        self.traterror= traterror
        Pdcha.__init__(self, None, nl)

    def influye_anulable(self, inf):
        for pd in self.l:
            n= pd.ninventario
            inf[n].append(self)

    def comprueba_anulable(self):
        for pd in self.l:
            if pd.anulable():
                self.esanulable= True
                break

    def influye_primeros(self, inf, primeros):
        yo= self.ninventario
        for pd in self.l:
            inf[pd.ninventario].append(yo)
        primeros[yo]= self.misprimeros

    def influye_siguientes(self, inf, siguientes):
        yo= self.ninventario
        for n in self.l:
            inf[yo].append(n.ninventario)
        siguientes[yo]= self.missiguientes

    def __str__(self):
        r=[]
        for i in self.l:
            r.append(str(i))
        return "( %s )" % " | ".join(r)

    def regla(self):
        r=[]
        for i in self.l:
            r.append(i.regla())
        return "( %s )" % " | ".join(r)

    def genera_codigo_interno(self, pizda, orden, garantizados, traza, esPuro ):
        c=[]
        el=""
        indent= ""
        if self.traterror and not esPuro:
            c.append("""self.mc_reintento.append(1)""")
            c.append("""mc_reintentar= self.mc_reintentar""")
            c.append("""while self.mc_reintento[-1]:""")
            c.append("""  self.mc_reintento[-1]= 0""")
            c.append("""  try:""")
            indent="    "
        if traza=="t":
            c.append(indent+"""mc_traza('> Analizando %s\\n')""" % self.regla())
            c.append(indent+"""indentacion_traza=indentacion_traza+2""")
        # No podemos hacer caso de las garantías si hay tratamiento de error;
        # no sabemos dónde se puede haber sincronizado.
        if garantizados and (esPuro or not self.traterror):
            g= garantizados.copy()
        else:
            g= None
        for i in self.l:
            if g!= None:
                r= i.aceptables().intersection(g)
            else:
                r= i.aceptables()
            if r:
                if g== None or len(r)< len(g): # Caso normal: los aceptables son menos que los garantizados
                    c.append(indent+el+"if %s:" % _test_set(r))
                    el="el"
                    indent2=indent+"  "
                elif len(r)== len(g):
                    if el== "": # Esta alternativa se lo lleva todo y no hemos visto ninguna otra
                        indent2=indent+""
                    else: # Estamos en la última alternativa
                        indent2=indent+"  "
                        c.append("else:")
                for l in i.genera_codigo_interno(pizda, orden, r, traza, esPuro):
                    c.append(indent2+l)
            if g:
                g.difference_update(r)
        if g== None: # Puede que haya un error en la entrada
            c.append(indent+"else:")
            if traza:
                c.append(indent+"  mc_traza('Error, no hay ninguna alternativa aceptable.\\n')")
            c.append(indent+"  mc_error('%s', %s)" % (pizda, _set_strlista(self.misaceptables)))
        if traza=="t":
            c.append(indent+"""indentacion_traza=indentacion_traza-2""")
            c.append(indent+"""mc_traza('< Fin de %s\\n')""" % self.regla())
        if self.traterror and not esPuro:
            c.append("  except mc_error_sintaxis, (mc_nt, mc_t):")
            indent= "    "
            for i in self.traterror:
                c.append(indent+i)
            c.append("self.mc_reintento.pop()")
        return c

    def aplica_funcion(self,f):
        f(self)
        for i in self.l:
            i.aplica_funcion(f)

    def recursividad_izquierda(self,nt):
        for i in self.l:
            if i.recursividad_izquierda(nt):
                return True
        return False

    def comprueba_conflictos(self, salida):
        vistos={}
        for r in self.l:
            for t in r.aceptables():
                if vistos.has_key(t):
                    salida.write("Aviso: hay un conflicto entre las opciones:\n"
                                 "    %s\n"
                                 "  y\n"
                                 "    %s\n"
                                 "  de la disyunción de la línea %d\n"
                                 "    %s\n"
                                 "  al ver el símbolo %s. Se tomará la primera.\n"
                                 % (vistos[t].regla(), r.regla(), self.nl, self.regla(), t))
                else:
                    vistos[t]= r
            r.comprueba_conflictos(salida)

class Iteracion(Pdcha):
    "Parte derecha representando cero o más iteraciones"
    def __init__(self, pd, nl):
        self.pd= pd
        Pdcha.__init__(self, True, nl)

    def __str__(self):
        return "( %s )*" % str(self.pd)

    def regla(self):
        return "( %s )*" % self.pd.regla()

    def influye_primeros(self, inf, primeros):
        inf[self.pd.ninventario].append(self.ninventario)
        primeros[self.ninventario]= self.misprimeros

    def influye_siguientes(self, inf, siguientes):
        inf[self.ninventario].append(self.pd.ninventario)
        siguientes[self.ninventario]= self.missiguientes

    def propaga_primeros_siguientes(self):
        self.pd.missiguientes.update(self.pd.primeros())

    def genera_codigo_interno(self, pizda, orden, garantizados, traza, esPuro):
        c=[]
        if traza=="t":
            c.append("""mc_traza('> Analizando %s\\n')""" % self.regla())
            c.append("""indentacion_traza= indentacion_traza+2""")
        c.append("while %s:" % _test_set(self.pd.primeros()))
        for l in self.pd.genera_codigo_interno(pizda, orden, self.pd.primeros(), traza, esPuro):
            c.append("  "+l)
        if traza=="t":
            c.append("""indentacion_traza= indentacion_traza-2""")
            c.append("""mc_traza('< Fin de %s\\n')""" % self.regla())
        c.append("if not %s:" % _test_set(self.missiguientes))
        if traza:
            c.append("  mc_traza('Error, no encontramos ninguno de los siguientes\\n')")
        c.append("  mc_error('%s',%s)" % (self.mi_nt, _set_strlista(self.misaceptables)))
        return c

    def aplica_funcion(self,f):
        f(self)
        self.pd.aplica_funcion(f)

    def recursividad_izquierda(self,nt):
        return self.pd.recursividad_izquierda(nt)

    def comprueba_conflictos(self, salida):
        if self.pd.anulable() and len(self.pd.primeros())== 0:
            if len(self.missiguientes)== 1:
                salida.write("Aviso: hay un conflicto en la clausura de la línea %d\n"
                             "   %s\n"
                             "  con el símbolo %s. No se entrará en la clausura.\n"
                             % (self.nl, self.regla(), [i for i in self.missiguientes ][0]))
            else:
                salida.write("Aviso: hay un conflicto en la clausura de la línea %d\n"
                             "   %s\n"
                             "  con los símbolos {%s}. No se entrará en la clausura.\n"
                             % (self.nl, self.regla(), ", ".join(self.missiguientes)))

        l= [ t for t in self.primeros() if t in self.missiguientes]
        if l:
            if len(l)== 1:
                salida.write("Aviso: hay un conflicto en la clausura de la línea %d:\n"
                             "   %s\n"
                             "  con el símbolo %s. En ese caso, desplazaré.\n"
                             % (self.nl, self.regla(), l[0]))
            else:
                salida.write("Aviso: hay conflictos en la clausura de la línea %d:\n"
                             "   %s\n"
                             "  con los símbolos {%s}. En caso de encontrarlos, los desplazaré.\n"
                             % (self.nl, self.regla(), ", ".join(l)))
        self.pd.comprueba_conflictos(salida)

class Repeticion(Pdcha):
    "Parte derecha representando una o más iteraciones"
    def __init__(self, pd, nl):
        self.pd= pd
        Pdcha.__init__(self, None, nl)

    def __str__(self):
        return "( %s )+" % str(self.pd)

    def regla(self):
        return "( %s )+" % self.pd.regla()

    def influye_anulable(self, inf):
        inf[self.pd.ninventario].append(self)

    def comprueba_anulable(self):
        self.esanulable= pd.anulable()

    def influye_primeros(self, inf, primeros):
        inf[self.pd.ninventario].append(self.ninventario)
        primeros[self.ninventario]= self.misprimeros

    def influye_siguientes(self, inf, siguientes):
        inf[self.ninventario].append(self.pd.ninventario)
        siguientes[self.ninventario]= self.missiguientes

    def propaga_primeros_siguientes(self):
        self.pd.missiguientes.update(self.pd.primeros())

    def genera_codigo_interno(self, pizda, orden, garantizados, traza, esPuro):
        c=[]
        if traza=="t":
            c.append("""mc_traza('> Analizando %s\\n')""" % self.regla())
            c.append("""indentacion_traza= indentacion_traza+2""")
        c.append("while True:")
        if garantizados== self.primeros(): # Sólo tenemos garantías si
            g= garantizados                # coinciden al principio y
        else:                              # en cada vuelta
            g= None
        for l in self.pd.genera_codigo_interno(pizda, orden, g, traza, esPuro):
            c.append("  "+l)
        c.append("  if %s: break" % _test_no_set(self.primeros()))
        if traza=="t":
            c.append("""indentacion_traza= indentacion_traza-2""")
            c.append("""mc_traza('< Fin de %s\\n')""" % self.regla())
        c.append("if not %s:" % _test_set(self.missiguientes))
        if traza:
            c.append("  mc_traza('Error, no encontramos ninguno de los siguientes\\n')")
        c.append("  mc_error('%s',%s)" % (self.mi_nt, _set_strlista(self.misprimeros|self.missiguientes)))
        return c

    def aplica_funcion(self,f):
        f(self)
        self.pd.aplica_funcion(f)

    def recursividad_izquierda(self,nt):
        return self.pd.recursividad_izquierda(nt)

    def comprueba_conflictos(self, salida):
        for t in self.primeros():
            if t in self.missiguientes:
                salida.write("Aviso: hay un conflicto en la clausura positiva de la línea %d:\n"
                             "   %s\n"
                             "  con el símbolo %s. En ese caso, desplazaré.\n"
                             % (self.nl, self.regla(), t))
        self.pd.comprueba_conflictos(salida)

#
#  Clase para las gramáticas:
#


class Gramatica:
    def __init__(self, noterminales, inicial, reglas, noEOF):
        self.noEOF= noEOF
        self.noterminales= noterminales
	self.inicial= inicial
        self.reglas= reglas

        self.inventario= [] # Cada elemento de la gramática tiene asociada su posición
                            # en esta lista

        def actualiza_inventario(elto, inv= self.inventario):
            """Actualiza el inventario con el elemento elto si no está"""
            if elto.ninventario== None:
                elto.ninventario= len(inv)
                inv.append(elto)
        for r in reglas:
            r.aplica_funcion(actualiza_inventario)
        self.calcula_anulables()
        self.calcula_primeros()
        self.calcula_siguientes()
        self.prepara_aceptables()

    def __str__(self):
        s= []
        for r in self.inicial.reglasizda:
            s.append(str(r))
        for nt in self.noterminales:
            if nt!= self.inicial:
                for r in nt.reglasizda:
                    s.append(str(r))
        return "\n".join(s)

    def lista_reglas(self):
        l=[]
        for r in self.reglas:
            l.append(r.regla())
        return "\n".join(l)

    def calcula_anulables(self):
        influye= [ [] for i in xrange(len(self.inventario)) ]
        cambiado= Set()
        for e in self.inventario:
            e.influye_anulable(influye)
            if e.anulable():
                cambiado.add(e.ninventario)
            else:
                e.esanulable= False
        while cambiado:
            n= cambiado.pop()
            e= self.inventario[n]
            for e2 in influye[n]:
                if not e2.anulable():
                    e2.comprueba_anulable()
                    if e2.anulable():
                        cambiado.add(e2.ninventario)

    def calcula_primeros(self):
        influye= [ [] for i in xrange(len(self.inventario)) ]
        inicial= [0] * len(self.inventario)
        for e in self.inventario:
            e.influye_primeros(influye, inicial)
        clausura(range(len(self.inventario)), inicial, influye)

    def calcula_siguientes(self):
        influye= [ [] for i in xrange(len(self.inventario)) ]
        inicial= [0] * len(self.inventario)
        for e in self.inventario:
            e.influye_siguientes(influye, inicial)
        for e in self.inventario:
            e.propaga_primeros_siguientes()
        self.inicial.missiguientes.add("mc_EOF")
        clausura(range(len(self.inventario)), inicial, influye)

    def prepara_aceptables(self):
        for e in self.inventario:
            e.prepara_aceptables()

    def aplica_funcion(self,f):
        for r in self.reglas:
            r.aplica_funcion(f)

    def recursividad_izquierda(self):
        l= Set()
        for nt in self.noterminales:
            for r in nt.reglasizda:
                if r.dcha.recursividad_izquierda(nt):
                    l.add(nt)
        return l

    def comprueba_conflictos(self, salida):
        for nt in self.noterminales:
            nt.comprueba_conflictos_globales(salida)

def main():
  mas= Terminal("!+", True, None, 0)
  menos= Terminal("!-", True, None, 0)
  por= Terminal("!*", True, None, 0)
  entre= Terminal("!/", True, None, 0)
  id= Terminal("id", False, None, 0)
  num= Terminal("num", False, None, 0)
  abre= Terminal("!(", True, None, 0)
  cierra= Terminal("!)", True, None, 0)
  pyc= Terminal("!;", True, None, 0)

  terminales= [mas,menos,por,entre,id,num,abre,cierra]

  Expresion= NoTerminal("Expresion", 0)
  Termino= NoTerminal("Termino", 0)
  Factor= NoTerminal("Factor", 0)
  Programa= NoTerminal("Programa", 0)

  noterminales= [Programa,Expresion,Termino,Factor] 

  R0= Regla(Programa, Repeticion(Secuencia([Opcional(Expresion, 0), pyc], 0), 0), 0);
  R1= Regla(Expresion, Secuencia([Termino,Iteracion(Secuencia([Disyuncion([mas,menos], 0),Termino], 0), 0)], 0), 0)
  R2= Regla(Termino, Secuencia([Factor,Iteracion(Secuencia([Disyuncion([por,entre], 0),Factor], 0), 0)], 0), 0)
  R3= Regla(Factor, Disyuncion([id,num,Secuencia([abre,Expresion,cierra], 0)], 0), 0)

  reglas= [R0, R1, R2, R3]

  g= Gramatica(noterminales, Programa, reglas, None)

  print g
  print "\n Símbolos anulables:"
  for i in g.inventario:
      print i.anulable(),"\t",i

  print "\n Primeros:"
  for i in g.inventario:
      print "Pr(%s)= { %s }" % (i, ", ".join([str(j) for j in i.primeros()]))

  print "\nSiguientes:"
  for i in g.inventario:
      print "Sig(%s)= { %s }" % (i, ", ".join([str(j) for j in i.siguientes()]))

  print "\nAceptables:"
  for i in g.inventario:
      print "Acept(%s)= { %s }" % (i, ", ".join([str(j) for j in i.aceptables()]))

if __name__ == "__main__":
    main()