Bison es un generador de analizadores sint�cticos de prop�sito general que convierte una descripci�n gramatical para una gram�tica independiente del contexto LALR(1) en un programa en C que analice esa gram�tica. Una vez que sea un experimentado en Bison, podr�a utilizarlo para desarollar un amplio rango de analizadores de lenguajes, desde aquellos usados en simples calculadoras de escritorio hasta complejos lenguajes de programaci�n.
Bison es compatible hacia arriba con Yacc: todas la gram�ticas escritas apropiadamente para Yacc deber�an funcionar con Bison sin ning�n cambio. Cualquiera que est� familiarizado con Yacc deber�a ser capaz de utilizar Bison con pocos problemas. Necesita ser fluente programando en C para poder utilizar Bison o para comprender este manual.
Comenzaremos con cap�tulos introductorios que explican los conceptos b�sicos del uso de Bison y muestran tres ejemplos comentados, cada uno construido sobre el anterior. Si no conoce Bison o Yacc, comience leyendo estos cap�tulos. A continuaci�n se encuentran los cap�tulos de referencia que describen los aspectos espec�ficos de Bison en detalle.
Bison fue escrito originalmente por Robert Corbett; Richard Stallman lo hizo compatible con Yacc. Wilfred Hansen de la Universidad de Carnegie Mellon a�adi� los literales de cadenas multicaracter y otras caracter�sticas.
Esta edici�n corresponde a la versi�n 1.27 de Bison.
Nota: las secciones tituladas "Licencia P�blica General GNU", "Condiciones para el uso de Bison" y el aviso de permiso son traducciones libres de las secciones originales en ingl�s "GNU General Public License", "Conditions for Using Bison" y el permiso original. Ninguna de estas traducciones ha sido aprobada por la Free Software Foundation oficialmente y se han inclu�do solamente para facilitar su entendimiento. Si desea estar seguro de si sus actuaciones est�n permitidas, por favor acuda a la versi�n original inglesa.
La Free Software Foundation recomienda fervientemente no usar estas traducciones como los t�rminos oficiales de distribuci�n para sus programas; en su lugar, por favor use las versiones inglesas originales, tal y como est�n publicadas por la Free Software Foundation.
@language=@ingles
As of Bison version 1.24, we have changed the distribution terms for
yyparse to permit using Bison's output in non-free programs.
Formerly, Bison parsers could be used only in programs that were free
software.
The other GNU programming tools, such as the GNU C compiler, have never had such a requirement. They could always be used for non-free software. The reason Bison was different was not due to a special policy decision; it resulted from applying the usual General Public License to all of the Bison source code.
The output of the Bison utility--the Bison parser file--contains a
verbatim copy of a sizable piece of Bison, which is the code for the
yyparse function. (The actions from your grammar are inserted
into this function at one point, but the rest of the function is not
changed.) When we applied the GPL terms to the code for yyparse,
the effect was to restrict the use of Bison output to free software.
We didn't change the terms because of sympathy for people who want to make software proprietary. Software should be free. But we concluded that limiting Bison's use to free software was doing little to encourage people to make other software free. So we decided to make the practical conditions for using Bison match the practical conditions for using the other GNU tools. @language=@espanol
Al igual que en la versi�n 1.24 de Bison, hemos cambiado los t�rminos de la
distribuci�n de yyparse para permitir el uso de la salida de Bison en
programas no-libres. En otro tiempo, los analizadores generados por Bison
solamente pod�an utilizarse en programas que fuesen software libre.
Las otras herramientas GNU de programaci�n, tales como el compilador de C GNU, nunca han tenido tal tipo de requisito. Estas herramientas siempre pod�an utilizarse para software no-libre. La raz�n de que con Bison fuera diferente no fue debido a una decisi�n pol�tica especial; ello result� de la aplicaci�n de la Licencia P�blica General usual a todo el c�digo fuente de Bison.
La salida de la utilidad Bison--el archivo del analizador de Bison--contiene
una copia literal de un considerable fragmento de Bison, que es el c�digo
para la funci�n yyparse. (Las acciones de tu gram�tica se insertan
dentro de esta funci�n en un punto, pero el resto de la funci�n no se
modifica.) Cuando aplicamos los t�rminos de la GPL al c�digo fuente para
yyparse, el efecto fue la restricci�n del uso de la salida de Bison en
software libre.
No cambiamos los t�rminos debido a simpat�a con la gente que quiere hacer software propietario. El software deber�a ser libre. Pero hemos concluido que limitando el uso de Bison en software libre era hacer poco por alentar a la gente a hacer otro software libre. As� que hemos decidido hacer que concuerden las condiciones pr�cticas para el uso de Bison con las condiciones pr�cticas para usar las otras utilidades GNU.
@language=@ingles Version 2, June 1991
Copyright (C) 1989, 1991 Free Software Foundation, Inc. 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed.
The licenses for most software are designed to take away your freedom to share and change it. By contrast, the GNU General Public License is intended to guarantee your freedom to share and change free software--to make sure the software is free for all its users. This General Public License applies to most of the Free Software Foundation's software and to any other program whose authors commit to using it. (Some other Free Software Foundation software is covered by the GNU Library General Public License instead.) You can apply it to your programs, too.
When we speak of free software, we are referring to freedom, not price. Our General Public Licenses are designed to make sure that you have the freedom to distribute copies of free software (and charge for this service if you wish), that you receive source code or can get it if you want it, that you can change the software or use pieces of it in new free programs; and that you know you can do these things.
To protect your rights, we need to make restrictions that forbid anyone to deny you these rights or to ask you to surrender the rights. These restrictions translate to certain responsibilities for you if you distribute copies of the software, or if you modify it.
For example, if you distribute copies of such a program, whether gratis or for a fee, you must give the recipients all the rights that you have. You must make sure that they, too, receive or can get the source code. And you must show them these terms so they know their rights.
We protect your rights with two steps: (1) copyright the software, and (2) offer you this license which gives you legal permission to copy, distribute and/or modify the software.
Also, for each author's protection and ours, we want to make certain that everyone understands that there is no warranty for this free software. If the software is modified by someone else and passed on, we want its recipients to know that what they have is not the original, so that any problems introduced by others will not reflect on the original authors' reputations.
Finally, any free program is threatened constantly by software patents. We wish to avoid the danger that redistributors of a free program will individually obtain patent licenses, in effect making the program proprietary. To prevent this, we have made it clear that any patent must be licensed for everyone's free use or not licensed at all.
The precise terms and conditions for copying, distribution and modification follow.
NO WARRANTY
If you develop a new program, and you want it to be of the greatest possible use to the public, the best way to achieve this is to make it free software which everyone can redistribute and change under these terms.
To do so, attach the following notices to the program. It is safest to attach them to the start of each source file to most effectively convey the exclusion of warranty; and each file should have at least the "copyright" line and a pointer to where the full notice is found.
one line to give the program's name and a brief idea of what it does. Copyright (C) 19yy name of author This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
Also add information on how to contact you by electronic and paper mail.
If the program is interactive, make it output a short notice like this when it starts in an interactive mode:
Gnomovision version 69, Copyright (C) 19yy name of author Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'. This is free software, and you are welcome to redistribute it under certain conditions; type `show c' for details.
The hypothetical commands `show w' and `show c' should show the appropriate parts of the General Public License. Of course, the commands you use may be called something other than `show w' and `show c'; they could even be mouse-clicks or menu items--whatever suits your program.
You should also get your employer (if you work as a programmer) or your school, if any, to sign a "copyright disclaimer" for the program, if necessary. Here is a sample; alter the names:
Yoyodyne, Inc., hereby disclaims all copyright interest in the program `Gnomovision' (which makes passes at compilers) written by James Hacker. signature of Ty Coon, 1 April 1989 Ty Coon, President of Vice
This General Public License does not permit incorporating your program into proprietary programs. If your program is a subroutine library, you may consider it more useful to permit linking proprietary applications with the library. If this is what you want to do, use the GNU Library General Public License instead of this License. @language=@espanol
Versi�n 2, Junio de 1991
Copyright (C) 1989, 1991 Free Software Foundation, Inc. 675 Mass Ave, Cambridge, MA 02139, EEUU Se permite a todo el mundo la copia y distribuci�n de copias literales de este documento de licencia, pero no se permite su modificaci�n.
Las licencias que cubren la mayor parte del software est�n dise�adas para quitarle a usted la libertad de compartirlo y modificarlo. Por el contrario, la Licencia P�blica General GNU pretende garantizarle la libertad de compartir y modificar software libre--para asegurar que el software es libre para todos sus usuarios. Esta Licencia P�blica General se aplica a la mayor parte del software de la Free Software Foundation y a cualquier otro programa cuyos autores se comprometen a utilizarla. (Alguna parte del software de la Free Software Foundation est� cubierto por la Licencia P�blica General GNU para Librer�as). Usted tambi�n la puede aplicar a sus programas.
Cuando hablamos de software libre, estamos refiri�ndonos a la libertad, no al precio. Nuestras Licencias P�blicas Generales est�n dise�adas para asegurarnos de que tenga la libertad de distribuir copias de software libre (y cobrar por ese servicio si quiere), que reciba el c�digo fuente o que pueda conseguirlo si lo quiere, que pueda modificar el software o usar fragmentos de �l en nuevos programas libres, y que sepa que puede hacer todas estas cosas.
Para proteger sus derechos necesitamos algunas restricciones que prohiban a cualquiera negarle a usted estos derechos o pedirle que renuncie a ellos. Estas restricciones se traducen en ciertas obligaciones que le afectan si distribuye copias del software, o si lo modifica.
Por ejemplo, si distribuye copias de uno de estos programas, sea gratuitamente, o a cambio de una contraprestaci�n, debe dar a los receptores todos los derechos que tiene. Debe asegurarse de que ellos tambi�n reciben, o pueden conseguir, el c�digo fuente. Y debe mostrarles estas condiciones de forma que conozcan sus derechos.
Protegemos sus derechos con la combinaci�n de dos medidas: (1) ponemos el software bajo copyright y (2) le ofrecemos esta licencia, que le da permiso legal para copiar, distribuir y/o modificar el software.
Tambi�n, para la protecci�n de cada autor y la nuestra propia, queremos asegurarnos de que todo el mundo comprende que no se proporciona ninguna garant�a para este software libre. Si el software es modificado por cualquiera y �ste a su vez lo distribuye, queremos que sus receptores sepan que lo que tienen no es el original, de forma que cualquier problema introducido por otros no afecte a la reputaci�n de los autores originales.
Por �ltimo, cualquier programa libre est� constantemente amenazado por patentes sobre el software. Queremos evitar el riesgo de que los redistribuidores de un programa libre individualmente obtengan patentes, haciendo el programa propietario a todos los efectos. Para prevenir esto, hemos dejado claro que cualquier patente debe ser concedida para el uso libre de cualquiera, o no ser concedida en absoluto.
Los t�rminos exactos y las condiciones para la copia, distribuci�n y modificaci�n se exponen a continuaci�n.
AUSENCIA DE GARANT�A
Si usted desarrolla un nuevo Programa, y quiere que sea del mayor uso posible para el p�blico en general, la mejor forma de conseguirlo es convirti�ndolo en software libre que cualquiera pueda redistribuir y cambiar bajo estos t�rminos.
Para hacerlo, a�ada los siguientes avisos al programa. Lo m�s seguro es a�adirlos al principio de cada fichero fuente para comunicar lo m�s efectivamente posible la ausencia de garant�a. Adem�s cada fichero deber�a tener al menos la l�nea de "copyright" y una indicaci�n del lugar donde se encuentra la notificaci�n completa.
una l�nea para indicar el nombre del programa y una r�pida idea de lo que hace. Copyright (C) 19aa nombre del autor Este programa es software libre; usted puede redistribuirlo y/o modificarlo bajo los t�rminos de la Licencia P�blica General GNU tal y como est� publicada por la Free Software Foundation; ya sea la versi�n 2 de la Licencia o (a su elecci�n) cualquier versi�n posterior. Este programa se distribuye con la esperanza de que sea �til, pero SIN NINGUNA GARANT�A; ni siquiera la garant�a impl�cita de COMERCIABILIDAD o APTITUD PARA UN PROP�SITO ESPEC�FICO. Vea la Licencia P�blica General GNU para m�s detalles. Usted deber�a haber recibido una copia de la Licencia P�blica General junto con este programa. Si no ha sido as�, escriba a la Free Software Foundation, Inc., en 675 Mass Ave, Cambridge, MA 02139, EEUU.
A�ada tambi�n informaci�n sobre c�mo contactar con usted mediante correo electr�nico y postal.
Si el programa es interactivo, haga que muestre un peque�o anuncio como el siguiente, cuando comience a funcionar en modo interactivo:
Gnomovision versi�n 69, Copyright (C) 19aa nombre del autor Gnomovision no ofrece ABSOLUTAMENTE NINGUNA GARANT�A; para m�s detalles escriba `show w'. Esto es software libre, y se le invita a redistribuirlo bajo ciertas condiciones. Escriba `show c' para m�s detalles.
Los comandos hipot�ticos `show w' y `show c' deber�an mostrar las partes adecuadas de la Licencia P�blica General. Por supuesto, los comandos que use pueden llamarse de cualquier otra manera. Podr�an incluso ser pulsaciones del rat�n o elementos de un men�---lo que sea apropiado para su programa).
Tambi�n deber�a conseguir que el empresario (si trabaja como programador) o su centro acad�mico, si es el caso, firme una "renuncia de copyright" para el programa, si es necesario. A continuaci�n se ofrece un ejemplo, cambie los nombres:
Yoyodyne, Inc. con la presente renuncia a cualquier inter�s de derechos de copyright con respecto al programa `Gnomovision' (que hace pasadas a compiladores) escrito por Pepe Programador. firma de Pepito Grillo, 20 de diciembre de 1996 Pepito Grillo, Presidente de Asuntillos Varios.
Esta Licencia P�blica General no permite incorporar su programa a programas propietarios. Si su programa es una librer�a de subrutinas, puede considerar m�s �til el permitir el enlazado de aplicaciones propietarias con la librer�a. Si este es el caso, use la Licencia P�blica General GNU para Librer�as en lugar de esta Licencia.
Este cap�tulo introduce muchos de los conceptos b�sicos sin los que no tendr�n sentido los detalles de Bison. Si no conoce ya c�mo utilizar Bison o Yacc, le sugerimos que comience por leer este cap�tulo atentamente.
Para que Bison analice un lenguaje, este debe ser descrito por una gram�tica independiente del contexto. Esto quiere decir que debe especificar uno o m�s grupos sint�cticos y dar reglas para contruirlos desde sus partes. Por ejemplo, en el lenguaje C, un tipo de agrupaci�n son las llamadas `expresiones'. Una regla para hacer una expresi�n ser�a, "Una expresi�n puede estar compuesta de un signo menos y otra expresi�n". Otra regla ser�a, "Una expresi�n puede ser un entero". Como puede ver, las reglas son a menudo recursivas, pero debe haber al menos una regla que lleve fuera la recursi�n.
El sistema formal m�s com�n de presentar tales reglas para ser leidas por los humanos es la Forma de Backus-Naur o "BNF", que fue desarrollada para especificar el lenguaje Algol 60. Cualquier gram�tica expresada en BNF es una gram�tica independiente del contexto. La entrada de Bison es en esencia una BNF legible por la m�quina.
No todos los lenguajes independientes del contexto pueden ser manejados por Bison, �nicamente aquellos que sean LALR(1). Brevemente, esto quiere decir que debe ser posible decir c�mo analizar cualquier porci�n de una cadena de entrada con un solo token de prean�lisis. Hablando estrictamente, esto es una descripci�n de una gram�tica LR(1), y la LALR(1) implica restricciones adicionales que son dif�ciles de explicar de manera sencilla; pero es raro en la pr�ctica real que se encuentre una gram�tica LR(1) que no sea LALR(1). See section Conflictos Misteriosos de Reducci�n/Reducci�n, para m�s informaci�n a cerca de esto.
En las reglas gramaticales formales para un lenguaje, cada tipo de unidad sint�ctica o agrupaci�n se identifica por un s�mbolo. Aquellos que son construidos agrupando construcciones m�s peque�as de acuerdo a reglas gramaticales se denominan s�mbolos no terminales; aquellos que no pueden subdividirse se denominan s�mbolos terminales o tipos de tokens. Denominamos token a un fragmento de la entrada que corresponde a un solo s�mbolo terminal, y grupo a un fragmento que corresponde a un solo s�mbolo no terminal.
Podemos utilizar el lenguaje C como ejemplo de qu� significan los s�mbolos, terminales y no terminales. Los tokens de C son los identificadores, constantes (num�ricas y cadenas de caracteres), y las diversas palabras reservadas, operadores aritm�ticos y marcas de puntuaci�n. Luego los s�mbolos terminales de una gram�tica para C incluyen `identificador', `n�mero', `cadena de caracteres', m�s un s�mbolo para cada palabra reservada, operador o marca de puntuaci�n: `if', `return', `const', `static', `int', `char', `signo-m�s', `llave-abrir', `llave-cerrar', `coma' y muchos m�s. (Estos tokens se pueden subdividir en caracteres, pero eso es una cuesti�n l�xica, no gramatical.)
Aqu� hay una funci�n simple en C subdividida en tokens:
int /* palabra reservada `int' */
cuadrado (x) /* identificador, par�ntesis-abrir */
/* identificador, par�ntesis-cerrar */
int x; /* palabra reservada `int', identificador, punto y coma */
{ /* llave-abrir */
return x * x; /* palabra reservada `return', identificador, */
/* asterisco, identificador, punto y coma */
} /* llave-cerrar */
Las agrupaciones sint�cticas de C incluyen a las expresiones, las sentencias, las declaraciones, y las definiciones de funciones. Estas se representan en la gram�tica de C por los s�mbolos no terminales `expresi�n', `sentencia', `declaraci�n' y `definici�n de funci�n'. La gram�tica completa utiliza docenas de construcciones del lenguaje adicionales, cada uno con su propio s�mbolo no terminal, de manera que exprese el significado de esos cuatro. El ejemplo anterios es la definici�n de una funci�n; contiene una declaraci�n, y una sentencia. En la sentencia, cada `x' es una expresi�n y tambi�n lo es `x * x'.
Cada s�mbolo no terminal debe poseer reglas gramaticales mostrando c�mo est�
compuesto de construcciones m�s simples. Por ejemplo, un tipo de
sentencia en C es la sentencia return; esta ser�a descrita
con una regla gramatical que interpretada informalmente ser�a as�:
Una `sentencia' puede estar compuesta de una parabra clave `return', una `expresi�n' y un `punto y coma'.
Aqu� existir�an muchas otras reglas para `sentencia', una para cada tipo de sentencia en C.
Se debe distinguir un s�mbolo no terminal como el s�mbolo especial que define una declaraci�n completa en el lenguaje. Este se denomina s�mbolo de arranque. En un compilador, este representa un programa completo. En el lenguaje C, el s�mbolo no terminal `secuencia de definiciones y declaraciones' juega este papel.
Por ejemplo, `1 + 2' es una expresi�n v�lida en C--una parte v�lida de un programa en C--pero no es v�lida como un programa en C completo. En la gram�tica independiente del contexto de C, esto se refleja en el hecho de que `expresi�n' no es el s�mbolo de arranque.
El analizador de Bison lee una secuencia de tokens como entrada, y agrupa los tokens utilizando las reglas gramaticales. Si la entrada es v�lida, el resultado final es que la secuencia de tokens entera se reduce a una sola agrupaci�n cuyo s�mbolo es el s�mbolo de arranque de la gram�tica. Si usamos una gram�tica para C, la entrada completa debe ser una `secuencia de definiciones y declaraciones'. Si no, el analizador informa de un error de sintaxis.
Una gram�tica formal es una construcci�n matem�tica. Para definir el lenguaje para Bison, debe escribir un archivo expresando la gram�tica con la sintaxis de Bison: un archivo de gram�tica de Bison. See section Archivos de Gram�tica de Bison.
Un s�mbolo no terminal en la gram�tica formal se representa en la entrada
de Bison como un identificador, similar a un identificador en C. Por
convenci�n, deber�an estar en min�sculas, tales como expr, stmt o
declaracion.
La representaci�n en Bison para un s�mbolo terminal se llama tambi�n un
tipo de token. Los tipos de tokens tambi�n se pueden representar como
identificadores al estilo de C. Por convenci�n, estos identificadores deber�an
estar en may�sculas para distinguirlos de los no terminales: por ejemplo,
INTEGER, IDENTIFICADOR, IF o RETURN. Un s�mbolo
terminal que represente una palabra clave en particular en el lenguaje deber�a
bautizarse con el nombre despu�s de pasarlo a may�sculas. El s�mbolo terminal
error se reserva para la recuperaci�n de errores.
See section S�mbolos, Terminales y No Terminales.
Un s�mbolo terminal puede representarse tambi�n como un caracter literal, al igual que una constante de caracter en C. Deber�a hacer esto siempre que un token sea simplemente un �nico caracter (par�ntesis, signo-m�s, etc.): use el mismo caracter en un literal que el s�mbolo terminal para ese token.
Una tercera forma de representar un s�mbolo terminal es con una cadena de caracteres de C conteniendo varios caracteres. See section S�mbolos, Terminales y No Terminales, para m�s informaci�n.
Las reglas gramaticales tienen tambi�n una expresi�n en la sintaxis de
Bison. Por ejemplo, aqu� est� la regla en Bison para una sentencia
return de C. El punto y coma entre comillas es un token de caracter
literal, representando parte de la sintaxis de C para la sentencia; el
punto y coma al descubierto, y los dos puntos, es puntuaci�n de Bison que se
usa en todas las reglas.
stmt: RETURN expr ';'
;
See section Sintaxis de las Reglas Gramaticales.
Una gram�tica formal selecciona tokens �nicamente por sus clasificaciones: por ejemplo, si una regla menciona el s�mbolo terminal `constante entera', quiere decir que cualquier constante entera es gramaticalmente v�lida en esa posici�n. El valor preciso de la constante es irrelevante en c�mo se analiza la entrada: si `x+4' es gramatical entonces `x+1' o `x+3989' es igualmente gramatical.
Pero el valor preciso es muy importante para lo que significa la entrada una vez que es analizada. �Un compilador es inservible si no puede distinguir entre 4, 1 y 3989 como constantes en el programa! Por lo tanto, cada token en una gram�tica de Bison tiene ambos, un tipo de token y un valor sem�ntico. See section Definiendo la Sem�ntica del Lenguaje, para detalles.
El tipo de token es un s�mbolo terminal definido en la gram�tica, tal como
INTEGER, IDENTIFICADOR o ','. Este dice todo lo que se
necesita para saber decidir d�nde podr�a aparecer v�lidamente el token y c�mo
agruparlo con los otros tokens. Las reglas gramaticales no saben nada acerca
de los tokens excepto de sus tipos.
El valor sem�ntico tiene todo el resto de informaci�n a cerca del
significado del token, tal como el valor de un entero, o el nombre de un
identificador. (Un token tal como ',' que es solo un signo de
puntuaci�n no necesita tener ning�n valor sem�ntico.)
Por ejemplo, un token de entrada podr�a clasificarse como un tipo de token
INTEGER y tener el valor sem�ntico 4. Otro token de entrada podr�a
tener el mismo tipo de token INTEGER pero valor 3989. Cuando una regla
gramatical dice que se admite un INTEGER, cualquiera de estos tokens se
acepta porque cada uno es un INTEGER. Cuando el analizador acepta el
token, este no pierde la pista del valor sem�ntico del token.
Cada agrupaci�n puede tener tambi�n un valor sem�ntico al igual que su s�mbolo no terminal. Por ejemplo, en una calculadora, una expresi�n t�picamente tiene un valor sem�ntico que es un n�mero. En un compilador para un lenguaje de programaci�n, una expresi�n t�picamente tiene un valor sem�ntico que es una estructura en �rbol describiendo el significado de la expresi�n.
Para que sea �til, un programa debe hacer algo m�s que analizar la entrada; este debe producir tambi�n alguna salida basada en la entrada. En una gram�tica de Bison, una regla gramatical puede tener una acci�n compuesta de sentencias en C. Cada vez que el analizador reconozca una correspondencia para esa regla, se ejecuta la acci�n. See section Acciones. La mayor parte del tiempo, el prop�sito de una acci�n es computar el valor sem�ntico de la construcci�n completa a partir de los valores sem�nticos de sus partes. Por ejemplo, suponga que tenemos una regla que dice que una expresi�n puede ser la suma de dos expresiones. Cuando el analizador reconozca tal suma, cada una de las subexpresiones posee un valor sem�ntico que describe c�mo fueron elaboradas. La acci�n para esta regla deber�a crear un tipo de valor similar para la expresi�n mayor que se acaba de reconocer.
Por ejemplo, he aqu� una regla que dice que una expresi�n puede ser la suma de dos subexpresiones:
expr: expr '+' expr { $$ = $1 + $3; }
;
La acci�n dice c�mo producir el valor sem�ntico de la expresi�n suma a partir de los valores de las dos subexpresiones.
Cuando ejecuta Bison, usted le da un archivo de gram�tica de Bison como entrada. La salida es un programa fuente en C que analiza el lenguaje descrito por la gram�tica. Este archivo se denomina un analizador de Bison. Tenga en cuenta que la utilidad Bison y el analizador de Bison son dos programas distintos: la utilidad Bison es un programa cuya salida es el analizador de Bison que forma parte de su programa.
El trabajo del analizador de Bison es juntar tokens en agrupaciones de acuerdo a las reglas gramaticales--por ejemplo, construir expresiones con identificadores y operadores. A medida que lo hace, este ejecuta las acciones de las reglas gramaticales que utiliza.
Los tokens provienen de una funci�n llamada el analizador l�xico
que usted debe proveer de alguna manera (por ejemplo escribi�ndola en C). El
analizador de Bison llama al analizador l�xico cada vez que quiera un
nuevo token. Este no sabe qu� hay "dentro" de los tokens (aunque sus
valores sem�nticos podr�an reflejarlo). T�picamente el analizador
l�xico construye los tokens analizando los caracteres del texto, pero
Bison no depende de ello. See section La Funcion del Analizador L�xico yylex.
El fichero del analizador de Bison es c�digo C que define una funci�n llamada
yyparse que implementa esa gram�tica. Esta funci�n no forma
un programa completo en C: debe proveer algunas funciones
adicionales. Una es el analizador l�xico. Otra es una funci�n de informe
de errores a la que el analizador llama para informar de un error. Adem�s,
un programa completo en C debe comenzar con una funci�n llamada
main; debe facilitarla, y colocar en esta una llamada a
yyparse o el analizador no ser� ejecutado nunca.
See section Interfaz del Analizador en Lenguaje C.
A parte de los nombres de tipo de token y los s�mbolos en las
acciones que escriba, todos los nombres de variable y funciones usados
en el archivo del analizador de Bison comienzan con `yy' o `YY'.
Esto incluye las funciones de interfaz tales como la funci�n del
analizador l�xico yylex, la funci�n de informe de errores
yyerror y la propia funci�n del analizador yyparse.
Esto tambi�n incluye un gran n�mero de identificadores utilizados
para uso interno. Por lo tanto, deber�a evitar utilizar identificadores
de C que comiencen con `yy' o `YY' en el archivo de la gram�tica
de Bison excepto para aquellos definidos en este manual.
El proceso real de dise�o de lenguajes utilizando Bison, desde la especificaci�n de la gram�tica hasta llegar a un compilador o int�rprete funcional, se compone de estas etapas:
yylex). Este puede
tambi�n generarse utilizando Lex, pero el uso de Lex no se trata en este
manual.
Para hacer que este c�digo fuente escrito se convierta en un programa ejecutable, debe seguir estos pasos:
El fichero de entrada para la utilidad Bison es un archivo de gramatica de Bison. La forma general de una gram�tica de Bison es la siguiente:
%{
declaraciones en C
%}
Declaraciones de Bison
%%
Reglas gramaticales
%%
C�digo C adicional
Los `%%', `%{' y `%}' son signos de puntuaci�n que aparecen en todo archivo de gram�tica de Bison para separar las secciones.
Las declaraciones en C podr�an definir tipos y variables utilizadas en
las acciones. Puede tambi�n usar comandos del preprocesador para
definir macros que se utilicen ah�, y utilizar #include para
incluir archivos de cabecera que realicen cualquiera de estas cosas.
Las declaraciones de Bison declaran los nombres de los s�mbolos terminales y no terminales, y tambi�n podr�an describir la precedencia de operadores y los tipos de datos de los valores sem�nticos de varios s�mbolos.
Las reglas gramaticales definen c�mo construir cada s�mbolo no terminal a partir de sus partes.
El c�digo C adicional puede contener cualquier c�digo C que desee
utilizar. A menudo suele ir la definici�n del analizador l�xico
yylex, m�s subrutinas invocadas por las acciones en la reglas
gramaticales. En un programa simple, todo el resto del programa puede ir aqu�.
Ahora presentaremos y explicaremos tres programas de ejemplo escritos utilizando Bison; una calculadora de notaci�n polaca inversa, una calculadora de notaci�n algebraica (infija), y una calculadora multi-funci�n. Los tres han sido comprobados bajo BSD Unix 4.3; cada uno produce una utilizable, aunque limitada, calculadora de escritorio.
Estos ejemplos son simples, pero las gram�ticas de Bison para lenguajes de programaci�n reales se escriben de la misma manera.
El primer ejemplo es el de una simple calculadora de doble precisi�n de notaci�n polaca inversa (una calculadora que utiliza operadores postfijos). Este ejemplo provee un buen punto de partida, ya que no hay problema con la precedencia de operadores. El segundo ejemplo ilustrar� c�mo se maneja la precendencia de operadores.
El c�digo fuente para esta calculadora se llama `rpcalc.y'. La extensi�n `.y' es una convenci�n utilizada para los archivos de entrada de Bison.
rpcalcAqui est�n las declaraciones de C y Bison para la calculadora de notaci�n polaca inversa. Como en C, los comentarios se colocan entre `/*...*/'.
/* Calculadora de notaci�n polaca inversa. */
%{
#define YYSTYPE double
#include <math.h>
%}
%token NUM
%% /* A continuaci�n las reglas gramaticales y las acciones */
La secci�n de declaraciones en C (see section La Secci�n de Declaraciones en C) contiene dos directivas del preprocesador.
La directiva #define define la macro YYSTYPE, de este modo
se especifica el tipo de dato de C para los valores sem�nticos de ambos,
tokens y agrupaciones (see section Tipos de Datos para Valores Sem�nticos).
El analizador de Bison utilizar� cualquier tipo que se defina
para YYSTYPE; si no lo define, por defecto es int.
Como hemos especificado double, cada token y cada expresi�n
tiene un valor asociado, que es un n�mero en punto flotante.
La directiva #include se utiliza para declarar la funci�n de
exponenciaci�n pow.
La segunda secci�n, declaraciones de Bison, provee informaci�n a Bison a cerca
de los tipos de tokens (see section La Secci�n de Declaraciones de Bison).
Cada s�mbolo terminal que no sea un caracter literal simple debe
ser declarado aqu� (Los caracteres literales simples no necesitan ser
declarados.) En este ejemplo, todos los operadores aritm�ticos se
designan por un caracter literal simple, as� que el �nico s�mbolo
terminal que necesita ser declarado es NUM, el tipo de token para
las constantes num�ricas.
rpcalcAqu� est�n las reglas gramaticales para una calculadora de notaci�n polaca inversa.
input: /* vac�o */
| input line
;
line: '\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
;
exp: NUM { $$ = $1; }
| exp exp '+' { $$ = $1 + $2; }
| exp exp '-' { $$ = $1 - $2; }
| exp exp '*' { $$ = $1 * $2; }
| exp exp '/' { $$ = $1 / $2; }
/* Exponenciaci�n */
| exp exp '^' { $$ = pow ($1, $2); }
/* Menos unario */
| exp 'n' { $$ = -$1; }
;
%%
Las agrupaciones del "lenguaje" de rpcalc definidas aqu� son la expresi�n
(con el nombre exp), la l�nea de entrada (line), y la
transcripci�n completa de la entrada (input). Cada uno de estos
s�mbolos no terminales tiene varias reglas alternativas, unidas por el
puntuador `|' que se lee como "o". Las siguientes secciones explican
lo que significan estas reglas.
La sem�ntica del lenguaje se determina por las acciones que se toman cuando una agrupaci�n es reconocida. Las acciones son el c�digo C que aparecen entre llaves. See section Acciones.
Debe especificar estas acciones en C, pero Bison facilita la forma de
pasar valores sem�nticos entre las reglas. En cada acci�n, la
pseudo-variable $$ representa el valor sem�ntico para la agrupaci�n
que la regla va a construir. El trabajo principal de la mayor�a de las
acciones es la asignaci�n de un valor para $$. Se accede al valor
sem�ntico de los componentes de la regla con $1, $2, y
as� sucesivamente.
input
Considere la definici�n de input:
input: /* vac�o */
| input line
;
Esta definici�n se interpreta as�: "Una entrada completa es o una cadena
vac�a, o una entrada completa seguida por una l�nea de entrada". Note que
"entrada completa" se define en sus propios t�rminos. Se dice que esta
definici�n es recursiva por la izquierda ya que input aparece
siempre como el s�mbolo m�s a la izquierda en la
secuencia. See section Reglas Recursivas.
La primera alternativa est� vac�a porque no hay s�mbolos entre
los dos puntos y el primer `|'; esto significa que input puede
corresponder con una cadena de entrada vac�a (sin tokens). Escribimos estas
reglas de esa manera porque es leg�timo escribir Ctrl-d despu�s de
arrancar la calculadora. Es cl�sico poner una alternativa vac�a
al principio y escribir en esta el comentario `/* vac�o */'.
La segunda alternativa de la regla (input line) maneja toda la entrada
no trivial. Esta significa, "Despu�s de leer cualquier n�mero de
l�neas, leer una m�s si es posible". La recursividad por la izquierda
convierte esta regla en un bucle. Ya que la primera alternativa concuerda
con la entrada vac�a, el bucle se puede ejecutar cero o m�s veces.
La funci�n yyparse del analizador contin�a con el procesamiento de la
entrada hasta que se encuentre con un error gramatical o el analizador diga
que no hay m�s tokens de entrada; convendremos que esto �ltimo suceder�
al final del fichero.
line
Ahora considere la definici�n de line:
line: '\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
;
La primera alternativa es un token que es un caracter de nueva-l�nea; esta
quiere decir que rpcalc acepta un l�nea en blanco (y la ignora, ya que no
hay ninguna acci�n). La segunda alternativa es una expresi�n seguida de
una l�nea nueva. Esta es la alternativa que hace que rpcalc sea �til. El
valor sem�ntico de la agrupaci�n exp es el valor de $1 porque
la exp en cuesti�n es el primer s�mbolo en la alternativa. La acci�n
imprime este valor, que es el resultado del c�lculo que solicit� el usuario.
Esta acci�n es poco com�n porque no asigna un valor a $$. Como
consecuencia, el valor sem�ntico asociado con line est� sin
inicializar (su valor ser� impredecible). Se tratar�a de un error si
ese valor se utilizara, pero nosotros no lo utilizaremos: una vez que
rpcalc haya imprimido el valor de la l�nea de entrada del usuario, ese
valor no se necesitar� m�s.
expr
La agrupaci�n exp tiene varias reglas, una para cada tipo de
expresi�n. La primera regla maneja la expresiones m�s simples: aquellas
que son solamente n�meros. La segunda maneja una expresi�n de adici�n,
que tiene el aspecto de dos expresiones seguidas de un signo m�s. La tercera
maneja la resta, y as� sucesivamente.
exp: NUM
| exp exp '+' { $$ = $1 + $2; }
| exp exp '-' { $$ = $1 - $2; }
...
;
Hemos utilizado `|' para unir las tres reglas de exp, pero
igualmente podr�amos haberlas escrito por separado:
exp: NUM ;
exp: exp exp '+' { $$ = $1 + $2; } ;
exp: exp exp '-' { $$ = $1 - $2; } ;
...
La mayor�a de las reglas tienen acciones que computan el valor de la expresi�n
en t�rminos del valor de sus componentes. Por ejemplo, en la regla de la
adici�n, $1 hace referencia al primer componenete exp y
$2 hace referencia al segundo. El tercer componente, '+',
no tiene un valor sem�ntico asociado con significado, pero si tuviese
alguno podr�a hacer referencia a este con $3. Cuando
yyparse reconoce una expresi�n de suma usando esta regla, la suma
de los valores de las dos subexpresiones producen el valor de toda la
expresi�n. See section Acciones.
Usted no tiene de dar una acci�n para cada regla. Cuando una regla no
tenga acci�n, por defecto Bison copia el valor de $1 en $$.
Esto es lo que sucede en la primera regla (la que usa NUM).
El formato mostrado aqu� es la convenci�n recomendada, pero Bison no lo requiere. Puede a�adir o cambiar todos los espacios en blanco que desee. Por ejemplo, esto:
exp : NUM | exp exp '+' {$$ = $1 + $2; } | ...
expresa lo mismo que esto:
exp: NUM
| exp exp '+' { $$ = $1 + $2; }
| ...
El �ltimo, sin embargo, es mucho m�s legible.
rpcalc
El trabajo del analizador l�xico es el an�lisis a bajo nivel: la conversi�n
de los caracteres o secuencia de caracteres en tokens. El analizador de Bison
obtiene sus tokens llamando al analizador l�xico.
See section La Funcion del Analizador L�xico yylex.
Solamente se necesita un analizador l�xico sencillo para la calculadora
RPN. Este analizador l�xico ignora los espacios en blanco y los
tabuladores, luego lee los n�meros como double y los devuelve
como tokens NUM. Cualquier otro caracter que no forme parte de un
n�mero es un token por separado. Tenga en cuenta que el c�digo del token
para un token de caracter simple es el propio caracter.
El valor de retorno de la funci�n de an�lisis l�xico es un c�digo num�rico
que representa el tipo de token. El mismo texto que se utiliz� en las reglas
de Bison para representar el tipo de token tambi�n es una expresi�n en C con el
valor num�rico del tipo. Esto funciona de dos maneras. Si el tipo de token es
un caracter literal, entonces su c�digo num�rico es el c�digo ASCII
de ese caracter; puede usar el mismo caracter literal en el analizador l�xico
para expresar el n�mero. Si el tipo de token es un identificador, ese
identificador lo define Bison como una macro en C cuya definici�n es un
n�mero apropiado. En este ejemplo, por lo tanto, NUM se convierte
en una macro para que la use yylex.
El valor sem�ntico del token (si tiene alguno) se almacena en la variable
global yylval, que es donde el analizador de Bison lo buscar�.
(El tipo de datos de C para yylval es YYSTYPE, que se defini�
al principio de la gram�tica; see section Declaraciones para rpcalc.)
Se devuelve un c�digo de tipo de token igual a cero cuando se llega al final del fichero. (Bison reconoce cualquier valor no positivo como indicador del final del fichero de entrada.)
Aqu� est� el c�digo para el analizador l�xico:
/* El analizador l�xico devuelve un n�mero en coma
flotante (double) en la pila y el token NUM, o el
caracter ASCII le�do si no es un n�mero. Ignora
todos los espacios en blanco y tabuladores,
devuelve 0 como EOF. */
#include <ctype.h>
yylex ()
{
int c;
/* ignora los espacios en blanco */
while ((c = getchar ()) == ' ' || c == '\t')
;
/* procesa n�meros */
if (c == '.' || isdigit (c))
{
ungetc (c, stdin);
scanf ("%lf", &yylval);
return NUM;
}
/* devuelve fin-de-fichero */
if (c == EOF)
return 0;
/* devuelve caracteres sencillos */
return c;
}
Para continuar acordes a este ejemplo, la funci�n de control
se mantiene escueta al m�nimo. El �nico requisito es que llame a
yyparse para comenzar el proceso de an�lisis.
main ()
{
yyparse ();
}
Cundo yyparse detecta un error de sintaxis, realiza una llamada a la
funci�n de informe de errores yyerror para que imprima un mensaje
de error (normalmente pero no siempre un "parse error"). Es cosa
del programador el proveer yyerror (see section Interfaz del Analizador en Lenguaje C), luego aqu� est� la definici�n que utilizaremos:
#include <stdio.h>
yyerror (s) /* Llamada por yyparse ante un error */
char *s;
{
printf ("%s\n", s);
}
Despu�s de que yyerror retorne, el analizador de Bison podr�a
recuperarse del error y continuar analizando si la gram�tica contiene una
regla de error apropiada (see section Recuperaci�n de Errores). De otra
manera, yyparse devolver� un valor distinto de cero. No hemos
escrito ninguna regla de error en este ejemplo, as� que una entrada no
v�lida provocar� que termine el programa de la calculadora. Este no es
el comportamiento adecuado para una calculadora real, pero es adecuado
en el primer ejemplo.
Antes de ejecutar Bison para producir un analizador, necesitamos decidir
c�mo ordenar todo en c�digo fuente en uno o m�s ficheros fuente. Para
un ejemplo tan sencillo, la manera m�s f�cil es poner todo en un archivo.
Las definiciones de yylex, yyerror y main van al final,
en la secci�n de "c�digo C adicional" del fichero.
(see section El Formato Global de una Gram�tica de Bison).
Para un proyecto m�s grande, probablemente tendr�a varios ficheros fuente, y
utilizar�a make para ordenar la recompilaci�n de estos.
Con todo el fuente en un �nico archivo, utilice el siguiente comando para convertirlo en el fichero del analizador:
bison nombre_archivo.y
En este ejemplo el archivo se llam� `rpcalc.y' (de "Reverse Polish
CALCulator", "Calculadora Polaca Inversa"). Bison produce un archivo
llamado `nombre_archivo.tab.c',
quitando el `.y' del nombre del fichero original. El fichero de salida
de Bison contiene el c�digo fuente para yyparse. Las funciones
adicionales en el fichero de entrada (yylex, yyerror y
main) se copian literalmente a la salida.
Aqu� est� la forma de compilar y ejecutar el archivo del analizador:
# Lista los archivos en el directorio actual.
% ls
rpcalc.tab.c rpcalc.y
# Compila el analizador de Bison.
# `-lm' le dice al compilador que busque la librer�a math para pow.
% cc rpcalc.tab.c -lm -o rpcalc
# Lista de nuevo los archivos.
% ls
rpcalc rpcalc.tab.c rpcalc.y
El archivo `rpcalc' contiene ahora el c�digo ejecutable. He aqu�
una sesi�n de ejemplo utilizando rpcalc.
% rpcalc 4 9 + 13 3 7 + 3 4 5 *+- -13 3 7 + 3 4 5 * + - n Note el menos unario, `n' 13 5 6 / 4 n + -3.166666667 3 4 ^ Exponenciaci�n 81 ^D Indicador de Fin-de-fichero %
calcAhora modificaremos rpcalc para que maneje operadores infijos en lugar de postfijos. La notaci�n infija trae consigo el concepto de la precedencia de operadores y la necesidad de par�ntesis anidados de profundidad arbitraria. Aqu� est� el c�digo de Bison para `calc.y', una calculadora infija de escritorio.
/* Calculadora de notaci�n infija--calc */
%{
#define YYSTYPE double
#include <math.h>
%}
/* Declaraciones de BISON */
%token NUM
%left '-' '+'
%left '*' '/'
%left NEG /* negaci�n--menos unario */
%right '^' /* exponenciaci�n */
/* A continuaci�n la gram�tica */
%%
input: /* cadena vac�a */
| input line
;
line: '\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
;
exp: NUM { $$ = $1; }
| exp '+' exp { $$ = $1 + $3; }
| exp '-' exp { $$ = $1 - $3; }
| exp '*' exp { $$ = $1 * $3; }
| exp '/' exp { $$ = $1 / $3; }
| '-' exp %prec NEG { $$ = -$2; }
| exp '^' exp { $$ = pow ($1, $3); }
| '(' exp ')' { $$ = $2; }
;
%%
Las funciones yylex, yyerror y main pueden ser
las mismas de antes.
Hay dos propiedades nuevas importantes presentadas en este c�digo.
En la segunda secci�n (declaraciones de Bison), %left declara
tipos de tokens y dice que son operadores asociativos por la izquierda.
Las declaraciones %left y %right (asociatividad por la derecha)
toma el lugar de %token que se utiliza para declarar un nombre de
tipo de token sin asociatividad. (Estos tokens son caracteres literales
simples, que de forma ordinaria no tienen que ser declarados. Los
declaramos aqu� para especificar la asociatividad.)
La precedencia de operadores se determina por el orden de l�nea
de las declaraciones; cuanto m�s alto sea el n�mero de l�nea
de la declaraci�n (esta est� m�s baja en la p�gina o en la pantalla),
m�s alta ser� la precedencia. Por tanto, la exponenciaci�n
tiene la precedencia m�s alta, el menos unario (NEG) es el
siguiente, seguido por `*' y `/', y
as� sucesivamente. See section Precedencia de Operadores.
La otra propiedad nueva importante es el %prec en la secci�n de
la gram�tica para el operador menos unario. El %prec simplemente
le dice a Bison que la regla `| '-' exp' tiene la misma precedencia
que NEG---en este caso la siguiente
a la m�s alta. See section Precedencia Dependiente del Contexto.
Aqu� hay un ejemplo de la ejecuci�n de `calc.y':
% calc 4 + 4.5 - (34/(8*3+-3)) 6.880952381 -56 + 2 -54 3 ^ 2 9
Hasta este punto, este manual no ha tratado el tema de la recuperaci�n
de errores---c�mo continuar analizando despu�s de que el analizador detecte
un error de sintaxis. Todo lo que hemos manejado es el informe de errores con
yyerror. Tenga presente que por defecto yyparse retorna
despu�s de llamar a yyerror. Esto quiere decir que una l�nea de
entrada err�nea hace que el programa de la calculadora finalice. Ahora
mostraremos c�mo rectificar esta deficiencia.
El lenguaje de Bison por s� mismo incluye la palabra reservada
error, que podr�a incluirse en las reglas de la gram�tica. En el
siguiente ejemplo esta se ha a�adido a una de las alternativas para line:
line: '\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
| error '\n' { yyerrok; }
;
Esta ampliaci�n a la gram�tica permite una recuperaci�n de errores simple
en caso de un error de an�lisis. Si se lee una expresi�n que no puede
ser evaluada, el error ser� reconocido por la tercera regla de line, y
el an�lisis continuar�. (La funci�n yyerror a�n se sigue llamando para
imprimir su mensaje tambi�n.) La acci�n ejecuta la sentencia
yyerrok, una macro definida autom�ticamente por Bison; su
significado es que la recuperaci�n de errores ha terminado
(see section Recuperaci�n de Errores). Note la diferencia entre
yyerrok y yyerror; no se trata de ninguna errata.
Esta forma de recuperaci�n de errores trata con errores sint�cticos. Existe
otro tipo de errores; por ejemplo, la divisi�n entre cero, que conlleva
una se�al de excepci�n que normalmente es fatal. Una calculadora real
debe tratar esta se�al y utilizar longjmp para retornar a main
y reanudar el an�lisis de l�neas de entrada; tambi�n tendr�a que descartar
el resto de la l�nea de entrada actual. No discutiremos esta cuesti�n
m�s all� porque no es espec�fica de los programas de Bison.
mfcalc
Ahora que se han explicado los conceptos b�sicos de Bison, es tiempo
de movernos a problemas m�s avanzados. Las calculadoras anteriores
ofrec�an solamente cinco funciones, `+', `-', `*',
`/' y `^'. Ser�a bueno tener una calculadora que
dispusiera de otras funciones matem�ticas tales como sin,
cos, etc.
Es f�cil a�adir nuevos operadores a la calculadora infija siempre que
estos sean �nicamente caracteres literales simples. El analizador l�xico
yylex pasa todos lo caracteres no num�ricos como tokens, luego
basta con nuevas reglas gramaticales para a�adir un nuevo operador. Pero
lo que queremos es algo m�s flexible: funciones incorporadas cuya
sintaxis tenga la siguiente forma:
nombre_funci�n (argumento)
Al mismo tiempo, a�adiremos memoria a la calculadora, permiti�ndole crear variables con nombre, almacenar valores en ellas, y utilizarlas m�s tarde. Aqu� hay una sesi�n de ejemplo con la calculadora multi-funci�n:
% mfcalc pi = 3.141592653589 3.1415926536 sin(pi) 0.0000000000 alpha = beta1 = 2.3 2.3000000000 alpha 2.3000000000 ln(alpha) 0.8329091229 exp(ln(beta1)) 2.3000000000 %
Note que est�n permitidas las asignaciones m�ltiples y las funciones anidadas.
mfcalcAqu� est�n las declaraciones de C y Bison para la calculadora multi-funci�n.
%{
#include <math.h> /* Para funciones matem�ticas, cos(), sin(), etc. */
#include "calc.h" /* Contiene definici�n de `symrec' */
%}
%union {
double val; /* Para devolver n�meros */
symrec *tptr; /* Para devolver punteros a la tabla de s�mbolos */
}
%token <val> NUM /* N�mero simple en doble precisi�n */
%token <tptr> VAR FNCT /* Variable y Funci�n */
%type <val> exp
%right '='
%left '-' '+'
%left '*' '/'
%left NEG /* Negaci�n--menos unario */
%right '^' /* Exponenciaci�n */
/* A continuaci�n la gram�tica */
%%
La gram�tica anterior introduce �nicamente dos nuevas propiedades del lenguaje de Bison. Estas propiedades permiten que los valores sem�nticos tengan varios tipos de datos. (see section M�s de Un Tipo de Valor).
La declaraci�n %union especifica la lista completa de tipos posibles;
esta se encuentra en lugar de la definici�n de YYSTYPE. Los tipos
permisibles son ahora double (para exp y NUM) y
puntero a entrada en la tabla de s�mbolos. See section La Colecci�n de Tipos de Valores.
Ya que ahora los valores pueden tener varios tipos, es necesario asociar
un tipo con cada s�mbolo gramatical cuyo valor sem�ntico se utilice. Estos
s�mbolos son NUM, VAR, FNCT, y exp. Sus
declaraciones aumentan con la informaci�n a cerca de su tipo de dato
(que se encuentra entre �ngulos).
La construcci�n de Bison %type se utiliza para la declaraci�n de
s�mbolos no terminales, al igual que %token se utiliza para
declarar tipos de tokens. No hemos usado %type anteriormente
porque los s�mbolos no terminales se declaran impl�citamente por las
reglas que los definen. Pero exp debe ser declarado
expl�citamente para poder especificar el tipo de su valor. See section S�mbolos No Terminales.
mfcalc
Aqu� est�n las reglas gramaticales para la calculadora multi-funci�n.
La mayor�a de ellas han sido copiadas directamente de calc; tres
reglas, aquellas que mencionan a VAR o FNCT, son nuevas.
input: /* vac�o */
| input line
;
line:
'\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
| error '\n' { yyerrok; }
;
exp: NUM { $$ = $1; }
| VAR { $$ = $1->value.var; }
| VAR '=' exp { $$ = $3; $1->value.var = $3; }
| FNCT '(' exp ')' { $$ = (*($1->value.fnctptr))($3); }
| exp '+' exp { $$ = $1 + $3; }
| exp '-' exp { $$ = $1 - $3; }
| exp '*' exp { $$ = $1 * $3; }
| exp '/' exp { $$ = $1 / $3; }
| '-' exp %prec NEG { $$ = -$2; }
| exp '^' exp { $$ = pow ($1, $3); }
| '(' exp ')' { $$ = $2; }
;
/* Fin de la gram�tica */
%%
mfcalcLa calculadora multi-funci�n requiere una tabla de s�mbolos para seguir la pista de los nombres y significado de las variables y funciones. Esto no afecta a las reglas gramaticales (excepto para las acciones) o las declaraciones de Bison, pero requiere algunas funciones de apoyo adicionales en C.
La tabla de s�mbolos de por s� contiene un lista enlazada de registros. Su definici�n, que est� contenida en la cabecera `calc.h', es la siguiente. Esta provee que, ya sean funciones o variables, sean colocadas en la tabla.
/* Tipo de datos para enlaces en la cadena de s�mbolos. */
struct symrec
{
char *name; /* nombre del s�mbolo */
int type; /* tipo del s�mbolo: bien VAR o FNCT */
union {
double var; /* valor de una VAR */
double (*fnctptr)(); /* valor de una FNCT */
} value;
struct symrec *next; /* campo de enlace */
};
typedef struct symrec symrec;
/* La tabla de s�mbolos: una cadena de `struct symrec'. */
extern symrec *sym_table;
symrec *putsym ();
symrec *getsym ();
La nueva versi�n de main incluye una llamada a init_table, una
funci�n que inicializa la tabla de s�mbolos. Aqu� est� esta, y tambi�n
init_table:
#include <stdio.h>
main ()
{
init_table ();
yyparse ();
}
yyerror (s) /* Llamada por yyparse ante un error */
char *s;
{
printf ("%s\n", s);
}
struct init
{
char *fname;
double (*fnct)();
};
struct init arith_fncts[]
= {
"sin", sin,
"cos", cos,
"atan", atan,
"ln", log,
"exp", exp,
"sqrt", sqrt,
0, 0
};
/* La tabla de s�mbolos: una cadena de `struct symrec'. */
symrec *sym_table = (symrec *)0;
init_table () /* pone las funciones aritm�ticas en una tabla. */
{
int i;
symrec *ptr;
for (i = 0; arith_fncts[i].fname != 0; i++)
{
ptr = putsym (arith_fncts[i].fname, FNCT);
ptr->value.fnctptr = arith_fncts[i].fnct;
}
}
Mediante la simple edici�n de la lista de inicializaci�n y a�adiendo los archivos de inclusi�n necesarios, puede a�adir funciones adicionales a la calculadora.
Dos funciones importantes permiten la localizaci�n e inserci�n de s�mbolos
en la tabla de s�mbolos. A la funci�n putsym se le pasa un nombre y
el tipo (VAR o FNCT) del objeto a insertar. El objeto se enlaza
por la cabeza de la lista, y devuelve un puntero al objeto. A la funci�n
getsym se le pasa el nombre del s�mbolo a localizar. Si se encuentra,
se devuelve un punteo a ese s�mbolo; en caso contrario se devuelve un cero.
symrec *
putsym (sym_name,sym_type)
char *sym_name;
int sym_type;
{
ptr = (symrec *) malloc (sizeof (symrec));
ptr->name = (char *) malloc (strlen (sym_name) + 1);
strcpy (ptr->name,sym_name);
ptr->type = sym_type;
ptr->value.var = 0; /* pone valor a 0 incluso si es fctn. */
ptr->next = (struct symrec *)sym_table;
sym_table = ptr;
return ptr;
}
symrec *
getsym (sym_name)
char *sym_name;
{
symrec *ptr;
for (ptr = sym_table; ptr != (symrec *) 0;
ptr = (symrec *)ptr->next)
if (strcmp (ptr->name,sym_name) == 0)
return ptr;
return 0;
}
La funci�n yylex debe reconocer ahora variables, valores num�ricos, y
los operadores aritm�ticos de caracter simple. Las cadenas de caracteres
alfanum�ricas que no comiencen con un d�gito son reconocidas como
variables o funciones dependiendo de lo que la tabla de s�mbolos diga
de ellas.
La cadena de caracteres se le pasa a getsym para que la localice en la
tabla de s�mbolos. Si el nombre aparece en la tabla, se devuelve a
yyparse un puntero a su localizaci�n y su tipo (VAR o
FNCT). Si no est� ya en la tabla, entonces se inserta como
VAR utilizando putsym. De nuevo, se devuelve a
yyparse un puntero y su tipo (que deber�a ser VAR).
No se necesita ning�n cambio en yylex para manejar los valores
num�ricos y los operadores aritm�ticos.
#include <ctype.h>
yylex ()
{
int c;
/* Ignora espacios en blanco, obtiene el primer caracter */
while ((c = getchar ()) == ' ' || c == '\t');
if (c == EOF)
return 0;
/* Comienza un n�mero => analiza el n�mero. */
if (c == '.' || isdigit (c))
{
ungetc (c, stdin);
scanf ("%lf", &yylval.val);
return NUM;
}
/* Comienza un identificador => lee el nombre. */
if (isalpha (c))
{
symrec *s;
static char *symbuf = 0;
static int length = 0;
int i;
/* Inicialmente hace el buffer lo suficientemente
largo para un nombre de s�mbolo de 40 caracteres. */
if (length == 0)
length = 40, symbuf = (char *)malloc (length + 1);
i = 0;
do
{
/* Si el buffer esta lleno, hacerlo mayor. */
if (i == length)
{
length *= 2;
symbuf = (char *)realloc (symbuf, length + 1);
}
/* A�adir este caracter al buffer. */
symbuf[i++] = c;
/* Obtiene otro caracter. */
c = getchar ();
}
while (c != EOF && isalnum (c));
ungetc (c, stdin);
symbuf[i] = '\0';
s = getsym (symbuf);
if (s == 0)
s = putsym (symbuf, VAR);
yylval.tptr = s;
return s->type;
}
/* Cualquier otro caracter es un token por s� mismo. */
return c;
}
Este programa es por ambos lados potente y flexible. Usted podr�a f�cilmente
a�adir nuevas funciones, y es un trabajo sencillo modificar este c�digo para
introducir tambi�n variables predefinidas tales como pi o e.
init_table para a�adir estas constantes a la tabla
de s�mbolos. Ser� mucha m�s f�cil darle a las constantes el
tipo VAR.
Bison toma como entrada la especificaci�n de una gram�tica independiente del contexto y produce una funci�n en lenguaje C que reconoce las instancias correctas de la gram�tica.
El archivo de entrada de la gram�tica de Bison tiene un nombre que finaliza por convenci�n en `.y'.
Un archivo de gram�tica de Bison tiene cuatro secciones principales, mostradas aqu� con los delimitadores apropiados:
%{
Declaraciones en C
%}
Declaraciones en Bison
%%
Reglas Gramaticales
%%
C�digo C adicional
Los comentarios encerrados entre `/* ... */' pueden aparecer en cualquiera de las secciones.
La secci�n de declaraciones en C contiene definiciones de macros
y declaraciones de funciones y variables que se utilizan en las acciones en
las reglas de la gram�tica. Estas se copian al principio del archivo del
analizador de manera que precedan la definici�n de yyparse. Puede
utlilizar `#include' para obtener las declaraciones de un archivo de
cabecera. Si no necesita ninguna declaraci�n en C, puede omitir los
delimitadores `%{' y `%}' que delimitan esta secci�n.
La secci�n de declaraciones de Bison contiene declaraciones que definen s�mbolos terminales y no terminales, especifica la precedencia, etc. En algunas gram�ticas simples puede que no necesite ninguna de las declaraciones. See section Declaraciones de Bison.
La secci�n de las reglas gramaticales contiene una o m�s reglas gramaticales, y nada m�s. See section Sintaxis de las Reglas Gramaticales.
Debe haber siempre al menos una regla gramatical, y el primer `%%' (que precede a las reglas gramaticales) no puede ser omitido nunca incluso si es la primera cosa en el fichero.
La secci�n de c�digo C adicional se copia al pie de la letra a la
salida del fichero del analizador, al igual que la secci�n de
declaraciones en C que se copia al principio. Este es el
lugar m�s conveniente para poner cualquier cosa que quiera
tener en el archivo del analizador pero que no deba venir antes
que la definici�n de yyparse. Por ejemplo, las definiciones
de yylex e yyerror
a menudo van ah�. See section Interfaz del Analizador en Lenguaje C.
Si la �ltima secci�n est� vac�a, puede omitir el `%%' que los separa de las reglas gramaticales.
El analizador de Bison en s� contiene muchas variables est�ticas cuyos nombres comienzan con `yy' y muchas macros cuyos nombres comienzan con `YY'. Es una buena idea evitar el uso de cualquiera de estos nombres (excepto aquellos documentados en este menual) en la secci�n de c�digo C adicional del archivo de la gram�tica.
Los s�mbolos en las gram�ticas de Bison representan las clasificaciones gramaticales del lenguaje.
Un s�mbolo terminal (tambi�n conocido como un tipo de token)
representa una clase de tokens equivalentes sint�cticamente. Usted utiliza
el s�mbolo en las reglas de la gram�tica para indicar que est� permitido
un token en esa clase. El s�mbolo se representa
en el analizador de Bison por un c�digo num�rico, y la funci�n
yylex devuelve un c�digo de tipo de token para indicar qu�
tipo de token se ha le�do. Usted no necesita conocer cual es el valor
del c�digo; puede utilizar el s�mbolo para representarlo.
Un s�mbolo no terminal representa una clase de agrupaciones sint�cticamente equivalentes. El nombre del s�mbolo se utiliza para escribir las reglas gramaticales. Por convenci�n, todos deber�an escribirse en min�sculas.
Los nombres de los s�mbolos pueden contener letras, d�gitos (no al principio), subrayados y puntos. Los puntos tienen sentido �nicamente en no-terminales.
Hay tres maneras de escribir s�mbolos terminales en la gram�tica:
%token. See section Nombres de Tipo de Token.
'+' es un tipo de token
de caracter. Un tipo de token de caracter no necesita ser declarado
a menos que necesite especificar el tipo de datos de su valor
sem�ntico (see section Tipos de Datos para Valores Sem�nticos),
asociatividad, o precedencia (see section Precedencia de Operadores).
Por convenci�n, un tipo de token de caracter se utiliza �nicamente
para representar un token que consista de ese caracter en particular.
De este modo, el tipo de token '+' se utiliza para representar el
caracter `+' como un token. No hay nada que obligue a seguir esta
convenci�n, pero si no lo hace, su programa ser� confuso para otros
lectores.
Todas las secuencias usuales de escape que se utilizan en caracteres literales
en C pueden ser utilizadas igualmente en Bison, pero
no debe usar el caracter nulo como un caracter literal porque
su codigo ASCII, el cero, es el c�digo que yylex devuelve
para el final de la entrada (see section Convenci�n de Llamada para yylex).
"<=" es un token de cadena
literal. Un token de cadena literal no necesita ser declarado a menos
que desee especificar el tipo de dato de su valor sem�ntico
(see section Tipos de Datos para Valores Sem�nticos), asociatividad, precedencia (see section Precedencia de Operadores).
Puede asociar el token de cadena literal con un nombre simb�lico como
un alias, utilizando la declaraci�n %token (see section Nombres de Tipo de Token).
Si no lo hace, el analizador l�xico debe recuperar el n�mero del token
para el token de cadena literal desde la tabla
yytname (see section Convenci�n de Llamada para yylex).
ADVERTENCIA: los tokens de cadena literal no funcionan en YACC.
Por convenci�n, un token de cadena literal se utiliza �nicamente para
representar un token que consiste en esa cadena en particular. As�,
deber�a utilizar el tipo de token "<=" para representar la
cadena `<=' como un token. Bison no impone esta convenci�n, pero
si se aparta de ella, la gente que lea su programa se ver� confusa.
Todas las secuencias de escape utilizadas en las cadenas de literales de
C pueden usarse igualmente en Bison. Un token de cadena literal debe contener
dos o m�s caracteres; para un token que contenga un solo caracter, utilice
un token de caracter (ver lo anterior).
El c�mo se escoge la manera de escribir un s�mbolo no tiene efecto en su significado gramatical. Esto depende �nicamente de d�nde aparece en las reglas y cu�ndo la funci�n de an�lisis sint�ctico devuelve ese s�mbolo.
El valor devuelto por yylex es siempre uno de los s�mbolos
terminlaes (� 0 para el fin de la entrada). Sea cual sea la manera en
la que escriba
el tipo de token en las reglas gramaticales, escr�bala de la misma
manera en la definici�n de yylex. El c�digo num�rico para
un tipo de token de caracter es simplemente el codigo ASCII para el
caracter, as� que yylex puede utilizar la constante id�ntica
del caracter para generar el c�digo requerido. Cada tipo de token
denominado se convierte en una macro en C en el fichero del analizador,
de manera que yylex puede utilizar el nombre para hacer referencia
al c�digo. (Esta es la raz�n por la que los puntos no tienen sentido
en los s�mbolos terminales.)
See section Convenci�n de Llamada para yylex.
Si se define yylex en un archivo aparte, debe prepararlo para que
las definiciones de las macros de los tipos de tokens est�n disponibles all�.
Utilice la opci�n `-d' cuando ejecute Bison, de esta forma se escribir�n
estas definiciones de las macros en un archivo de cabecera por separado
`nombre.tab.h' que puede incluir en los otros archivos fuente
que lo necesite. See section Invocando a Bison.
El s�mbolo error es un s�mbolo terminal reservado para la
recuperaci�n de errores (see section Recuperaci�n de Errores); no deber�a
utilizarlo para cualquier otro prop�sito. En particular, yylex
nunca deber�a devolver este valor.
Una regla gramatical de Bison tiene la siguiente forma general:
resultado: componentes...
;
donde resultado es el s�mbolo no terminal que describe esta regla y componentes son los diversos s�mbolos terminales y no terminales que est�n reunidos por esta regla (see section S�mbolos, Terminales y No Terminales).
Por ejemplo,
exp: exp '+' exp
;
dice que dos agrupaciones de tipo exp, con un token `+' en medio,
puede combinarse en una agrupaci�n mayor de tipo exp.
Los espacios en blanco en las reglas son significativos �nicamente para separar s�mbolos. Puede a�adir tantos espacios en blanco extra como desee.
Distrubu�dos en medio de los componentes pueden haber acciones que determinan la sem�ntica de la regla. Una acci�n tiene el siguiente aspecto:
{sentencias en C}
Normalmente hay una �nica acci�n que sigue a los componentes. See section Acciones.
Se pueden escribir por separado varias reglas para el mismo resultado o pueden unirse con el caracter de barra vertical `|' as�:
resultado: compoenentes-regla1...
| componentes-regla2...
...
;
Estas a�n se consideran reglas distintas incluso cuando se unen de esa manera.
Si los componentes en una regla est�n vac�os, significa que
resultado puede concordar con la cadena vac�a. Por ejemplo, aqu�
aparece c�mo definir una secuencia separada por comas de cero o m�s
agrupaciones exp:
expseq: /* vac�o */
| expseq1
;
expseq1: exp
| expseq1 ',' exp
;
Es habitual escribir el comentario `/* vac�o */' en cada regla sin componentes.
Una regla se dice recursiva cuando su no-terminal resultado aparezca tambi�n en su lado derecho. Casi todas las gram�ticas de Bison hacen uso de la recursi�n, ya que es la �nica manera de definir una secuencia de cualquier n�mero de cosas. Considere esta definici�n recursiva de una secuencia de una o m�s expresiones:
expseq1: exp
| expseq1 ',' exp
;
Puesto que en el uso recursivo de expseq1 este es el s�mbolo
situado m�s a la izquierda del lado derecho, llamaremos a esto
recursi�n por la izquierda. Por contraste, aqu� se define la
misma construcci�n utilizando recusi�n por la derecha:
expseq1: exp
| exp ',' expseq1
;
Cualquier tipo de secuencia se puede definir utilizando ya sea la recursi�n por la izquierda o recursi�n por la derecha, pero deber�a utilizar siempre recursi�n por la izquierda, porque puede analizar una secuencia de elementos sin ocupar espacio de pila. La recursi�n por la derecha utiliza espacio en la pila de Bison en proporci�n al n�mero de elementos en la secuencia, porque todos los elementos deben ser desplazados en la pila antes de que la regla pueda aplicarse incluso una �nica vez. See section El Algoritmo del Analizador de Bison, para una explicaci�n adicional a cerca de esto.
La recursi�n indirecta o mutua sucede cuando el resultado de la regla no aparece directamente en su lado derecho, pero aparece en las reglas de otros no terminales que aparecen en su lado derecho.
Por ejemplo:
expr: primario
| primario '+' primario
;
primario: constante
| '(' expr ')'
;
define dos no-terminales recursivos mutuamente, ya que cada uno hace referencia al otro.
Las reglas gramaticales para un lenguaje determinan �nicamente la sintaxis. La sem�ntica viene determinada por los valores sem�nticos asociados con varios tokens y agrupaciones, y por las acciones tomadas cuando varias agrupaciones son reconocidas.
Por ejemplo, la calculadora calcula bien porque el valor asociado con cada expresi�n es el n�mero apropiado; �sta suma correctamente porque la acci�n para la agrupaci�n `x + y' es sumar los n�meros asociados con x e y.
En un programa sencillo podr�a ser suficiente con utilizar el mismo tipo de datos para los valores sem�nticos de todas las construcciones del lenguaje. Esto fue cierto en los ejemplos de calculadora RPN e infija (see section Calculadora de Notaci�n Polaca Inversa).
Por defecto Bison utiliza el tipo int para todos los valores
sem�nticos. Para especificar alg�n otro tipo, defina YYSTYPE
como una macro, de esta manera:
#define YYSTYPE double
Esta definici�n de la macro debe ir en la secci�n de declaraciones en C del fichero de la gram�tica (see section Resumen de una Gram�tica de Bison).
En la mayor�a de los programas, necesitar� diferentes tipos de datos
para diferentes clases de tokens y agrupaciones. Por ejemplo, una
constante num�rica podr�a necesitar el tipo
int o long, mientras que una cadena constante necesita
el tipo char *, y un identificador podr�a necesitar un puntero
a la tabla de s�mbolos.
Para utilizar m�s de un tipo de datos para los valores sem�nticos en un analizador, Bison le pide dos cosas:
%union (see section La Colecci�n de Tipos de Valores).
%token
(see section Nombres de Tipo de Token) y para las agrupaciones con la
declaraci�n de Bison %type (see section S�mbolos No Terminales).
Una acci�n acompa�a a una regla sint�ctica y contiene c�digo C a ser ejecutado cada vez que se reconoce una instancia de esa regla. La tarea de la mayor�a de las acciones es computar el valor sem�ntico para la agrupaci�n construida por la regla a partir de los valores sem�nticos asociados a los tokens o agrupaciones m�s peque�as.
Una acci�n consiste en sentencias de C rodeadas por llaves, muy parecido a las sentencias compuestas en C. Se pueden situar en cualquier posici�n dentro de la regla; esta se ejecuta en esa posici�n. La mayor�a de las reglas tienen s�lo una acci�n al final de la regla, a continuaci�n de todos los componentes. Las acciones en medio de una regla son dif�ciles y se utilizan �nicamente para prop�sitos especiales (see section Acciones a Media Regla).
El c�digo C en una acci�n puede hacer referencia a los valores
sem�nticos de los componentes reconocidos por la regla con la construcci�n
$n, que hace referencia al valor de la componente n-�sima.
El valor sem�ntico para la agrupaci�n que se est� construyendo es $$.
(Bison traduce ambas construcciones en referencias a elementos de un array
cuando copia las acciones en el fichero del analizador.)
Aqu� hay un ejemplo t�pico:
exp: ...
| exp '+' exp
{ $$ = $1 + $3; }
Esta regla contruye una exp de dos agrupaciones exp m�s
peque�as conectadas por un token de signo m�s. En la acci�n, $1
y $3 hacen referencia a los valores sem�nticos de las dos
agrupaciones exp componentes, que son el primer y
tercer s�mbolo en el lado derecho de la regla. La suma se almacena
en $$ de manera que se convierte en el valor sem�ntico de
la expresi�n de adici�n reconocida por la regla. Si hubiese un
valor sem�ntico �til asociado con el token `+', deber�a
hacerse referencia con $2.
Si no especifica una acci�n para una regla, Bison suministra una por defecto:
$$ = $1. De este modo, el valor del primer s�mbolo en la regla
se convierte en el valor de la regla entera. Por supuesto, la regla por
defecto solo es v�lida si concuerdan los dos tipos de datos. No hay una regla
por defecto con significado para la regla vac�a; toda regla vac�a
debe tener una acci�n expl�cita a menos que el valor de la regla
no importe.
$n con n cero o negativo se admite para hacer referencia
a tokens o agrupaciones sobre la pila antes de aquellas que empareja la
regla actual. Esta es una pr�ctica muy arriesgada, y para utilizarla de
forma fiable debe estar seguro del contexto en el que se aplica la
regla. Aqu� hay un donde puede utilizar esto de forma fiable:
foo: expr bar '+' expr { ... }
| expr bar '-' expr { ... }
;
bar: /* vac�o */
{ previous_expr = $0; }
;
Siempre que bar se utilice solamente de la manera mostrada aqu�,
$0 siempre hace referencia a la exp que precede a bar en
la definici�n de foo.
Si ha elegido un tipo de datos �nico para los valores sem�nticos, las
construcciones $$ y $n siempre tienen ese tipo de datos.
Si ha utilizado %union para especificar una variedad de tipos de datos,
entonces debe declarar la elecci�n de entre esos tipos para cada s�mbolo
terminal y no terminal que puede tener un valor sem�ntico. Entonces
cada vez que utilice $$ o $n, su tipo de datos
se determina por el s�mbolo al que hace referencia en la regla. En este
ejemplo,
exp: ...
| exp '+' exp
{ $$ = $1 + $3; }
$1 y $3 hacen referencia a instancias de exp, de manera
que todos ellos tienen el tipo de datos declarado para el s�mbolo no terminal
exp. Si se utilizase $2, tendr�a el tipo de datos declarado para
el s�mbolo terminal '+', cualquiera que pudiese ser.
De forma alternativa, puede especificar el tipo de datos cuando se hace referencia al valor, insertando `<tipo>' despu�s del `$' al comienzo de la referencia. Por ejemplo, si ha definido los tipos como se muestra aqu�:
%union {
int tipoi;
double tipod;
}
entonces puede escribir $<tipoi>1 para hacer referencia a la
primera subunidad de la regla como un entero, o $<tipod>1 para
referirse a este como un double.
Ocasionalmente es de utilidad poner una acci�n en medio de una regla. Estas acciones se escriben como las acciones al final de la regla, pero se ejecutan antes de que el analizador llegue a reconocer los componentes que siguen.
Una acci�n en mitad de una regla puede hacer referencia a los
componentes que la preceden utilizando $n, pero
no puede hacer referencia a los componentes subsecuentes porque
esta se ejecuta antes de que sean analizados.
Las acciones en mitad de una regla por s� mismas cuentan como uno de los
componentes de la regla. Esto produce una diferencia cuando hay otra
acci�n m�s tarde en la misma regla (y normalmente hay otra al final): debe
contar las acciones junto con los s�mbolos cuando quiera saber qu� n�mero
n debe utilizar en $n.
La acci�n en la mitad de una regla puede tambi�n tener un valor sem�ntico.
La acci�n puede establecer su valor con una asignaci�n a $$, y
las acciones posteriores en la regla pueden hacer referencia al valor
utilizando $n. Ya que no hay un s�mbolo que identifique la
acci�n, no hay manera de declarar por adelantado un tipo de datos para
el valor, luego debe utilizar la construcci�n `$<...>' para
especificar un tipo de datos cada vez que haga referencia a este valor.
No hay forma de establecer el valor de toda la regla con una
acci�n en medio de la regla, porque las asignaciones a $$ no
tienen ese efecto. La �nica forma de establecer el valor para toda
la regla es con una acci�n corriente al final de la regla.
Aqu� hay un ejemplo tomado de un compilador hipot�tico, manejando
una sentencia let de la forma `let (variable)
sentencia' y sirve para crear una variable denominada
variable temporalmente durante la duraci�n de la
sentencia. Para analizar esta construcci�n, debemos poner
variable dentro de la tabla de s�mbolos mientras se analiza
sentencia, entonces se quita despu�s. Aqu� est� c�mo se hace:
stmt: LET '(' var ')'
{ $<contexto>$ = push_contexto ();
declara_variable ($3); }
stmt { $$ = $6;
pop_contexto ($<contexto>5); }
Tan pronto como `let (variable)' se haya reconocido, se
ejecuta la primera acci�n. Esta guarda una copia del contexto
sem�ntico actual (la lista de variables accesibles) como su
valor sem�ntico, utilizando la alternativa contexto de
la union de tipos de datos. Entonces llama a declara_variable
para a�adir una nueva variable a la lista. Una vez que finalice
la primera acci�n, la sentencia inmersa en stmt puede ser
analizada. Note que la acci�n en mitad de la regla es la componente
n�mero 5, as� que `stmt' es la componente n�mero 6.
Despu�s de que la sentencia inmersa se analice, su valor sem�ntico
se convierte en el valor de toda la sentencia let. Entonces el
valor sem�ntico de la acci�n del principio se utiliza para recuperar
la lista anterior de variables. Esto hace quitar la variable temporal
del let de la lista de manera que esta no parecer� que exista
mientras el resto del programa se analiza.
Tomar una acci�n antes de que la regla sea reconocida completamente a veces induce a conflictos ya que el analizador debe llegar a un an�lisis para poder ejecutar la acci�n. Por ejemplo, las dos reglas siguientes, sin acciones en medio de ellas, pueden coexistir en un analizador funcional porque el analizador puede desplazar el token de llave-abrir y ver qu� sigue antes de decidir si hay o no una declaraci�n:
compuesta: '{' declaracion sentencias '}'
| '{' sentencias '}'
;
Pero cuando a�adimos una acci�n en medio de una regla como a continuaci�n, la regla se vuelve no funcional:
compuesta: { prepararse_para_variables_locales (); }
'{' declaraciones sentencias '}'
| '{' sentencias '}'
;
Ahora el analizador se ve forzado a decidir si ejecuta la acci�n en medio de la regla cuando no ha le�do m�s alla de la llave-abrir. En otras palabras, debe decidir si utilia una regla u otra, sin informaci�n suficiente para hacerlo correctamente. (El token llave-abrir es lo que se llama el token de prean�lisis en este momento, ya que el analizador est� decidiendo a�n qu� hacer con �l. See section Tokens de Prean�lisis.)
Podr�a pensar que puede corregir el problema poniendo acciones id�nticas en las dos reglas, as�:
compuesta: { prepararse_para_variables_locales (); }
'{' declaraciones sentencias '}'
| { prepararse_para_variables_locales (); }
'{' sentencias '}'
;
Pero esto no ayuda, porque Bison no se da cuenta de que las dos acciones son id�nticas. (Bison nunca intenta comprender el c�digo C de una acci�n.)
Si la gram�tica es tal que una declaraci�n puede ser distinguida de una sentencia por el primer token (lo que es cierto en C), entonces una soluci�n que funciona es poner la acci�n despu�s de la llave-abrir, as�:
compuesta: '{' { prepararse_para_variables_locales (); }
declaraciones sentencias '}'
| '{' sentencias '}'
;
Ahora el primer token de la siguiente declaraci�n o sentencia, que en cualquier caso dir�a a Bison la regla a utilizar, puede hacerlo a�n.
Otra soluci�n es introducir la acci�n dentro de un s�mbolo no terminal que sirva como una subrutina:
subrutina: /* vac�o */
{ prepararse_para_variables_locales (); }
;
compuesta: subrutina
'{' declaraciones sentencias '}'
| subrutina
'{' sentencias '}'
;
Ahora Bison puede ejecutar la acci�n en la regla para subrutina sin
decidir qu� regla utilzar� finalmente para compuesta. Note que la
acci�n est� ahora al final de su regla. Cualquier acci�n en medio de
una regla puede convertirse en una acci�n al final de la regla de
esta manera, y esto es lo que Bison realmente hace para implementar
acciones en mitad de una regla.
La secci�n de declaraciones de Bison de una gram�tica de Bison define los s�mbolos utilizados en la formulaci�n de la gram�tica y los tipos de datos de los valores sem�nticos. See section S�mbolos, Terminales y No Terminales.
Todos los nombres de tipos de tokens (pero no los tokens de caracter literal
simple tal como '+' y '*') se deben declarar. Los s�mbolos
no terminales deben ser declarados si necesita especificar el tipo de dato
a utilizar para los valores
sem�nticos (see section M�s de Un Tipo de Valor).
La primera regla en el fichero tambi�n especifica el s�mbolo de arranque, por defecto. Si desea que otro s�mbolo sea el s�mbolo de arranque, lo debe declarar expl�citamente (see section Lenguajes y Gram�ticas independientes del Contexto).
La forma b�sica de declarar un nombre de tipo de token (s�mbolo terminal) es como sigue:
%token nombre
Bison convertir� esto es una directiva #define en
el analizador, as� que la funci�n yylex (si est� en
este fichero) puede utilizar el nombre nombre para representar
el c�digo de este tipo de token.
De forma alternativa, puede utilizar %left, %right, o
%nonassoc en lugar de %token, si desea especificar
la precedencia. See section Precedencia de Operadores.
Puede especificar expl�citamente el c�digo num�rico para un token a�adiendo un valor entero en el campo que sigue inmediatamente al nombre del token:
%token NUM 300
Es generalmente lo mejor, sin embargo, permitir a Bison elegir los c�digos num�ricos para todos los tipos de tokens. Bison autom�ticamente seleccionar� los c�digos que no provoquen conflictos unos con otros o con caracteres ASCII.
En el caso de que el tipo de la pila sea una union, debe aumentar
%token u otra declaraci�n de tokens para incluir la
opci�n de tipo de datos delimitado por
�ngulos (see section M�s de Un Tipo de Valor).
Por ejemplo:
%union { /* define el tipo de la pila */
double val;
symrec *tptr;
}
%token <val> NUM /* define el token NUM y su tipo */
Puede asociar un token de cadena literal con un nombre
de tipo de token escribiendo la cadena literal al final de la
declaraci�n %type que declare el nombre. Por ejemplo:
%token arrow "=>"
Por ejemplo, una gram�tica para el lenguaje C podr�a especificar estos nombres con los tokens de cadena literal equivalente:
%token <operator> OR "||" %token <operator> LE 134 "<=" %left OR "<="
Una vez que iguale la cadena literal y el nombre del token, puede
utilizarlo indistintamente en ulteriores declaraciones en reglas
gramaticales. La funci�n yylex puede utilizar el nombre del
token o la cadena literal para obtener el n�mero de c�digo del
tipo de token (see section Convenci�n de Llamada para yylex).
Use las declaraciones %left, %right o %nonassoc
para declarar un token y especificar su precedencia y asociatividad,
todo a la vez. Estas se llaman declaraciones de precedencia.
See section Precedencia de Operadores, para informaci�n general
a cerca de la precedencia de operadores.
La sintaxis de una declaraci�n de precedencia es la misma que
la de %token: bien
%left s�mbolos...
o
%left <tipo> s�mbolos...
Y realmente cualquiera de estas declaraciones sirve para los mismos
prop�sitos que %token. Pero adem�s, estos especifican la
asociatividad y precedencia relativa para todos los s�mbolos:
%left especifica
asociatividad por la izquierda (agrupando x con y primero) y
%right especifica asociatividad por la derecha (agrupando
y con z primero). %nonassoc especifica no asociatividad,
que significa que `x op y op z' se
considera como un error de sintaxis.
La declaraci�n %union especifica la colecci�n completa de posibles
tipos de datos para los valores sem�nticos. La palabra clave %union
viene seguida de un par de llaves conteniendo lo mismo que va dentro de una
union en C.
Por ejemplo:
%union {
double val;
symrec *tptr;
}
Esto dice que los dos tipos de alternativas son double y
symrec *. Se les ha dado los nombres val y tptr;
estos nombres se utilizan en las declaraciones de %token y
%type para tomar uno de estos tipos para un s�mbolo terminal o no
terminal (see section S�mbolos No Terminales).
Note que, a diferencia de hacer una declaraci�n de una union en C,
no se escribe un punto y coma despu�s de la llave que cierra.
Cuando utilice %union para especificar varios tipos de valores, debe
declarar el tipo de valor de cada s�mbolo no terminal para los valores
que se utilicen. Esto se hace con una declaraci�n %type, como esta:
%type <tipo> noterminal...
Aqu� noterminal es el nombre de un s�mbolo no terminal, y tipo
es el nombre dado en la %union a la alternativa que desee
(see section La Colecci�n de Tipos de Valores). Puede dar
cualquier n�mero de s�mbolos no terminales en la misma declaraci�n
%type, si tienen el mismo tipo de valor. Utilice espacios para
separar los nombres de los s�mbolos.
Puede tambi�n declarar el tipo de valor de un s�mbolo terminal. Para
hacer esto, utilice la misma construcci�n <tipo> en una
declaraci�n para el s�mbolo terminal. Todos las clases de declaraciones
de tipos permiten <tipo>.
Bison normalmente avisa si hay alg�n conflicto en la gram�tica
(see section Conflictos de Desplazamiento/Reducci�n),
pero la mayor�a de las gram�ticas reales tienen confictos
desplazamiento/reducci�n inofensivos que se resuelven de una manera
predecible y ser�an muy dif�ciles de eliminar. Es deseable suprimir los
avisos a cerca de estos conflictos a menos que el n�mero de conflictos
cambie. Puede hacer esto con la declaraci�n %expect.
La declaraci�n tiene este aspecto:
%expect n
Aqu� n es un entero decimal. La declaraci�n dice que no deben haber avisos si hay n conflictos de desplazamiento/reducci�n y ning�n conflicto reducci�n/reducci�n. Los avisos usuales se dan si hay m�s o menos conflictos, o si hay alg�n conflicto reducci�n/reducci�n.
En general, el uso de %expect implica estos pasos:
%expect. Utilice la opci�n `-v'
para obtener una lista amplia de d�nde ocurrieron los conflictos. Bison
tambi�n imprimir� el n�mero de conflictos.
%expect, copiando el n�mero n a
partir del n�mero que imprime Bison.
Ahora Bison dejar� de molestarle con los conflictos que ha comprobado, pero le avisar� de nuevo si cambia el resultado de la gram�tica con conflictos adicionales.
Bison asume por defecto que el s�mbolo de arranque para la gram�tica es
el primer no terminal que se encuentra en la secci�n de especificaci�n de
la gram�tica. El programador podr�a anular esta restricci�n con
la declaraci�n %start as�:
%start s�mbolo
Un programa reentrante es aquel que no cambia en el curso de la ejecuci�n; en otras palabras, consiste enteramente de c�digo puro (de s�lo lectura). La reentrancia es importante siempre que la ejecuci�n as�ncrona sea posible; por ejemplo, un programa no reentrante podr�a no ser seguro al ser llamado desde un gestor de se�ales. En sistemas con m�ltiples hilos de control, un programa no reentrante debe ser llamado �nicamente dentro de interbloqueos.
Normalmente, Bison genera un analizador que no es reentrante. Esto es
apropiado para la mayoria de los casos, y permite la compatibilidad
con YACC. (Los interfaces estandares de YACC son inherentemente no
reentrantes, porque utilizan variables asignadas est�ticamente para la
comunicaci�n con yylex, incluyendo yylval y
yylloc.)
Por otra parte, puede generar un analizador puro, reentrante. La
declaraci�n de Bison %pure_parser dice que desea que el
analizador sea reentrante. Esta aparece as�:
%pure_parser
El resultado es que las variables de comunicaci�n yylval y
yylloc se convierten en variables locales en yyparse, y se
utiliza una convenci�n de llamada diferente para la funci�n del
analizador l�xico yylex. See section Convenciones de Llamada para Analizadores Puros, para los detalles a cerca de esto. La
variable yynerrs tambi�n se convierte en local en yyparse
(see section La Funci�n de Informe de Errores yyerror).
La convenci�n para llamar a yyparse no cambia.
Que el analizador sea o no puro no depende de las reglas gramaticales. Puede generar indistintamente un analizador puro o un analizador no reentrante a partir de cualquier gram�tica v�lida.
Aqu� hay un sumario de todas las declaraciones de Bison:
%union
%token
%right
%left
%nonassoc
%type
%start
%expect
%pure_parser
%no_lines
#line del proprocesador en el
fichero del analizador. Normalmente Bison escribe estos comandos
en el archivo del analizador de manera que el compilador de C y
los depuradores asociar�n los errores y el c�digo objeto con
su archivo fuente (el archivo de la gram�tica). Esta directiva
provoca que asocien los errores con el archivo del analizador, trat�ndolo
como un archivo fuente independiente por derecho propio.
%raw
%token_table
yytname; yytname[i] es el nombre
del token cuyo n�mero de c�digo de token interno de Bison es i. Los
primeros tres elementos de yytname son siempre "$",
"error", e "$illegal"; despu�s de estos vienen los s�mbolos
definidos en el archivo de la gram�tica.
Para tokens de caracter literal y tokens de cadena literal, el
nombre en la tabla incluye los caracteres entre comillas simples o dobles:
por ejemplo, "'+'" es un literal de caracter simple y "\"<=\""
es un token de cadena literal. Todos los caracteres del token de cadena
literal aparecen textualmente en la cadena encontrada en la tabla; incluso
los caracteres de comillas-dobles no son traducidos. Por ejemplo, si el token
consiste de tres caracteres `*"*', su cadena en yytname
contiene `"*"*"'. (En C, eso se escribir�a como "\"*\"*\"").
Cuando especifique %token_table, Bison tambi�n generar� definiciones
para las macros YYNTOKENS, YYNNTS, y YYNRULES y
YYNSTATES;
YYNTOKENS
YYNNTS
YYNRULES
YYNSTATES
La mayor�a de los programa que usan Bison analizan s�lo un lenguaje
y por lo tanto contienen s�lo un analizador de Bison. Pero , �qu� pasa
si desea analizar m�s de un lenguaje con el mismo programa? Entonces
necesita evitar un conflicto de nombres entre diferentes definiciones
de yyparse, yylval, etc.
La manera m�s f�cil de hacer esto es utilizar la opci�n `-p prefijo' (see section Invocando a Bison). Esta renombra las funciones de interfaz y variables del analizador de Bison para comenzar con prefijo en lugar de `yy'. Puede utilizarlo para darle a cada analizador nombres diferentes que no provoquen conflicto.
La lista precisa de s�mbolos renombrados es yyparse, yylex,
yyerror, yynerrs, yylval, yychar e
yydebug. Por ejemplo, si utiliza `-p c', los nombres se convierten
em cparse, clex, etc.
El resto de las variables y macros asociadas con Bison no se
renombran. Estas otras no son globales. Por ejemplo, YYSTYPE no se
renombra, pero definirla de diferente forma en analizadores diferentes
no provoca confusi�n (see section Tipos de Datos para Valores Sem�nticos).
La opci�n `-p' funciona a�adiendo definiciones de macros al comienzo
del archivo fuente del analizador, definiendo yyparse como
prefijoparse, etc. Esto sustituye efectivamente un nombre
por el otro en todo el fichero del analizador.
El analizador de Bison es en realidad una funci�n en C llamada yyparse.
Aqu� describimos las convenciones de interfaz de yyparse y las otras
funciones que �ste necesita usar.
Tenga en cuenta que el analizador utiliza muchos identificadores en C comenzando con `yy' e `YY' para prop�sito interno. Si utiliza tales identificadores (a parte de aquellos en este manual) en una acci�n o en codigo C adicional en el archivo de la gram�tica, es probable que se encuentre con problemas.
yyparse
Se llama a la funci�n yyparse para hacer que el an�lisis
comience. Esta funci�n lee tokens, ejecuta acciones, y por �ltimo
retorna cuando se encuentre con el final del fichero o un error de
sintaxis del que no puede recuperarse. Usted puede tambi�n escribir
acciones que ordenen a yyparse retornar inmediatamente
sin leer m�s all�.
El valor devuelto por yyparse es 0 si el an�lisis tuvo �xito
(el retorno se debe al final del fichero).
El valor es 1 si el an�lisis fall� (el retorno es debido a un error de sintaxis).
En una acci�n, puede provocar el retorno inmediato de yyparse
utilizando estas macros:
YYACCEPT
YYABORT
yylex
La funci�n del analizador l�xico, yylex, reconoce tokens
desde el flujo de entrada y se los devuelve al analizador. Bison no crea
esta funci�n autom�ticamente; usted debe escribirla de manera que
yyparse pueda llamarla. A veces se hace referencia a la funci�n como
el scanner l�xico.
En programas simples, yylex se define a menudo al final del archivo
de la gram�tica de Bison. Si yylex se define en un archivo fuente
por separado, necesitar� que las definiciones de las macros de tipos de
tokens est�n disponibles ah�. Para hecer esto, utilice la opci�n `-d'
cuando ejecute Bison, de manera que �ste escribir� esas definiciones de macros
en un archivo de cabecera por separado
`nombre.tab.h' que puede incluir en otros ficheros fuente que lo
necesiten. See section Invocando a Bison.
yylex
El valor que yylex devuelve debe ser un c�digo num�rico para el
tipo de token que se ha encontrado, o 0 para el final de la entrada.
Cuando se hace referencia a un token en las reglas gramaticales con
un nombre, ese nombre en el archivo del analizador se convierte en una
macro de C cuya definici�n es el valor num�rico apropiado para
ese tipo de token. De esta manera yylex puede utilizar el
nombre para indicar ese tipo. See section S�mbolos, Terminales y No Terminales.
Cuando se hace referencia a un token en las reglas gramaticales por un
caracter literal, el c�digo num�rico para ese caracter tambi�n es el c�digo
para el tipo de token. As� yylex puede simplemente devolver ese
c�digo de caracer. El caracter nulo no debe utilizarse de esta manera,
porque su c�digo es el cero y eso es lo que simboliza el final de la entrada.
Aqu� hay un ejemplo mostrando estas cosas:
yylex ()
{
...
if (c == EOF) /* Detecta el fin de fichero. */
return 0;
...
if (c == '+' || c == '-')
return c; /* Asume que el tipo de token para `+' es '+'. */
...
return INT; /* Devuelve el tipo del token. */
...
}
Este interfaz se ha dise�ado para que la salida de la utilidad
lex pueda utilizarse sin cambios como definici�n de yylex.
Si la gram�tica utiliza tokens de cadena literal, hay dos maneras
por las que yylex puede determianr los c�digos de tipo de token
para estos:
yylex puede utilizar estos
nombres simb�licos como los dem�s. En este caso, el uso de tokens de
cadena literal en el archivo de la gram�tica no tiene efecto sobre
yylex.
yylex puede encontrar el token multi-caracter en la tabla
yytname. El �ndice del token en la tabla es el c�digo del
tipo de token. El nombre de un token multi-caracter se almacena
en yytname con una comilla doble, los caracteres del token, y otra
comilla doble. Los caracteres del token no son traducidos de ninguna
forma; ellos aparecen textualmente en el contenido de la cadena
dentro de la tabla.
Aqu� est� el c�digo para localizar un token en yytname, asumiendo
que los caracteres del token se almacenan en token_buffer.
for (i = 0; i < YYNTOKENS; i++)
{
if (yytname[i] != 0
&& yytname[i][0] == '"'
&& strncmp (yytname[i] + 1, token_buffer,
strlen (token_buffer))
&& yytname[i][strlen (token_buffer) + 1] == '"'
&& yytname[i][strlen (token_buffer) + 2] == 0)
break;
}
La tabla yytname se genera s�lo si se utiliza la declaraci�n
%token_table. See section Sumario de Declaraciones de Bison.
En un analizador ordinario (no reentrante), los valores sem�nticos del
token deben almacenarse en la variable global yylval. Cuando est�
usando un solo tipo de valores sem�nticos, yylval tiene ese tipo.
As�, si el tipo es int (por defecto), podr�a escribir esto en
yylex:
... yylval = valor; /* Pone valor en la pila de Bison. */ return INT; /* Devuelve el tipo del token. */ ...
Cuando est� utilizando varios tipos de datos, el tipo de yylval es una
union compuesta a partir de la declaraci�n
%union (see section La Colecci�n de Tipos de Valores).
As� cuando almacene un valor de token, debe utilizar el miembro
apropiado de la union. Si la declaraci�n %union tiene el
siguiente aspecto:
%union {
int intval;
double val;
symrec *tptr;
}
entonces el c�digo en yylex podr�a ser as�:
... yylval.intval = valor; /* Pone el valor en la pila de Bison. */ return INT; /* Devuelve el tipo del token. */ ...
Si est� usando la propiedad `@n' (see section Propiedades Especiales para su Uso en Acciones) en
acciones para seguir la pista de las posiciones en el texto de los tokens
y agrupaciones, entonces debe proveer esta informaci�n en yylex. La
funci�n yyparse espera encontrar la posici�n en el texto de
un token que se acaba de analizar en la variable global yylloc.
Por ello yylex debe almacenar el dato apropiado en esa variable.
El valor de yylloc es una estructura y solo tiene que inicializar
los miembros que vayan a ser utilizados por las acciones. Los cuatro
miembros se denominan first_line, first_column,
last_line y last_column (1). Note que el
uso de estas caracter�sticas hacen al analizador notablemente m�s lento.
El tipo de dato de yylloc tiene el nombre YYLTYPE.
Cuando utilice la declaraci�n %pure_parser para solicitar un
analizador puro, reentrante, las variables globales de comunicaci�n
yylval y yylloc no pueden usarse. (See section Un Analizador Puro (Reentrante).)
En tales analizadores las dos variables globales se reemplazan
por punteros pasados como par�metros a yylex. Debe declararlos
como se muestra aqu�, y pasar la informaci�n de nuevo almacen�ndola
a trav�s de esos punteros.
yylex (lvalp, llocp)
YYSTYPE *lvalp;
YYLTYPE *llocp;
{
...
*lvalp = valor; /* Pone el valor en la pila de Bison. */
return INT; /* Devolver el tipo del token. */
...
}
Si el archivo de la gram�tica no utiliza la construcci�n `@' para
hacer referencia a las posiciones del texto, entonces el tipo YYLTYPE
no ser� definido. En este caso, omitir el segundo argumento; yylex
ser� llamado con solo un argumento.
Si utiliza un analizador reentrante, puede opcionalmente pasar
informaci�n de par�metros adicional de forma reentrante. Para hacerlo,
defina la macro YYPARSE_PARAM como un nombre de variable. Esto
modifica la funci�n yyparse para que acepte un argumento, de tipo
void *, con ese nombre.
Cuando llame a yyparse, pase la direcci�n de un objeto, haciendo
una conversi�n de tipos de la direcci�n a void *. Las acciones
gramaticales pueden hacer referencia al contenido del objeto haciendo
una conversi�n del valor del puntero a su tipo apropiado y entonces
derreferenci�ndolo. Aqu� hay un ejemplo. Escriba esto en el analizador:
%{
struct parser_control
{
int nastiness;
int randomness;
};
#define YYPARSE_PARAM parm
%}
Entonces llame al analizador de esta manera:
struct parser_control
{
int nastiness;
int randomness;
};
...
{
struct parser_control foo;
... /* Almacena los datos apropiados en foo. */
value = yyparse ((void *) &foo);
...
}
En las acciones gramaticales, utilice expresiones como �sta para hacer referencia a los datos:
((struct parser_control *) parm)->randomness
Si desea pasar los datos de par�metros adicionales a yylex,
defina la macro YYLEX_PARAM como YYPARSE_PARAM, tal
como se muestra aqu�:
%{
struct parser_control
{
int nastiness;
int randomness;
};
#define YYPARSE_PARAM parm
#define YYLEX_PARAM parm
%}
Deber�a entonces definir yylex para que acepte un argumento
adicional--el valor de parm. (Este hace uno o tres argumentos
en total, dependiendo de si se le pasa un argumento de tipo YYLTYPE.)
Puede declarar el argumento como un puntero al tipo de objeto apropiado, o
puede declararlo como void * y acceder al contenido como se mostr� antes.
Puede utilizar `%pure_parser' para solicitar un analizador reentrante
sin usar tambi�n YYPARSE_PARAM. Entonces deber�a llamar a
yyparse sin argumentos, como es usual.
yyerror
El analizador de Bison detecta un error de an�lisis o error
de sintaxis siempre que lea un token que no puede satisfacer ninguna
regla sint�ctica. Una acci�n en la gram�tica puede tambi�n
expl�citamente declarar un error, utilizando la macro
YYERROR (see section Propiedades Especiales para su Uso en Acciones).
El analizador de Bison espera advertir del error llamando a una
funci�n de informe de errores denominada yyerror, que se debe
proveer. Esta es llamada por yyparse siempre que encuentre
un error sint�ctico, y �sta recibe un argumento. Para un error de
an�lisis, la cadena normalmente es "parse error".
Si define la macro YYERROR_VERBOSE en la secci�n de
declaraciones de Bison (see section La Secci�n de Declaraciones de Bison),
entonces Bison facilita una cadena de mensaje de error mas locuaz y espec�fica
que el simple "parse error". No importa qu� definiciones
utilice para YYERROR_VERBOSE, si ya lo define.
El analizador puede detectar otro tipo de error: desbordamiento de pila. Esto
sucede cuando la entrada contiene construcciones que son profundamente
anidadas. No parece que vaya a encontrarse con esto, ya que el analizador
de Bison extiende su pila autom�ticamente hasta un l�mite muy largo. Pero
si el desbordamiento sucede, yyparse llama a yyerror de la
manera usual, excepto que la cadena del argumento es "parser stack
overflow".
La siguiente definici�n es suficiente para programas simples:
yyerror (s)
char *s;
{
fprintf (stderr, "%s\n", s);
}
Despu�s yyerror retorna a yyparse, este �ltimo intentar�
la recuperaci�n de errores si ha escrito reglas gramaticales de recuperaci�n
de errores apropiadas (see section Recuperaci�n de Errores).
Si la recuperaci�n es imposible, yyparse devolver� inmediatamente un 1.
La variable yynerrs contiene el n�mero de errores sint�cticos
hasta ahora. Normalmente esta variable es global; pero si solicita un
analizador puro (see section Un Analizador Puro (Reentrante))
entonces es una variable local a la que s�lo las acciones pueden acceder.
Aqu� hay una tabla de construcciones, variables y macros que son �tiles en las acciones.
$$ pero especifica la alternativa alttipo en la
union especificada por la declaraci�n
%union. See section Tipos de Datos de Valores en Acciones.
$n pero especifica la alternativa alttipo
en la union especificada por la declaraci�n %union.
See section Tipos de Datos de Valores en Acciones.
yyparse, indicando fallo.
See section La Funci�n del Analizador yyparse.
yyparse, indicando �xito.
See section La Funci�n del Analizador yyparse.
yychar cuando no hay un token
de prean�lisis.
yyerror, y no imprime
ning�n mensaje. Si quiere que imprima un mensaje de error, llame
a yyerror expl�citamente antes de la sentencia `YYERROR'.
See section Recuperaci�n de Errores.
yyparse.)
Cuando no hay un token de prean�lisis, el valor de YYEMPTY se
almacena en la variable. See section Tokens de Prean�lisis.
struct {
int first_line, last_line;
int first_column, last_column;
};
De esta manera, para obtener el n�mero de l�nea de comienzo del tercer
componente, utilizar�a `@3.first_line'.
Para que los miembros de esta estructura contengan informaci�n v�lida,
debe hacer que yylex facilite esta informaci�n para cada token.
Si solo necesita de ciertos miembros, entonces yylex necesita
�nicamente rellenar esos miembros.
El uso de esta caracter�stica hace al analizador notablemente
m�s lento.
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.
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.
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
;
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.
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 '<' 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 `<', 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 `<'.
�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.
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.
En nuestro ejemplo, quer�amos las siguientes declaraciones:
%left '<' %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 '<' '>' '=' 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.)
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.
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
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).
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
;
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
;
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.
Normalmente no es aceptable que un programa termine ante un error de an�lisis. Por ejemplo, un compilador deber�a recuperarse lo suficiente como para que analice el resto del archivo de entrada y comprobar sus errores; una calculadora deber�a aceptar otra expresi�n.
En un analizador de comandos interactivo sencillo donde cada entrada es
una l�nea, podr�a ser suficiente con permitir a yyparse devolver
un 1 ante un error y hacer que la funci�n invocadora ignore el resto de
la l�nea de entrada cuando suceda (y entonces llamar a yyparse de
nuevo). Pero esto es inadecuado para un compilador, porque olvida todo el
contexto sint�ctico desde el comienzo hasta donde se encontr� el error.
Un error de sintaxis profundo dentro de una funci�n del fichero de entrada
del compilador no deber�a provocar que el compilador trate la l�nea
siguiente como el principio de un fichero fuente.
Puede definir c�mo recuperarse de un error de sintaxis escribiendo
reglas para reconocer el token especial error. Este es un s�mbolo
terminal que siempre se define (no necesita declararlo) y reservado para
tratamiento de errores. El analizador de Bison genera un token error
siempre que ocurra un error de sintaxis; si ha facilitado una regla que
reconozca este token en el contexto actual, el analizador puede continuar.
Por ejemplo:
stmnts: /* cadena vac�a */
| stmnts '\n'
| stmnts exp '\n'
| stmnts error '\n'
La cuarta regla en este ejemplo dice que un error seguido de una nueva
l�nea forma una adici�n v�lida a cualquier stmnts.
�Qu� sucede si aparece un error de sintaxis en medio de una exp? La
regla de recuperaci�n de errores, interpretada estrictamente, se aplica
a la secuencia precisa de una stmnts, un error y una nueva
l�nea. Si aparece un error en medio de una exp, probablemente
existan tokens adicionales y subexpresiones por leer antes de la nueva l�nea.
De manera que la regla no es aplicable de la forma habitual.
Pero Bison puede forzar la situaci�n para que se ajuste a la regla,
descartando parte del contexto sem�ntico y parte de la entrada.
Primero descarta estados y objetos de la pila hasta que regrese a un
estado en el que el token error sea aceptable. (Esto quiere decir
que las subexpresiones ya analizadas son descartadas, retrocediendo
hasta el �ltimo stmnts completo.) En este punto el token
error puede desplazarse. Entonces, si el antiguo token
de prean�lisis no es aceptable para ser desplazado, el analizador
lee tokens y los descarta hasta que encuentre un token que sea
aceptable. En este ejemplo, Bison lee y descarta entrada hasta la
siguiente l�nea de manera que la cuarta regla puede aplicarse.
La elecci�n de reglas de error en la gram�tica es una elecci�n de estrategias para la recuperaci�n de errores. Una estrategia simple y �til es sencillamente saltarse el resto de la l�nea de entrada actual o de la sentencia actual si se detecta un error:
stmnt: error ';' /* ante un error, saltar hasta que se lea ';' */
Tambi�n es �til recuperar el delimitador de cierre que empareja con un un delimitador de apertura que ya ha sido analizado. De otra manera el delimitador de cierre probablemente aparecer� como sin emparejar, y generar� otro, esp�reo mensaje de error:
primary: '(' expr ')'
| '(' error ')'
...
;
Las estrategias de recuperaci�n de errores son por fuerza adivinanzas.
Cuando estas adivinan mal, un error de sintaxis a menudo provoca otro.
En el ejemplo anterior, la regla de recuperaci�n de errores sospecha que
el error es debido a una mala entrada en un stmnt. Suponga que
en su lugar se inserta un punto y coma accidental en medio de un stmt
v�lido. Despu�s de recuperarse del primer error con la regla de
recuperaci�n de errores, se encontrar� otro error de sintaxis directamente,
ya que el texto que sigue al punto y coma accidental tambi�n es una
stmnt inv�lida.
Para prevenir una cascada de mensajes de error, el analizador no mostrar� mensajes de error para otro error de sintaxis que ocurra poco despu�s del primero; solamente despu�s de que se hayan desplazado con �xito tres tokens de entrada consecutivos se reanudar�n los mensajes de error.
Note que las reglas que aceptan el token error podr�an tener
acciones, al igual que cualquiera de las otras reglas pueden tenerlas.
Puede hacer que los mensajes de error se reanuden inmediatamente
usando la macro yyerrok en una acci�n. Si lo hace en
la acci�n de la regla de error, no se suprimir� ning�n mensaje
de error. Esta macro no requiere ning�n argumento;
`yyerrok;' es una sentencia v�lida de C.
El token de prean�lisis anterior se reanaliza inmediatamente despu�s de un
error. Si este no es aceptable, entonces la macro yyclearin podr�a
utilizarse para limpiar ese token. Escriba la sentencia
`yyclearin;' en la acci�n de la regla de error.
Por ejemplo, suponga que ante un error de an�lisis, se llama a una rutina de manejo de errores que avanza el flujo de entrada en alg�n punto donde el an�lisis prodr�a comenzar de nuevo. El pr�ximo s�mbolo devuelto por el analizador l�xico ser� probablemente correcto. El token de prean�lisis anterior convendr�a que se descartara con `yyclearin;'.
La macro YYRECOVERING representa una expresi�n que tiene
el valor 1 cuando el analizador se est� recuperando de un error
de sintaxis, y 0 durante el resto del tiempo. Un valor de 1 indica
que actualmente los mensajes de error se est�n suprimiendo para
nuevos errores de sintaxis.
El paradigma de Bison es analizar tokens en primer lugar, entonces agruparlos en unidades sint�cticas m�s grandes. En muchos lenguajes, el significado de un token se ve afectado por su contexto. A pesar de que esto viola el paradigma de Bison, ciertas t�cnicas (conocidas como kludges) podr�an permitirle escribir analizadores de Bison para tales lenguajes.
(Realmente, "kludge" significa cualquier t�cnica que hace su trabajo pero no de una manera limpia o robusta.)
El lenguaje C tiene una dependencia del contexto: la manera en la que se utiliza un identificador depende de cu�l es su significado. Por ejemplo, considere esto:
foo (x);
Esto parece la sentencia de llamada a una funci�n, pero si foo es
un nombre de tipo definido, entonces esto realmente es una declaraci�n
de x. �C�mo puede un analizador de Bison para C decidirse
c�mo analizar esta entrada?
El m�todo utilizado en GNU C es tener dos tipos diferentes
de tokens, IDENTIFIER y TYPENAME. Cuando yylex
encuentre un identificador, localiza la declaraci�n actual del identificador
para decidir que tipo de token devolver: TYPENAME si el identificador
se declara como una definici�n de tipo, IDENTIFIER en otro caso.
Las reglas gramaticales pueden entonces expresar la dependencia del contexto
eligiendo el tipo de token a reconocer. IDENTIFIER se acepta
como una expresi�n, pero TYPENAME no lo es. TYPENAME puede
empezar una declaraci�n, pero TYPENAME no. En contextos donde el
significado del identificador no es significativo, tal como en
declaraciones que pueden ocultar nombre de definici�n de tipo, no se
acepta ni TYPENAME o IDENTIFIER---hay una regla para cada
uno de los dos tipos de tokens.
Esta t�cnica es sencilla de usar si la decisi�n de qu� tipos de identificadores se permiten se hace en un lugar cercano a donde se analiza el identificador. Pero en C esto no es siempre as�: C permite en una declaraci�n redeclarar un nombre de tipo definido siempre que se haya especificado antes un tipo expl�cito:
typedef int foo, bar, lose; static foo (bar); /* redeclarabarcomo variable est�tica */ static int foo (lose); /* redeclarafoocomo funci�n */
Por desgracia, el nombre que se est� declarando se encuentra separado de la construcci�n de la declaraci�n por una estructura sint�ctica complicada--el "declarador".
Como resultado, la parte del analizador de Bison para C necesita ser duplicada, con todos los nombres de los no terminales cambiados: una vez para el an�lisis de una declaraci�n en la que se puede redefinir un nombre de declaraci�n de tipo, y una vez para el an�lisis de una declaraci�n en la que no puede hacerse. Aqu� hay parte de la duplicaci�n, con las acciones omitidas por brevedad:
initdcl:
declarator maybeasm '='
init
| declarator maybeasm
;
notype_initdcl:
notype_declarator maybeasm '='
init
| notype_declarator maybeasm
;
Aqu� initdcl puede redeclarar un nombre de definici�n de tipo, pero
notype_initdcl no puede. La distinci�n entre declarator y
notype_declarator es del mismo tipo.
Hay aqu� alguna similitud entre esta t�cnica y una ligadura l�xica (descrita a continuaci�n), en que la informaci�n que altera el an�lisis l�xico se cambia durante el an�lisis por otras partes del programa. La diferencia es que aqu� la informaci�n es global, y se utiliza para otros prop�sitos en el programa. Una verdadera ligadura l�xica tiene una bandera de prop�sito especial controlada por el contexto sint�ctico.
Una manera de manejar las dependencias del contexto es la ligadura l�xica: una bandera que se activa en acciones de Bison, cuyo prop�sito es alterar la manera en la que se analizan los tokens.
Por ejemplo, soponga que tenemos un lenguaje vagamente parecido a C, pero
con una construcci�n especial `hex (hex-expr)'. Despu�s de
la palabra clave hex viene una expresi�n entre par�ntesis en el
que todos los enteros son hexadecimales. En particular, el token `a1b'
debe tratarse como un entero en lugar de como un identificador si aparece
en ese contexto. He aqu� c�mo puede hacerlo:
%{
int hexflag;
%}
%%
...
expr: IDENTIFIER
| constant
| HEX '('
{ hexflag = 1; }
expr ')'
{ hexflag = 0;
$$ = $4; }
| expr '+' expr
{ $$ = make_sum ($1, $3); }
...
;
constant:
INTEGER
| STRING
;
Aqu� asumimos que yylex mira el valor de hexflag; cuando no es
cero, todos los enteros se analizan en hexadecimal, y los tokens que comiencen
con letras se analizan como enteros si es posible.
La declaraci�n de hexflag mostrada en la secci�n de declaraciones en C
del archivo del analizador se necesita para hacerla accesible a las acciones
(see section La Secci�n de Declaraciones en C). Debe
tambi�n escribir el c�digo en yylex para obedecer a la bandera.
Las ligaduras l�xicas hacen demandas estrictas sobre cualquier regla de recuperaci�n de errores que tenga. See section Recuperaci�n de Errores.
La raz�n de esto es que el prop�sito de una regla de recuperaci�n de errores es abortar el an�lisis de una construcci�n y reanudar en una construcci�n mayor. Por ejemplo, en lenguajes como C, una regla t�pica de recuperaci�n de errores es saltarse los tokens hasta el siguiente punto y coma, y entonces comenzar una sentencia nueva, como esta:
stmt: expr ';'
| IF '(' expr ')' stmt { ... }
...
error ';'
{ hexflag = 0; }
;
Si hay aqu� un error de sintaxis en medio de una construcci�n
`hex (expr)', esta regla de error se aplicar�, y entonces
la acci�n para la `hex (expr)' nunca se ejecutar�. As�
que hexflag continuar�a activada durante el resto de la entrada,
o hasta la pr�xima palabra clave hex, haciendo que los
identificadores se malinterpreten como enteros.
Para evitar este problema la regla de recuperaci�n de errores por s�
misma desactiva hexflag.
Aqu� podr�a existir tambi�n una regla de recuperaci�n de errores que trabaje dentro de expresiones. Por ejemplo, podr�a haber una regla que se aplique dentro de los par�ntesis y salte al par�ntesis-cerrar:
expr: ...
| '(' expr ')'
{ $$ = $2; }
| '(' error ')'
...
Si esta regla act�a dentro de la construcci�n hex, no se va a
abortar esa construcci�n (ya que �sta aparece a un nivel m�s interno
de par�ntesis dentro de la construcci�n). Por lo tanto, no deber�a
desactivar la bandera: el resto de la construcci�n hex deber�a
analizarse con la bandera a�n activada.
�Qu� suceder�a si hay una regla de recuperaci�n de errores que
pudiese abortar fuera la construcci�n hex o pudiese que no,
dependiendo de las circunstancias? No hay manera de escribir la
acci�n para determinar si una construcci�n hex est� siendo
abortada o no. De manera que si est� utilizando una ligadura l�xica,
es mejor que est� seguro que sus reglas de recuperaci�n de errores no
son de este tipo. Cada regla debe ser tal que pueda estar seguro que
siempre tendr� que tener que limpiar la bandera, o siempre no.
Si una gram�tica de Bison compila adecuadamente pero no hace lo que
quiere cuando se ejecuta, la propiedad de traza del analizador yydebug
puede ayudarle para darse cuenta del por qu�.
Para activar la compilaci�n de las facilidades de traza, debe definir
la macro YYDEBUG cuando compile el analizador. Podr�a utilizar
`-DYYDEBUG=1' como una opci�n del compilador o podr�a poner
`#define YYDEBUG 1' en la secci�n de declaraciones de C del archivo
de la gram�tica (see section La Secci�n de Declaraciones en C).
De forma alternativa, utilice la opci�n `-t' cuando ejecute Bison
(see section Invocando a Bison).
Siempre definiremos YYDEBUG de manera que la depuraci�n siempre
es posible.
La facilidad de traza utiliza stderr, de manera que debe a�adir
#include <stdio.h> en la secci�n de declaraciones de C a menos
que ya est� ah�.
Una vez que haya compilado el programa con las facilidades de traza, la
manera de solicitar una traza es almacenar un valor distinto de cero en
la variable yydebug. Puede hacer esto poniendo c�digo C que lo
haga (en main, tal vez), o puede alterar el valor con un depurador
de C.
Cada paso tomado por el analizador cuando yydebug no es cero
produce una l�nea o dos de informaci�n de traza, escrita sobre stderr.
Los mensajes de traza le cuentan estas cosas:
yylex, qu� tipo de token
ha sido leido.
Para hacerse una idea de esta informaci�n, ayuda el hacer referencia al listado del archivo producido por la opci�n `-v' de Bison (see section Invocando a Bison). Este archivo muestra el significado de cada estado en t�rminos de posici�n en varias reglas, y tambi�n qu� har� cada estado con cada token de entrada posible. A medida que lea los mensajes de traza sucesivos, puede ver que el analizador est� fucionando de acuerdo a su especificaci�n en el achivo del listado. Finalmente llegar� al lugar donde sucede algo indeseable, y ver� qu� parte de la gram�tica es la culpable.
El archivo del analizador es un programa en C y puede utilizar depuradores de C con �ste, pero no es f�cil interpretar lo que est� haciendo. La funci�n del analizador es un int�rprete de una m�quina de estado finito, y aparte de las acciones �ste ejecuta el mismo c�digo una y otra vez. Solamente los valores de las variables muestran sobre qu� lugar de la gram�tica se est� trabajando.
La informaci�n de depuraci�n normalmente da el tipo de token de
cada token le�do, pero no su valor sem�ntico. Puede opcionalmente
definir una macro llamada YYPRINT para facilitar una manera
de imprimir el valor. Si define YYPRINT, esta deber�a
tomar tres argumentos. El analizador pasar� un flujo de
entrada/salida estandar, el valor num�rico del tipo de token, y el
valor del token (de yylval).
Aqu� hay un ejemplo de YYPRINT apropiado para la calculadora
multifunci�n (see section Declaraciones para mfcalc):
#define YYPRINT(file, type, value) yyprint (file, type, value)
static void
yyprint (file, type, value)
FILE *file;
int type;
YYSTYPE value;
{
if (type == VAR)
fprintf (file, " %s", value.tptr->name);
else if (type == NUM)
fprintf (file, " %d", value.val);
}
La manera habitual de invocar a Bison es la siguiente:
bison fichero-entrada
Aqu� fichero-entrada es el nombre del fichero de la gram�tica, que normalmente termina en `.y'. El nombre del archivo del analizador se construye reemplazando el `.y' con `.tab.c'. As�, el nombre de fichero `bison foo.y' produce `foo.tab.c', y el nombre de fichero `bison hack/foo.y' produce `hack/foo.tab.c'.
Bison soporta las opciones tradicionales de una �nica letra y nombres de opci�n mnem�nicos largos. Los nombres de opci�n largos se indican con `--' en lugar de `-'. Las abreviaciones para los nombres de opci�n se permiten siempre que sean �nicas. Cuando una opci�n larga toma un argumento, como `--file-prefix', se conecta el nombre de la opcion con el argumento con `='.
Aqu� hay una lista de opciones que puede utilizar con Bison, alfabetizadas por la opci�n corta.
YYSTYPE, adem�s de unas
cuantas declaraciones de variables extern.
Si el archivo de salida del analizador se llama `name.c'
entonces este archivo se llama `name.h'.
Este archivo de salida es esencial si desea poner las definiciones
de yylex en un archivo fuente por separado, porque yylex
necesita ser capaz de hacer referencia a los c�digos de tipo de token
y las variables yylval. See section Valores Sem�nticos de los Tokens.
#line del preprocesador en el fichero del
analizador. Normalmente Bison los pone en el archivo del analizador
de manera que el compilador de C y los depuradores asocien errores
con su fichero fuente, el achivo de la gram�tica. Esta opci�n
hace que asocien los errores con el archivo del analizador, trat�ndolo
como un archivo fuente independiente por derecho propio.
#define
y declaraciones de variables est�ticas.
Esta opci�n tambi�n le dice a Bison que escriba el c�digo C para
las acciones gramaticales en un archivo llamado `nombrefichero.act',
en la forma de un cuerpo encerrado entre llaves para formar una
sentencia switch.
yyparse, yylex, yyerror,
yynerrs, yylval, yychar y yydebug.
Por ejemplo, si utiliza `-p c', los nombres ser�n cparse,
clex, etc.
See section M�ltiples Analizadores en el Mismo Programa.
%raw. See section Sumario de Declaraciones de Bison.
YYDEBUG en el achivo
del analizador, de manera que las facilidades de depuraci�n sean
compiladas. See section Depurando Su Analizador.
bison -y $*
Aqu� hay una lista de opciones, alfabetizada por la opcion larga, para ayudarle a encontrar la opci�n corta correspondiente.
La sintaxis de la l�nea de comandos para Bison sobre VMS es una variante de la sintaxis del comando de Bison usual--adaptada para ajustarse a las convenciones de VMS.
Para encontrar el equivalente VMS de cualquier opci�n de Bison, comience con la opci�n larga, y sustituya con `/' el `--' inicial, y sustituya con `_' cada `-' en el nombre de opci�n largo. Por ejemplo, la siguiente invocaci�n bajo VMS:
bison /debug/name_prefix=bar foo.y
es equivalente al siguiente comando bajo POSIX.
bison --debug --name-prefix=bar foo.y
El sistema de archivos de VMS no permite nombre de ficheros tales como `foo.tab.c'. En el ejemplo anterior, el archivo de salida se llamar�a `foo_tab.c'.
error
error llega a ser el token de prean�lisis actual.
Las acciones correspondientes a error se ejecutan entonces, y el
token de prean�lisis se reestablace al token que originalmente
provoc� la violaci�n.
See section Recuperaci�n de Errores.
YYABORT
yyparse devuelva un 1 inmediatamente.
La funci�n de informe de errores yyerror no se llama.
See section La Funci�n del Analizador yyparse.
YYACCEPT
yyparse devuelva un 0 inmediatamente.
See section La Funci�n del Analizador yyparse.
YYBACKUP
YYERROR
yyerror y entonces realiza una recuperaci�n
de errores normal si es posible (see section Recuperaci�n de Errores), o
(si la recuperaci�n es imposible) hace que yyparse devuelva
un 1. See section Recuperaci�n de Errores.
YYERROR_VERBOSE
#define en la secci�n de declaraciones
de Bison para solicitar cadenas de mensajes de errores amplias, espec�ficas
cuando se llame a yyerror.
YYINITDEPTH
YYLEX_PARAM
yyparse los pase a yylex. See section Convenciones de Llamada para Analizadores Puros.
YYLTYPE
yylloc; una estructura con
cuatro componentes. See section Posiciones en el Texto de los Tokens.
yyltype
YYMAXDEPTH
YYPARSE_PARAM
yyparse
deber�a aceptar. See section Convenciones de Llamada para Analizadores Puros.
YYRECOVERING
YYSTYPE
int
por defecto. See section Tipos de Datos para Valores Sem�nticos.
yychar
yyparse.) Las acciones de las reglas de
recuperaci�n de errores podr�an examinar esta variable.
See section Propiedades Especiales para su Uso en Acciones.
yyclearin
yydebug
yydebug un valor distinto de cero, el analizador sacar�
informaci�n a cerca de los s�mbolos de entrada y acciones del
analizador. See section Depurando Su Analizador.
yyerrok
yyerror
yyparse
ante un error. La funci�n recibe un argumento, un puntero a una
cadena de caracteres conteniendo un mensaje de error.
See section La Funci�n de Informe de Errores yyerror.
yylex
yylex.
yylval
yylex deber�a poner el
valor sem�ntico asociado con un token. (En un analizador puro,
es una variable local dentro de yyparse, y su direcci�n se
le pasa a yylex.) See section Valores Sem�nticos de los Tokens.
yylloc
yylex deber�a poner el n�mero
de l�nea y columna asociado a un token. (En un analizador puro,
es una variable local dentro de yyparse, y su direcci�n se
le pasa a yylex.) Puede ignorar esta variable si no utiliza
la propiedad `@' en las acciones gramaticales.
See section Posiciones en el Texto de los Tokens.
yynerrs
yyparse.) See section La Funci�n de Informe de Errores yyerror.
yyparse
yyparse.
%left
%no_lines
#line
en el fichero del analizador. See section Sumario de Declaraciones de Bison.
%nonassoc
%prec
%pure_parser
%raw
%right
%start
%token
%token_table
%type
%union
Estos son los puntuadores y delimitadores utilizados en la entrada de Bison:
yylex.
if.
See section Lenguajes y Gram�ticas independientes del Contexto.
mfcalc.
else
calc
else, balanceo del
mfcalc
rpcalc
primera l�nea, primera columna, �ltima l�nea y �ltima columna respectivamente
This document was generated on 23 May 1999 using the texi2html translator version 1.51.