La Gaceta de Linux ... ¡ haciendo a Linux un poco más divertido !

Tutorial del Generador de Análisis Gramatical Lemon

Por Mike Chirico

Traducción al español por Pablo Wolter
el día 4 de Abril de 2005, para La Gaceta de Linux

Lemon es un generador de análisis gramatical compacto, seguro, bien probado escrito por el Dr. Richard Hipp. Usar un Generador de Análisis Gramatical, junto con un escáner como flex, puede ser ventajoso porque hay menos código que escribir. Uno sólo escribe la gramática para el analizador gramatical.

Ejemplo 1: Empezando

Comparemos esto con escribir todo el código fuente desde cero. Por ejemplo comparemos la básica calculadora de escritorio en C++ con el archivo de abajo. Abajo esta un archivo de sintáxis que contiene la gramática que usa el parser. "example1.y" es un ejemplo de un archivo de sintáxis para una calculadora bien básica.

example1.y


    1  %token_type {int}
    2
    3  %left PLUS MINUS.
    4  %left DIVIDE TIMES.
    5
    6  %include {
    7  #include <iostream>
    8  #include "example1.h"
    9  }
    10
    11  %syntax_error {
    12    std::cout << "Syntax error!" << std::endl;
    13  }
    14
    15  program ::= expr(A).   { std::cout << "Result=" << A << std::endl; }
    16
    17  expr(A) ::= expr(B) MINUS  expr(C).   { A = B - C; }
    18  expr(A) ::= expr(B) PLUS  expr(C).   { A = B + C; }
    19  expr(A) ::= expr(B) TIMES  expr(C).   { A = B * C; }
    20  expr(A) ::= expr(B) DIVIDE expr(C).  {
    
    
    21           if(C != 0){
    22             A = B / C;
    23            }else{
    24             std::cout << "divide by zero" << std::endl;
    25             }
    26  }  /* end of DIVIDE */
    
    
    27  expr(A) ::= INTEGER(B). { A = B; }

Como se puede ver, este archivo sólo tiene 27 líneas de código, sin contar los espacios en blanco. Es mucho más fácil modificar la gramática que reescribir largas secciones del código fuente.

El generador gramatical (lemon.c y lempar.c) toma como entrada el archivo de sintáxis "example1.y" y crea el archivo analizador de gramática "example1.c", junto con otros dos archivos 'example1.h", el cual contiene las definiciones para los tokens, y 'example1.out", el que entrega una completa lista de los estados de reducción para la gramática listada en "example1.y".

Vayamos por partes, empezando primero compilando el código fuente de lemon (disponible aquí). El primer paso es compilar lemon.c:


    $ gcc -o lemon lemon.c

Ahora tenemos el generador de análisis de gramática, lemon, ahora corramos el archivo de sintáxis "example1.y" a través de él.


    $ ./lemon example1.y

Eso creará example1.c, example1.h y example1.out. Que hay de lempar.c? Comparemos el "example1.c" con "lempar.c", y se verá que éste contiene un montón del mismo código. "lempar.c" es un archivo de plantilla. Se puede modificar el código si se desea, y todas las modificaciones serán pasadas a "example1.c" (incluyendo cualquier comentario).

Pero "example1.c" no esta completo. Debemos agregarle el contenido del archivo "main_part", el cual contiene una función principal y tokens. "main_parts" es llamado el driver.

main_part


    1  int main()
    2  {
    3    void* pParser = ParseAlloc (malloc);
    
    4    /* First input:
    5        15 / 5
    6                                  */
    7    Parse (pParser, INTEGER, 15);
    8    Parse (pParser, DIVIDE, 0);
    9    Parse (pParser, INTEGER, 5);
    10    Parse (pParser, 0, 0);
    
    11    /*  Second input:
    12          50 + 125
    13                                 */
    
    14    Parse (pParser, INTEGER, 50);
    15    Parse (pParser, PLUS, 0);
    16    Parse (pParser, INTEGER, 125);
    17    Parse (pParser, 0, 0);
    
    18    /*  Third input:
    19          50 * 125 + 125
    20                                 */
    
    
    
    21    Parse (pParser, INTEGER, 50);
    22    Parse (pParser, TIMES, 0);
    23    Parse (pParser, INTEGER, 125);
    24    Parse (pParser, PLUS, 0);
    25    Parse (pParser, INTEGER, 125);
    26    Parse (pParser, 0, 0);
    
    27    ParseFree(pParser, free );
    
    28  }

