🏗️ Compiladores y teoría de la computación

1. ¿Cuál es la primera fase de la etapa de análisis de un compilador, encargada de agrupar los caracteres de la entrada en tokens (componentes elementales del programa fuente)?

1. El análisis léxico
2. El análisis sintáctico
3. El análisis semántico
4. La generación de código intermedio

El análisis léxico (scanner) es la primera fase del front-end y agrupa los caracteres en tokens; el análisis sintáctico y semántico operan después, sobre esos tokens. (Aho, Lam, Sethi, Ullman, Compiladores: principios, técnicas y herramientas, 2a ed., cap. 1.)

2. En la fase de análisis léxico de un compilador, ¿qué formalismo se emplea típicamente para especificar los patrones que definen cada tipo de token?

1. Las expresiones regulares
2. Las gramáticas libres de contexto
3. Los árboles de sintaxis abstracta
4. Las tablas de símbolos

El análisis léxico usa expresiones regulares (implementadas mediante autómatas finitos) para reconocer patrones de tokens; las gramáticas libres de contexto se usan en la fase sintáctica. (Aho, Lam, Sethi, Ullman, Compiladores, 2a ed., cap. 3.)

3. ¿Qué fase de un compilador verifica que la secuencia de tokens producida por el analizador léxico cumpla las reglas de una gramática libre de contexto y construye el árbol de análisis (parse tree)?

1. El análisis sintáctico
2. El análisis léxico
3. El análisis semántico
4. La optimización de código

El análisis sintáctico (parser) recibe los tokens y construye el árbol de análisis conforme a una gramática libre de contexto; el léxico solo produce tokens y el semántico revisa significado, no estructura. (Aho, Lam, Sethi, Ullman, Compiladores, 2a ed., cap. 4.)

4. Un programa escrito en un lenguaje fuertemente tipado intenta sumar directamente un valor entero con una cadena de texto, sin ninguna conversión explícita, y el compilador reporta un error de incompatibilidad de tipos. ¿En qué fase del compilador se detecta este error?

1. En el análisis semántico
2. En el análisis léxico
3. En el análisis sintáctico
4. En la generación de código objeto

La verificación de tipos es tarea del análisis semántico, que revisa el significado de construcciones ya validadas sintácticamente; el léxico y el sintáctico solo revisan tokens y estructura gramatical. (Aho, Lam, Sethi, Ullman, Compiladores, 2a ed., cap. 1.)

5. Un analizador sintáctico construye el árbol de derivación partiendo del símbolo inicial de la gramática y expandiéndolo hacia los tokens de la entrada, como hacen los analizadores de tipo LL. Este método de análisis se clasifica como:

1. Descendente (top-down)
2. Ascendente (bottom-up)
3. Léxico
4. Semántico

Los analizadores LL parten del símbolo inicial y expanden hacia abajo, por lo que se llaman descendentes; los analizadores LR/SLR/LALR parten de los tokens y reducen hacia el símbolo inicial (ascendentes). (Aho, Lam, Sethi, Ullman, Compiladores, 2a ed., cap. 4.)

6. ¿Cuál de las siguientes es una herramienta clásica utilizada para generar analizadores léxicos a partir de expresiones regulares?

1. Lex (o Flex)
2. Yacc (o Bison)
3. ANTLR
4. LLVM

Lex y su variante Flex generan analizadores léxicos a partir de expresiones regulares; Yacc/Bison y ANTLR generan analizadores sintácticos, y LLVM es una infraestructura para generación y optimización de código. (Aho, Lam, Sethi, Ullman, Compiladores, 2a ed., cap. 3.)

7. Una gramática libre de contexto es ambigua: existe al menos una cadena que admite dos árboles de derivación distintos. ¿Qué consecuencia práctica tiene esta ambigüedad para el diseño de un analizador sintáctico determinista, como uno de tipo LL o LR?

1. El analizador no puede decidir de manera única qué derivación aplicar, generando conflictos de análisis
2. El analizador léxico deja de reconocer los tokens de la cadena
3. El árbol de análisis sintáctico se vuelve equivalente al árbol de análisis semántico
4. La gramática deja de pertenecer a la jerarquía de Chomsky

