Analizador de precedencia simple

En informática , un analizador de precedencia simple es un tipo de analizador ascendente para gramáticas libres de contexto que sólo pueden ser utilizados por gramáticas de precedencia simple .

La implementación del analizador es bastante similar a la del analizador ascendente genérico . Una pila se utiliza para almacenar un prefijo viable de una forma de oración 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 desplazar o cuándo reducir .

Implementación

• Calcule la tabla de relaciones de precedencia de Wirth-Weber para una gramática con símbolo inicial S.
• Inicializa una pila con el marcador inicial $.
• Agregue 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 :
    • Empujar (pila, relación)
    • Empujar (pila, siguiente token (entrada))
    • EliminarNextToken(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 de la pila (comenzando desde arriba)
    • Empujar (pila, relación)
    • Empujar (apilado, sin terminal)

SearchProductionToReduce (pila)

• Encuentra el ⋖ superior en la pila; Este y todos los símbolos que aparecen encima son el Pivote .
• Encuentre la producción de la gramática que tiene el Pivote como lado derecho.

Ejemplo

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

mi --> mi + T' | T'T' --> TT --> T * F | FF --> ( mi ' ) | númeromi' --> mi

num es una terminal y el lexer analiza cualquier número 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 ) $ CAMBIO$ ⋖ 2 ⋗ * ( 1 + 3 )$ REDUCIR (F -> núm)$ ⋖ F ⋗ * ( 1 + 3 )$ REDUCIR (T -> F)$ ⋖ T ≐ * ( 1 + 3 ) $ MAYÚS$ ⋖ T ≐ * ⋖ ( 1 + 3 ) $ MAYÚS$ ⋖ T ≐ * ⋖ ( ⋖ 1 + 3 ) $ MAYÚS$ ⋖ T ≐ * ⋖ ( ⋖ 1 ⋗ + 3 )$ REDUCIR 4× (F -> num) (T -> F) (T' -> T) (E ->T ')$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + 3 ) $ MAYÚS$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + ⋖ 3 ) $ MAYÚS$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + < 3 ⋗ )$ REDUCIR 3× (F -> num) (T -> F) (T' -> T)$ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + ≐ T ⋗ )$ REDUCIR 2× (E -> E + T) (E' -> E)$ ⋖ T ≐ * ⋖ ( ≐ E ' ≐ ) $ MAYÚS$ ⋖ 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 del diseño de compiladores . 1ª Edición. Addison-Wesley.
• William A. Barrett, John D. Couch (1979). Construcción de compiladores: teoría y práctica . Asociado de Investigación Científica.
• Jean-Paul Tremblay, PG Sorenson (1985). La teoría y práctica de la escritura compiladora . McGraw-Hill.