Diseño del compilador: tipos de análisis

Los analizadores de sintaxis siguen reglas de producción definidas mediante gramática libre de contexto. La forma en que se implementan las reglas de producción (derivación) divide el análisis sintáctico en dos tipos: análisis de arriba hacia abajo y análisis de abajo hacia arriba.

Análisis de arriba hacia abajo

Cuando el analizador comienza a construir el árbol de análisis sintáctico desde el símbolo de inicio y luego intenta transformar el símbolo de inicio en la entrada, se denomina análisis de arriba hacia abajo.

• Recursive descent parsing: Es una forma común de análisis de arriba hacia abajo. Se llama recursivo porque utiliza procedimientos recursivos para procesar la entrada. El análisis sintáctico de descenso recursivo sufre retroceso.

• Backtracking: Significa que si falla una derivación de una producción, el analizador de sintaxis reinicia el proceso usando diferentes reglas de la misma producción. Esta técnica puede procesar la cadena de entrada más de una vez para determinar la producción correcta.

Análisis de abajo hacia arriba

Como sugiere el nombre, el análisis de abajo hacia arriba comienza con los símbolos de entrada e intenta construir el árbol de análisis hasta el símbolo de inicio.

Example:

Cadena de entrada: a + b * c

Reglas de producción:

S → E
E → E + T
E → E * T
E → T
T → id

Comencemos a analizar de abajo hacia arriba

a + b * c

Lea la entrada y verifique si alguna producción coincide con la entrada:

a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S