La ambigüedad impide que un analizador determinista elija una única derivación, generando conflictos de análisis; esto no afecta al analizador léxico ni cambia el tipo de la gramática en la jerarquía de Chomsky. (Aho, Lam, Sethi, Ullman, Compiladores, 2a ed., cap. 4.)

8. ¿Cuál de las siguientes fases forma parte de la etapa de síntesis (back-end) de un compilador, y no de la etapa de análisis (front-end)?

1. La generación de código objeto (código máquina)
2. El análisis léxico
3. El análisis sintáctico
4. El análisis semántico

La generación de código objeto pertenece a la etapa de síntesis (back-end), que traduce la representación intermedia a código máquina; el análisis léxico, sintáctico y semántico forman la etapa de análisis (front-end). (Aho, Lam, Sethi, Ullman, Compiladores, 2a ed., cap. 1.)

9. ¿Cuál de las siguientes actividades NO es una fase reconocida de un compilador dentro del modelo clásico de análisis y síntesis?

1. La recolección de basura en tiempo de ejecución
2. El análisis léxico
3. El análisis semántico
4. La generación de código intermedio

La recolección de basura es una actividad del entorno de ejecución (runtime), no una fase del compilador; el análisis léxico, semántico y la generación de código intermedio sí son fases reconocidas del modelo clásico. (Aho, Lam, Sethi, Ullman, Compiladores, 2a ed., cap. 1.)

10. ¿Cómo se define formalmente un autómata finito determinista (AFD)?

1. Como una 5-tupla (Q, Σ, δ, q0, F)
2. Como una 7-tupla (Q, Σ, Γ, δ, q0, Z0, F)
3. Como una 4-tupla (Q, Σ, δ, F)
4. Como una 6-tupla (Q, Σ, δ, q0, F, Γ)

Un AFD se define como la 5-tupla (Q, Σ, δ, q0, F): estados, alfabeto, función de transición, estado inicial y estados de aceptación; la 7-tupla con Γ y Z0 corresponde a un autómata de pila. (Hopcroft, Motwani, Ullman, Introduction to Automata Theory, Languages, and Computation, 3a ed., cap. 2.)

11. Un AFD reconoce las cadenas binarias con un número par de unos. Tiene dos estados: q0 (inicial y de aceptación, número par de unos leídos) y q1 (número impar de unos leídos). Su tabla de transición es: δ(q0,0)=q0, δ(q0,1)=q1, δ(q1,0)=q1, δ(q1,1)=q0. ¿Cuál de las siguientes cadenas es aceptada por este autómata?

1. 1001
2. 1101
3. 1110
4. 1011

La cadena 1001 contiene exactamente dos unos (número par), por lo que el autómata termina en q0 y acepta; las otras tres cadenas contienen tres unos (número impar) y terminan en q1, sin ser aceptadas. (Hopcroft, Motwani, Ullman, Introduction to Automata Theory..., cap. 2 (tabla de transición de un AFD).)

12. ¿Cuál es la diferencia formal entre la función de transición de un AFD y la de un AFN?

1. En el AFD, δ: Q×Σ→Q (exactamente un estado siguiente); en el AFN, δ: Q×Σ→P(Q) (cero, uno o varios estados)
2. En el AFD la función de transición admite transiciones vacías (ε) y en el AFN no las admite
3. En el AFD el alfabeto de entrada es infinito y en el AFN es finito
4. En el AFD el conjunto de estados de aceptación F contiene un único estado, y en el AFN puede contener varios

La diferencia formal está en el codominio de δ: el AFD mapea a un único estado (Q) y el AFN a un subconjunto de estados (P(Q)), incluyendo transiciones ε; el alfabeto y el tamaño de F no distinguen a ambos modelos. (Hopcroft, Motwani, Ullman, Introduction to Automata Theory..., cap. 2.)

