{"id":16173,"date":"2022-07-16T19:04:43","date_gmt":"2022-07-16T19:04:43","guid":{"rendered":"https:\/\/blogs.ugto.mx\/rea\/?p=16173"},"modified":"2022-09-24T02:59:50","modified_gmt":"2022-09-24T02:59:50","slug":"clase-digital-11-analisis-sintactico-analisis-ascendente-lr","status":"publish","type":"post","link":"https:\/\/blogs.ugto.mx\/rea\/clase-digital-11-analisis-sintactico-analisis-ascendente-lr\/","title":{"rendered":"Clase digital 11. An\u00e1lisis sint\u00e1ctico: An\u00e1lisis ascendente LR"},"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-18162\" alt=\"\" src=\"data:image\/gif;base64,R0lGODlhAQABAIAAAAAAAP\/\/\/yH5BAEAAAAALAAAAAABAAEAAAIBRAA7\" data-src=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/1742687.jpg\" style=\"object-position:68% 36%\" data-object-fit=\"cover\" data-object-position=\"68% 36%\" \/><noscript><img loading=\"lazy\" decoding=\"async\" width=\"1280\" height=\"874\" class=\"wp-block-cover__image-background wp-image-18162\" alt=\"\" src=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/1742687.jpg\" style=\"object-position:68% 36%\" data-object-fit=\"cover\" data-object-position=\"68% 36%\" srcset=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/1742687.jpg 1280w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/1742687-300x205.jpg 300w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/1742687-1024x699.jpg 1024w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/1742687-768x524.jpg 768w\" 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\">An\u00e1lisis sint\u00e1ctico: An\u00e1lisis ascendente LR<\/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!<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u00a1Vaya qu\u00e9 momento m\u00e1s grato el poder saludarte! Es un orgullo que contin\u00faes como estudiante de este curso. Espero que sigas perseverando hasta el final, por lo pronto te invito a revisar esta onceava sesi\u00f3n.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">En esta sesi\u00f3n aprenderemos sobre&nbsp;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Iniciemos nuestra aventura del conocimiento ahondando un poco m\u00e1s en el conocimiento del tema.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u00a1Mucho \u00e9xito!<\/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\">An\u00e1lisis Ascendente (BU):<\/h3>\n\n\n\n<ul class=\"wp-block-list\"><li>Es un tipo de an\u00e1lisis que construye el \u00e1rbol sint\u00e1ctico desde las hojas (la parte inferior) hasta la ra\u00edz (la parte superior).<ul><li>Aplica reducciones (pasos de la derivaci\u00f3n en reversa) y desplazamientos (lecturas de tokens de entrada).<\/li><li>Las hojas del \u00e1rbol sint\u00e1ctico son los s\u00edmbolos terminales de entrada (tokens) y el nodo ra\u00edz es el s\u00edmbolo inicial.<\/li><li>Es uno de los m\u00e9todos m\u00e1s poderosos y generales.<ul><li>Funciona para muchos tipos de gram\u00e1ticas CFG aunque tengan recursividad izquierda.<\/li><\/ul><\/li><li>Explora la secuencia de tokens de izquierda a derecha.<\/li><\/ul><\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>Se puede construir el \u00e1rbol sint\u00e1ctico usando reducci\u00f3n aleatoria<br>Se tiene el problema de c\u00f3mo determinar las reducciones correctas<br>Se pueden hacer retrocesos<br><br>Analizador LR:<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>Es una forma especial de analizador BU inventada por Knuth en 1969.<ul><li>La L significa exploraci\u00f3n de izquierda a derecha.<\/li><li>La R significa construir la derivaci\u00f3n derecha en reversa.<\/li><li>Su dise\u00f1o es m\u00e1s laborioso y complicado que para el analizador descendente.<\/li><li>Forma parte de los analizadores m\u00e1s poderosos y generales.<\/li><li>Tambi\u00e9n puede usar b\u00fasqueda hacia delante.<ul><li>LR(1), LR(2), etc.<\/li><\/ul><\/li><li>La tabla de an\u00e1lisis puede indicar el tipo de gram\u00e1tica.<\/li><\/ul><\/li><li>Variantes:<ul><li>LR can\u00f3nico: es el m\u00e1s poderoso y costoso.<\/li><li>SLR (Simple LR): funciona para menos gram\u00e1ticas pero es f\u00e1cil de implementar.<\/li><li>LALR (LookAhead LR): funciona con la mayor\u00eda de las gram\u00e1ticas de los lenguajes de programaci\u00f3n pero con un poco de esfuerzo.<\/li><\/ul><\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">GLR (Generalized LR): es una extensi\u00f3n de LR para manejar gram\u00e1ticas ambiguas y no determin\u00edsticas.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Los analizadores sint\u00e1cticos ascendentes LR son m\u00e1s poderosos que los analizadores descendentes LL.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">An\u00e1lisis LR:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Construir \u00e1rbol de an\u00e1lisis desde las hojas hacia la ra\u00edz, explorando de izquierda a derecha (resultando en derivaci\u00f3n m\u00e1s a la derecha en reversa).<br>G: <br><em>S&nbsp; <\/em>\u2192<em>&nbsp; a A B e  <\/em>        entrada: abbcde<br>A \u2192<em>&nbsp; A b c | b<br>B <\/em>\u2192 <em>&nbsp;d<\/em><\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>Sea&nbsp;G&nbsp;=<br>S&nbsp;\u2192&nbsp;aABe<br>A&nbsp;\u2192&nbsp;Abc|b &nbsp; &nbsp; <br>B&nbsp;\u2192&nbsp;d<br><br>La cadena&nbsp;abbcde puede ser <em>reducida<\/em> a S seg\u00fan los pasos siguientes:<br>abbcde<br>aAbcde<br>aAde<br>aABe &nbsp; &nbsp; <br>S<\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>Las reducciones anteriores dan la siguiente derivaci\u00f3n m\u00e1s a la derecha en reversa:<\/li><\/ul>\n\n\n<div class=\"wp-block-image is-style-default\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" src=\"data:image\/gif;base64,R0lGODlhAQABAIAAAAAAAP\/\/\/yH5BAEAAAAALAAAAAABAAEAAAIBRAA7\" data-src=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.00.53-1024x62.png\" alt=\"\" class=\"wp-image-18151\" \/><noscript><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"62\" src=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.00.53-1024x62.png\" alt=\"\" class=\"wp-image-18151\" srcset=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.00.53-1024x62.png 1024w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.00.53-300x18.png 300w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.00.53-768x46.png 768w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.00.53.png 1239w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/noscript><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\"><li>An\u00e1lisis LR \u2260 Reducci\u00f3n Izquierda<ul><li>La primera subcadena reducible no siempre resulta en un an\u00e1lisis exitoso.<\/li><li>Handle(s): los que conducen a&nbsp;<\/li><li>S exitosamente.<\/li><\/ul><\/li><li>An\u00e1lisis Descendente:<ul><li>Expansi\u00f3n.<\/li><li>Concordancia.<\/li><\/ul><\/li><li>An\u00e1lisis Ascendente: Desplazar\/Reducir<ul><li>Localizar siguiente \u201chandle\u201d para reducir<\/li><\/ul><\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Podado de Handles<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Handles o Asideros:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Handle de una cadena o forma sentencial derecha.<br>Es una subcadena que concuerda con una parte derecha de una producci\u00f3n, y cuya reducci\u00f3n al no terminal de la izquierda representa un paso para su reducci\u00f3n al s\u00edmbolo inicial.<ul><li>Un handle de una forma sentencial derecha es:<br>Una producci\u00f3n A\u03b2 y una posici\u00f3n donde la cadena \u03b2 puede ser reemplazada por A para producir la forma sentencial derecha previa en una derivaci\u00f3n derecha de<\/li><\/ul><\/li><\/ul>\n\n\n\n<ul class=\"wp-block-list\"><li>Si S\u21d2\u03b1A\u03c9\u21d2\u03b1\u03b2\u03c9, entonces<br>A\u03b2 en la posici\u00f3n que sigue a es un handle de \u03b1\u03b2\u03c9<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">La cadena contiene s\u00f3lo s\u00edmbolos terminales.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Si la gram\u00e1tica no es ambigua, entonces cada forma sentencial derecha tiene exactamente un handle.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Sea la gram\u00e1tica:<br>S<em>aABe<\/em><br>A&nbsp;Abc&nbsp;|&nbsp;b<br>B&nbsp;d<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">La cadena de tokens abbcde puede ser reducida a S como:<br>abbcde&nbsp; tiene como handle A&nbsp;b en posici\u00f3n 2&nbsp;<br>aAbcde&nbsp; tiene como handle A&nbsp;Abc&nbsp;en posici\u00f3n 2&nbsp;<br>aAde&nbsp; &nbsp;   tiene como handle B&nbsp;d en posici\u00f3n 3<br>aABe&nbsp; &nbsp;   tiene como handle S&nbsp;aABe en posici\u00f3n 1<br>S<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Las reducciones anteriores dan la siguiente derivaci\u00f3n derecha en reversa:<\/p>\n\n\n<div class=\"wp-block-image is-style-default\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" src=\"data:image\/gif;base64,R0lGODlhAQABAIAAAAAAAP\/\/\/yH5BAEAAAAALAAAAAABAAEAAAIBRAA7\" data-src=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.46.39-1024x63.png\" alt=\"\" class=\"wp-image-18159\" \/><noscript><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"63\" src=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.46.39-1024x63.png\" alt=\"\" class=\"wp-image-18159\" srcset=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.46.39-1024x63.png 1024w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.46.39-300x19.png 300w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.46.39-768x48.png 768w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.46.39.png 1228w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/noscript><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\"><li>Gram\u00e1tica:<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">S \u2192 E<br>E \u2192 E+T | E-T | T<br>T \u2192 T*F | T\/F | F<br>F \u2192 <strong>number<\/strong> | <strong>id<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Handles para id1*id2<\/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\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.46.49.png\" alt=\"\" class=\"wp-image-18160\" width=\"552\" height=\"293\" \/><noscript><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.46.49.png\" alt=\"\" class=\"wp-image-18160\" width=\"552\" height=\"293\" srcset=\"https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.46.49.png 736w, https:\/\/blogs.ugto.mx\/rea\/wp-content\/uploads\/sites\/71\/2022\/08\/Captura-de-Pantalla-2022-08-17-a-las-14.46.49-300x159.png 300w\" sizes=\"auto, (max-width: 552px) 100vw, 552px\" \/><\/noscript><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Una colecci\u00f3n de \u00edtems es un estado del analizador LR<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">El analizador sint\u00e1ctico ascendente LR utiliza tabla y stack.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Una ventaja de los analizadores sint\u00e1cticos LR es que existen herramientas en l\u00ednea para calcular las tablas de an\u00e1lisis.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Tipo de analizador sint\u00e1ctico que generan las herramientas Yacc y Bison: LALR(1).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"conclusion\">Conclusi\u00f3n<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Para recordar:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Hemos llegado al final de la sesi\u00f3n. \u00a1Mis felicitaciones por tu gran logro! Espero que el tema sea de mucha ayuda en tus aprendizajes. Acude con tu asesor para despejar las dudas que hayan surgido. Resuelve la consigna en tiempo y forma.&nbsp;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Nos encontraremos en la siguiente sesi\u00f3n.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"fuentes-de-informacion\">Fuentes de informaci\u00f3n<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/www.youtube.com\/watch?v=3s_O_GrVY6k\" target=\"_blank\" rel=\"noreferrer noopener\">Algoritmo de an\u00e1lisis sint\u00e1ctico LR(1), 0:31 \u2013 9:54.<\/a><\/li><li><a href=\"http:\/\/jsmachines.sourceforge.net\/machines\/lr1.html\" target=\"_blank\" rel=\"noreferrer noopener\">LR(1) Parser Generator \u2013 JSMachines.<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Introducci\u00f3n \u00a1Hola! \u00a1Vaya qu\u00e9 momento m\u00e1s grato el poder saludarte! Es un orgullo que contin\u00faes como estudiante de este curso. Espero que sigas perseverando hasta el final, por lo pronto te invito a revisar esta onceava sesi\u00f3n. En esta sesi\u00f3n aprenderemos sobre&nbsp; Iniciemos nuestra aventura del conocimiento ahondando un poco m\u00e1s en el conocimiento del &#8230; <a title=\"Clase digital 11. An\u00e1lisis sint\u00e1ctico: An\u00e1lisis ascendente LR\" class=\"read-more\" href=\"https:\/\/blogs.ugto.mx\/rea\/clase-digital-11-analisis-sintactico-analisis-ascendente-lr\/\" aria-label=\"Leer m\u00e1s sobre Clase digital 11. An\u00e1lisis sint\u00e1ctico: An\u00e1lisis ascendente LR\">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-16173","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\/16173","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=16173"}],"version-history":[{"count":3,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/posts\/16173\/revisions"}],"predecessor-version":[{"id":19165,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/posts\/16173\/revisions\/19165"}],"wp:attachment":[{"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/media?parent=16173"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/categories?post=16173"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ugto.mx\/rea\/wp-json\/wp\/v2\/tags?post=16173"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}