Please enable JavaScript.

Coggle requires JavaScript to display documents.

Análisis sintáctico image, 4.3 Análisis sintáctico ascendente, 4.2.4.…

- - - - Consultando los estados finales del diagrama.
  - - - Consultando los estados que transitan al estado de aceptación.
  - - - Siguiendo las transiciones del diagrama,
  - - - Para comprobarlo
        
        Se plantea la construcción de la tabla de análisis LR(0).
        
        (1)<Bloque> ::= begin <Decs> ; <Ejecs> end
        (2)<Decs> ::= dec
        (3) | <Decs>;dec
        (4)<Ejecs> ::= ejec
        (5) | ejec ; <Ejecs>
        
        La gramática extendida añade la siguiente regla de producción:
        
        (0)<Bloque’> ::= <Bloque>$
    - - Es una técnica de análisis que simplifica la técnica LR
        
        Árbol de derivación de la palabra begin dec; ejec; ejec end por parte de la
        gramática GB.
        
        Efecto de la reducción de la regla <Ejecs>→ejec.
        
        Recorrido del analizador sintáctico sobre la cadena begin dec; ejec; ejec
        end si el estado s7 fuera sólo de reducción.
        
        Efecto de desplazar el símbolo ‘;’ en el análisis de la palabra begin dec;
        ejec; ejec end.
        
        Recorrido hasta el estado s7
        
        Que el análisis sintáctico debería realizar sobre el
        diagrama del analizador sintáctico
        
        Para analizar correctamente la cadena begin dec; ejec;
        ejec end.
        
        Que el análisis sintáctico debería realizar sobre el diagrama del analizador sintáctico
        
        Para analizar correctamente la cadena begin dec;
        ejec; ejec end.
        
        Recorrido hasta la última reducción
        
        Últimos pasos del recorrido
    - - Una gramática independiente del contexto G es una gramática SLR(1) si y sólo si su tabla de análisis SLR(1) es determinista, es decir, no presenta conflictos.
      - Análisis LR(1)
        
        Considérese Gaxb, ejemplo de una gramática que no es SLR(1).
        
        El símbolo b pertenece a si-
        guiente(B) a causa de las reglas A::=B y A::=aAb.
        
        Comparación entre los dos posibles recorridos previos a las reducciones de la regla B::=x: (a) en el estado s5, (b) en el estado s8.
        
        Construcción
        
        Desplazamientos.
        
        Reducciones.
        
        Aceptación.
        
        Error.
        
        1 more item...
        
        No se aplica el mismo proceso que en las tablas LR(0).
        
        No se aplica el mismo proceso que en las tablas LR(0) ni SLR(1).
        
        Igual que en LR(0), se obtienen siguiendo las transiciones del diagrama.
      - Diferencias entre los análisis LR(0) y LR(1).
        
        La configuración inicial del estado inicial
        
        Construcción de los conjuntos de símbolos de adelanto.
        
        Gramática aumentada.
        
        También es posible calcular este conjunto de la siguiente manera:
  - - - Excepto las reducciones
        
        La acción rk se añadirá sólo en las casillas correspondientes a las columnas
- - - - Realiza la derivación S→*x.
  - - - Reconstruye en sentido inverso la derivación S→*x.
- - - - Si X∈ΣN, primero(X) = {V | X →+ Vx, V∈ΣT, x∈Σ*}
      - Si X∈ΣT, primero(X) = {X}
      - siguiente(X) = {V | S →+ xXVy, X∈ΣN, V∈ΣT, x,y∈Σ*}, donde S es el axima.
  - - - Sea α=X1X2...Xn. Para calcular primero(α)
        
        Se aplicará el siguiente algoritmo:
        
        Añadir a primero(α) todos los símbolos de primero(X1), excepto λ.
        
        Si primero(X1) contiene λ, añadir a primero(α) todos los símbolos de primero(X2), excepto λ.
        
        Si primero(X1) y primero(X2) contienen λ, añadir a primero(α) todos los símbolos de primero(X3), excepto λ.
        
        Así sucesivamente.
        
        Si ∀i ∈ {1,2,..,n} primero(Xi) contiene λ, entonces añadir λ a primero(α).