Bueno, que esta haciendo "main_part"?. Bien, la línea 3 inicializa el parser. Notar que pParser es pasado a cada llamada de la función "Parse" empezando en la línea 7. La expresión 15/5, o 15 DIVIDE 5, es ejecutada en las líneas 7 hasta 10, mandando primero el INTEGER 15, entonces el identificador DIVIDE, el que no necesita un valor, así 0 es elegido como el tercer parámetro en la línea 8. Finalmente, la línea 10, con 0 como el segundo parámetro en "Parse(pParser, 0, 0);" señala el fin de la entrada para esta expresión. (Por favor note que en "example4.y", la gramática manejará esto con un NEWLINE, y "Parse(pParser,0,...);" será llamado sólo al final del archivo de sintáxis.)

"main_part" es agregado a "example1.c". Querrás referenciar el Makefile con el ejemplo descargable, el que tiene este paso


    $ cat main_part >> example1.c

Después, sólo compile example1.c, y está listo para usar.


    $ g++ -o ex1 example1.c

Ahora ejecute "ex1", y veremos que el resultado de 15/5 es, por supuesto, 3. Y 50+125 es igual a 175, y 50*125+125 es efectivamente igual a (50*125)+125= 6375. Este ultimo resultado verifica que la MULTIPLICACION tiene mayor precedencia que la SUMA.


    $ ./ex1
    Result=3
    Result=175
    Result=6375

Ahora miremos más de cerca al archivo de sintáxis (example1.y). Por que la MULTIPLICACION tiene una mayor precedencia que la SUMA? La línea 3 y 4 determinan la precedencia de los operadores MAS, MENOS, DIVIDIR y MULTIPLICAR.


    3  %left PLUS MINUS.
    4  %left DIVIDE TIMES.

Las líneas de arriba tienen menor precedencia. Esto es muy importante de resaltar. SUMA y RESTA tienen menor precedencia de operador que DIVIDIR y MULTIPLICAR porque SUMA y RESTA están en la línea 3, mientras que DIVIDIR y MULTIPLICAR están en la línea 4. Si, por ejemplo, se agregara la EXPONENCIACION, como EXP tiene aun mayor precedencia de operador que MULTIPLICACION Y DIVISION, este sería agregado abajo de la línea 4.

Que pasaría si quisieramos números reales en la entrada, 15.5,5.2 en lugar de enteros? Como hariamos eso? Es fácil. Estos tokens son actualmente enteros debido a la siguiente línea en "example1.y":


    1  %token_type {int}

Así para alojar un double, la línea 1 debe ser cambiada por:


    %token_type {double}

Moviendonos hacia abajo varias líneas en "example1.y", hay una directiva "include" en la línea 6. La declaración include en "example1.y" pasa como cualquier declaración de C, la cual es insertada al principio del archivo analizador "example1.c". Otra vez, los contenidos son insertados al principio de "example1.c", lo que es necesario para las declaraciones y encabezados.


    ...
    6  %include {
    7  #include <iostream>
    8  #include "example1.h"
    9  }
    ...

Notar que "example1.h" es generado desde "$ ./lemon example1.y". Este define los tokens, o, puesto de otra forma, asigna valores enteros a los nombres de los token empezando en 1. Por que empezar en 1, y no en 0? Porque 0 esta reservado para la función Parse. Recuerda, "Parse (pParser, 0, 0);", con el segundo parámetro en cero, marca el fin de la entrada.

