Resumen

Vista previa del material en texto

TIPO 0(Irrestricta o Sin Restricciones-GI): Gramática estructurada por frases sin ninguna restricción.
O sea que sus reglas de producción tienen, en la parte izquierda al menos un símbolo no terminal y en la parte derecha cualquier secuencia de terminales o no-terminales, inclusive vacía.
Todo lenguaje formal generado por una GI y que no puede ser generado por una gramática de menor jerarquía, se llama Lenguaje Irrestricto o Recursivamente Enumerable (LI).
S UVX X λ
S UVX aUYX aUVaX aaX aa
S UVX bUZX bUVbX baUYbX baUbYX baUbVaX baUVbaX babaX baba
TIPO 1(Dependiente del / Sensible al Contexto-GDC): Gramática estructurada por frases cuyas reglas de producción se restringen en la longitud de su parte derecha, la cual no puede ser menor que la longitud de la parte izquierda. O sea que no tienen reglas compresoras. Excepto la regla de borrado Sλ, siempre que S no figure a la derecha de ninguna regla, con el único objetivo de generar la palabra vacía.
Todo lenguaje formal generado por una GDC y que no puede ser generado por una gramática de menor jerarquía, se llama Lenguaje Dependiente del Contexto (LDC).
S T abD abc
S T aTBD aabDBD aabBDD aabbDD aabbcD aabbcc
S T aTBD aaTBDBD aaabDBDBD aaabBDDBD aaabbDDBD aaabbDBDD aaabbBDDD aaabbbDDD aaabbbccc
TIPO 2(Independiente / Libre del Contexto-GIC): Gramática estructurada por frases cuyas reglas de producción se restringen en la longitud de su parte izquierda, que debe ser igual a 1. O sea que la parte izquierda es un no-terminal y la parte derecha puede ser cualquier secuencia de terminales o no-terminales.
Todo lenguaje formal generado por una GIC y que no puede ser generado por una gramática de menor jerarquía, se llama Lenguaje Independiente del Contexto (LIC).
Sab
SaSbaabb
SaSbaaSbbaaabbb
TIPO 3(Lineal / Regular-GR): Gramática estructurada por frases cuyas reglas de producción se restringen en la longitud de su parte izquierda, que debe ser igual a 1. O sea que la parte izquierda es un no-terminal y la parte derecha puede ser una secuencia de terminales con un no-terminal como sufijo (GR por la derecha) o con un no-terminal como prefijo (GR por la izquierda) o simplemente una secuencia de terminales.
Existe una equivalencia entre ambas formas.
Todo lenguaje formal generado por una GR por la derecha o por la izquierda, se llama Lenguaje Regular (LR).
SaaAaabb
SaaAaaaaAaaaabb
SbbSbbaaAbbaabb
SbbSbbaaAbbaaaaAbbaaaabb
PROCESO DE COMPILACIÓN
TRADUCTOR: Un traductor se define como un programa capaz de convertir un texto o programa fuente escrito en un lenguaje determinado, en otro texto o programa escrito en otro lenguaje distinto. Existen distintos tipos:
· PREPROCESADORES: Permiten modificar el programa fuente antes de la verdadera compilación. Hacen uso de macroinstrucciones y directivas de compilación. 
· COMPILADOR: Transforman un programa fuente escrito en un lenguaje de alto nivel, obteniendo como resultado un archivo objeto con la traducción a un lenguaje de bajo nivel.
· INTERPRÉTE: Traducen sentencia por sentencia de un programa escrito en un lenguaje de alto nivel y la van ejecutando, sin crear un fichero objeto.
· PSEUDO-INTERPRETE: Traducen un programa fuente escrito en un lenguaje de alto nivel, obteniendo un archivo objeto con un código intermedio, que posteriormente es interpretado por un motor de ejecución.
· INTERPRETES DE COMANDOS: Traducen sentencias simples a invocaciones a programas de una biblioteca. Se utilizan especialmente en los sistemas operativos.
· ENSAMBLADOR: Permite la traducción de cada sentencia fuente a una única instrucción de código máquina. El lenguaje fuente se suele llamar lenguaje simbólico, ya que utiliza nemotécnicos para hacer referencia a operaciones, registros, direcciones de memoria, etc.
· TRANSPILADOR: Traducen un programa escrito en un lenguaje de alto nivel a otro lenguaje de alto nivel, con lo que se consigue una mayor portabilidad de éstos lenguajes.
· TRADUCTOR DE IDIOMAS: Son traductores de lenguajes naturales, es decir, tienen como entrada un texto escrito en un idioma y dan como salida una texto equivalente escrito en otro idioma. 
FASES DE EJECUCIÓN: Existen 3 fases para la ejecución de un programa escrito con lenguaje de alto nivel.
· COMPILADOR: No produce un fichero ejecutable, sino que el código generado se estructura en módulos que se almacenan en un fichero objeto. Los ficheros objeto poseen información relativa tanto al código máquina como a una tabla de símbolos que almacena la estructura de las variables y tipos utilizados por el programa fuente.
· ENLANZADOR: Engloba en un único bloque los distintos módulos que almacenan código máquina, estructura el bloque de memoria destinado a almacenar las variables en tiempo de ejecución y genera el ejecutable final incorporando algunas rutinas adicionales procedentes de librerías y del Sistema Operativo.
· CARGADOR: es la parte del sistema operativo cuya función es cargar el contenido de los archivos ejecutables en la memoria RAM, asignando a cada segmento de éstos archivos las direcciones de memoria bases correspondientes.
ETAPA DE ANÁLISIS: Parser, Scanner, Verificación semántica.
ETAPA DE SINTESIS: Generación y optimización de código intermedio, Generación de código máquina.
TABLA DE SIMBOLOS: Es una importante estructura de datos creada y mantenida durante el proceso de análisis y de síntesis de un compilador, con el fin de almacenar información acerca de la ocurrencia de diversas entidades, tales como nombres de variables y funciones, objetos, clases, interfaces, etc.
 