13. Un AFD tiene estados {q0, q1, q2}, alfabeto {0, 1}, estado inicial q0 y único estado de aceptación q2. Su tabla de transición es: δ(q0,0)=q1, δ(q0,1)=q0, δ(q1,0)=q2, δ(q1,1)=q0, δ(q2,0)=q2, δ(q2,1)=q2. ¿Cuál de las siguientes cadenas es aceptada por este autómata?

1. 100
2. 010
3. 101
4. 011

Con la cadena 100 el autómata recorre q0→q0→q1→q2, terminando en el estado de aceptación q2 (reconoce cadenas que contienen la subcadena 00); las otras tres cadenas terminan en q0 o q1, sin ser aceptadas. (Hopcroft, Motwani, Ullman, Introduction to Automata Theory..., cap. 2 (simulación sobre tabla de transición).)

14. Se tiene un AFN con 4 estados. Al aplicarle el algoritmo de construcción de subconjuntos (subset construction) para obtener un AFD equivalente, ¿cuál es el número MÁXIMO de estados que puede tener el AFD resultante?

1. 16
2. 8
3. 4
4. 24

El teorema de la construcción de subconjuntos garantiza que un AFN de n estados produce un AFD de a lo sumo 2^n estados; con n=4 el máximo es 2^4=16, no una simple duplicación (8) ni el mismo número de estados (4). (Hopcroft, Motwani, Ullman, Introduction to Automata Theory..., cap. 2 (teorema de subconjuntos).)

15. Según el teorema de Kleene, ¿cuáles de los siguientes formalismos son equivalentes entre sí en poder expresivo?

1. El autómata finito, la expresión regular y la gramática regular (Tipo 3)
2. El autómata de pila, la expresión regular y la gramática libre de contexto
3. La máquina de Turing, el autómata finito y la gramática regular
4. El autómata de pila, la gramática libre de contexto y la máquina de Turing

El teorema de Kleene establece la equivalencia entre autómatas finitos, expresiones regulares y gramáticas regulares (Tipo 3); el autómata de pila corresponde a las gramáticas libres de contexto (Tipo 2), un nivel distinto de la jerarquía. (Kleene (1956); Hopcroft, Motwani, Ullman, Introduction to Automata Theory..., cap. 3.)

16. En una tabla de transición de un autómata finito escrita en forma de texto, ¿qué convención se usa habitualmente para señalar el estado inicial?

1. Una flecha (->) colocada junto a ese estado
2. Un asterisco (*) colocado junto a ese estado
3. Un círculo doble alrededor del estado
4. El subrayado del nombre del estado

Por convención, el estado inicial se marca con una flecha (->) y los estados de aceptación con un asterisco (*); el círculo doble es una convención de los diagramas de estados, no de las tablas. (Hopcroft, Motwani, Ullman, Introduction to Automata Theory..., cap. 2.)

17. Un AFN tiene, desde el estado q0 y con el símbolo 'a', transiciones simultáneas hacia q1 y hacia q2. ¿Qué algoritmo permite convertir este AFN en un AFD equivalente que reconozca exactamente el mismo lenguaje?

1. La construcción de subconjuntos (subset construction)
2. El lema del bombeo
3. La eliminación de recursividad izquierda
4. La factorización por la izquierda

La construcción de subconjuntos convierte cualquier AFN en un AFD equivalente tratando cada subconjunto de estados alcanzables como un estado del AFD; el lema del bombeo sirve para probar que un lenguaje no es regular, y la eliminación de recursividad izquierda y la factorización por la izquierda son técnicas para preparar gramáticas para el análisis LL, no para convertir autómatas. (Hopcroft, Motwani, Ullman, Introduction to Automata Theory..., cap. 2.)

18. En la tabla de transición de un autómata finito, ¿qué representan, respectivamente, cada fila y cada columna?

1. Cada fila corresponde a un estado y cada columna a un símbolo del alfabeto
2. Cada fila corresponde a un símbolo del alfabeto y cada columna a un estado
3. Cada fila corresponde a una cadena aceptada y cada columna a un estado de rechazo
4. Cada fila corresponde a una transición vacía (ε) y cada columna a un estado final

