Capitulos de este wiki

Inicio

1 Bison. El Generador de Analizadores Sintacticos compatible con YACC
2 Los Conceptos de Bison
3 Ejemplos (I)
4 Ejemplos (II)
5 Ejemplos (III)
6 Archivos de Gramatica de Bison (I)
7 Archivos de Gramatica de Bison (II)
8 Archivos de Gramatica de Bison (III)
9 Interfaz del Analizador en Lenguaje C
10 El Algoritmo del Analizador de Bison
11 Recuperación de Errores
12 Manejando Dependencias del Contexto
13 Depurando Su Analizador
14 Invocando a Bison
15 Símbolos de Bison
16 Glosario

Bison - El Algoritmo del Analizador de Bison

10 - El Algoritmo del Analizador de Bison

A medida que Bison lee tokens, los va insertando en una pila junto con su valor semántico. La pila se denomina **pila del analizador**. El insertar un token tradicionalmente se denomina **desplazamiento**.

Por ejemplo, suponga que la calculadora infija ha leído `1 + 5 *', con un `3' por venir. La pila contendrá cuatro elementos, uno para cada token que fue desplazado.

Pero la pila no siempre contiene un elemento para cada token leído. Cuando los últimos n tokens y agrupaciones desplazadas concuerden con los componentes de una regla gramatical, estos pueden combinarse de acuerdo a esa regla. A esto se le denomina **reducción**. Esos tokens y agrupaciones se reemplazan en la pila por una sola agrupación cuyo símbolo es el resultado (lado izquierdo) de esa regla. La ejecución de la acción de la regla es parte del proceso de reducción, porque ésta es la que computa el valor semántico de la agrupación resultante.

Por ejemplo, si el analizador de la calculadora infija contiene esto:

1 + 5 * 3

y el siguiente token de entrada es un caracter de nueva línea, entonces los tres últimos elementos pueden reducirse a 15 mediante la regla:

expr: expr '*' expr;

Entonces la pila contiene exactamente estos tres elementos:

1 + 15

En este punto, se puede realizar otra reducción, resultando en el valor 16. Entonces el token de nueva línea se puede desplazar.

El analizador intenta, mediante desplazamientos y reducciones, reducir la entrada completa a una sola agrupación cuyo símbolo es el símbolo de arranque de la gramática (see section Lenguajes y Gramáticas independientes del Contexto).

Este tipo de analizador se conoce en la literatura como analizador ascendente.

===== Tokens de Preanálisis =====

El analizador de Bison //no// siempre reduce inmediatamente tan pronto como los últimos n tokens y agrupaciones se correspondan con una regla. Esto es debido a que es inadecuada una estrategia tan simple para manejar la mayoría de los lenguajes. En su lugar, cuando es posible una reducción, el analizador algunas veces "mira hacia delante" al próximo token para decidir qué hacer.

Cuando se lee un token, este no se desplaza inmediatamente; primero se convierte en el **token de preanálisis**, que no se pone sobre la pila. Ahora el analizador puede realizar una o más reducciones de tokens y agrupaciones sobre la pila, mientras que el token de preanálisis se mantiene fuera a un lado. Esto no significa que se han realizado todas las posibles reducciones; dependiendo del tipo de token del token de preanálisis, algunas reglas podrían escoger retrasar su aplicación.