example1.h (nota, éste es un archivo generado; no le agregues código):


    #define PLUS                            1
    #define MINUS                           2
    #define DIVIDE                          3
    #define TIMES                           4
    #define INTEGER                         5

Ejemplo 2: Creando un tipo o estructura token custom

"example2.y" se diferencia de "example1.y" por la definición del tipo token como una estructura. Específicamente, este tipo token esta definido en el archivo "ex2def.h". Definir nuestra propia estructura puede darnos flexibilidad en la acción semántica, o el pedazo de código a la derecha de la regla de producción. Aquí hay un ejemplo:


    expr(A) ::= expr(B) TIMES  expr(C).   { A.value = B.value * C.value;
    A.n = B.n+1  + C.n+1;
    }

El token_type en "example2.y" esta definido como Token en la línea 6.


    6  %token_type {Token}

Esta estructura Token esta definida en "ex2def.h" como sigue:

ex2def.h


    struct Token {
    const char *z;
    int value;
    unsigned n;
    };
    

Nota especial: "const char *z" no se usa en estos ejemplos, pero la mantuve en esta estructura, porque es el siguiente paso lógico en una calculadora, asignar una expresión a una variable. Por ejemplo, variable1=2+5, donde variable1 puede ser un valor en una tabla simbólica. Ver ésta referencia.

Otra vez, notar el cambio en la directiva include, la inclusión de "ex2def.h", que define la estructura Token.

example2.y


    1  #include {
    2  #include <iostream>
    3  #include "ex2def.h"
    4  #include "example2.h"
    5  }
    
    6  %token_type {Token}
    7  %default_type {Token}
    
    8  %type expr {Token}
    9  %type NUM {Token}
    10
    11  %left PLUS MINUS.
    12  %left DIVIDE TIMES.
    13
    14
    15  %syntax_error {
    16    std::cout << "Syntax error!" << std::endl;
    17  }
    18
    19  program ::= expr(A).   {
    20                          std::cout << "Result.value=" << A.value << std::endl;
    21                          std::cout << "Result.n=" << A.n << std::endl;
    
    22                           }
    
    23  expr(A) ::= expr(B) MINUS  expr(C).   { A.value = B.value - C.value;
    24                                         A.n = B.n+1  + C.n+1;
    25                                        }
    
    
    26  expr(A) ::= expr(B) PLUS  expr(C).   { A.value = B.value + C.value;
    27                                         A.n = B.n+1  + C.n+1;
    28                                        }
    
    29  expr(A) ::= expr(B) TIMES  expr(C).   { A.value = B.value * C.value;
    30                                          A.n = B.n+1  + C.n+1;
    
    31                                           }
    32  expr(A) ::= expr(B) DIVIDE expr(C).  {
    
    
    33           if(C.value != 0){
    34             A.value = B.value / C.value;
    35             A.n = B.n+1 + C.n+1;
    36            }else{
    37             std::cout << "divide by zero" << std::endl;
    38             }
    39  }  /* end of DIVIDE */
    40  expr(A) ::= NUM(B). { A.value = B.value; A.n = B.n+1; }

Como se puede ver abajo, dando una mirada de cerca a la línea 23 hasta 25, la estructura Token A ahora toma miembros "A.value" y "A.n", con ".value" tomando el valor de la expresión y ".n" el número de veces que la asignación es realizada:


    23  expr(A) ::= expr(B) MINUS  expr(C).   { A.value = B.value - C.value;
    24                                         A.n = B.n+1  + C.n+1;
    25                                        }

Esta es una manera rápida de ver el "shift" y "reduce" dinámicamente. "shift" es el número de veces que el token es sacado del stack o pila. "reduce" es el número de veces que una regla de expresión ha calsado. Una vez que calzo, puede ser reducida. Como puedes recordar, cuando lemon corre, se crean normalmente tres archivos: *.c, *.h y *.out. Este *.out contiene cada paso de la gramática, así como los estados de shift y reduce. Si se quiere un sumario simple, correr lemon con la opción "-s":


    $ ./lemon -s example2.y
    Parser statistics: 6 terminals, 3 nonterminals, 6 rules
    11 states, 0 parser table entries, 0 conflicts

