Tipos De Parsers En Un Compilador

Los analizadores de sintaxis siguen reglas de producción definidas a través de gramáticas libres de contexto. La forma en que las reglas de producción son implementadas (derivadas) se dividen en dos tipos de parsers: Top-Down y Bottom-Up

Top-down

Cuando el parser comienza a construir su árbol desde el símbolo de inicio e inmediatamente después trata de transformar el símbolo de inicio, entonces se le llama top-down parsing y hay dos formas de lograrlo.

• Parseo recursivo descendente:  Es una forma común de parseo. Es llamado recursivo pues usa procedimientos recursivos para procesar el código de entrada.
• Backtracking : Significa que si una derivación de la producción falla, La sintaxis del analizador reinicia el proceso usando diferentes reglas de la misma producción. Esta técnica puede procesar una cadena de entrada mas de una vez para determinar la regla de producción correcta.

Bottom-up

O en español de abajo a arriba, Como el nombre los sugiere, el parseo de abajo a arriba comienza a parser la entrada desde abajo hacia arriba y trata de construir el árbol de parseo hasta el símbolo de inicio.

Ejemplo:

cadena de entrada: a + b * c

Reglas de produccion:

S -> E
E -> E + T
E -> E * T
E -> T
T -> id

Comencemos de abajo hacia arriba

a + b * c

Leemos la cadena de entrada y revisamos si alguna de las reglas de producción encajan con la cadena de entrada.

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

En los posts subsecuentes estaremos construyendo ambos tipos de parsers.