Un pequeño ejemplo

Para facilitar la compresión de la incorporación del comportamiento no determinista, vamos a utilizar un pequeño ejemplo. Como en castellano hay un gran número de reglas léxicas, lo que nos obligaría a definir numerosas condiciones de arranque para crear un ejemplo mínimamente real, hemos sonsiderado más conveniente utilizar como ejemplo un pequeño analizador léxico en el que se muestra cómo reconocer todas las variantes de la palabra inglesa bellow. Este ha sido el ejemplo sobre el que hemos trabajado con Vern Paxon. La palabra bellow tienen cuatro entradas en un diccionario:

bellow

noun bramido, rugido.

bellow

intransitive verb gritar, vociferar.

bellow

transitive verb bramar, rugir.

bellows

noun plural fuelle.

El problema surge al tener que reconocer una palabra como bellows, que puede ser:

• El singular del sustantivo bellows.
• El plural del sustantivo bellow.
• La tercera persona del presente del verbo bellow.

Para ser capaces de tratar con estas definiciones, debemos crear dos condiciones de arranque, que son las siguientes:

• N para los sustantivos.
• V para los verbos.

Para ello utilizamos la siguiente línea de código, en la que también incluimos la declaración de la condición E de error:

/* Start conditions */
%x E N V

A continiuación se definen los patrones de los separadores y de los no separadores:

/* Separators */
sep     [" ",;:\.\t\n]

/* Non separators */
nosep   [^" ",;:\.\t\n]

Algo muy importante es declarar las variables enteras match_no y semaphore:

%{
unsigned int match_no, semaphore;
%}

A continuación ya se pasa a escribir las reglas léxicas con el no determinismo incorporado, no sin antes haber escrito un pequeño trozo de código en el cual se establece a cero el valor de las dos variables anteriores. Esta porción de código situado después de %% y encerrada entre %{ y %} se ejecutrá cada vez que se llame a la función yylex.

%%

%{
/* Code executed each time yylex is called */
match_no = 0;
semaphore = 0;
%}

/* Error condition: Panic mode */
<E>{nosep}*/{sep}    { printf("%s -> error \n\n", yytext);
                       BEGIN(INITIAL);RETURN(1);
                     }

/* Verbs */
<V>s/{sep}           printf("%s -> verb, 3rd        \n",yytext);REJECT;
<V>ed/{sep}          printf("%s -> verb, past       \n",yytext);REJECT;
<V>ing/{sep}         printf("%s -> verb, gerund     \n",yytext);REJECT; 
<V>""/{sep}          printf("%s -> verb, infinitive \n",yytext);REJECT;
<V>""/.              yyless(0); BEGIN(INITIAL);

/* Nouns */
<N>s/{sep}           printf("%s -> noun, plural   \n",yytext);REJECT;
<N>""/{sep}          printf("%s -> noun, singular \n",yytext);REJECT;
<N>""/.              yyless(0);BEGIN(INITIAL);

/* WORDS */
bellow               { if ( semaphore!=0) { semaphore--; REJECT; }; 
                       match_no++; semaphore=match_no;

                       yymore(); BEGIN(V);
                     }

bellow               { if ( semaphore!=0) { semaphore--; REJECT; }; 
                       match_no++; semaphore=match_no;

                       yymore(); BEGIN(N);
                     }

bellows              { if ( semaphore!=0) { semaphore--; REJECT; }; 
                       match_no++; semaphore=match_no;

                       yymore(); BEGIN(N);
                     }

/* Separators */
" "                  |
\t                   |
\n                   |
","                  |
","                  |
";"                  |
":"                  |
"."                  printf("%s -> separator \n\n'', yytext);return(1);

.                    yymore(); BEGIN (E);

<<EOF>> yyterminate();

%%

Mediante la utilización de las dos líneas iniciales de código de todas las reglas con comportamiento no determinista

if ( semaphore!=0) { semaphore--; REJECT; }
match_no++;semaphore=match_no;

se comprueba si el valor del semáforo es correcto. Si no lo es, se realiza un REJECT, con lo cual el resto de las acciones de esa regla no se ejecutan. En caso contrario, se actualizan las variables convenientemente. Para facilitar la escritura de reglas en Flex, se puede definir una macro NDFLEX que contenga esas instrucciones, que van a ser iguales en todas las reglas que se quiere que participen del comportamiento no determinista.

La última regla permite evitar que el reconocedor genere errores cuando se intenta llamar a yylex y ya se ha alcanzado el fin de fichero. Puede ser eliminada y el programa seguirá funcionando, pero se recomienda que sea incluida.

En este ejemplo, por sencillez, no se ha utilizado la condición de arranque S, sino que yylex devuelve el control cuando encuentra un separador. En un programa real los espacios, tabuladores y retornos de carro se ignorarían y las marcas de puntuación se reconocerían como componentes léxicos.

Aunque el ejemplo se ha puesto en inglés por cuestiones de legibilidad, en castellano se dan muchos más casos de ambigüedades. Por ejemplo, la palabra para puede ser reconocida como:

• Una preposición.
• La tercera persona del presente de indicativo del verbo ``parar''.
• La segunda persona del imperativo del verbo ``parar''.
• La primera persona del presente de subjuntivo del verbo ``parir''
• La tercera persona del presente de subjuntivo del verbo ``parir''

Existen muchos casos como éste, pero para mostrarlos es necesario escibir muchas reglas debido a la complejidad de la conjugación verbal, por lo que son poco adecuados para un ejemplo didáctico.