1. CADENA
1.1. Una cadena es una secuencia finita de símbolos de un determinado alfabeto.
1.1.1. LONGITUD DE CADENA Consiste en el número de símbolos pertenecientes a la cadena. Ejm. Tomando en cuenta los ejemplos de cadena podemos decir que: · |abcb| es de longitud 4 · |a + 2*b| es de longitud 5 · |000111| es de longitud 6 · |if a>b then a=b;| es de longitud 9
1.1.2. CADENA VACÍA Se denomina cadena vacía, que no tiene símbolos y se denota con l, por lo que su longitud es : | l |
1.1.3. CONCATENACIÓN DE CADENAS Sean A y B dos cadenas cualesquiera, se denomina concatenación de A y B a una nueva cadena AB constituida por los símbolos de la cadena A seguidos por los de la cadena B. El elemento neutro de la concatenación es l: A l = lA = A
2. FASES DE UN COMPILADOR
2.1. Alternativamente, las fases descritas para las tareas de análisis y síntesis se pueden agrupar en Front-end y Back-end.
2.1.1. Front-end: Es la parte que analiza el código fuente, comprueba su validez, genera el árbol de derivación (ver El Análisis Sintáctico) y rellena los valores de la tabla de símbolos.Esta parte suele ser independiente de la plataforma o sistema para el cual se vaya a compilar.
2.1.2. Back-end: Es la parte que genera el código de máquina, específico de una plataforma, a partir de los resultados de la fase de análisis, realizada por el Front End
2.2. Esta división permite que el mismo Back End se utilice para generar el código máquina de varios lenguajes de programación distintos y que el mismo Front End, que sirve para analizar el código fuente de un lenguaje de programación concreto, sirva para generar código máquina en varias plataformas distintas.
3. FUENTES DE INFORMACION
3.1. Aho Alfred V., Lam Monica S., Compiladores, principios, técnicas y herramientas, Segunda edición, México: Pearson educación, 2008.
3.2. Kennenth C. Louden, Construccion de compiladores: principios y practica, Thomson, 2004
3.3. Sergio Gálvez Rojas, Miguel Ángel Mora Mata. Java a tope: Compiladores y traductores Lex/Yacc, Edición Electrónica, 2005.
3.4. Emiliano Llano Díaz, Análisis y Diseño de Compiladores, 1 era edición, junio México, 2002.
3.5. Jacinto Ruiz Catalán, Compiladores. Teoría e implantación, Impresión en España, Baena, Octubre de 2009.
4. ALFABETO
4.1. Conjunto de símbolos finito y no vacío.Convencionalmente se utiliza el símbolo S para designar un alfabeto.
4.2. Usamos meta–símbolos para escribir sobre lo que hablamos. Desde el contexto siempre será claro, si se trata de un símbolo del alfabeto o si se trata de un meta–símbolo.
4.3. Usamos normalmente las minúsculas como alfabeto = {a, . . . , z}, en los ejemplos normalmente letras desde el principio del alfabeto.
4.4. Cardinalidad del alfabeto (número de elementos del alfabeto): || > 0, || < 1.
5. LENGUAJE
5.1. Un lenguaje es un conjunto de cadenas.
5.2. Un conjunto de palabras, formado por símbolos en un alfabeto dado. Puede ser infinito.
5.3. El conjunto vacío Ø y el conjunto formado por la cadena vacía { E } son lenguajes.
5.4. Un lenguaje es cualquier subconjunto del universo sobre algún alfabeto, es decir, L W(), o también L .
5.4.1. Lenguajes triviales • L = ; es el lenguaje vacio (que no contiene ninguna palabra), |L| = 0 • L = {} es el lenguaje que solamente contiene la palabra vacio, |L| = 1 son independientes del alfabeto y por eso son lenguajes sobre cualquier alfabeto.
5.4.2. Unión: L1 [ L2 = {w | w 2 L1 o w 2 L2} Propiedades (unos ejemplos): Conmutatividad: L1 [ L2 = L2 [ L1 Asociatividad: (L1 [ L2) [ L3 = L1 [ (L2 [ L3) Idempotencia: L [ L = L Operación con ;: L [ ; = L = ; [ L Operación con : L [ = = [ L Intersección: L1 \ L2 = {w | w 2 L1 y w 2 L2} Propiedades (unos ejemplos): Conmutatividad: L1 \ L2 = L2 \ L1 Asociatividad: (L1 \ L2) \ L3 = L1 \ (L2 \ L3) Idempotencia: L \ L = L Operación con ;: L \ ; = ; = ; \ L1 Operación con : L \ = L = \ L Dr. Arno Formella 13 Complemento: L = {w | w 2 y w /2 L} Propiedades (unos ejemplos): Regla de DeMorgan: L1 [ L2 = L1 \ L2 L1 \ L2 = L1 [ L2 Con estas tres operaciones la estructura (,[,\, ) forma una álgebra booleana. Diferencia: L1 − L2 = {w | w 2 L1 pero w /2 L2} Propiedades (unos ejemplos): L1 = − L1 L1 − L2 = L1 \ \ L2) Concatenación: L1.L2 = {w | w = w1.w2 y w1 2 L1 y w2 2 L2} Propiedades (unos ejemplos): No–Conmutatividad: L1.L2 6= L2.L1 (en general) Operación con ;: L1.; = L1 = ;.L1 Operación con {}: L1.{} = L1 = {}.L1 Potencia: Li = |L .{.z. L} i-veces i 2 IN Propiedades (unos ejemplos): Cero–Potencia: L0 = {} Inducción: Li.L = Li+1 = L.Li
6. INTERPRETE
6.1. Es como un compilador, solo que la salida es una ejecución, la traducción se hace “frase a frase”.
6.2. El programa de entrada se reconoce y ejecuta a la vez.
6.3. No se produce un resultado físico (código máquina) sino lógico (una ejecución).
6.4. un programa que analiza y ejecuta simultáneamente un programa escrito en un lenguaje fuente
7. TIPOS DE ANALISIS
7.1. Análisis sintáctico
7.1.1. Se entiende como el proceso de determinar si una cadena de componentes léxicos o tokens puede ser generada por una gramática, y en caso de conseguirlo, se debe poder descubrir su estructura gramatical, esto es, el camino de derivación.
7.2. Análisis semántico
7.2.1. Es el encargado de verificar el cumplimiento de las reglas semánticas para un lenguaje dado. Formalmente se encarga de verificar si el árbol de análisis sintáctico generado es válido en cuanto a reglas semánticas. Aunque se aprecie como un componente separado, en la práctica, el análisis semántico se da en el mismo momento que el análisis sintáctico extendiéndose inclusive hasta la generación de código.
7.3. Análisis léxico
7.3.1. Es la primera fase o etapa de desarrollo de un compilador. Para entender mejor su función principal, es necesario definir el concepto de lexema y token. El lexema, es una secuencia de caracteres en el código fuente, que poseen en conjunto un significado especial en el lenguaje de programación. El token es un símbolo con un significado especial en el lenguaje. Es precisamente el significado que se le otorga a un lexema