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
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.
