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 reconoc