- - - - Cada derivaciones es una submeta.
        
        (Caso 1) Xi=xi: submeta reconocida. Se pasa a la submeta siguiente.
        
        Este método puede ser ineficiente.
        
        Para mejorarlo se puede aplicar una variante del método, llamado análisis descendente con vuelta atrás rápida.
        
        (Caso 2) Xi≠xi y Xi es un símbolo terminal: submeta rechazada.
        
        (Caso 3) Xi es un símbolo no terminal. Se buscan las reglas de las que Xi es parte izquierda.
  - - - Son una familia de analizadores sintácticos descendentes en los que la entrada se lee desde la izquierda.
  - - - A ::= ax, donde A ∈ Σ N, a ∈ Σ T, x ∈ Σ N*
      - Dos condiciones:
        
        La parte derecha de las reglas empieza por un símbolo terminal
        
        seguido opcionalmente por símbolos no terminales.
        
        No existen dos reglas con la misma parte izquierda
        
        cuya parte derecha empiece por el mismo símbolo terminal.
    - - Una regla es recursiva a izquierdas si tiene la forma A ::= Ax, donde x ∈ Σ*.
      - Para convertir una gramática en otra equivalente, es preciso eliminar las reglas recursivas a izquierdas, si las hay.
    - - Si existen bucles de la forma Ai::=Ajα, Aj::=Aiβ, se elige un orden arbitrario entre los símbolos no terminales Ai y Aj.
      - Después de definir la relación de orden, se clasifican las reglas de P en:
        
        Reglas de la forma A ::= ax, donde a ∈ ΣT, x ∈ Σ*.
        
        Reglas de la forma Ai ::= Ajx, donde Ai < Aj y x ∈ Σ*.
        
        Reglas de la forma Ai ::= Ajx, donde Ai > Aj y x ∈ Σ*.
    - - Los símbolos no terminales se clasifican en:
        
        Símbolo no terminal sin regla-λ.
        
        Contiene las siguientes reglas:
        U::=x X1 X2...Xn | y Y1 Y2...Ym |...| z Z1 Z2...Zp
        
        Símbolo no terminal con
        regla-λ.
        
        Contiene las siguientes reglas:
        U ::= x X1 X2 ... Xn | ... | z Z1 Z2 ... Zp | λ
    - - Invocar la función correspondiente al axioma de la gramática con los argumentos x y 0.
        
        Si el valor devuelto por la función coincide con la longitud de la cadena de entrada
        
        La cadena queda reconocida.
        
        En caso contrario,
        
        la función devolverá un número negativo, que indica el error detectado.
- - - - LR(1) origina el automata de analisis LALR(1) una transicion (Sp, a)→Si_j
  - - - Debido al mecanismo de construccion del analizador LALR(1)
        
        NO SE PUEDEN AÑADIR CONFLICTOS REDUCCION/DESPLAZAMIENTO
- - - - SE DEFINEN
        
        first(U) = {V | U →+ Vx, V∈∑, x∈∑*}
        
        Estos conjuntos se calculan aplicando conceptos de la teoria algebraica de relaciones
        
        last(U) = {V | U →+ xV, V∈∑, x∈∑*}
- - - - si todos los elementos a∈A cumplen que aRa.
    - - si todos los elementos a,b,c∈A cumplen que aRb ∧ bRc ⇒ aRc.
    - - al producto de R por sí misma n veces.
  - - - para algun K positivo menor o igual
        
        Significa que A es finito
- - - - dos operaciones fundamentales:
        
        Reducción
        
        Se aplica cuando se ha identificado en la cadena de entrada
        
        Desplazamiento
        
        operación para avanzar un símbolo, simultáneamente en la cadena de entrada
- - - - diversas notaciones para las configuraciones LR(0).
        
        Notación explícita
        
        escribir la regla completa y marcar con un símbolo especial
        
        Notación de pares numéricos
        
        Identifica una configuración con un
        par de números.
  - - - pasos de un conjunto de configuraciones
        
        • Gramática aumentada.
        
        Operación de cierre.
        
        Operación ir a.
        
        Grafo de estados y transiciones del autómata
  - - - Desplazamientos
        
        Se obtienen siguiendo las transiciones del diagrama.
      - Reducciones.
        
        Se obtienen consultando los estados finales del diagrama
      - Aceptación.
        
        Se obtienen consultando los estados que transitan al estado de aceptación
      - Error.
        
        corresponden a errores sintácticos.
- - - - contienen una información equivalente a la función de transición
    - - La especificación completa del algoritmo general de análisis
        
        lenguaje asociado
        
        • Inicio del análisis
        
        • Desplazamiento
        
        • Reducción
        
        • Aceptación
        
        • Error