En la representación estándar de la función δ como tabla, cada fila representa un estado del conjunto Q y cada columna un símbolo del alfabeto Σ, con la celda indicando el estado siguiente. (Hopcroft, Motwani, Ullman, Introduction to Automata Theory..., cap. 2.)

19. Según la jerarquía de Chomsky, ¿qué modelo de máquina reconoce exactamente los lenguajes de Tipo 3 (regulares)?

1. El autómata finito
2. El autómata de pila
3. El autómata linealmente acotado
4. La máquina de Turing

En la jerarquía de Chomsky, los lenguajes regulares (Tipo 3) son reconocidos exactamente por autómatas finitos; el autómata de pila corresponde al Tipo 2, el linealmente acotado al Tipo 1 y la máquina de Turing al Tipo 0. (Hopcroft, Motwani, Ullman, Introduction to Automata Theory..., cap. sobre la jerarquía de Chomsky.)

20. ¿Qué modelo de máquina de la jerarquía de Chomsky reconoce exactamente los lenguajes libres de contexto (Tipo 2)?

1. El autómata de pila
2. El autómata finito
3. El autómata linealmente acotado
4. La máquina de Turing

Los lenguajes libres de contexto (Tipo 2) son reconocidos exactamente por autómatas de pila (no deterministas); el autómata finito corresponde al Tipo 3 y el linealmente acotado al Tipo 1. (Hopcroft, Motwani, Ullman, Introduction to Automata Theory..., cap. 6.)

21. ¿Qué modelo de máquina corresponde, dentro de la jerarquía de Chomsky, a los lenguajes sensibles al contexto (Tipo 1)?

1. El autómata linealmente acotado
2. El autómata de pila
3. El autómata finito
4. La máquina de Turing sin restricciones

Los lenguajes sensibles al contexto (Tipo 1) son reconocidos por el autómata linealmente acotado, una máquina de Turing cuya cinta está limitada al tamaño de la entrada; el autómata de pila y el finito corresponden a niveles menos potentes, y la máquina de Turing sin restricciones al Tipo 0. (Hopcroft, Motwani, Ullman, Introduction to Automata Theory..., cap. sobre la jerarquía de Chomsky.)

22. ¿A qué tipo de lenguajes de la jerarquía de Chomsky corresponden los reconocidos por una máquina de Turing sin restricciones (Tipo 0)?

1. Los lenguajes recursivamente enumerables
2. Los lenguajes regulares
3. Los lenguajes libres de contexto
4. Los lenguajes sensibles al contexto

El Tipo 0 de la jerarquía de Chomsky corresponde a los lenguajes recursivamente enumerables, reconocidos por una máquina de Turing sin restricciones; los otros tipos corresponden a modelos más restringidos. (Hopcroft, Motwani, Ullman, Introduction to Automata Theory..., cap. sobre la jerarquía de Chomsky.)

23. Considera la siguiente definición en notación BNF: <digito> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ; <numero> ::= <digito> | <digito><numero>. ¿A qué tipo de la jerarquía de Chomsky corresponde el lenguaje generado por esta gramática (secuencias de uno o más dígitos)?

1. Tipo 3, regular
2. Tipo 2, libre de contexto pero no regular
3. Tipo 1, sensible al contexto
4. Tipo 0, recursivamente enumerable

El lenguaje generado son las cadenas de uno o más dígitos ([0-9]+), que es regular (Tipo 3); aunque la producción <numero> ::= <digito><numero> incluya el no terminal <digito>, este deriva un solo terminal, por lo que la gramática equivale a una lineal por la derecha. (Naur (ed.), Report on the Algorithmic Language ALGOL 60; Hopcroft, Motwani, Ullman, jerarquía de Chomsky.)

24. Se quiere demostrar que el lenguaje L = { aⁿbⁿ : n ≥ 0 } NO es un lenguaje regular. ¿Qué herramienta formal es la adecuada para construir esta demostración?

