{"id":16159,"date":"2022-07-16T19:00:38","date_gmt":"2022-07-16T19:00:38","guid":{"rendered":"https:\/\/blogs.ugto.mx\/rea\/?p=16159"},"modified":"2022-09-24T02:54:20","modified_gmt":"2022-09-24T02:54:20","slug":"clase-digital-4-herramientas-de-software-yacc-bison","status":"publish","type":"post","link":"https:\/\/blogs.ugto.mx\/rea\/clase-digital-4-herramientas-de-software-yacc-bison\/","title":{"rendered":"Clase digital 4. Herramientas de software: Yacc\/Bison"},"content":{"rendered":"\n\n\n<div class=\"wp-block-cover\" style=\"min-height:284px;aspect-ratio:unset;\"><span aria-hidden=\"true\" class=\"wp-block-cover__background has-background-dim-40 has-background-dim\"><\/span><img decoding=\"async\" class=\"wp-block-cover__image-background wp-image-17997\" alt=\"\" src=\"data:image\/gif;base64,R0lGODlhAQABAIAAAAAAAP\/\/\/yH5BAEAAAAALAAAAAABAAEAAAIBRAA7\" data-src=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/1841550.jpg\" style=\"object-position:33% 26%\" data-object-fit=\"cover\" data-object-position=\"33% 26%\" \/><noscript><img loading=\"lazy\" decoding=\"async\" width=\"1280\" height=\"853\" class=\"wp-block-cover__image-background wp-image-17997\" alt=\"\" src=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/1841550.jpg\" style=\"object-position:33% 26%\" data-object-fit=\"cover\" data-object-position=\"33% 26%\" srcset=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/1841550.jpg 1280w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/1841550-300x200.jpg 300w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/1841550-1024x682.jpg 1024w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/1841550-768x512.jpg 768w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/1841550-272x182.jpg 272w\" sizes=\"auto, (max-width: 1280px) 100vw, 1280px\" \/><\/noscript><div class=\"wp-block-cover__inner-container is-layout-flow wp-block-cover-is-layout-flow\">\n<p class=\"has-text-align-center has-base-3-color has-text-color has-large-font-size wp-block-paragraph\">Herramientas de software: Yacc\/Bison<\/p>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"introduccion\">Introducci\u00f3n<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u00a1Hola respetable estudiante!<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u00bfC\u00f3mo te has sentido? \u00bfQu\u00e9 te ha parecido esta unidad de aprendizaje? Espero que la&nbsp; encuentres fascinante. Te comparto los siguientes temas que son muy interesantes, ampliar\u00e1n tus conocimientos y desarrollar\u00e1n tus habilidades.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">En esta sesi\u00f3n veremos c\u00f3mo se usan las herramientas de desarrollo de compiladores llamadas Yacc y bison, as\u00ed como tambi\u00e9n las razones que propiciaron su desarrollo y su historia.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Dada la complejidad de los compiladores, el dise\u00f1o de compiladores debe apoyarse en el uso de herramientas como son los compiladores de compiladores. Los cuales son en realidad herramientas de generaci\u00f3n de c\u00f3digo para dise\u00f1ar analizadores l\u00e9xicos y sint\u00e1cticos. Las ventajas de usar esas herramientas son: ayudan a reducir el tiempo, el costo de desarrollo y el n\u00famero de errores o bugs.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Las herramientas Yacc y bison son importantes para el desarrollo de analizadores sint\u00e1cticos 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\u00e9n otras aplicaciones de procesamiento del lenguaje. Por ejemplo, las herramientas Yacc y bison tambi\u00e9n se pueden utilizar para implementar herramientas tales como los analizadores de frases, int\u00e9rpretes de motores de consulta de bases de datos.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">El c\u00f3digo del analizador sint\u00e1ctico generado por las herramientas Yacc y bison se puede integrar con el c\u00f3digo del analizador l\u00e9xico generado por otras herramientas tales como Lex y flex.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">El an\u00e1lisis sint\u00e1ctico se basa en el concepto de gram\u00e1tica independiente de contexto el cual surgi\u00f3 en ling\u00fc\u00edstica para describir la estructura de frases del lenguaje natural. El conocimiento sobre an\u00e1lisis sint\u00e1ctico y gram\u00e1ticas libres de contexto tiene tambi\u00e9n aplicaci\u00f3n en el \u00e1rea de teor\u00eda de los lenguajes formales.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">En relaci\u00f3n con lo anterior, \u00a1prosigamos nuestro trabajo de aprendizaje!<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u00a1Adelante!<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"desarrollo-del-tema\">Desarrollo del tema <\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">Gram\u00e1ticas libres de contexto<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Las gram\u00e1ticas libres de contexto (CFG) fueron originalmente inventadas por Chomsky a mediados de 1950 para el an\u00e1lisis del lenguaje natural.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Una gram\u00e1tica libre de contexto es una gram\u00e1tica con reglas de producci\u00f3n de la forma:<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\">A\u2192\u03b1<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">donde&nbsp;A es un s\u00edmbolo no terminal y \u03b1 es una cadena de s\u00edmbolos (terminales y no terminales).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Una gram\u00e1tica formal es \u201cindependiente de contexto\u201d si sus reglas de producci\u00f3n pueden ser aplicadas sin importar el contexto del s\u00edmbolo no terminal.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Una gram\u00e1tica formal es un conjunto de reglas de producci\u00f3n que describen todas las cadenas de un lenguaje formal.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Yacc<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Yacc (Yet Another Compiler Compiler) es un generador de analizadores sint\u00e1cticos desarrollado por Johnson a inicios de los 1970s.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">El analizador sint\u00e1ctico generado por Yacc requiere de un analizador l\u00e9xico.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Yacc ha sido utilizado para implementar compiladores para los lenguajes AWK, C++, Fortran 77, Ratfor, APL, bc, m4, etc.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">La entrada consiste de una gram\u00e1tica libre de contexto (CFG) especificada en un archivo de texto.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">La salida consiste de:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>C\u00f3digo en Lenguaje C de un analizador sint\u00e1ctico ascendente LALR(1).<\/li><li>Una cabecera de s\u00edmbolos o tokens.<\/li><\/ol>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Versiones de Yacc y bison:<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Yacc<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Existe en la mayor\u00eda de los sistemas UNIX.<\/li><li>Actualmente, Yacc es c\u00f3digo abierto y est\u00e1 disponible como parte de Opensolaris y Plan 9.<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Bison<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Es el equivalente de Yacc en c\u00f3digo abierto, forma parte de GNU<\/li><li>Existe bajo todas las distribuciones de Linux.<\/li><li>Puede utilizarse bajo la plataforma WSL de Windows.<br><em>WSL (Windows Subsystem for Linux) es un subsistema que permite ejecutar Linux bajo Windows<\/em><\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>BSD yacc<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Bajo BSD tambi\u00e9n existe una versi\u00f3n de Yacc.<\/li><li>Existen otras versiones para MSDOS, Mac OSX y Windows<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Win Bison Flex<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Es una librer\u00eda que se integra con Visual Studio.<\/li><li>Esta contiene versiones de Bison y flex para ejecutarse desde la l\u00ednea de comandos o Visual Studio.<\/li><\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Formato Yacc:<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">El formato de la especificaci\u00f3n de Yacc consta de tres secciones: definiciones, reglas y c\u00f3digo suplementario. Cada secci\u00f3n est\u00e1 separada por una l\u00ednea que inicia con doble car\u00e1cter %.<\/p>\n\n\n<div class=\"h5p-iframe-wrapper\"><iframe id=\"h5p-iframe-308\" class=\"h5p-iframe\" data-content-id=\"308\" style=\"height:1px\" src=\"about:blank\" frameBorder=\"0\" scrolling=\"no\" title=\"Formato Yacc:\"><\/iframe><\/div>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Precedencia\/Asociatividad:<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">La precedencia y asociatividad es un mecanismo que puede utilizarse para solucionar problemas de ambig\u00fcedad en la gram\u00e1tica (usualmente en reglas de expresiones aritm\u00e9ticas, l\u00f3gicas, etc.).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Las directivas %left, %right y %nonassoc se pueden utilizar para definir las precedencias y asociatividades de los s\u00edmbolos terminales. La primera directiva define los s\u00edmbolos de m\u00e1s baja precedencia y la \u00faltima directiva define los s\u00edmbolos de m\u00e1s alta precedencia.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">En seguida se muestra un ejemplo de definici\u00f3n de precedencia y asociatividad:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">%left PLUS MINUS&nbsp;<br>%left MULT DIV*<br>%right NEG&nbsp;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">En este caso, los tokens PLUS y MINUS son los que tienen la precedencia m\u00e1s baja y se agrupan de izquierda a derecha. Los tokens MULT y DIV tienen una precedencia m\u00e1s alta que los anteriores y tambi\u00e9n se agrupan de izquierda a derecha. El token NEG tiene la precedencia m\u00e1s alta y se agrupa de derecha a izquierda.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">La precedencia y asociatividad es un mecanismo que puede utilizarse para solucionar problemas de ambig\u00fcedad en la gram\u00e1tica (usualmente en reglas de expresiones aritm\u00e9ticas, l\u00f3gicas, etc.).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Sin embargo, existen casos de ambig\u00fcedad que se resuelven de manera m\u00e1s elaborada. Por ejemplo, la instrucci\u00f3n if\u2026else es usualmente ambigua. Los compiladores de C solucionan este problema agrupando un <strong>else<\/strong> con el <strong>if<\/strong> inmediatamente anterior.&nbsp;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">La siguiente gram\u00e1tica ilustra c\u00f3mo eliminar la ambig\u00fcedad de la instrucci\u00f3n if\u2026else.<\/p>\n\n\n<div class=\"wp-block-image is-style-default\">\n<figure class=\"aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"data:image\/gif;base64,R0lGODlhAQABAIAAAAAAAP\/\/\/yH5BAEAAAAALAAAAAABAAEAAAIBRAA7\" data-src=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/09\/Instruccion-if.png\" alt=\"\" class=\"wp-image-19157\" width=\"642\" height=\"206\" \/><noscript><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/09\/Instruccion-if.png\" alt=\"\" class=\"wp-image-19157\" width=\"642\" height=\"206\" srcset=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/09\/Instruccion-if.png 512w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/09\/Instruccion-if-300x96.png 300w\" sizes=\"auto, (max-width: 642px) 100vw, 642px\" \/><\/noscript><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">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\u00e1s precedencia que el token NOELSE. Enseguida se agrega la directiva %prec NOELSE a la primera forma de if.&nbsp;<br>En conclusi\u00f3n, la segunda forma se aplica primero en una sustituci\u00f3n porque tiene m\u00e1s precedencia el token ELSE.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Funcionamiento de YACC:<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">La funci\u00f3n yyparse()<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Es la que implementa el analizador sint\u00e1ctico<br><\/li><li>Es generada por Yacc (o Bison)<br>&#8211; Llama a yylex() para buscar tokens.<br>&#8211; Recibe tokens encontrados por analizador l\u00e9xico.<br>&#8211; Ejecuta las acciones correspondientes.<br>&#8211; Termina cuando encuentra un error o cuando se termina la entrada.<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>Valor de retorno:<br><strong>0<\/strong> <br>El an\u00e1lisis fue exitoso<br><strong>1<\/strong> <br>Se encontr\u00f3 un error de sintaxis<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"fuentes-de-informacion\">Conclusi\u00f3n<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">En la teor\u00eda de los lenguajes formales, una gram\u00e1tica libre de contexto es una gram\u00e1tica con reglas de producci\u00f3n de la forma:<br><br>                                                                                                    A\u2192\u03b1<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">donde <em>A<\/em> es un s\u00edmbolo no terminal y es una cadena de s\u00edmbolos (terminales y no terminales).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Yacc (Yet Another Compiler Compiler) es un generador de analizadores sint\u00e1cticos desarrollado por Johnson a inicios de los 70s.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">El analizador sint\u00e1ctico generado por Yacc y bison requiere de un analizador l\u00e9xico. Yacc y bison se pueden integrar con el c\u00f3digo del analizador l\u00e9xico generado por otras herramientas tales como Lex y flex.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">El analizador generado por Yacc y bison contiene una funci\u00f3n llamada yyparse() que:&nbsp;<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>Implementa un analizador sint\u00e1ctico ascendente LALR(1).<\/li><li>Llama a yylex() para buscar tokens.<\/li><li>Procesa los tokens encontrados por analizador l\u00e9xico.<\/li><li>Efect\u00faa sustituciones y ejecuta las acciones correspondientes.<\/li><li>Termina cuando encuentra un error o cuando se termina la entrada.<\/li><\/ol>\n\n\n\n<ul class=\"wp-block-list\"><li>Valor de retorno: <strong>0<\/strong><br>El an\u00e1lisis fue exitoso.<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>Valor de retorno: <strong>1<\/strong><br>Se encontr\u00f3 un error de sintaxis.<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">El formato de la especificaci\u00f3n de Yacc consta de tres secciones: definiciones, reglas y c\u00f3digo suplementario.<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li><strong>Secci\u00f3n definiciones<\/strong>. Contiene c\u00f3digo en C delimitado por %{ y %}, definiciones de s\u00edmbolos terminales y no terminales y otras directivas de Yacc.&nbsp;<br><\/li><li><strong>Secci\u00f3n reglas<\/strong>.&nbsp;<br>Contiene reglas de producci\u00f3n y acciones a ejecutar cuando el analizador sint\u00e1ctico aplica una regla de producci\u00f3n para hacer una sustituci\u00f3n. Las reglas del lenguaje son escritas en una notaci\u00f3n similar a BNF.<\/li><\/ol>\n\n\n\n<ol class=\"wp-block-list\" start=\"3\"><li><strong>Secci\u00f3n c\u00f3digo suplementario<\/strong>.&nbsp;<br>Contiene c\u00f3digo en C que requiera el analizador sint\u00e1ctico.<\/li><\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Yacc es patentado bajo la mayor\u00eda de los sistemas UNIX. Actualmente, Yacc es c\u00f3digo abierto. Sin embargo, bison es un generador de analizadores sint\u00e1cticos compatible con Yacc y de c\u00f3digo abierto disponible en casi todas las plataformas.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Hemos arribado al final de nuestra clase. \u00a1Te felicito, bien hecho! Por favor resuelve la consigna definida para este tema; esfu\u00e9rzate y trabaja lo suficiente para que la entregues en tiempo y forma.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Te encuentro en la siguiente clase digital. \u00a1\u00c1nimo, vas avanzando muy bien en tu aprendizaje! Hasta luego.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Fuentes de informaci\u00f3n<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/www.gnu.org\/software\/bison\/manual\/bison.pdf\" target=\"_blank\" rel=\"noreferrer noopener\">Bison &#8211; The Yacc-compatible Parser GeneratorURL.<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Introducci\u00f3n \u00a1Hola respetable estudiante! \u00bfC\u00f3mo te has sentido? \u00bfQu\u00e9 te ha parecido esta unidad de aprendizaje? Espero que la&nbsp; encuentres fascinante. Te comparto los siguientes temas que son muy interesantes, ampliar\u00e1n tus conocimientos y desarrollar\u00e1n tus habilidades. En esta sesi\u00f3n veremos c\u00f3mo se usan las herramientas de desarrollo de compiladores llamadas Yacc y bison, as\u00ed &#8230; <a title=\"Clase digital 4. Herramientas de software: Yacc\/Bison\" class=\"read-more\" href=\"https:\/\/blogs.ugto.mx\/rea\/clase-digital-4-herramientas-de-software-yacc-bison\/\" aria-label=\"Leer m\u00e1s sobre Clase digital 4. Herramientas de software: Yacc\/Bison\">Leer m\u00e1s<\/a><\/p>\n","protected":false},"author":142,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"_crdt_document":"","episode_type":"","audio_file":"","podmotor_file_id":"","podmotor_episode_id":"","cover_image":"","cover_image_id":"","duration":"","filesize":"","filesize_raw":"","date_recorded":"","explicit":"","block":"","itunes_episode_number":"","itunes_title":"","itunes_season_number":"","itunes_episode_type":"","footnotes":""},"categories":[180,19,471],"tags":[41,472,473],"class_list":["post-16159","post","type-post","status-publish","format-standard","hentry","category-cideap","category-ingenieria-en-sistemas-computacionales","category-uda-compiladores","tag-clase-digital","tag-iili06025","tag-jose-ruiz-pinales"],"acf":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/posts\/16159","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/users\/142"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/comments?post=16159"}],"version-history":[{"count":4,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/posts\/16159\/revisions"}],"predecessor-version":[{"id":19158,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/posts\/16159\/revisions\/19158"}],"wp:attachment":[{"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/media?parent=16159"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/categories?post=16159"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/tags?post=16159"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}