Herramientas de software: Yacc/Bison
Introducción
¡Hola respetable estudiante!
¿Cómo te has sentido? ¿Qué te ha parecido esta unidad de aprendizaje? Espero que la encuentres fascinante. Te comparto los siguientes temas que son muy interesantes, ampliarán tus conocimientos y desarrollarán tus habilidades.
En esta sesión veremos cómo se usan las herramientas de desarrollo de compiladores llamadas Yacc y bison, así como también las razones que propiciaron su desarrollo y su historia.
Dada la complejidad de los compiladores, el diseño de compiladores debe apoyarse en el uso de herramientas como son los compiladores de compiladores. Los cuales son en realidad herramientas de generación de código para diseñar analizadores léxicos y sintácticos. Las ventajas de usar esas herramientas son: ayudan a reducir el tiempo, el costo de desarrollo y el número de errores o bugs.
Las herramientas Yacc y bison son importantes para el desarrollo de analizadores sintácticos en los compiladores y en aplicaciones de procesamiento del lenguaje. Por lo tanto, el dominio de estas herramientas permite a los ingenieros de software desarrollar también otras aplicaciones de procesamiento del lenguaje. Por ejemplo, las herramientas Yacc y bison también se pueden utilizar para implementar herramientas tales como los analizadores de frases, intérpretes de motores de consulta de bases de datos.
El código del analizador sintáctico generado por las herramientas Yacc y bison se puede integrar con el código del analizador léxico generado por otras herramientas tales como Lex y flex.
El análisis sintáctico se basa en el concepto de gramática independiente de contexto el cual surgió en lingüística para describir la estructura de frases del lenguaje natural. El conocimiento sobre análisis sintáctico y gramáticas libres de contexto tiene también aplicación en el área de teoría de los lenguajes formales.
En relación con lo anterior, ¡prosigamos nuestro trabajo de aprendizaje!
¡Adelante!
Desarrollo del tema
Gramáticas libres de contexto
Las gramáticas libres de contexto (CFG) fueron originalmente inventadas por Chomsky a mediados de 1950 para el análisis del lenguaje natural.
Una gramática libre de contexto es una gramática con reglas de producción de la forma:
A→α
donde A es un símbolo no terminal y α es una cadena de símbolos (terminales y no terminales).
Una gramática formal es “independiente de contexto” si sus reglas de producción pueden ser aplicadas sin importar el contexto del símbolo no terminal.
Una gramática formal es un conjunto de reglas de producción que describen todas las cadenas de un lenguaje formal.
Yacc
Yacc (Yet Another Compiler Compiler) es un generador de analizadores sintácticos desarrollado por Johnson a inicios de los 1970s.
El analizador sintáctico generado por Yacc requiere de un analizador léxico.
Yacc ha sido utilizado para implementar compiladores para los lenguajes AWK, C++, Fortran 77, Ratfor, APL, bc, m4, etc.
La entrada consiste de una gramática libre de contexto (CFG) especificada en un archivo de texto.
La salida consiste de:
- Código en Lenguaje C de un analizador sintáctico ascendente LALR(1).
- Una cabecera de símbolos o tokens.
Versiones de Yacc y bison:
Yacc
- Existe en la mayoría de los sistemas UNIX.
- Actualmente, Yacc es código abierto y está disponible como parte de Opensolaris y Plan 9.
Bison
- Es el equivalente de Yacc en código abierto, forma parte de GNU
- Existe bajo todas las distribuciones de Linux.
- Puede utilizarse bajo la plataforma WSL de Windows.
WSL (Windows Subsystem for Linux) es un subsistema que permite ejecutar Linux bajo Windows
BSD yacc
- Bajo BSD también existe una versión de Yacc.
- Existen otras versiones para MSDOS, Mac OSX y Windows
Win Bison Flex
- Es una librería que se integra con Visual Studio.
- Esta contiene versiones de Bison y flex para ejecutarse desde la línea de comandos o Visual Studio.
Formato Yacc:
El formato de la especificación de Yacc consta de tres secciones: definiciones, reglas y código suplementario. Cada sección está separada por una línea que inicia con doble carácter %.
Precedencia/Asociatividad:
La precedencia y asociatividad es un mecanismo que puede utilizarse para solucionar problemas de ambigüedad en la gramática (usualmente en reglas de expresiones aritméticas, lógicas, etc.).
Las directivas %left, %right y %nonassoc se pueden utilizar para definir las precedencias y asociatividades de los símbolos terminales. La primera directiva define los símbolos de más baja precedencia y la última directiva define los símbolos de más alta precedencia.
En seguida se muestra un ejemplo de definición de precedencia y asociatividad:
%left PLUS MINUS
%left MULT DIV*
%right NEG
En este caso, los tokens PLUS y MINUS son los que tienen la precedencia más baja y se agrupan de izquierda a derecha. Los tokens MULT y DIV tienen una precedencia más alta que los anteriores y también se agrupan de izquierda a derecha. El token NEG tiene la precedencia más alta y se agrupa de derecha a izquierda.
La precedencia y asociatividad es un mecanismo que puede utilizarse para solucionar problemas de ambigüedad en la gramática (usualmente en reglas de expresiones aritméticas, lógicas, etc.).
Sin embargo, existen casos de ambigüedad que se resuelven de manera más elaborada. Por ejemplo, la instrucción if…else es usualmente ambigua. Los compiladores de C solucionan este problema agrupando un else con el if inmediatamente anterior.
La siguiente gramática ilustra cómo eliminar la ambigüedad de la instrucción if…else.
En este caso, se definieron dos tokens no asociativos usando la directiva %nonassoc. El token ELSE es definido al final. Por lo tanto, tiene más precedencia que el token NOELSE. Enseguida se agrega la directiva %prec NOELSE a la primera forma de if.
En conclusión, la segunda forma se aplica primero en una sustitución porque tiene más precedencia el token ELSE.
Funcionamiento de YACC:
La función yyparse()
- Es la que implementa el analizador sintáctico
- Es generada por Yacc (o Bison)
– Llama a yylex() para buscar tokens.
– Recibe tokens encontrados por analizador léxico.
– Ejecuta las acciones correspondientes.
– Termina cuando encuentra un error o cuando se termina la entrada.
- Valor de retorno:
0
El análisis fue exitoso
1
Se encontró un error de sintaxis
Conclusión
En la teoría de los lenguajes formales, una gramática libre de contexto es una gramática con reglas de producción de la forma:
A→α
donde A es un símbolo no terminal y es una cadena de símbolos (terminales y no terminales).
Yacc (Yet Another Compiler Compiler) es un generador de analizadores sintácticos desarrollado por Johnson a inicios de los 70s.
El analizador sintáctico generado por Yacc y bison requiere de un analizador léxico. Yacc y bison se pueden integrar con el código del analizador léxico generado por otras herramientas tales como Lex y flex.
El analizador generado por Yacc y bison contiene una función llamada yyparse() que:
- Implementa un analizador sintáctico ascendente LALR(1).
- Llama a yylex() para buscar tokens.
- Procesa los tokens encontrados por analizador léxico.
- Efectúa sustituciones y ejecuta las acciones correspondientes.
- Termina cuando encuentra un error o cuando se termina la entrada.
- Valor de retorno: 0
El análisis fue exitoso.
- Valor de retorno: 1
Se encontró un error de sintaxis.
El formato de la especificación de Yacc consta de tres secciones: definiciones, reglas y código suplementario.
- Sección definiciones. Contiene código en C delimitado por %{ y %}, definiciones de símbolos terminales y no terminales y otras directivas de Yacc.
- Sección reglas.
Contiene reglas de producción y acciones a ejecutar cuando el analizador sintáctico aplica una regla de producción para hacer una sustitución. Las reglas del lenguaje son escritas en una notación similar a BNF.
- Sección código suplementario.
Contiene código en C que requiera el analizador sintáctico.
Yacc es patentado bajo la mayoría de los sistemas UNIX. Actualmente, Yacc es código abierto. Sin embargo, bison es un generador de analizadores sintácticos compatible con Yacc y de código abierto disponible en casi todas las plataformas.
Hemos arribado al final de nuestra clase. ¡Te felicito, bien hecho! Por favor resuelve la consigna definida para este tema; esfuérzate y trabaja lo suficiente para que la entregues en tiempo y forma.
Te encuentro en la siguiente clase digital. ¡Ánimo, vas avanzando muy bien en tu aprendizaje! Hasta luego.