Analizador de precedencia simple

En informática , un analizador sintáctico de precedencia simple es un tipo de analizador de abajo hacia arriba para gramáticas libres de contexto que solo pueden ser utilizadas por gramáticas de precedencia simple .

La implementación del analizador es bastante similar a la del analizador genérico ascendente . Se utiliza una pila para almacenar un prefijo viable de una forma oracional a partir de una derivación situada más a la derecha . Los símbolos ⋖, ≐ y ⋗ se utilizan para identificar el pivote y para saber cuándo cambiar o reducir .

Implementación

• Calcule la tabla de relación de precedencia de Wirth-Weber para una gramática con símbolo inicial S.
• Inicializar una pila con el marcador inicial $.
• Añade un marcador final $ a la cadena que se está analizando ( Entrada ).
• Hasta que la pila sea igual a "$ S" y la entrada sea igual a "$"
  • Busque en la tabla la relación entre Top(stack) y NextToken(Input)
  • si la relación es ⋖ o ≐
    • Cambio :
    • Push(Pila, relación)
    • Push(Pila, SiguienteToken(Entrada))
    • Eliminar siguiente token (entrada)
  • Si la relación es ⋗
    • Reducir :
    • BuscarProducciónParaReducir(Pila)
    • Quitar el pivote de la pila
    • Busque en la tabla la relación entre el no terminal de la producción y el primer símbolo en la pila (comenzando desde arriba)
    • Push(Pila, relación)
    • Push(Pila, No terminal)

Búsqueda de producción para reducir (pila)

• Encuentra el ⋖ más alto en la pila; este y todos los símbolos encima de él son el Pivote .
• Encuentra la producción de la gramática que tiene el Pivote como su lado derecho.

Ejemplo

Dado el siguiente lenguaje, que puede analizar expresiones aritméticas con las operaciones de multiplicación y suma:

E --> E + T' | T'T'--> TV --> V * F | FF --> ( E' ) | numMi' --> Mi

num es una terminal y el analizador léxico analiza cualquier entero como num ; E representa una expresión aritmética, T es un término y F es un factor.

y la tabla de análisis:

ACCIÓN DE ENTRADA DE PRECEDENCIA DE PILA$ ⋖ 2 * ( 1 + 3 )$ DESPLAZAMIENTO$ ⋖ 2 ⋗ * ( 1 + 3 )$ REDUCIR (F -> núm)$ ⋖ F ⋗ * ( 1 + 3 )$ REDUCIR (V -> F)$ ⋖ T ≐ * ( 1 + 3 )$ DESPLAZAMIENTO$ ⋖ T ≐ * ⋖ ( 1 + 3 )$ DESPLAZAMIENTO$ ⋖ T ≐ * ⋖ ( ⋖ 1 + 3 )$ DESPLAZAMIENTO$ ⋖ T ≐ * ⋖ ( ⋖ 1 ⋗ + 3 )$ REDUCIR 4× (F -> num) (T -> F) (T' -> T) (E ->T ')$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + 3 )$ DESPLAZAMIENTO$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + ⋖ 3 )$ DESPLAZAMIENTO$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + < 3 ⋗ )$ REDUCIR 3× (F -> num) (T -> F) (T' -> T)$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + ≐ T ⋗ )$ REDUCIR 2× (E -> E + T) (E' -> E)$ ⋖ T ≐ * ⋖ ( ≐ E' ≐ )$ DESPLAZAMIENTO$ ⋖ T ≐ * ⋖ ( ≐ E' ≐ ) ⋗ $ REDUCIR (F -> ( E' ))$ ⋖ T ≐ * ≐ F ⋗ $ REDUCIR (T -> T * F)$ ⋖ T ⋗ $ REDUCIR 2× (T' -> T) (E -> T')$ ⋖ E $ ACEPTAR

Referencias

• Alfred V. Aho, Jeffrey D. Ullman (1977). Principios de diseño de compiladores . Primera edición. Addison–Wesley.
• William A. Barrett, John D. Couch (1979). Construcción de compiladores: teoría y práctica . Investigador asociado en ciencias.
• Jean-Paul Tremblay, PG Sorenson (1985). La teoría y la práctica de la escritura de compiladores . McGraw-Hill.