Técnicas de Parsing: Top-Down y Bottom-Up

¿Cuáles son las técnicas más populares de parsing?

Según cómo se construya nuestro parsing tree, la estructura de datos en donde almacenaremos los Tokens que se generan al hacer el Análisis léxico de nuestro código fuente o Source Code, tendremos dos grandes tipos de técnicas de Parseo comúnmente utilizadas.

1. Top-Down Parsing (de arriba hacia abajo).

2. Bottom-Up Parsing (de abajo hacia arriba).

¿Para qué nos sirve un Parser?

Nos sirve para:

• Realizar un análisis de la sintaxis sin importar el contexto.
• Guiar el análisis que sí será sensitivo al contexto.
• Generar código intermedio.
• Reportar errores de sintaxis en caso de existir.
• Intentar corregir los errores (en caso que se desee).

En este curso utilizaremos un Top Down Parser, en combinación con la técnica Pratt Parsing.

¿Qué es pratt parsing?

Esta es una técnica que fue originalmente descrita por el Computer Scientist, Vaughn Pratt, en 1973. Cuando estás construyendo un Parser, usar la técnica de “Recursive Descent” o descenso recursivo es una de las más fáciles opciones que puedes tener y funciona de maravilla cuando puedes saber qué hacer después con base en el bloque de código que estás parseando. Esto, por ejemplo, con los statements de tu lenguaje, cuando cuentas con un identificador único, if, for, while, etc.

Sin embargo, se puede complicar cuando llegas a las expresiones, cuando utilizas operadores como +, ++, --, etc. Puede ser difícil de definir qué tipo de expresión estás parseando hasta que ya has avanzado bastante.

Esto lo puedes hacer utilizando descenso recursivo siempre y cuando crees una función única para la operación que busques, como cuando escribes un if para cada posible caso en tu programa. Puede ser tedioso.

También lo podrías hacer a través de bucles hasta que termines de parsear una expresión entera y con esto saber qué harás con ella, esto también es tedioso.

Y justo este es el problema que resolvió Pratt (de hecho, es usado, por ejemplo, en JSLint, la brillante herramienta de análisis de código que revisa si el código fuente en JavaScript que está analizando cumple con ciertas reglas a seguir, ya sabes funciona lo que antes de tomar estos cursos conocías como magia de tu Visual Studio Code).

En pocas palabras (y al ser algo que aprenderás a crear en las próximas clases) te diré lo que es: es un tipo de parsing que utiliza tanto bucles como recursividad para permitirnos manejar asociatividad y precedencia del objeto que estemos analizando.