Otra vez, como en el ejemplo previo, "main_part2", el driver, es agregado a "example2.c":


    $ cat main_part2 >> example2.c

Ahora "example2.c' puede ser compilado y ejecutado;


    $ g++ -o ex2  example2.c
    
    $ ./ex2
    Result.value=17
    Result.n=4
    Result.value=-9
    Result.n=4
    Result.value=78
    Result.n=10

Ejemplo 3: Trabajando con el token destructor

Una ventaja de lemon sobre bison es la habilidad para liberar memoria usada por un no-terminal. Uno puede llamar la función de su elección. "expr" es un ejemplo de un no-terminal. Cuando el programa termina con el no-terminal, la función definida por token_destructor es llamada.

example3.y


    1  %include {
    2  #include <iostream>
    3  #include "ex3def.h"
    4  #include "example3.h"
    
    
    5    void token_destructor(Token t)
    6      {
    7        std::cout << "In token_destructor t.value= " << t.value << std::endl;
    8        std::cout << "In token_destructor t.n= " << t.n << std::endl;
    9      }
    
    
    10  }
    
    
    11  %token_type {Token}
    12  %default_type {Token}
    13  %token_destructor { token_destructor($$); }
    ...

En la línea 13, token_destructor es la función "token_destructor($$);". La función "token_destructor" esta definida en las líneas 5 a 9. Para este ejemplo simple, no se reserva memoria, así que no hay necesidad de llamar a free. En su lugar, para ver que está pasando, la salida será escrita a std::cout.

Después que el programa es compilado, se puede ejecutar como sigue. Note que se han agregado números de línea a la salida de 'ex3" para una fácil referencia.


    $ ./ex3
    1  t0.value=4  PLUS t1.value=13
    2  In token_destructor t.value= 4
    3  In token_destructor t.n= 0
    4  Result.value=17
    5  Result.n=4
    6  parsing complete!
    ...

Después que la expresión ha sido reducida, el destructor es llamado, pero el sólo es llamado para el token.value=4. Por qué? Para una respuesta debemos echar una mirada a "main_part3".

