¡Bienvenidos a nuestra guía completa sobre los Fundamentos de Compiladores y Lenguajes! Este campo es esencial para entender cómo los programas que escribimos se transforman en instrucciones que una máquina puede ejecutar. Desde el análisis léxico hasta la generación de código, cada fase es crucial.En este artículo, exploraremos los principios clave, conceptos de sintaxis y semántica, y las herramientas utilizadas en la construcción de compiladores, todo explicado de forma clara y accesible para estudiantes. Prepárate para desentrañar el fascinante mundo detrás de cada línea de código.

Explorando los Fundamentos de Compiladores y Lenguajes

El estudio de los compiladores y lenguajes se adentra en la estructura y el comportamiento de los lenguajes de programación y los procesos para traducirlos. Aquí abordaremos desde la resolución de expresiones hasta el funcionamiento de autómatas, aspectos fundamentales para cualquier estudiante de informática.

Análisis de Expresiones en C: Prioridad y Asociatividad

Para entender cómo un compilador interpreta el código, es vital comprender la prioridad y asociatividad de los operadores. Tomemos como ejemplo la expresión 3-((2-1||5&&0)<r*s<=-1!=1).

La resolución de esta expresión sigue un orden estricto:

Paréntesis internos: (2-1||5&&0). Primero 2-1 (resultado 1). Luego 5&&0 (resultado 0). Así, queda (1||0).
Operador ||: 1||0 (resultado 1). La expresión se simplifica a 3-(1<r*s<=-1!=1).
Comparaciones de izquierda a derecha (<, <=): 1<r*s<=-1. El resultado de la comparación (1<r*s) será 0 o 1. Luego, (0 o 1)<=-1 resultará en 0 (falso).
Operador !=: 0!=1 (resultado 1).
Resta final: 3-1 (resultado 2).

La asociatividad del operador || es de IZQUIERDA A DERECHA, debido a la recursividad a izquierda en su definición BNF.
La prioridad del operador <= es MAYOR que la del operador !=, ya que está más lejos del axioma en la gramática.
La cantidad de derivaciones a derecha de la expresión es 1, determinada por la precedencia y asociatividad de los operadores.

Expresiones Regulares (ERX) y Tipos de Constantes Enteras

Las expresiones regulares son fundamentales en el análisis léxico para reconocer patrones. Analicemos cómo se aplican a las constantes enteras decimales, octales y hexadecimales.

[1-7]* | (33): No corresponde a ninguna constante, ya que acepta la palabra nula (Clausura de Kleene).
0[x-X]1FAG? | 0X[8-9]+: No corresponde a ninguna, debido al intervalo entre x y X.
[18]{4,7}: Corresponde a constante DECIMAL.
[5-7]+[1-34-5]?: Corresponde a constante DECIMAL.
03[1-3]*[4-7]*: Corresponde a constante OCTAL.
0 | (00)?: No corresponde a ninguna, ya que permite la palabra nula.
0[x-X]1(FA)? | 0X[8-9]+: No corresponde a ninguna, por el intervalo de x a X.
0x[1-f]{4,7}: No corresponde a ninguna, porque el intervalo [1-f] no es continuo en ASCII.
[3-9]+[2-45-7]?: Corresponde a constante DECIMAL.
| 0[1-5]{1,2}: No corresponde a ninguna, porque apunta a octales pero permite 8.
0x7AaF | 0XFA19?: Corresponde a constante HEXADECIMAL.
[1-9]*57: Corresponde a constante DECIMAL.

Análisis Léxico con Flex: Ejemplos Prácticos

El análisis léxico es la primera fase de la compilación, donde el código fuente se divide en lexemas (tokens). Usaremos reglas de flex para ilustrar este proceso.

Ejemplo 1: Cadena yyin: " 071711B H 696Ga234C7 "

Reglas de flex:

a= 3+3+696+3+3+3+3;
c= 1 [0-7]+ acumulador = acumulador + 3;
[a-z]+ contador += 1;
[0-9]{2,4} acumulador = acumulador + atoi(yytext);
[A-Ga-g] acumulador += 3;

