Fase sintáctica (Segunda fase)

Análisis sintáctico

El análisis de sintaxis consiste en descubrir la estructura del código. Determina si un texto sigue o no el formato esperado. El objetivo principal de esta fase es asegurarse de que el código fuente escrito por el programador sea correcto o no.
El análisis de sintaxis se basa en las reglas basadas en el lenguaje de programación específico mediante la construcción del árbol de análisis con la ayuda de tokens. También determina la estructura del idioma de origen y la gramática o sintaxis del idioma.

Figura 5. Analizador sintáctico.

Curso Compiladores UAEH. (2010, noviembre). Unidad III: Analizador sintáctico. Recuperado de https://cursocompiladoresuaeh.blogspot.com/2010/11/unidad-iii-analizador-sintactico.html

En esta Figura 5 vemos la estructura del analizador sintáctico así como su conexión con la fase léxica.

¿Qué es una gramática libre de contexto?

Una gramática libre de contexto (GLC) es un conjunto de reglas que describe cómo formar cadenas válidas en un lenguaje. Es una herramienta fundamental en la construcción de compiladores, ya que define las estructuras sintácticas válidas de un lenguaje de programación.
Se llama "libre de contexto" porque las reglas no dependen del contexto en el que se aplican: cada regla se evalúa de manera independiente.

Gramática: G(N,T,P,S)

N=No terminales 

T=Terminales 

P=Reglas de producción 

S=Axioma inicia 

 

Componentes de una GLC para nuestro lenguaje

1. Conjunto de símbolos no terminales (N):

   • Representan conceptos o categorías del lenguaje, como "declaración" o "expresión".
   • Ejemplo en nuestro lenguaje: programa, declaración, expresión.

2. Conjunto de símbolos terminales (Σ):

   • Son los tokens generados por el analizador léxico.
   • Ejemplo en nuestro lenguaje: palabras clave (si, imprime), operadores (+, =), y delimitadores ({, }).

3. Conjunto de reglas de producción (P):

   • Definen cómo los no terminales se expanden en secuencias de terminales y no terminales.
   • Ejemplo: programa → declaración_lista.

4. Símbolo inicial (S):

   • Es el punto de partida de la gramática.
   • En nuestro caso: S = programa

Composición de nuestra gramática

El mini lenguaje de C en español tiene las siguientes características:

Símbolos no terminales (N):

• Programa: Representa el programa completo.
• Declaración_lista: Una lista de declaraciones.
• Declaración: Una declaración individual.
• Asignación, estructura_control, impresión: Tipos de declaraciones.
• Bloque: Un bloque de código delimitado por { y }.
• Expresión, término, factor: Partes de una expresión aritmética.

Símbolos terminales (Σ):

Estos son los tokens producidos por la fase léxica:

• Palabras clave: si, imprime, mientras.
• Operadores: +, -, *, /, =, >, <, >=, <=, ==, !=.
• Símbolos especiales: {, }, (, ), ;.
• Otros: IDENTIFICADOR, NUMERO, CADENA.

Reglas de producción (P):

En este punto utilizaremos las reglas de producción de las expresiones aritméticas de nuestro lenguaje en español:

Las expresiones aritméticas pueden incluir sumas, restas, multiplicaciones y divisiones, con precedencia adecuada:

Figura 6. Reglas de producción.

La Figura 6 enseña la forma en la que se debe de estructurar las expresiones aritméticas en este caso las operaciones dentro del lenguaje. 

Árboles de derivación

Un árbol de derivación es una representación gráfica que muestra cómo una cadena de entrada (como el código fuente) se deriva utilizando una gramática libre de contexto.

En este árbol:

• Cada nodo interno representa un símbolo no terminal.
• Cada hoja representa un símbolo terminal (token generado por el analizador léxico).
• La raíz del árbol es el símbolo inicial de la gramática.
• Las ramas del árbol siguen las reglas de producción de la gramática.

Ejemplo: Árbol de derivación para una asignación

Supongamos que tenemos el siguiente fragmento de código en nuestro lenguaje de figuras geométricas:x = x + 1;

Y la gramática que define la estructura de este lenguaje es Figura 6:

Figura 6. Reglas de producción.

Esto significa que una asignación está compuesta por:

• Un IDENTIFICADOR (el nombre de una variable).
• El símbolo "=" (el operador de asignación).
• Una expresión que produce un valor.
• El símbolo ";" que marca el final de la asignación.

Árbol Sintáctico:

El árbol sintáctico para el código x = x + 1; es el siguiente:

Basándonos en la gramática y el código, el árbol sintáctico se construye de la siguiente manera:

Figura 8. Árbol sintáctico.

Explicación del árbol

1. Raíz:

   • La raíz es asignación, ya que es el punto de entrada para esta gramática.

2. Hijos inmediatos:

   • El lado izquierdo de la asignación se deriva como IDENTIFICADOR (x).
   • El operador = aparece directamente como un terminal.
   • El lado derecho es una expresión, que se expande según sus reglas.

3. Expansión de la expresión:

   • La expresión se descompone en términos (término), que se conectan con el operador "+".

4. Términos y factores:

   • El primer término es un factor que resulta ser un IDENTIFICADOR (x).
   • El segundo término es un factor que resulta ser un NUMERO (1).

Dejo el link de un video para conocer mas del tema:

Alex Ortega Díaz. (2018, 13 agosto). Fases del compilador Análisis léxico, sintáctico y semántico [Vídeo]. YouTube. https://www.youtube.com/watch?v=7sAU-7z0X1E

Referencias:

Urrutia, D. (2024, 1 noviembre). Qué es un analizador sintáctico o parser | Definición, significado y para qué sirve. Arimetrics. https://www.arimetrics.com/glosario-digital/analizador-sintactico-parser

Cerulean, K. (2024, 26 septiembre). Phases of Compiler with Example: Compilation Process & Steps. Guru99. https://www.guru99.com/es/compiler-design-phases-of-compiler.html