Generar Tablas LR para Análisis Sintáctico

Las gramáticas LR nos permiten construir analizadores sintácticos para la gran mayoría de los lenguajes de programación que conocemos en la actualidad, en el proceso de creación de analizadores sintácticos de desplazamiento-reducción, como también son llamados, la parte mas difícil es la creación de las tablas, por lo que estudiaremos los algoritmos para la creación de las mismas y crearemos un programa que las genere automáticamente.

Debemos tener en cuenta que existen gramáticas de libre contexto con la que no podemos usar este tipo de analizadores, en un determinado momento podremos tener dos acciones para una misma entrada por lo que el analizador no sabría si desplazar o reducir, en este caso tendríamos un conflicto.

Conjunto de elementos LR(0)

El primer concepto que debemos conocer es el de elemento, un elemento es una producción con un punto en cierta posición, esta posición le indica al parser que parte de la producción se esta analizando, ejemplo: la producción A –> XYZ tendrá los siguientes elementos:

Si la producción deriva en cadena vacía tendrá el elemento A –> .
Para crear el conjunto de elemento de la gramática aumentada G’ proporcionamos el siguiente método:

private HashSet<Element> GetElements()
{
    if (_elementos == null)
    {
        _elementos = new HashSet<Element>();

        _elementos.Add(new Element(_gramatica.Start, 0));
        _elementos.Add(new Element(_gramatica.Start, 1));

        foreach (Production prod in _gramatica.Productions)
        {
            for (int i = 0; i < prod.Right.Count; i++)
            {
                _elementos.Add(new Element(prod, i));
            }
        }
    }

    return _elementos;
}

Cerradura de conjunto de elementos

Para crear la cerradura de un conjunto de elementos proporcionado aplicamos la siguiente regla: verificamos cada elemento del conjunto y obtenemos los símbolos NO TERMINALES localizados justo a la derecha del punto, agregamos todas aquellas producciones que inicien con estos símbolos y que tengan el punto en la posición inicial, luego analizamos las producciones que acabamos de agregar y aplicamos la regla anterior, repetimos hasta que no podamos agregar mas producciones.