Con acumulador = 0 y contador = 0 inicialmente:

Salida yyout: "H"
Total de lexemas reconocidos: 8
Valor final de acumulador: 714
Valor final de contador: 1
Emparejamientos por regla:
Regla 1: 3 veces
Regla 2: 1 vez
Regla 3: 1 vez
Regla 4: 3 veces

Ejemplo 2: Cadena yyin: " 000871G165Fazt850C05ag "

Reglas de flex (diferentes al ejemplo 1):

[1-9]+ ;
[a-z]+ contador += 1;
[0-8]{3,5} acumulador = acumulador + atoi(yytext);
[A-Fa-g] acumulador += 2;

Salida yyout: "Gztag"
Total de lexemas reconocidos: 7
Valor final de acumulador: 1724
Valor final de contador: 2
Emparejamientos por regla:
Regla 1: 3 veces
Regla 2: 2 veces
Regla 3: 1 vez
Regla 4: 1 vez

Sintaxis y Semántica en Compiladores

Una vez que el análisis léxico ha generado los tokens, las siguientes etapas del compilador, como el análisis sintáctico y semántico, verifican la estructura y el significado del programa.

Errores Léxicos, Sintácticos y Semánticos en C

Analicemos un fragmento de código C para identificar distintos tipos de errores:

Fragmento de código 1:

int funcion (float a, int b) {
 int b =.7E2, _c[3]={-1,2.0,5,4};
 a = b, a = c_[2];
 return {a+1};
}

Operadores y puntuación: No existe en una misma sentencia simple un caracter o par de caracteres que actúen como operador y puntuación de forma simultánea.
Corrección Léxica: Es léxicamente correcto. Todas las palabras pertenecen a alguna categoría léxica. Total de tokens: 50.
Corrección Sintáctica: Es sintácticamente INCORRECTO. La sentencia return {a+1}; no es estándar, ya que la gramática de C indica que return debe ir seguido de una expresión (opcional) y un ;. Las construcciones con sentencias compuestas ({...}) son extensiones no estándar de algunos compiladores como GCC.
Corrección Semántica: Es semánticamente INCORRECTO.
Doble declaración de la variable b.
Acceso a la variable c_ que no fue declarada (se confunde con _c).
Inicialización del arreglo _c con más elementos de los declarados.

Fragmento de código 2:

float ñ; // Error léxico aquí
int f() {
 return (("hola" + "chau") == "hola" ) == 1);
 b == a;
 b;
 e[5] = 4;
 return b
}

Corrección Léxica: Posee un error léxico debido a la ñ, que no pertenece al alfabeto inglés estándar y no es reconocido. Total de lexemas: 51 (o 54 si se sigue contando después del error).
Corrección Sintáctica: Posee un error sintáctico en la anteúltima línea (return b) por la ausencia del ;.
Corrección Semántica: Posee errores semánticos.
Intento de sumar strings ("hola" + "chau"), lo que es un conflicto de tipos. En C, los strings son punteros a char y su suma no tiene el significado esperado.
Acceso a e[5], fuera de los límites del arreglo e (si e se declaró con un tamaño menor a 6). Esto lleva a un comportamiento indefinido en tiempo de ejecución.
Asignar una cadena a una variable entera _ (si es que _ se declaró como entero y se toma la suma de literales).

Fragmento de código 3:

int funcion (char c, int d) {
 int _ = c, d[4]={1,2,3};
 d[4]=d[3], d[3] = _;
 return {_*d[5]};
}

Operadores y puntuación: La coma actúa como operador (d[4]=d[3]**,** d[3]=_) y como caracter de puntuación (int d[4]={1,2,3**};**), dentro de la misma sentencia compuesta.
Corrección Léxica: Es léxicamente correcto. Total de lexemas: 39.
Corrección Sintáctica: Es sintácticamente INCORRECTO. La sentencia return {_*d[5]}; es una extensión no estándar de C (como se explicó previamente).
Corrección Semántica: No posee errores semánticos. Es posible inicializar un arreglo con menos elementos de los declarados (el resto se inicializan en 0). Acceder a d[5] podría ser un error, pero el contexto sugiere que d podría haber sido redimensionado o la pregunta se centra en la inicialización.

