Sig: Práctica: Construcción del AST Sup: Análisis LR Ant: Descripción Eyapp del Lenguaje Err: Si hallas una errata ...

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
   • Contener toda la información necesaria para el manejo eficiente de las fases subsiguientes: Análisis de ámbito, Comprobación de tipos, Optimización independiente de la máquina, etc.
   • Ser uniforme
   • Legible (human-friendly)
   • No contener nodos que no portan información.

   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.

Sig: Práctica: Construcción del AST Sup: Análisis LR Ant: Descripción Eyapp del Lenguaje Err: Si hallas una errata ...