Práctica: Un C simplificado

Escriba un analizador sintáctico usando Parse::Yapp para el siguiente lenguaje. La descripción utiliza una notación tipo BNF: las llaves indican 0 o mas repeticiones y los corchetes opcionalidad.



program $ \rightarrow$ definitions { definitions }
definitions $ \rightarrow$ datadefinition $ \vert$ functiondefinition
datadefinition $ \rightarrow$ basictype declarator { ',' declarator } ';'
declarator $ \rightarrow$ ID { '$ [$' constantexp '$ ]$' }
functiondefinition $ \rightarrow$ $ [$ basictype $ ]$ functionheader functionbody
basictype $ \rightarrow$ INT $ \vert$ CHAR
functionheader $ \rightarrow$ ID '(' $ [$ parameters $ ]$ ')'
parameters $ \rightarrow$ basictype declarator { ',' basictype declarator }
functionbody $ \rightarrow$ '{' { datadefinition } { statement } '}'
statement $ \rightarrow$ $ [$ exp $ ]$ ';'
    $ \vert$ '{' { datadefinition } { statement } '}'
    $ \vert$ IF '(' exp ')' statement $ [$ ELSE statement $ ]$
    $ \vert$ WHILE '(' exp ')' statement
    $ \vert$ RETURN $ [$ exp $ ]$ ';'
constantexp $ \rightarrow$ exp
exp $ \rightarrow$ lvalue '=' exp $ \vert$ lvalue '+=' exp
    $ \vert$ exp '&&' exp $ \vert$ exp '$ \vert\vert$' exp $ \vert$
    $ \vert$ exp '==' exp $ \vert$ exp '!=' exp $ \vert$
    $ \vert$ exp '$ <$' exp $ \vert$ exp '$ >$' exp $ \vert$ exp '$ <=$' exp $ \vert$ exp '$ >=$' exp $ \vert$
    $ \vert$ exp '+' exp $ \vert$ exp '-' exp $ \vert$
    $ \vert$ exp '*' exp $ \vert$ exp '/' exp $ \vert$
    $ \vert$ unary
unary $ \rightarrow$ '$ ++$' lvalue $ \vert$ '$ -$' lvalue $ \vert$ primary
primary $ \rightarrow$ '(' exp ')' $ \vert$ ID '(' $ [$ argumentlist $ ]$ ')' $ \vert$ lvalue $ \vert$ NUM $ \vert$ CHARACTER
lvalue $ \rightarrow$ ID { '$ [$' exp '$ ]$' }
argumentlist $ \rightarrow$ exp { ',' exp }


Su analizador, además de seguir los consejos explícitados en la sección 35.17, deberá cumplir las siguientes especificaciones:

  1. Método de Trabajo

    Parta de la definición BNF y proceda a introducir las reglas poco a poco:

    1 %token declarator basictype functionheader functionbody
    2 %%
    3 program: definitionslist
    4        ;
    5
    6 definitionslist: definitions definitionslist
    7                | definitions
    8                ;
    9
    10 definitions: datadefinition
    11            | functiondefinition
    12            ;
    13 datadefinition: basictype declaratorlist ';'
    14               ;
    15
    16 declaratorlist: declarator ',' declaratorlist
    17               | declarator
    18               ;
    19 functiondefinition: basictype functionheader functionbody
    20                   | functionheader functionbody
    21                   ;
    22
    23 %%
    

    1. Comienze trabajando en el cuerpo de la gramática.
    2. Olvídese del analizador léxico por ahora. Su objetivo es tener una gramática limpia de conflictos y que reconozca el lenguaje dado.
    3. Sustituya las repeticiones BNF por listas. Si una variable describe una lista de cosas llámela cosaslist.
    4. Si tiene un elemento opcional en la BNF, por ejemplo, en la regla:

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

      sustitúyala por dos reglas una en la que aparece el elemento y otra en la que no.

      19 functiondefinition: basictype functionheader functionbody
      20                   | functionheader functionbody
      21                   ;
      
    5. Cada par de reglas que introduzca vuelva a recompilar con yapp la gramática para ver si se han producido conflictos. Cuando estoy editando la gramática suelo escribir a menudo la orden

      :!yapp %

      para recompilar:



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


      Esto llama a yapp con el fichero bajo edición. Si hay errores los detectaré enseguida.

    6. Insisto, procure detectar la aparición de un conflicto lo antes posible. Es terrible tener que limpiar una gramática llena de conflictos.
    7. Ponga nombres significativos a las variables y terminales. Por favor, no los llame d1, d2, etc.
    8. 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 como en el código que aparece encima. De esta manera evitará las quejas de yapp.

  2. Resolución de Conflictos

    Las operaciones de asignación tienen la prioridad mas baja, seguidas de las lógicas, los test de igualdad y después de los de comparación, a continuación las aditivas, multiplicativas y por último los unary y primary. Exprese la asociatividad natural y la prioridad especificada usando los mecanismos que yapp provee al efecto.

    La gramática 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$

    Utilice los mecanismos de priorización proporcionados por yapp para resolver el conflicto shift-reduce generado. ¿Es correcta en este caso particular la conducta a la que da lugar la acción yapp por defecto?

  3. Analizador Léxico

    Además del tipo de terminal y su valor el analizador léxico deberá devolver el número de línea. El analizador léxico deberá aceptar comentarios C. En la gramática, el terminal CHARACTER se refiere a caracteres entre comillas simples (por ejemplo 'a').

    Se aconseja que las palabras reservadas del lenguaje no se traten con expresiones regulares específicas sino que se capturen en el patrón de identificador [a-z_]\w+. Se mantiene para ello un hash con las palabras reservadas que es inicializado al comienzo del programa. Cuando el analizador léxico encuentra un identificador mira en primer lugar en dicho hash para ver si es una palabra reservada y, si lo es, devuelve el terminal correspondiente. En caso contrario se trata de un identificador.

  4. Recuperación de Errores

    Extienda la práctica con reglas para la recuperación de errores. Para las listas, siga los consejos dados en la sección 35.2. En aquellos casos en los que la introducción de las reglas de recuperación produzca ambiguedad, resuelva los conflictos.

  5. Árbol de Análisis Abstracto

    La semántica del lenguaje es similar a la del lenguaje C (por ejemplo, las expresiones lógicas se tratan como expresiones enteras). El analizador deberá producir un árbol sintáctico abstracto. Como se hizo para el lenguaje Tutu introducido en el capítulo 33, cada clase de nodo deberá corresponderse con una clase Perl. Por ejemplo, para una regla como

    exp '*' exp

    la acción asociada sería algo parecido a

    { bless [ $_[1], $_[3]], 'MULT' }

    donde usamos un array anónimo. Mejor aún es usar un hash anónimo:

    { bless { LEFT => $_[1], RIGHT => $_[3]}, 'MULT' }

    Defina formalmente el arbol especificando la gramática árbol correspondiente a su diseño (repase la sección 33.9.1). Introduzca en esta parte la tabla de símbolos. La tabla de símbolos es, como en el compilador de Tutu, una lista de referencias a hashes conteniendo las tablas de símbolos locales a cada bloque. En cada momento, la lista refleja el anidamiento de bloques actual. Es posible que, en la declaración de funciones, le interese crear un nuevo bloque en el que guardar los parámetros, de manera que las variables globales queden a nivel 0, los parámetros de una función a nivel 1 y las variables locales de la función a nivel 2 o superior.

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