Aquí hay un caso simple donde se necesita el token de preanálisis. Estas tres reglas definen expresiones que contienen operadores de suma binaria y operaciones factoriales unarios postfijos (`!'), y se permiten los paréntesis para agrupar.

expr:     term '+' expr
	    | term
	    ;

term:     '(' expr ')'
	    | term '!'
	    | NUMBER
	    ;

Suponga que se ha leído el token `1 + 2' y ha sido desplazado; ¿qué debería hacerse? Si el próximo token es `)', entonces los primeros tres tokens deberían reducirse para formar una ##expr##. Este es el único camino válido, porque el desplazamiento de `)' produciría una secuencia de símbolos ##term ')'##, y ninguna regla lo permite.

Si el siguiente token es `!', entonces debe ser desplazado inmediatamente de manera que `2 !' se pueda reducir para hacer un ##term##. Si en su lugar el analizador fuera a reducir antes de desplazar, `1 + 2' se convertiría en una ##expr##. Sería entonces imposible desplazar el `!' porque haciéndolo produciría en la pila la secuencia de símbolos ##expr '!'##. Ninguna regla permite esa secuencia.

El token de preanálisi actual se almacena en la variable ##yychar##. See section Propiedades Especiales para su Uso en Acciones.

===== Conflictos de Desplazamiento/Reducción =====

Suponga que estamos analizando un lenguaje que tiene las sentencias if-then y if-then-else, con un par de reglas como estas:

if_stmt:
	      IF expr THEN stmt
	    | IF expr THEN stmt ELSE stmt
	    ;

Aquí asumimos que ##IF##, ##THEN## y ##ELSE## son símbolos terminales de tokens para palabras clave específicas.

Cuando se lea el token ##ELSE## y se convierta en el token de preanálisis, el contenido de la pila (asumiendo que la entrada es válida) está listo para una reducción por la primera regla. Pero también es legítimo desplazar el ##ELSE##, porque eso conllevaría a una redución provisional por la segunda regla.

Esta situación, donde sería válido un desplazamiento o una reducción, se denomina un **conflicto desplazamiento/reducción**. Bison está diseñado para resolver estos conflictos eligiendo el desplazamiento, a menos que se le dirija con declaraciones de precedencia de operadores. Para ver la razón de esto, vamos a contrastarlo con la otra alternativa.

Ya que el analizador prefiere desplazar el ##ELSE##, el resultado sería ligar la cláusula else con la sentencia if más interior, haciendo que estas dos entradas sean equivalentes:

if x then if y then gana (); else pierde;

if x then do; if y then gana (); else pierde; end;

Pero si el analizador escoge la reducción cuando es posible en lugar de desplazar, el resultado sería ligar la cláusula else a la sentencia if más exterior, haciendo que estas dos entradas sean equivalentes:

if x then if y then gana (); else pierde;

if x then do; if y then gana (); end; else pierde;

El conflicto existe porque la gramática escrita es ambigua: en todo caso el análisis de la sentencia if simple anidada es legítima. La convención es que estas ambigüedades se resuelvan emparejando la cláusula else a la sentencia if más interior; esto es lo que Bison consigue eligiendo el desplazamiento en vez de la reducción. (Idealmente sería más adecuado escribir una gramática no ambigua, pero eso es muy duro de hacer en este caso.) Esta ambigüedad en particular se encontró en primer lugar en la especificación de Algol 60 y se denominó la ambiguedad del "balanceado del ##else##".

Para evitar advertencias de Bison a cerca de los predecibles, legítimos conflictos de desplazamiento/reducción, utilice la declaración ##%expect n##. No se producirán avisos mientras el número de conflictos de desplazamiento/reducción sea exactamente n. See section Suprimiendo Advertencias de Conflictos.

La definición de ##if_stmt## anterior es la única que se va a quejar del conflicto, pero el conflicto no aparecerá en realidad sin reglas adicionales. Aquí hay un fichero de entrada de Bison completo que manfiesta realmente el conflicto:

%token IF THEN ELSE variable
%%
stmt:     expr
	    | if_stmt
	    ;

if_stmt:
	      IF expr THEN stmt
	    | IF expr THEN stmt ELSE stmt
	    ;

expr:     variable
	    ;

===== Precedencia de Operadores =====

Otra situación en donde pararecen los conflictos desplazamiento/reducción es en las expresiones aritméticas. Aquí el desplazamiento no siempre es la resolución preferible; las declaraciones de Bison para la precedencia de operadores le permite especificar cuándo desplazar y cuando reducir.

==== Cuándo se Necesita la Precedencia ====

Considere el siguiente fragmento de gramática ambigua (ambigua porque la entrada `1 - 2 * 3' puede analizarse de dos maneras):

expr:     expr '-' expr
	    | expr '*' expr
	    | expr '&lt;' expr
	    | '(' expr ')'
	    ...
	    ;

Suponga que el analizador ha visto los tokens `1', `-' y `2'; ¿debería reducirlos por la regla del operador de adición? Esto depende del próximo token. Por supuesto, si el siguiente token es un `)', debemos reducir; el desplazamiento no es válido porque ninguna regla puede reducir la secuencia de tokens `- 2 )' o cualquier cosa que comience con eso. Pero si el próximo token es `*' o `&lt;', tenemos que elegir: ya sea el desplazamiento o la reducción permitiría al analizador terminar, pero con resultados diferentes.

Para decidir qué debería hacer Bison, debemos considerar los resultados. Si el siguiente token de operador op se desplaza, entonces este debe ser reducido primero para permitir otra oportunidad para reducir la suma. El resultado es (en efecto) `1 - (2 op 3)'. Por otro lado, si se reduce la resta antes del desplazamiento de op, el resultado es `(1 - 2) op 3'. Claramente, entonces, la elección de desplazar o reducir dependerá de la precedencia relativa de los operadores `-' y op: `*' debería desplazarse primero, pero no `&lt;'.

¿Qué hay de una entrada tal como `1 - 2 - 5'; debería ser esta `(1 - 2) - 5' o debería ser `1 - (2 - 5)'? Para la mayoría de los operadores preferimos la primera, que se denomina **asociación por la izquierda**. La última alternativa, **asociación por la derecha**, es deseable para operadores de asignación. La elección de la asociación por la izquierda o la derecha es una cuestión de qué es lo que el analizador elige si desplazar o reducir cuando la pila contenga `1 - 2' y el token de preanálisis sea `-': el desplazamiento produce asociatividad por la derecha.

==== Especificando Precedencia de Operadores ====

Bison le permite especificar estas opciones con las declaraciones de precedencia de operadores ##%left## y ##%right##. Cada una de tales declaraciones contiene una lista de tokens, que son los operadores cuya precedencia y asociatividad se está declarando. La declaración ##%left## hace que todos esos operadores sean asociativos por la izquierda y la declaración ##%right## los hace asociativos por la derecha. Una tercera alternativa es ##%nonassoc##, que declara que es un error de sintaxis encontrar el mismo operador dos veces "en un fila".

La precedencia relativa de operadores diferentes se controla por el orden en el que son declarados. La primera declaración ##%left## o ##%right## en el fichero declara los operadores cuya precedencia es la menor, la siguiente de tales declaraciones declara los operadores cuya precedencia es un poco más alta, etc.

==== Ejemplos de Precedencia ====

En nuestro ejemplo, queríamos las siguientes declaraciones:

%left '&lt;'
%left '-'
%left '*'

En un ejemplo más completo, que permita otros operadores también, los declararíamos en grupos de igual precedencia. Por ejemplo, ##'+'## se declara junto con ##'-'##:

%left '&lt;' '&gt;' '=' NE LE GE
%left '+' '-'
%left '*' '/'

(Aquí ##NE## y el resto representan los operadores para "distinto", etc. Asumimos que estos tokens son de más de un caracter de largo y por lo tanto son representados por nombres, no por caracteres literales.)

==== Cómo Funciona la Precedencia ====

El primer efecto de las declaraciones de precedencia es la asignación de niveles de precedencia a los símbolos terminales declarados. El segundo efecto es la asignación de niveles de precedencia a ciertas reglas: cada regla obtiene su precedencia del último simbolo terminal mencionado en las componentes. (También puede especificar explícitamente la precedencia de una regla. See section Precedencia Dependiente del Contexto.)

Finalmente, la resolución de conflictos funciona comparando la precendecia de la regla que está siendo considerada con la del token de preanálisis. Si la precedencia del token es más alta, la elección es desplazar. Si la precedencia de la regla es más alta, la elección es reducir. Si tienen la misma precedencia, la elección se hace en base a la asociatividad de ese nivel de precedencia. El archivo de salida amplia producido por `-v' (see section Invocando a Bison) dice cómo fue resuelto cada conflicto.

No todas las reglas y no todos los tokens tienen precedencia. Si bien la regla o el token de preanálisis no tienen precedencia, entonces por defecto de desplaza.

===== Precedencia Dependiente del Contexto =====

A menudo la precedencia de un operador depende del contexto. Esto suena raro al principio, pero realmente es muy común. Por ejemplo, un signo menos típicamente tiene una precedencia muy alta como operador unario, y una precedencia algo menor (menor que la multiplicación) como operador binario.

Las declaraciones de precedencia de Bison, ##%left##, ##%right## y ##%nonassoc##, puede utilizarse únicamente para un token dado; de manera que un token tiene sólo una precedencia declarada de esta manera. Para la precedencia dependiente del contexto, necesita utilizar un mecanismo adicional: el modifidor ##%prec## para las reglas.

El modificador ##%prec## declara la precedencia de una regla en particular especificando un símbolo terminal cuya precedencia debe utilizarse para esa regla. No es necesario por otro lado que ese símbolo aparezca en la regla. La sintaxis del modificador es:

%prec símbolo-terminal

y se escribe despúes de los componentes de la regla. Su efecto es asignar a la regla la precedencia de símbolo-terminal, imponiéndose a la precedencia que se deduciría de forma ordinaria. La precedencia de la regla alterada afecta enconces a cómo se resuelven los conflictos relacionados con esa regla (see section Precedencia de Operadores).

Aquí está cómo ##%prec## resuelve el problema del menos unario. Primero, declara una precedencia para un símbolo terminal ficticio llamada ##UMINUS##. Aquí no hay tokens de este tipo, pero el símbolo sirve para representar su precedencia:

...
%left '+' '-'
%left '*'
%left UMINUS

Ahora la precedencia de ##UMINUS## se puede utilizar en reglas específicas:

exp:    ...
	    | exp '-' exp
	    ...
	    | '-' exp %prec UMINUS

===== Estados del Analizador =====

La función ##yyparse## se implementa usando una máquina de estado finito. Los valores insertados sobre la pila no son únicamente códigos de tipos de tokens; estos representan toda la secuencia de símbolos terminales y no terminales en o cerca del tope de la pila. El estado actual colecciona toda esta información sobre la entrada anterior que es relevante para decidir qué hacer a continuación.

Cada vez que se lee un token de preanálisis, el estado actual del analizador junto con el tipo de token de preanálisis se localizan en una tabla. Esta entrada en la tabla puede decir, "Desplace el token de preanálisis." En este caso, también especifica el nuevo estado del analizador, que se pone sobre el tope de la pila del analizador. O puede decir, "Reduzca utilizando la regla número n." Esto quiere decir que un cierto número de tokens o agrupaciones se sacan de la pila, y se reemplazan por una agrupación. En otras palabras, se extrae ese número de estados de la pila, y se empuja un nuevo estado.

Hay otra alternativa: la tabla puede decir que el token de preanálisis es erróneo en el estado actual. Esto provoca que comience el procesamiento de errores (see section Recuperación de Errores).

===== Conflictos de Reducción/Reducción =====

Se produce un conflicto de reducción/reducción si hay dos o más reglas que pueden aplicarse a la misma secuencia de entrada. Esto suele indicar un error serio en la gramática.

Por ejemplo, aquí hay un intento fallido de definir una secuencia de cero o más agrupaciones de ##palabra##.

secuencia: /* vacío */
	             { printf ("secuencia vacía\n"); }
	     | posiblepalabra
	     | secuencia palabra
	             { printf ("palabra añadida %s\n", $2); }
	     ;
posiblepalabra: /* vacío */
	            { printf ("posiblepalabra vacío\n"); }
	    | palabra
	            { printf ("palabra sencilla %s\n", $1); }
	    ;

El error es una ambigüedad: hay más de una manera de analizar una ##palabra## sencilla en una ##secuencia##. Esta podría reducirse a una ##posiblepalabra## y entonces en una ##secuencia## mediante la segunda regla. Alternativamente, la cadena vacía se prodría reducir en una ##secuencia## mediante la primera regla, y esto prodría combinarse con la ##palabra## utilizando la tercera regla para ##secuencia##.

Existe también más de una manera de reducir la cadena vacía en una ##secuencia##. Esto se puede hacer directamente mediante la primera regla, o indirectamente mediante ##posiblepalabra## y entonces la segunda regla.

Podría pensar que esto es una distinción sin ninguna diferencia, porque esto no cambia si una entrada particular es válida o no. Pero sí afecta en las acciones que son ejecutadas. Una ordenación del análisis ejecuta la acción de la segunda regla; la otra ejecuta la acción de la primera regla y la acción de la tercera regla. En este ejemplo, la salida del programa cambia.

Bison resuelve un conflicto reducción/reducción eligiendo el uso de la regla que aparece en primer lugar dentro de la gramática, pero es muy arriesgado contar con esto. Cada conflicto de reducción/reducción se debe estudiar y normalmente eliminar. Aquí está la manera apropiada de definir ##secuencia##:

secuencia: /* vacío */
	             { printf ("secuencia vacía\n"); }
	     | secuencia palabra
	             { printf ("palabra añadida %s\n", $2); }
	     ;

Aquí hay otro error común que produce un conflicto reducción/reducción.

secuencia: /* vacío */
	     | secuencia palabras
	     | secuencia redirecciones
	     ;

palabras: /* vacío */
	    | palabras palabra
	    ;

redirecciones: /* vacío */
	         | redirecciones redireccion
	         ;

La intención aquí es definir una secuencia que pueda contener ya sea agrupaciones ##palabra## o ##redireccion##. Las definiciones individuales de ##secuencia##, ##palabras## y ##redirecciones## están libres de errores, pero las tres juntas producen una ambigüedad sutil: ¡incluso una entrada vacía puede analizarse en una infinidad de maneras diferentes!

Considere esto: la cadena vacía podría ser una ##palabras##. O podrían ser dos ##palabras## en una fila, o tres, o cualquier número. Podría igualmente ser una ##redirecciones##, o dos, o cualquier número. O podría ser una ##palabras## seguido de tres ##redirecciones## y otra ##palabras##. Y así sucesivamente.

Aquí hay dos maneras de corregir estas reglas. Primero, convertirlo en una secuencia de un sólo nivel:

secuencia: /* vacío */
	     | secuencia palabra
	     | secuencia redireccion
	     ;

Segundo, prevenir bien un ##palabras## o un ##redireccion## de que sea vacío:

secuencia: /* vacío */
	     | secuencia palabras
	     | secuencia redirecciones
	     ;

palabras: palabra
	    | palabras palabra
	    ;

redirecciones: redireccion
	      | redirecciones redireccion
	      ;

===== Conflictos Misteriosos de Reducción/Reducción =====

Algunas veces con los conflictos reducción/reducción puede suceder que no parezcan garantizados. Aquí hay un ejemplo:

%token ID

%%
def:    espc_param espc_return ','
	    ;
espec_param:
	         tipo
	    |    lista_nombre ':' tipo
	    ;
espec_return:
	         tipo
	    |    nombre ':' tipo
	    ;
tipo:        ID
	    ;
nombre:        ID
	    ;
lista_nombre:
	         nombre
	    |    nombre ',' lista_nombre
	    ;

Parecería que esta gramática puede ser analizada con sólo un único token de preanálisis: cuando se está leyendo un ##espc_param##, un ##ID## es un ##nombre## si le sigue una coma o un punto, o un ##tipo## si le sigue otro ##nombre##. En otras palabras, esta gramática es LR(1).

Sin embargo, Bison, como la mayoría de los generadores de analizadores sintácticos, no pueden en realidad manejar todas las gramáticas LR(1). En esta gramática, los dos contextos, aquél después de un ##ID## al principio de un ##espc_param## y también al principio de un ##espc_return##, son lo suficientemente similares para que Bison asuma que son el mismo. Estos parecen similares porque estarían activos el mismo conjunto de reglas--la regla de reducción a un ##nombre## y aquella para la reducción de ##tipo##. Bison es incapaz de determinar a ese nivel de procesamiento que las reglas requerirían diferentes tokens de preanálisis en los dos contextos, así que construye un solo estado del analizador para ambos. Combinando los dos contextos provoca un conflicto más tarde. En la terminología de los analizadores sintácticos, este suceso significa que la gramática no es LALR(1).

En general, es mejor arreglar las deficiencias que documentarlas. Pero esta deficiencia en particular es intrínsecamente difícil de arreglar; los generadores de analizadores sintácticos que pueden manejar gramáticas LR(1) son duros de escribir y tienden a producir analizadores que son muy grandes. En la práctica, Bison es más útil como es ahora.

Cuando el problema aparece, puede a veces arreglarlo identificando los dos estados del analizador que están siendo confundidos, y añadir algo para hacerlos pareceer distintos. En el ejemplo anterior, añadiendo una regla a ##espc_return## como a continuación hace que el problema desaparezca:

%token BOGUS
...
%%
...
espc_return:
	         tipo
	    |    nombre ':' tipo
	    /* Esta regla nunca se usa.  */
	    |    ID BOGUS
	    ;

Esto corrige el problema porque introduce la posibilidad de una regla activa adicional en el contexto después de ##ID## al principio de un ##espc_param##, así que los dos contextos reciben estados distinto del analizador. Siempre que el token ##BOGUS## no se genere nunca por ##yylex##, la regla adicional no podrá alterar la manera en la que la entrada es analizada.

En este ejemplo en particular, hay otra forma de resolver este problema: reescribir la regla de ##espc_return## para usar ##ID## directamente en lugar de hacerlo a través de ##nombre##. Esto también provoca que los dos contextos confusos tengan conjuntos de reglas activas distintas, porque la de ##espc_return## activa la regla alterada para ##espc_return## en vez que la de ##nombre##.

espc_param:
	         tipo
	    |    lista_nombre ':' tipo
	    ;
espc_return:
	         tipo
	    |    ID ':' tipo
	    ;

===== Desbordamiento de Pila, y Cómo Evitarlo =====

La pila del analizador de Bison puede desbordarse si se desplazan demasiados tokens y no son reducidos. Cuando esto sucede, la función del analizador ##yyparse## devuelve un valor distinto de cero, haciendo pausas solamente para llamar a ##yyerror## para informar del desbordamiento.

Definiendo la macro ##YYMAXDEPTH##, puede controlar cuán profundo puede llegar a ser la pila del analizador antes de que suceda un desbordamiento de la pila. Defina esta macro con un valor que sea un entero. Este valor es el número máximo de tokens que pueden ser desplazados (y sin ser reducidos) antes de un desbordamiento. Debe ser una expresión constante cuyo valor se conozca en tiempo de compilación.

El espacio de la pila permitido no es asignado necesariamente. Si especifica un valor grande para ##YYMAXDEPTH##, el analizador realmente asigna un pequeña pila al principio, y entonces la hace mayor por etapas a medida que se necesite. Esta asignación incremental ocurre automáticamente y silenciosamente. Por lo tanto, no necesita hacer a ##YYMAXDEPTH## angustiosamente pequeño meramente para ahorrar espacio para entradas ordinarias que no necesitan mucha pila.

El valor por defecto de ##YYMAXDEPTH##, si no lo define, es 10000.

Usted puede controlar cuánta pila se asigna inicialmente definiendo la macro ##YYINITDEPTH##. Este valor también debe ser una constante entera en tiempo de compilación. El valor por defecto es 200.

Añade una nota a tu edición que explique en qué consisten tus cambios:

Opinar
2 opiniones

BISON

HHHH

oRLANDO

Bison.

Esta bueno.

Tutoriales relacionados con 'Bison'

Características principales de Linux

Este documento proporciona una información básica sobre el sistema operativo Linux, incluyendo una explicación de... Más »

Anuncios Google

Autor y licencia de 'Bison'

Tutorial de Charles Donnelly y Richard Stallman. Extraido de: http://es.tldp.org/Manuales-LuCAS/guides/bison-guide/bison-es-1.27.html CopyLeft

Licencia GNU Free Documentation License: http://www.es.gnu.org/licencias/fdles.html

Este contenido ha sido recopilado por el equipo de Wikilearning. Todo el contenido recopilado se ha obtenido respetando y comunicando en nuestro site la licencia de cada fuente.

Wikilearning tiene permiso expreso por escrito de los autores para publicar los contenidos que ha extraído de otras webs, incluyendo su uso comercial.