1. El lema del bombeo (pumping lemma) para lenguajes regulares
2. La construcción de subconjuntos
3. El teorema de Kleene
4. El algoritmo de eliminación de recursividad izquierda

El lema del bombeo es una condición necesaria de los lenguajes regulares y se usa para probar, por contradicción, que un lenguaje dado no es regular; la construcción de subconjuntos convierte AFN en AFD y el teorema de Kleene establece equivalencias entre formalismos regulares, sin servir para demostrar no regularidad. (Hopcroft, Motwani, Ullman, Introduction to Automata Theory..., cap. 4.)

25. En la notación BNF (Backus-Naur Form), empleada en la definición formal de ALGOL 60, ¿qué representa el metasímbolo '::='?

1. Que el no terminal de la izquierda 'se define como' la expresión de la derecha
2. La alternancia entre dos posibles producciones
3. La repetición cero o más veces de un símbolo
4. La concatenación obligatoria de dos símbolos no terminales

El metasímbolo '::=' introduce la regla de producción, indicando que el no terminal de la izquierda 'se define como' la expresión de la derecha; la alternancia se expresa con el metasímbolo '|', no con '::='. (Naur (ed.), Report on the Algorithmic Language ALGOL 60 (1960/1963).)

26. En la notación BNF (Backus-Naur Form) utilizada para describir gramáticas libres de contexto, el metasímbolo ::= que aparece en una producción significa...

1. Que el símbolo de la izquierda debe repetirse cero o más veces en la derivación
2. Que el símbolo de la izquierda representa una alternativa entre dos producciones posibles
3. Que el símbolo de la izquierda se define mediante la expresión que aparece a la derecha
4. Que el símbolo de la izquierda pertenece al conjunto de símbolos terminales del lenguaje

En BNF, ::= indica que el no terminal de la izquierda se define por la expresión de la derecha; la alternativa se expresa con el símbolo |, no con ::=. (Naur (ed.), "Report on the Algorithmic Language ALGOL 60" (1960/1963).)

27. La notación BNF se popularizó en la teoría de lenguajes de programación porque se utilizó para especificar formalmente la sintaxis de...

1. El lenguaje ALGOL 60
2. El lenguaje FORTRAN 77
3. El lenguaje COBOL 68
4. El lenguaje LISP 1.5

El informe sobre ALGOL 60, editado por Peter Naur, popularizó la notación BNF para describir formalmente la gramática libre de contexto del lenguaje. (Naur (ed.), "Report on the Algorithmic Language ALGOL 60" (1960/1963).)

28. En una gramática escrita en BNF, un símbolo encerrado entre los metasímbolos < y > representa...

1. Un símbolo no terminal que debe sustituirse mediante otra producción
2. Un símbolo terminal que aparece tal cual en la cadena final
3. Un comentario que el analizador sintáctico debe ignorar
4. Una alternativa opcional que puede omitirse en la derivación

Los metasímbolos < y > encierran no terminales, es decir, símbolos que aún deben expandirse mediante producciones hasta llegar a terminales. (Naur (ed.), "Report on the Algorithmic Language ALGOL 60" (1960/1963).)

29. Un compilador utiliza la gramática E ::= E + E | E * E | id sin ninguna regla de precedencia. Al analizar la cadena 'id + id * id', el equipo de desarrollo detecta que...

1. La cadena no pertenece al lenguaje generado por la gramática y debe rechazarse
2. El análisis requiere una pila de tamaño ilimitado para completarse
3. La cadena solo puede derivarse aplicando recursión por la derecha
4. La cadena admite más de un árbol de derivación, por lo que la gramática es ambigua

La cadena puede derivarse agrupando primero la suma o primero la multiplicación, generando dos árboles distintos; este es el problema clásico de ambigüedad que se resuelve con reglas de precedencia. (Aho, Lam, Sethi, Ullman, "Compiladores: principios, técnicas y herramientas" (Libro del Dragón), 2a ed., cap. 4.)

30. Se dice que una gramática libre de contexto es ambigua cuando...

