Diseño de Analizadores con Parse::Eyapp

A la hora de construir un analizador sintáctico tenga en cuenta las siguientes normas de buena programación:

  1. Comienze trabajando en el cuerpo de la gramática.
  2. Olvídese al principio del analizador léxico. Su primer objetivo es tener una gramática limpia de conflictos y que reconozca el lenguaje dado.
  3. Sustituya las repeticiones BNF por listas usando los operadores eyapp +, * y sus variantes con separadores. Si una variable describe una lista de cosas pongale un adjetivo adecuado como cosaslist. Ponga nombres significativos a las variables y terminales. No los llame d1, d2, etc.
  4. Si tiene un elemento opcional en la BNF, por ejemplo, en la regla:

    functiondefinition $ \rightarrow$ $ [$ basictype $ ]$ functionheader functionbody

    use el operador ?.

  5. Cada par de reglas que introduzca vuelva a recompilar con eyapp la gramática para ver si se introducido ambiguedad. Cuando estoy editando la gramática suelo escribir a menudo la orden

    :!eyapp %

    para recompilar:



         15
         16 declaratorlist: declarator +
         17 ;
         18 functiondefinition: 
         19    basictype functionheader functionbody
         20  | functionheader functionbody
         21 ;
         22
         23 %%
    ~
    ~
    ~
    ~
    ~
    ~
    ~
    ~
    ~
    ~
    :!eyapp %
    


    Esto llama a eyapp con el fichero bajo edición. Si hay errores o conflictos (esto es, hemos introducido ambiguedad) los detectarémos enseguida. Procure detectar la aparición de un conflicto lo antes posible. Observe el sangrado del ejemplo. Es el que le recomiendo.

  6. Cuando esté en el proceso de construcción de la gramática y aún le queden por rellenar variables sintácticas, declárelas como terminales mediante %token. De esta manera evitará las quejas de eyapp.

  7. Resolución de Ambiguedades y Conflictos

    Las operaciones de asignación tienen la prioridad mas baja, seguidas de las lógicas, los test de igualdad, los de comparación, a continuación las aditivas, multiplicativas y por último las operaciones de tipo unary y primary. Exprese la asociatividad natural y la prioridad especificada usando los mecanismos que eyapp provee al efecto: %left, %right, %nonassoc y %prec.

  8. La gramática de SimpleC es ambigua, ya que para una sentencia como

    if $ E_1$ then if $ E_2$ then $ S_1$ else $ S_2$

    existen dos árboles posibles: uno que asocia el ``else'' con el primer ``if'' y otra que lo asocia con el segundo. Los dos árboles corresponden a las dos posibles parentizaciones:

    if $ E_1$ then (if $ E_2$ then $ S_1$ else $ S_2$)

    Esta es la regla de prioridad usada en la mayor parte de los lenguajes: un ``else'' casa con el ``if'' mas cercano. La otra posible parentización es:

    if $ E_1$ then (if $ E_2$ then $ S_1$) else $ S_2$

    La conducta por defecto de eyapp es parentizar a derechas. El generador eyapp nos informará del conflicto pero si no se le indica como resolverlo parentizará a derechas. Resuelva este conflicto.

  9. ¿Que clase de árbol debe producir el analizador? La respuesta es que sea lo mas abstracto posible. Debe

    El siguiente ejemplo muestra una versión aceptable de árbol abstracto. Cuando se le proporciona el programa de entrada:

    nereida:~/doc/casiano/PLBOOK/PLBOOK/code> cat -n prueba5.c
         1  int f(int a)
         2  {
         3    if (a>0)
         4      a = f(a-1);
         5  }
    

    El siguiente árbol ha sido producido por un analizador usando la directiva %tree y añadiendo las correspondientes acciones de bypass. Puede considerarse un ejemplo aceptable de AST:

    nereida:~/doc/casiano/PLBOOK/PLBOOK/code> eyapp Simple2 ;\
                                      usesimple2.pl prueba5.c
    PROGRAM(
      TYPEDFUNC(
        INT(TERMINAL[INT:1]),
        FUNCTION(
          TERMINAL[f:1],
          PARAMS(
            PARAM(
              INT(TERMINAL[INT:1]),
              TERMINAL[a:1],
              ARRAYSPEC
            )
          ),
          BLOCK(
            DECLARATIONS,
            STATEMENTS(
              IF(
                GT(
                  VAR(TERMINAL[a:3]),
                  INUM(TERMINAL[0:3])
                ),
                ASSIGN(
                  VAR(TERMINAL[a:4]),
                  FUNCTIONCALL(
                    TERMINAL[f:4],
                    ARGLIST(
                      MINUS(
                        VAR(TERMINAL[a:4]),
                        INUM(TERMINAL[1:4])
                      )
                    ) # ARGLIST
                  ) # FUNCTIONCALL
                ) # ASSIGN
              ) # IF
            ) # STATEMENTS
          ) # BLOCK
        ) # FUNCTION
      ) # TYPEDFUNC
    ) # PROGRAM
    

    Es deseable darle una estructura uniforme al árbol. Por ejemplo, como consecuencia de que la gramática admite funciones con declaración implícita del tipo retornado cuando este es entero

     1  definition:
     2      funcDef { $_[1]->type("INTFUNC"); $_[1] }
     3    | %name TYPEDFUNC
     4      basictype funcDef
     5    | declaration { $_[1] }
     6  ;
    

se producen dos tipos de árboles. Es conveniente convertir las definiciones de función con declaración implícita en el mismo árbol que se obtiene con declaración explícita.

Casiano Rodríguez León
2013-04-23