Autómatas y Lenguajes Formales

Los autómatas finitos (AFDs) y las gramáticas son herramientas teóricas esenciales para definir y reconocer lenguajes. Comprender sus capacidades y limitaciones es clave en Fundamentos de Compiladores y Lenguajes.

Afirmaciones Clave sobre Autómatas y Gramáticas

Analicemos la veracidad de algunas afirmaciones relacionadas con autómatas y gramáticas:

Un AFD completo puede poseer estados inalcanzables. VERDADERO. La condición de ser completo no excluye la existencia de estados a los que no se pueda llegar desde el estado inicial.
El lenguaje L = { aⁿ bᵐ aⁿ / n>1, m>0 } no puede ser reconocido por un AFD. VERDADERO. Este lenguaje requiere una memoria (pila) para contar y comparar las a iniciales y finales, algo que los AFDs no poseen. Los AFDs solo reconocen lenguajes regulares.
Para hallar la intersección entre dos AFD es necesario que ambos posean único estado inicial y único estado final. FALSO. Un AFD siempre tiene un único estado inicial, pero puede tener múltiples estados finales. La intersección se define sobre el producto cartesiano de los conjuntos de estados finales.
Una gramática independiente de contexto (GIC) puede ser equivalente a una gramática regular (GR). VERDADERO. Las GR son un subconjunto de las GIC, por lo que toda GR tiene al menos una GIC equivalente. El recíproco no es cierto.
Las constantes enteras decimales de C son un subconjunto de las constantes reales de C. VERDADERO. Un entero puede ser expresado como un real sin pérdida de información (ej. 5 es 5.0).
Si una expresión es sintácticamente correcta, es derivable de la BNF. VERDADERO. Para ser sintácticamente correcta, debe cumplir con la derivabilidad de la BNF y las restricciones del lenguaje.
En el proceso de compilación la etapa de preprocesamiento puede ser eliminada. FALSO. Ninguna etapa puede ser eliminada, aunque en algunos casos su acción sea mínima (ej. sin directivas o comentarios que procesar).
Toda gramática independiente de contexto posee una gramática regular equivalente. FALSO. Las GIC son más potentes que las GR; no todas las GIC pueden simplificarse a GR.
La expresión de asignación: d = 1 = h es sintácticamente correcta. FALSO. El lado izquierdo de una asignación (Lvalue) debe ser modificable. 1 es una constante y no puede ser un Lvalue modificable.
Una gramática regular puede generar un lenguaje infinito. VERDADERO. Por ejemplo, S -> aS | b genera cadenas como b, ab, aab,..., que es un lenguaje infinito.
El AFD no puede reconocer lenguajes que no sean regulares. VERDADERO. Por definición, los AFDs solo reconocen lenguajes regulares.
Para hallar la unión entre dos AFD no es necesario que ambos posean un único estado inicial y un único estado final. FALSO. Los AFDs tienen un único estado inicial, pero pueden tener múltiples estados finales. Esto no impide calcular la unión.
Toda categoría léxica de C posee un AFD que la reconoce. VERDADERO. Las categorías léxicas (como identificadores, palabras reservadas) son lenguajes regulares y, por lo tanto, pueden ser reconocidas por un AFD.
Las palabras reservadas de C no son un subconjunto de los identificadores de C. VERDADERO. Son conjuntos disjuntos; una palabra reservada no puede ser utilizada como identificador.

Evaluación de Expresiones Complejas: Asociatividad y Prioridad

Analicemos otra expresión para solidificar la comprensión de la evaluación:

Expresión: ((3+c<(a||b)) == (7&&d) > 4)

Esta expresión depende de las variables a, b, c y d.

Paréntesis internos: (a||b) (resultado 0 o 1). Luego 3+c (resultado numérico). La comparación 3+c < (a||b) dará 0 o 1.
Segundo paréntesis interno: (7&&d) (resultado 0 o 1).
Comparación >: (0 o 1) > 4 siempre resultará 0 (falso), ya que 0 o 1 nunca son mayores que 4.
Operador ==: (0 o 1) == 0 (resultado final 0 o 1).