1. Contiene producciones con más de un símbolo no terminal en el lado derecho
2. Existe al menos una cadena del lenguaje con más de un árbol de derivación
3. Genera un lenguaje que no puede reconocerse mediante un autómata de pila
4. Incluye producciones que derivan la cadena vacía

La definición estándar de ambigüedad exige la existencia de al menos una cadena con dos o más árboles de derivación distintos, no simplemente producciones con varios no terminales. (Aho, Lam, Sethi, Ullman, "Compiladores" (Libro del Dragón), 2a ed., cap. 4.)

31. Dentro de la jerarquía de Chomsky, las gramáticas que se escriben típicamente en notación BNF, con producciones de la forma A -> α donde A es un único no terminal y α una cadena cualquiera de terminales y no terminales, corresponden al...

1. Tipo 1, reconocidas por autómatas linealmente acotados
2. Tipo 3, reconocidas por autómatas finitos
3. Tipo 2, reconocidas por autómatas de pila
4. Tipo 0, reconocidas por máquinas de Turing

Tener un único no terminal a la izquierda y una parte derecha sin restricciones define a las gramáticas libres de contexto (Tipo 2), reconocidas por autómatas de pila; el Tipo 3 (regular) impone además restricciones a la parte derecha. (Hopcroft, Motwani, Ullman, "Introduction to Automata Theory, Languages, and Computation", 3a ed.)

32. Un desarrollador construye un compilador y necesita verificar que la secuencia de tokens entregada por el analizador léxico cumpla las reglas de la gramática escrita en BNF, además de construir el árbol de análisis correspondiente. Esta tarea corresponde a la fase de...

1. Análisis sintáctico
2. Análisis léxico
3. Análisis semántico
4. Generación de código intermedio

El análisis sintáctico (parser) usa la gramática libre de contexto para validar la secuencia de tokens y construir el árbol de análisis; el análisis léxico solo agrupa caracteres en tokens. (Aho, Lam, Sethi, Ullman, "Compiladores" (Libro del Dragón), 2a ed., cap. 1 y 4.)

33. Un analizador sintáctico construye el árbol de derivación comenzando desde el símbolo inicial de la gramática y expandiendo las producciones hacia los símbolos terminales, en vez de partir de la cadena de entrada y reducirla hasta el símbolo inicial. Este analizador se clasifica como...

1. Ascendente (bottom-up), de tipo LALR
2. Descendente (top-down), de tipo LL
3. Ascendente (bottom-up), de tipo SLR
4. Ascendente (bottom-up), de tipo LR

LL construye el árbol desde el símbolo inicial hacia las hojas (descendente); LALR, SLR y LR son variantes ascendentes que parten de la cadena y reducen hasta el símbolo inicial. (Aho, Lam, Sethi, Ullman, "Compiladores" (Libro del Dragón), 2a ed., cap. 4.)

34. Un equipo de desarrollo ya escribió la gramática de su lenguaje en notación similar a BNF y quiere generar automáticamente el analizador sintáctico correspondiente. La herramienta clásica para esta tarea es...

1. Lex / Flex
2. Make / CMake
3. Git / Subversion
4. Yacc / Bison

Yacc/Bison generan analizadores sintácticos a partir de gramáticas tipo BNF; Lex/Flex generan analizadores léxicos a partir de expresiones regulares, no de gramáticas. (Aho, Lam, Sethi, Ullman, "Compiladores" (Libro del Dragón), 2a ed., cap. 4.)

35. Un autómata finito determinista (AFD) se define formalmente como la 5-tupla (Q, Σ, δ, q0, F). En esta definición, F representa...

1. El alfabeto de símbolos de entrada
2. El conjunto de estados de aceptación
3. La función de transición entre estados
4. El estado inicial del autómata

F es el conjunto de estados finales o de aceptación; Σ es el alfabeto, δ la función de transición y q0 el estado inicial, cada uno un componente distinto de la 5-tupla. (Hopcroft, Motwani, Ullman, "Introduction to Automata Theory...", cap. 2.)