En la imagen se observa la cerradura para el conjunto de un solo elemento { E –> E + . T }, como T se encuentra a la derecha del punto agregamos las producciones T con punto al inicio: { T –> . T * F } y { T –> . F }, aplicamos nuevamente la regla y encontramos T y F a la derecha del punto, como las producciones T ya se encuentran en el conjunto agregamos solo las F con punto al inicio: { F –> . (E) } y { F –> . id }, repetimos el proceso pero nos encontramos con los terminales ( y id a la derecha del punto por lo que no agregamos mas elementos.

private HashSet<Element> Cerradura(HashSet<Element> elements)
{
    HashSet<Element> cerradura = new HashSet<Element>();

    foreach (var item in elements)
    {
        cerradura.Add(item);

        for (int i = 0; i < cerradura.Count; i++)
        {
            Symbol sm = cerradura.ElementAt(i).GetRightSymbol();

            if (sm != null)
            {
                var temp = GetElements().Where(e => e.Production.Left == sm && e.Position == 0);

                cerradura.UnionWith(temp);
            }
        }
    }

    return cerradura;
}

La función IR_A o Goto

Esta es otra función que necesitamos conocer IR_A(I, A) donde I es un conjunto de elementos y A es un símbolo gramatical, nos servirá para definir las transiciones del autómata LR(0), la cerradura de un conjunto de elementos representan los estados y la función IR_A proporciona las transiciones.

Calculo de IR_A para el conjunto I = { [ E –> E . ], [ E –> E . + T ] }, A = +, de este modo IR_A(I, +) se define como: Buscamos en “ I ” los elementos que tengan un “ + ” justo a la derecha del punto, E –> E . + T es la único elemento en I que cumple la regla, avanzamos la posición del punto en los elementos encontrados, E –> E + . T y creamos un nuevo conjunto de elementos con los mismos, finalizamos buscando la cerradura para este conjunto de elementos.

private HashSet<Element> Ir_A(HashSet<Element> elementos, Symbol simbolo)
 {
     HashSet<Element> conjunto = new HashSet<Element>();

     foreach (var item in elementos)
     {
         if (item.GetRightSymbol() == simbolo)
         {
             conjunto.Add(new Element(item.Production, item.Position + 1));
         }
     }

     return Cerradura(conjunto);
 }

Colección canónica de conjunto de elementos LR(0)

Necesitamos de una gramática aumentada para poder construir el parser LR(0), también requerimos calcular el conjunto de todos los posibles elementos de la gramática, para la gramática siguiente con producción inicial aumentada: S’ –> S $

El algoritmo para construir el parser LR(0) es el siguiente:

Iniciamos T con la cerradura del elemento de la gramática aumentada S’ –> . S $, T será la colección de conjuntos de elementos, cada conjunto de elementos representa un estado, por lo que el primer estado estará dado por la cerradura de S’ –> . S $.

Por cada estado I en T y por cada elemento en I, obtenemos el símbolo gramatical X a la derecha del punto y calculamos J = IR_A(I,X), si J no esta en T lo agregamos, E representa el conjunto de transiciones donde I es el estado actual, J el estado siguiente y X la entrada o símbolo gramatical que produce la transición, si la transición I –> J con X no esta en E la agregamos. Repetimos si E o T se han modificado.

public HashSet<SetElement> LR()
{
    HashSet<SetElement> T = new HashSet<SetElement>();

    var inicial = GetElements().ElementAt(0);
    var closure = Cerradura(new HashSet<Element>() { inicial });
    int stateIndex = 1;

    T.Add(new SetElement(closure, stateIndex++));

    for (int i = 0; i < T.Count; i++)
    {
        SetElement I = T.ElementAt(i);

        foreach (var item in I.Elementos)
        {
            Symbol X = item.GetRightSymbol();

            if (X != null && X.Tipo != SymbolType.Empty)
            {
                if (X.Tipo != SymbolType.EndOfFile)
                {
                    SetElement estado = new SetElement(Ir_A(I.Elementos, X), stateIndex);

                    if (!T.Add(estado))
                    {
                        estado = T.Single(ee => ee == estado);
                    }
                    else stateIndex++;

                    switch (X.Tipo)
                    {
                        case SymbolType.Terminal:
                            if (!I.Acciones.ContainsKey(X))
                                I.Acciones.Add(X, LRAction.Shift(estado));
                            break;
                        case SymbolType.NoTerminal:
                            if (!I.Acciones.ContainsKey(X))
                                I.Acciones.Add(X, LRAction.Goto(estado));
                            break;
                        default: break;
                    }
                }
                else { I.Acciones.Add(X, new LRAction(LRActionType.Aceptar, null, null)); }
            }

        }
    }

    return SLRReduce(T);
}

Para la gramática establecida se produce la siguiente salida, donde las flechas indican las transiciones y el símbolo que las produce, el conjunto de elementos representa los estados, la salida que produce esta función no enumera los estados en el mismo orden que la imagen.

La función J = IR_A(I,X) genera dos tipos de transiciones, si X es un Terminal la acción del parser será Desplazarse (Shift) a J, si X es No Terminal la acción es Ir (Goto) a J.

Recordemos que $ es el marcador especial para indicar el final de la cadena, no debemos calcular Goto(I, $), en su lugar debemos indicar la aceptación de la cadena.

Analizador sintáctico SLR(1)

Ya casi hemos terminado de construir la tabla LR solo nos falta establecer las acciones de reducción para ello haremos uso de dos funciones que nos ayudaran, PRIMERO y SIGUIENTE ambas nos ayudaran a evitar posibles ambigüedades que se puedan producir, veamos como calcular PRIMERO(X).

Definimos como PRIMERO(X) todos los símbolos terminales que empiecen la parte derecha de la producción que tiene X en la parte izquierda.

Para la producción { [ Z –> + ] , [ Z –> – ] } el calculo de PRIMER(Z) = [ +, – ] , si una producción P deriva en cadena vacía, podemos decir que PRIMERO(P) es nulo.

Para una producción como { [ Z –> EFG ] } los elementos de PRIMERO(E) estarán en PRIMERO(Z), si PRIMERO(E) es nulo entonces agregamos a PRIMERO(Z) los elementos de PRIMERO(F) y así sucesivamente. En caso de que E, F y G sean nulos Z también lo será.

La funcione PRIMERO(x) donde x es No Terminal es igual al no terminal x.

Definimos SIGUIENTE(A) para un No Terminal A como el conjunto de terminales que puede aparecer en el cuerpo de la producción a la derecha A, SIGUIENTE(X) para la producción { Y –> X p } será igual a p, para calcular SIGUIENTE(A) iteramos sobre cada una de las producciones de la gramática y aplicamos la siguientes reglas:

Por cada producción con la forma M→αNβ agregamos los elementos de PRIMERO(β) a SIGUIENTE(N).

Por cada producción con la forma M→αNβ donde PRIMERO(β) es nulo agregamos los elementos de SIGUIENTE(M) a SIGUIENTE(N).

// Algorithm to compute FIRST, FOLLOW, and nullable.
Dictionary<Symbol, FirstFollow> ffn = new Dictionary<Symbol, FirstFollow>();

// Initialize FIRST and FOLLOW to all empty sets, and nullable to all false.
// for each terminal symbol Z
//      FIRST[Z] ← {Z}
foreach (var symbol in _gramatica.SymbollList())
{
    ffn[symbol] = new FirstFollow(symbol);
}

bool stop;
do // repeat
{
    stop = false;

    //  for each production X →Y1Y2 · · · Yk
    foreach (var production in _gramatica.Productions)
    {
        Symbol X = production.Left;
        var Y = production.Right;

        // if Y1 . . . Yk are all nullable (or if {k = 0} => X -> λ)
        //      then nullable[X] ← true
        if (production.IsEmpty() || AllNullable(ffn, Y))
            stop |= SetNullable(ffn[X]);

        // for each i from 1 to k, each j from i + 1 to k
        int k = Y.Count;
        for (int i = 1; i <= k; i++)
        {
            // if Y1 · · · Yi−1 are all nullable (or if i = 1)
            //      then FIRST[X] ← FIRST[X] ∪ FIRST[Yi ]
            if (i == 1 || StartNullable(ffn, production, i))
            {
                stop |= Unir(ffn[X].First, ffn[Y[i - 1]].First);
            }

            // if Yi+1 · · · Yk are all nullable (or if i = k)
            //      then FOLLOW[Yi] ← FOLLOW[Yi] ∪ FOLLOW[X]
            if (i == k || EndNullable(ffn, production, i))
            {
                if (Y[i - 1].Tipo == SymbolType.NoTerminal)
                    stop |= Unir(ffn[Y[i - 1]].Follow, ffn[X].Follow);
            }

            // if Yi+1 · · · Yj−1 are all nullable (or if i + 1 = j )
            //      then FOLLOW[Yi] ← FOLLOW[Yi] ∪ FIRST[Yj ]
            for (int j = i + 1; j <= k; j++)
            {
                if (i + 1 == j || RangeNullable(ffn, production, i, (j - 1) - i))
                    if (Y[i - 1].Tipo == SymbolType.NoTerminal)
                        stop |= Unir(ffn[Y[i - 1]].Follow, ffn[Y[j - 1]].First);
            }
        }

    }
} while (stop); // until FIRST, FOLLOW, and nullable did not change in this iteration.

return ffn;

Para terminar con la creación de la tabla SLR(1) solo nos falta encontrar las acciones de reducción a agregarlas a la tabla, para hacerlo aplicamos el siguiente algoritmo:

T es la colección de conjunto de elementos que representan los estados del autómata LR(0), por cada estado I en T, como I es un conjunto de elementos buscamos todos los elementos con la forma A →α. (un elemento con el punto al final), por cada uno de los elementos que cumplan esta regla buscamos SIGUIENTE(A), el conjunto de reducciones para el estado I cuando la entrada sea un terminal de SIGUIENTE(A) deberemos reducir mediante la producción A →α

private HashSet<SetElement> SLRReduce(HashSet<SetElement> T)
{
    first_follow = FirstFollowNullable();

    foreach (var I in T)
    {
        foreach (var A in I.Elementos)
        {
            if (A.IsEndPosition())
            {
                foreach (var siguiente in first_follow[A.Production.Left].Follow)
                {
                    if (!I.Acciones.ContainsKey(siguiente))
                        I.Acciones.Add(siguiente, new LRAction(
                            LRActionType.Reducir, null, A.Production));
                }
            }
        }
    }

    return T;
}

Con esto hemos creado una tabla como la siguiente , aunque nuestro programa la muestra en pantalla de forma diferente y la numeración de los estados es distinta al aplicar las correspondientes reducciones y desplazamientos llegaremos al mismo resultado.

Hemos optado por presentar la tabla en un formato diferente al de una matriz, como podemos ver existen espacios vacíos los mismo indican un error y como estas tablas pueden tener cientos de estado y entradas podríamos tener una matriz de miles de elementos, para ahorrar espacio nuestro programa presenta la tabla de la siguiente manera: Estado: # seguido de las posibles entradas con su correspondiente acción.

Descargar código Visual Studio C#

Buscar en este blog

Tutor de Programación