La asociatividad del operador == es de IZQUIERDA A DERECHA.
La prioridad del operador < es IGUAL que la del operador >, ya que están a la misma distancia del axioma en la BNF.
Si se reemplaza > por >= (((3+c<(a||b)) == (7&&d) >= 4)), el valor de la expresión sería EL MISMO, porque 0 o 1 nunca serán mayores o iguales a 4, manteniendo el resultado de esa subexpresión en 0.

Expresión: 2-c+d<e+f<g==1+3

Esta expresión depende de las variables c, d, e, f y g. Resolvamos paso a paso:

Suma/Resta de izquierda a derecha: c+d (resultado numérico). 2-(0|!0<0|!0+e<0==1)+3.
Suma/Resta de izquierda a derecha: 0|!0+e (resultado numérico). 2-(0|!0<0|!0<0==1)+3.
Operador < (mayor prioridad que ==) de izquierda a derecha: 0|!0<0|!0 (resultado 0 o 1). 2-(0|1<0==1)+3.
Operador <: 0|1<0 (resultado 0, ya que 0 o 1 nunca es menor que 0). 2-(0==1)+3.
Operador ==: 0==1 (resultado 0). 2-(0)+3.
Paréntesis: (0) (resultado 0). 2-0+3.
Suma/Resta de izquierda a derecha: 2-0 (resultado 2). Luego 2+3 (resultado 5).

El valor de la expresión siempre será 5.
La prioridad del operador || es MENOR que la del operador &&.
La asociatividad del operador - es de IZQUIERDA A DERECHA.

Preguntas Frecuentes sobre Compiladores y Lenguajes

Aquí respondemos algunas de las dudas más comunes que surgen al estudiar los Fundamentos de Compiladores y Lenguajes.

¿Qué es la prioridad y asociatividad de operadores?

La prioridad de operadores define el orden en que se evalúan diferentes tipos de operadores en una expresión (ej. * antes que +). La asociatividad define el orden de evaluación para operadores del mismo nivel de prioridad (ej. de izquierda a derecha para + o -). Ambas reglas son cruciales para que un compilador interprete correctamente las expresiones.

¿Cuál es la diferencia entre un error léxico, sintáctico y semántico?

Un error léxico ocurre cuando un carácter o secuencia de caracteres no forma un token válido (ej. un símbolo desconocido). Un error sintáctico se da cuando los tokens no siguen las reglas gramaticales del lenguaje (ej. return b sin ;). Un error semántico implica que el código, aunque gramaticalmente correcto, no tiene un significado válido o coherente (ej. doble declaración de una variable, suma de tipos incompatibles, o acceso a un índice fuera de un arreglo).

¿Pueden las gramáticas regulares generar lenguajes infinitos?

Sí, las gramáticas regulares pueden generar lenguajes infinitos. Un ejemplo claro es una producción como S -> aS | b, que permite repetir el símbolo a un número ilimitado de veces, generando cadenas como b, ab, aab, y así sucesivamente, lo cual constituye un lenguaje infinito.

¿Qué implicaciones tiene que un lenguaje no sea reconocido por un AFD?

Si un lenguaje no puede ser reconocido por un Automata Finito Determinista (AFD), significa que no es un lenguaje regular. Esto implica que el lenguaje requiere algún tipo de "memoria" para su reconocimiento, como una pila, característica de los autómatas de pila o máquinas de Turing. Los AFDs tienen capacidades limitadas para manejar dependencias entre elementos de una cadena que están distanciados, como aⁿbᵐaⁿ.

¿Por qué las palabras reservadas de C no son identificadores de C?

Las palabras reservadas de C (como int, if, while) tienen un significado predefinido y especial en el lenguaje. Por esta razón, no pueden ser utilizadas por el programador para nombrar variables, funciones u otros identificadores. Constituyen conjuntos disjuntos; intentar usar una palabra reservada como identificador resultaría en un error léxico o sintáctico, dependiendo del compilador.

Fundamentos de Compiladores y Lenguajes