Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 44 vistas

    Análisis Ascendente

    Cargado por

    Jhon Carlos Castillo Atencio
    El análisis ascendente construye el árbol sintáctico de una cadena de entrada desde las hojas (los símbolos terminales) hasta la raíz (el axioma). Existen dos tipos principales: con retroceso, que intenta todas las posibles operaciones mediante fuerza bruta, y sin retroceso, que busca una derivación derecha de forma determinista aplicando gramáticas LR. Los analizadores LR tienen la ventaja de poder reconocer prácticamente cualquier gramática CFG, pero la desventaja es que su construcción es compleja y requiere de generadores automátic

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    Análisis Ascendente

    Cargado por

    Jhon Carlos Castillo Atencio
    44 vistas4 páginas
    El análisis ascendente construye el árbol sintáctico de una cadena de entrada desde las hojas (los símbolos terminales) hasta la raíz (el axioma). Existen dos tipos principales: con retroceso, que intenta todas las posibles operaciones mediante fuerza bruta, y sin retroceso, que busca una derivación derecha de forma determinista aplicando gramáticas LR. Los analizadores LR tienen la ventaja de poder reconocer prácticamente cualquier gramática CFG, pero la desventaja es que su construcción es compleja y requiere de generadores automátic

    Título original

    ANÁLISIS ASCENDENTE

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El análisis ascendente construye el árbol sintáctico de una cadena de entrada desde las hojas (los símbolos terminales) hasta la raíz (el axioma). Existen dos tipos principales: con retroceso, que intenta todas las posibles operaciones mediante fuerza bruta, y sin retroceso, que busca una derivación derecha de forma determinista aplicando gramáticas LR. Los analizadores LR tienen la ventaja de poder reconocer prácticamente cualquier gramática CFG, pero la desventaja es que su construcción es compleja y requiere de generadores automátic

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    44 vistas4 páginas

    Análisis Ascendente

    Cargado por

    Jhon Carlos Castillo Atencio
    El análisis ascendente construye el árbol sintáctico de una cadena de entrada desde las hojas (los símbolos terminales) hasta la raíz (el axioma). Existen dos tipos principales: con retroceso, que intenta todas las posibles operaciones mediante fuerza bruta, y sin retroceso, que busca una derivación derecha de forma determinista aplicando gramáticas LR. Los analizadores LR tienen la ventaja de poder reconocer prácticamente cualquier gramática CFG, pero la desventaja es que su construcción es compleja y requiere de generadores automátic

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    Está en la página 1de 4

    ANÁLISIS ASCENDENTE

    Parte de la cadena de entrada para construir la inversa de una derivación por la


    derecha. Genera el árbol de análisis sintáctico partiendo de las hojas hasta
    alcanzar el axioma.
    Análisis ascendente se construye el árbol de análisis sintáctico de la cadena de
    entrada desde las hojas hasta la raíz. En las hojas tenemos la cadena a
    analizar (los símbolos terminales) que se intentan reducir al axioma, que se
    encontrara en la raíz, si la cadena es correcta sintácticamente.
    Análisis Ascendente con retroceso
    Al igual que ocurría con el caso descendente, este tipo de análisis intenta
    probar todas las posibles operaciones (reducciones y desplazamientos)
    mediante un método de fuerza bruta, hasta llegar al árbol sintáctico, o bien
    agotar todas las opciones, en cuyo caso la cadena se rechaza.
    En el análisis con retroceso no se permiten las reglas ԑ, puesto que estas se
    podrán aplicar de forma indefinida.
    Análisis Ascendente sin retroceso
     El análisis ascendente sin retroceso busca una derivación derecha de la
    cadena de entrada de forma determinista.
     Este se sustenta en su aplicación a las gramáticas LR(K).
     La L viene de la lectura de la cadena de entrada de izquierda a derecha.
     La R de producir un árbol de derivación derecho.
     La k indica el número de símbolos que es necesario leer a la entrada
    para tomar la decisión de qué producción emplear.
     Un parser del tipo shift-reduce puede verse como un autómata de pila
    determinista extendido que realiza el análisis de abajo hacia arriba.
     Dada una cadena de entrada w, simula una derivación más a la derecha.
    Ventajas de los Analizadores LR
     El conjunto de gramáticas LL es un subconjunto propio de las
    gramáticas LR.
     Es posible construir un analizador sintáctico LR para reconocer
    prácticamente la totalidad de las construcciones de los lenguajes de
    programación que se pueden definir mediante gramáticas CFG.
     El método de análisis LR es el método del tipo shift-reduce, sin
    retroceso, más general que se conoce, pero además su aplicación es
    tan eficiente como la de otros métodos shift-reduce menos generales.
     Los errores pueden detectarse tan pronto como sea posible hacerlo, en
    un examen de la entrada de izquierda a derecha.
    Desventajas de los Analizadores LR
    Como desventaja principal podemos indicar la de que construir un
    analizador sintáctico de este tipo para una gramática dada es demasiado
    complejo como para intentar hacerlo a mano.
    Para ello se deben usar generadores de analizadores automáticos como
    YACC.
    Ejemplo:
    Entrada = abcdef
    Pila vacía

    Avanza
    Pila = a

    Reduce A->a
    Pila = A

    Avanza
    Pila = Ab
    Reduce B->Ab
    Pila = B

    Avanza
    Pila = Bc

    Avanza
    Pila = Bcd

    Avanza.
    Pila = Bcde
    (Secuencia de prefijos de partes derechas)

    Avanza
    Pila = Bcdef

    Reduce C->ef
    Pila = BcdC

    Reduce D->C
    Pila = BcdD

    Reduce E->dD
    Pila = BcE

    Reduce F->epsilon
    Pila = BcEF
    (Pila crece sin consumir
    entrada)
    Reduce S->BcEF
    Pila = S
    (Fin del reconocimiento)

    También podría gustarte