Como crear un analizador sintáctico
Disclaimer: Para entender este articulo necesitaras conocimientos de cómo funciona un compilador, un analizador LR, reglas gramáticas e INGLÉS.
¿Qué es un analizador sintáctico y donde se usa?
Un analizador sintáctico es parte del compilador, se encarga de revisar todas las palabras y caracteres en el programa y se asegura que todo tenga un sentido y este en su lugar. Esto es realizado revisando las reglas de gramática que será cargada, y asegurándose que cumpla con cada una de las reglas que empieza.
¿Dónde empezar?
Necesitas saber que el analizador sintáctico ya es la segunda parte del compilador, esto significa que antes de esto, un analizador léxico es llamado para asegurarse de que todos los caracteres y palabras sean un token y así crear una lista de tokens para que el analizador sintáctico lo use.
También necesitaras otras dos cosas, un archivo o dos donde se encuentren las reglas de la gramática en texto plano, con todas las reglas, el número de reglas y la cantidad de ítems a desapilar, y otro que será la tabla LR que solo serán números, 0 será null, los números positivos serán desplazamientos, y los negativos serán reglas.
1.- Archivo de las reglas LR con su número de regla y el número de ítems a desapilar. (Ejemplo)
2.- Archivo de tabla LR. (Ejemplo)
Algoritmo
Antes que nada, mencionamos que necesitaremos una lista de tokens(o COLA así será como nos vamos a referir a él en el algoritmo, pues siempre se va solo necesitar el primer ítem en la cola) , también necesitaremos una PILA de enteros (o cualquier clase que estas usando en caso de querer regresar un árbol sintáctico, pero en el algoritmo de este articulo NO se crea un árbol, solo se verifica que sea correcta la sintaxis) y esa pila la inicializaremos con un 0 como primer valor, las reglas leídas estarán en una lista de reglas, y la tabla LR en un arreglo bidimensional.
Ahora solo sigue este algoritmo (ESTA EN INGLES):
3.- Algoritmo del analizador sintáctico
De esta manera, al final, solo tendrás dos caminos al acabar el algoritmo, si fue aceptado o si hubo un error, y así, tu analizador sintáctico estará listo para leer todos los programas que cumplan con las reglas que insertaste.