DISTINTOS SWITCHS DEL COMANDO GCC
-Wall: Muestra todos los mensajes de error y advertencia del compilador, incluso algunos cuestionables.
-E: Realiza solo el preprocesamiento, enviando el resultado a la salida estándar.
-S: Realiza el preprocesamiento y la traducción del programa fuente a lenguaje simbólico o ensamblador.
-o: Indica el nombre de salida, cualesquiera sean las etapas cumplidas.
-c: Realiza el preprocesamiento y compilación, obteniendo el archivo en código objeto, no realiza el enlazado.
1>: Redirecciona la salida estándar de resultados del comando o programa al archivo especificado.
2>: Redirecciona la salida estándar de errores del comando o programa al archivo especificado.
HASKELL
Para la operación de potencia de un lenguaje, las opciones correctas son: 
· potenciaLenguajes x 1 = x, es el caso base de la recursión. 
· potenciaLenguajes x 0 = [""], es un caso particular pero no es caso base de la recursión.
· Si se elimina la línea: potenciaLenguajes x 1 = x, el programa sigue funcionando correctamente pero disminuye su eficiencia.
Los siguientes símbolos son operadores: : , | y :: .
Un Lenguaje se representa con una Lista en Haskell, las condiciones que debe cumplir son:
· Sus elementos deben ser de tipo String. 
· No debe tener elementos repetidos.
Para las Operaciones sobre Lenguajes: Producto Cartesiano y Concatenación, las opciones correctas son:
· El algoritmo para ambas operaciones es el mismo, excepto que en el producto cartesiano se construyen pares ordenados de palabras y en la concatenación se realizan concatenaciones de palabras. 
· Ambas operaciones dan como resultado un conjunto.
 Dado que un lenguaje se representa en Haskell con una lista de palabras y que el operador Haskell ++ actúa sobre dos listas obteniendo como resultado otra lista con los elementos de la primera seguidos de los elementos de la segunda, entonces este resultado puede interpretarse como la CONCATENACIÓN de los lenguajes que representan cada una de las listas.
Para la operación Producto Cartesiano de dos Lenguajes, las opciones correctas son:
· Puede resolverse con Recursividad. 
· El resultado es de tipo Lista de Tuplas: [(String,String)]
Para la implementación de las operaciones con lenguaje en Haskell, la interpretación de [ ] correcta es:
· inversaPalabra [ ]: [] representa la palabra vacía.
· longitud [ ]: [] representa la palabra vacía.
· inversaLenguaje [ ]: [] representa el lenguajevacío.
· pertenece [ ] [ ]: La primera [ ] representa la palabra vacía y la segunda [ ] representa un lenguaje vacío.
Para las operaciones Estrella de Kleene y Estrella Positiva, las opciones correctas son:
· L* = L0 U L+
· L* = { λ } U L+
· (L*)-1 = (L-1 )*
· Ф* = { λ }
Para las siguientes gramáticas para estructura de frases, los lenguajes formales correspondientes son:
S→ aSB | a
aB → Ba
B → b                         |W|a = |W|b + 1  
S → aSb | aS | a                              a^n b^m / m>=0, n>m 
S→ aSB | aB
aB → Ba
SB → S
B → b                         |W|a >= |W|b
S → aSB						
SB → λ		 S → aX | a
B → b                         X → Sb                         a^n+1 b^n / n>=0
S → aS | bS | λ                         {a, b}*
S → Sb | X
X → Xa | λ                         a^n b^m / n, m>=0
S → XY			 
X → aX | a		 S →  aS | aX 						 
Y → bY | b                        X →  bX | b                         S→ aS | Sb | ab                         a^n b^m / n, m>0
S → aSb | ab                         a^n b^n / n>0
Para las siguientes gramáticas para estructuras de frases, se emparejan con el tipo de menor complejidad según Jerarquía de Chomsky.
TIPO 0
S→ aSB | Ab			S → aSB
aB → Ba			SB → λ
SB → S				B → b
B → b 
TIPO 1
S → C | λ			S→ aSB | a
C → aCB | a			aB → Ba
aB → Ba			B → b
B → b 
TIPO 2
S → XY
X → aX | a 		S → aX | a		S → aSb | aS | a 		S → aSb | ab		S→ aS | Sb | ab
Y → bY | b		X → Sb 					                 
TIPO 3
S → Sb | X 			S →  aS | Ax			S → aS | bS | λ
X → Xa | λ 			X →  bX | b 
No es una Gramática para Estructuras de Frases
S→ ASA | λ			S → aSA | aA
bb → bAb			λ → aAa
SA → AS			SA → S
AA → b 			A → b