Introducción al análisis de sintaxis en el diseño de compiladores

Cuando se entrega una string de entrada (código fuente o un programa en algún idioma) a un compilador, el compilador la procesa en varias fases, comenzando desde el análisis léxico (escanea la entrada y la divide en tokens) hasta la generación del código de destino.

El Análisis Sintáctico o Parsing es la segunda fase, es decir, después del análisis léxico. Comprueba la estructura sintáctica de la entrada dada, es decir, si la entrada dada está en la sintaxis correcta (del idioma en el que se ha escrito la entrada) o no. Lo hace construyendo una estructura de datos, llamada árbol de análisis o árbol de sintaxis. El árbol de análisis se construye utilizando la gramática predefinida del idioma y la string de entrada. Si la string de entrada dada se puede producir con la ayuda del árbol de sintaxis (en el proceso de derivación), se encuentra que la string de entrada tiene la sintaxis correcta. si no, el analizador de sintaxis informa del error.

El autómata pushdown (PDA) se utiliza para diseñar la fase de análisis de sintaxis.

La gramática de una lengua consta de reglas de producción.

Ejemplo: supongamos que las reglas de producción para la gramática de un idioma son:

  S -> cAd
  A -> bc|a
  And the input string is “cad”.

Ahora el analizador intenta construir un árbol de sintaxis a partir de esta gramática para la string de entrada dada. Utiliza las reglas de producción dadas y las aplica según sea necesario para generar la string. Para generar la string «cad», utiliza las reglas que se muestran en el diagrama dado:

En el paso (iii) anterior, la regla de producción A->bc no era adecuada para aplicar (porque la string producida es «cbcd» y no «cad»), aquí el analizador debe retroceder y aplicar la siguiente regla de producción disponible con A que se muestra en el paso (iv), y se produce la string «cad».

Por lo tanto, la entrada dada puede ser producida por la gramática dada, por lo tanto, la entrada es correcta en la sintaxis. Pero se necesitaba retroceder para obtener el árbol de sintaxis correcto, que es realmente un proceso complejo de implementar.

Puede haber una manera más fácil de resolver esto, que veremos en el próximo artículo “Conceptos de conjuntos FIRST y FOLLOW en Compiler Design”.

Cuestionario sobre análisis de sintaxis

Este artículo ha sido compilado por Vaibhav Bajpai . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.