main_part3


    1  int main()
    2  {
    3    void* pParser = ParseAlloc (malloc);
    
    4    struct Token t0,t1;
    5    struct Token mToken;
    
    6    t0.value=4;
    7    t0.n=0;
    
    8    t1.value=13;
    9    t1.n=0;
    
    10    std::cout << " t0.value=4  PLUS t1.value=13 " << std::endl;
    
    11    Parse (pParser, NUM, t0);
    12    Parse (pParser, PLUS, t0);
    13    Parse (pParser, NUM, t1);
    14    Parse (pParser, 0, t0);
    
    15    std::cout << " t0.value=4  DIVIDE t1.value=13 " << std::endl;
    
    16    Parse (pParser, NUM, t0);
    17    Parse (pParser, DIVIDE, t0);
    18    Parse (pParser, NUM, t1);
    19    Parse (pParser, 0, t1);
    ...

La línea 14 termina la gramática con t0 como tercer parámetro. Ese tercer parámetro es pasado como "$$" a la función definida destructor, "token_destructor(...". Cuando llamamos a "Parse" una segunda vez inmediatamente, esta indefinida, así que debes llamar a la función destructor una sola vez después que se pasaron los tokens para completar la expresión. En otras palabras, nunca puedes llamar "Parse (pParser, 0, t0);", inmediatamente seguido por otro "Parse (pParser, 0, t0);".

En la línea 19, token_destructor es llamada para t1.value= 13. Si miras "main_part3", línea 19, verás que Parse es llamado con t1 como tercer parámetro y 0 como el segundo parámetro.

Continuación de la salida del programa:


    7
    8
    9   t1.value=13  PLUS  t0.value=4
    10   In token_destructor t.value= 13
    11   In token_destructor t.n= 0
    12   Result.value=17
    13   Result.n=4
    14   parsing complete!

t0 es llamado en la posición del tercer parámetro en la línea 14 y t1 es llamado en la línea 19. Esto no debería ser un problema. Una variable puede contener el valor de los tokens. Por ejemplo, main_part3 podría tener al Token t0 usado como ambos el valor 4 y 14 como sigue:


    ...
    struct Token t0;
    
    t0.value=4;
    t0.n=0;
    
    Parse (pParser, NUM, t0);
    Parse (pParser, PLUS, t0);
    
    t0.value=13;
    t0.n=0;
    
    Parse (pParser, NUM, t0);
    Parse (pParser, 0, t0);
    ...
    

Ejemplo 4: Finalizando la gramática con NEWLINE

Notemos que en los tres últimos ejemplos, Parse(pParse,0.. tine que ser llamado para señalar el fin de la entrada para una expresión. Esto es torpe. En su lugar, la gramática debe dictar cuando la expresión no puede ser reducida más.

"example4.y" contine las siguientes líneas:

example4.y


    1  %include {
    2  #include <iostream>
    3  #include "ex4def.h"
    4  #include "example4.h"
    
    ...
    
    23
    24  %syntax_error {
    25    std::cout << "Syntax error!" << std::endl;
    26  }
    27
    28  /*  This is to terminate with a new line */
    29  main ::= in.
    30  in ::= .
    31  in ::= in state NEWLINE.
    
    
    32  state ::= expr(A).   {
    33                          std::cout << "Result.value=" << A.value << std::end
    34                          std::cout << "Result.n=" << A.n << std::endl;
    
    
    35                           }
    
    
    
    36  expr(A) ::= expr(B) MINUS  expr(C).   { A.value = B.value - C.value;
    37                                         A.n = B.n+1  + C.n+1;
    38                                        }
    
    ...

Notemos las líneas 29 a 35. "main" y "in" deben estar definidas (líneas 29-31). Si eres un usuario de Bison, puedes continuar sin tener que definir la no-terminal principal, pero lemon actualmente requiere eso.

Con este cambio echo a la gramática en "example4.y", "main_part4" pueden terminar ahora cada expresión pasando el token NEWLINE.

Aquí una parte de main_part4:

main_part4


    1  int main()
    2  {
    3    void* pParser = ParseAlloc (malloc);
    
    4    struct Token t0,t1;
    5    struct Token mToken;
    
    6    t0.value=4;
    7    t0.n=0;
    
    8    t1.value=13;
    9    t1.n=0;
    
    10    std::cout << std::endl <<" t0.value=4  PLUS t1.value=13 " << std::endl << std::endl;
    
    11    Parse (pParser, NUM, t0);
    12    Parse (pParser, PLUS, t0);
    13    Parse (pParser, NUM, t1);
    14    Parse (pParser, NEWLINE, t1);
    
    
    15    std::cout << std::endl <<" t0.value=4  TIMES t1.value=13 " << std::endl << std::endl;

Note que la línea 14 esta pasando el token NEWLINE y chequeando "example4.h". NEWLINE en este caso esta definido como un entero, 6.

Así, mirando la salida de "ex4", con números de línea agregados para clarificar, tenemos lo siguiente:


    $ ./ex4
    
    1  t0.value=4  PLUS t1.value=13
    2
    3  In token_destructor t.value= 4
    4  In token_destructor t.n= 0
    5  Result.value=17
    6  Result.n=4
    7
    8   t0.value=4  TIMES t1.value=13
    9
    10  In token_destructor t.value= 4
    11  In token_destructor t.n= 0
    12  Result.value=52
    13  Result.n=4
    14  parsing complete!

Tenemos el resultado en la línea 5, y no hay necesidad de llamar a Parse (pParser, 0, t0);. En su lugar, Parse( pParse, NEWLINE, t0) funcionó.

Ejemplo 5: Usando flex para el tokenizador

El siguiente ejemplo toma la entrada directamente de un terminal, y flex creará un escaner para encontrar los tokens apropiados.

Primero, un rápido vistazo al programa en flex "lexer.1", otra vez con los números de línea agregados para mayor claridad:

lexer.l


    1  %{
    2  #include "lexglobal.h"
    3  #include "example5.h"
    4  #include <string.h>
    5  #include <math.h>
    
    6  int line = 1, col = 1;
    
    7  %}
    8  %%
    
    9  [0-9]+|[0-9]*\.[0-9]+    {                      col += (int) strlen(yytext);
    10                                                  yylval.dval = atof(yytext);
    11                                                  return NUM; }
    12  [ \t]   { col += (int) strlen(yytext); }               /* ignore but count white space */
    13  [A-Za-z][A-Za-z0-9]*                           { /* ignore but needed for variables */
    
    14                                                  return 0;
    15                                                 }
    
    16  "+"           {  return PLUS; }
    17  "-"           {  return MINUS; }
    18  "*"           {  return TIMES; }
    19  "/"           {  return DIVIDE; }
    
    20  \n      { col = 0; ++line; return NEWLINE; }
    
    21  .       { col += (int) strlen(yytext); return yytext[0]; }
    22  %%
    23  /**
    24   * reset the line and column count
    25   *
    26   *
    27   */
    28  void reset_lexer(void)
    29  {
    
    30    line = 1;
    31    col  = 1;
    
    32  }
    
    33  /**
    34   * yyerror() is invoked when the lexer or the parser encounter
    35   * an error. The error message is passed via *s
    36   *
    37   *
    38   */
    39  void yyerror(char *s)
    40  {
    41    printf("error: %s at line: %d col: %d\n",s,line,col);
    
    42  }
    
    43  int yywrap(void)
    44  {
    45    return 1;
    46  }
    

El formato para flex es básicamente una regla en el lado izquierdo seguido por código en C a ser ejecutado en el lado derecho. Tomemos la línea 9, "[0-9]+|[0-9]*\.[0-9]+", que coincidirá con cualquiera de 3, .3, 0.3 y 23.4 y retornará un NUM. Cuál es el valor de NUM? Este es tomado de la línea 3, que incluye el archivo "example5.h", generado por el lemon parser. En la línea 10, yylval.dval es asignado con el valor de "yytext" después que es convertido a float. La estructura de yylval esta definida en "lexglobal.h" en la línea 2.

"lexglobal.h" con números de línea agregados:

lexglobal.h


    1  #ifndef YYSTYPE
    2  typedef union {
    3    double    dval;
    4    struct symtab *symp;
    5  } yystype;
    6  # define YYSTYPE yystype
    7  # define YYSTYPE_IS_TRIVIAL 1
    8  #endif
    
    9  /* extern YYSTYPE yylval; */
    10  YYSTYPE yylval;
    

yystype es la unión de dval y symtab. Otra vez, symtab no es usado en éstos ejemplos, pero te llevarán a una calculadora con variables que pueden ser asignadas, cuando tengas que usarlo. Mirar la Referencia 3 para un ejemplo completo de una calculadora con flex y bison.

Otra vez mirando las líneas 9 a 11 en lexer.l;


    ...
    9  [0-9]+|[0-9]*\.[0-9]+    {                      col += (int) strlen(yytext);
    10                                                  yylval.dval = atof(yytext);
    11                                                  return NUM; }
    ...

Ambos tipos de token, NUM y su valor deben ser pasados. Necesitamos saber sus números, pero también necesitamos saber el valor del número.

A diferencia de lo que necesitamos con PLUS, MINUS, TIME y DIVIDE, sólo necesitamos saber que el identificador particular ha sido encontrado. Sin embargo, en lexer.1, las líneas 16 a 19 solo retornan el valor del token.


    16  "+"           {  return PLUS; }
    17  "-"           {  return MINUS; }
    18  "*"           {  return TIMES; }
    19  "/"           {  return DIVIDE; }
    
    20  \n      { col = 0; ++line; return NEWLINE; }
    
    21  .       { col += (int) strlen(yytext); return yytext[0]; }
    22  %%

La línea 20 coincidirá en NEWLINE. Aunque no usados, los números de línea mantienen un traceo de la variable "line" y col es usado para mantener un traceo de los números de columna. Esta es una buena idea; es de ayuda cuando se buscan errores.

El driver, main_part5, contiene un monton de código. La declaración de bajo nivel read se usa en stdin. Esto se puede cambiar fácilmente para aceptar entradas desde un descriptor de socket, así si tienes un programa Web scraping* que escanea entradas desde un socket TCP, el descriptor del socket reemplazará "fileno(stdin)" en la línea 33.

Nota del Traductor: No supe como traducir esto :-)

main_part5


    
    1  #include <stdio.h>
    2  #include <unistd.h>
    3  #include <sys/types.h>
    4  #include <sys/stat.h>
    5  #include <fcntl.h>
    6  #include <stdlib.h>
    
    7  #define BUFS 1024
    
    8  /**
    9   * We have to declare these here - they're not  in any header files
    10   * we can include.  yyparse() is declared with an empty argument list
    11   * so that it is compatible with the generated C code from bison.
    12   *
    13   */
    
    14  extern FILE *yyin;
    15  typedef struct yy_buffer_state *YY_BUFFER_STATE;
    
    16  extern "C" {
    17    int             yylex( void );
    18    YY_BUFFER_STATE yy_scan_string( const char * );
    19    void            yy_delete_buffer( YY_BUFFER_STATE );
    20  }
    
    21  int main(int argc,char** argv)
    22  {
    23    int n;
    24    int yv;
    25    char buf[BUFS+1];
    26    void* pParser = ParseAlloc (malloc);
    
    27    struct Token t0,t1;
    28    struct Token mToken;
    
    29    t0.n=0;
    30    t0.value=0;
    
    31    std::cout << "Enter an expression like 3+5 <return>" << std::endl;
    32    std::cout << "  Terminate with ^D" << std::endl;
    
    33    while ( ( n=read(fileno(stdin), buf, BUFS )) >  0)
    34      {
    35        buf[n]='\0';
    36        yy_scan_string(buf);
    37        // on EOF yylex will return 0
    38        while( (yv=yylex()) != 0)
    39          {
    40            std::cout << " yylex() " << yv << " yylval.dval " << yylval.dval << std::endl;
    41            t0.value=yylval.dval;
    42            Parse (pParser, yv, t0);
    43          }
    
    44      }
    
    45    Parse (pParser, 0, t0);
    46    ParseFree(pParser, free );
    
    47  }

La línea 16, 'extern "C"', es necesaria porque "lexer.1" fue corrido a través de flex para crear el código C, a diferencia del código C++:


    $ flex lexer.l

Ve el manual de flex, Reference 7. "flex++" producirá código C++. Sin embargo, para escaneos complejos, el código en C será más rápido. "main_part5", el cual está compilado como un programa en C++, realiza la transición suavemente.

El parser deberá siempre terminar la entrada con 0 en el segundo parámetro "Parse(pParser,0,..". Cuando no hay más entradas hacia flex, el deberá regresar un cero, así el loop while abajo en la línea 38 termina con un cero. Entonces la declaración read, línea 33, mira por más entradas. Esto es algo que querrás hacer cuando lees datos desde un socket, porque a lo mejor éste está retrasado.

Pero si el read inicial (línea 33 la primera vez) no es exitoso, flex no tiene manera de retornar un cero. Sin embargo, la línea 45 tiene un cero como segundo parámetro.


    ...
    33    while ( ( n=read(fileno(stdin), buf, BUFS )) >  0)
    
    ...
    38        while( (yv=yylex()) != 0)
    39          {
    40            std::cout << " yylex() " << yv << " yylval.dval " << yylval.dval << std::endl;
    41            t0.value=yylval.dval;
    42            Parse (pParser, yv, t0);
    43          }
    ...
    45    Parse (pParser, 0, t0);
    46    ParseFree(pParser, free );

Sumario

lemon es rápido, completamente en el dominio publico, bien probado en SQLite, y seguro. Los generadores gramaticales pueden ayudar a los desarrolladores a escribir código reusable para tareas complejas en una fracción del tiempo que necesitarian para escribir el programa completo desde el principio. El archivo de sintáxis, el archivo que almacena la gramática, pueden modificarse para satisfacer multiples necesidades.

Aunque yo no tuve problemas con lemon.c, hay algunas advertencias del compilador acerca de enteros signed y unsigned cuando se compila con los flags -Wall y -W:


    [chirico@third-fl-71 lemon_examples]$ gcc -Wall -W -O2 -s -pipe lemon.c
    lemon.c: In function `resolve_conflict':
    lemon.c:973: warning: unused parameter `errsym'
    lemon.c: In function `main':
    lemon.c:1342: warning: unused parameter `argc'
    lemon.c: At top level:
    lemon.c:2308: warning: return type defaults to `int'
    lemon.c: In function `preprocess_input':
    lemon.c:2334: warning: comparison between signed and unsigned
    lemon.c:2352: warning: control reaches end of non-void function
    lemon.c:2311: warning: `start' might be used uninitialized in this function
    lemon.c:2313: warning: `start_lineno' might be used uninitialized in this function
    lemon.c: In function `Parse':
    lemon.c:2393: warning: comparison between signed and unsigned
    lemon.c: In function `tplt_open':
    lemon.c:2904: warning: implicit declaration of function `access'
    lemon.c: In function `append_str':
    lemon.c:3019: warning: comparison between signed and unsigned
    lemon.c:3011: warning: unused variable `i'
    lemon.c: In function `translate_code':
    lemon.c:3109: warning: control reaches end of non-void function

Esto puede ser un inconveniente cuando se agrega el archivo parse.c a código existente. Un arreglo esta en camino. Puesto que espero que los cambios sean depurados pronto, esta versión de lemon.c es la misma versión que tu puedes obtener desde el sitio del autor, lo que hara más fácil el aplicar los parches.

Habra ocaciones en que un parser como lemon o bison pueden ser damasiado. Estas son herramientas poderosas. Una alternativa interesante, si eres un programador C++ y sólo necesitas hacer analisis en línea, es la libreria spirit. Ver referencia 9.

Ejemplos para este artículo

Los archivos fuente completos para estos ejemplos, incluyendo el parser mismo, pueden ser bajados aquí.

Referencias

  1. An example desktop calculator from scratch
  2. An example of a flex and bison parser
  3. The home of the lemon parser generator
  4. The home of SQLite
  5. A glossary of parser terms
  6. A good introduction to parsers
  7. The GNU flex manual
  8. The GNU bison manual
  9. The spirit parser
  10. Getting a C++ Bison parser to use a C Flex lexer
  11. The Lex-YACC-HOWTO

 


[BIO]

Mike Chirico, padre de trillisos (todas mujeres) vive en las afueras de Philadelphia, PA, USA. Ha trabajado con Linux desde 1996, tiene un Masters en Computer Science y Matemáticas de la Universidad Villanova, y ha desempeñado trabajos relacionados a computadores desde Wall Street a la Universidad de Pennsylvania. Su heroe es Paul Erdos, un brillante teórico númerico quien ha sido conocido por su abierta ayuda a los demas.
la página de notas de Mike es souptonuts.


Copyright © 2004, Mike Chirico. Publicado bajo la licencia Open Publication

Publicado en el número 106 de la gaceta de Linux, Septiembre 2004