Unidad Ii - Compiladores

REPÚBLICA BOLIVARIANA DE VENEZUELA
UNIVERSIDAD ALONSO DE OJEDA
VICERRECTORADO ACADÉMICO
FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
COMPILADORES
UNIDAD II
AUTORES:
 WISTON SANCHEZ V-30.475.750.

 ALBERTO MADRID V-29.672.200.
 ELIANA GUARIQUE V-30.061.224.
 DARISBELL PAZ V-29.984.684.
 FABIANA QUINTERO V-30.684.537.
CIUDAD OJEDA, NOVIEMBRE DEL 2022.

1. El Análisis Léxico:
Es la primera fase de un compilador y consiste en un programa que recibe como entrada el

código fuente de otro programa (secuencia de caracteres) y produce una salida compuesta de
tokens (componentes léxicos) o símbolos. Estos tokens sirven para una posterior etapa del
proceso de traducción, siendo la entrada para el Análisis Sintáctico.
La especificación de un lenguaje de programación a menudo incluye un conjunto de reglas que

definen el léxico. Estas reglas consisten comúnmente en expresiones regulares que indican el
conjunto de posibles secuencias de caracteres que definen un token o lexema.
En algunos lenguajes de programación es necesario establecer patrones para caracteres

especiales (como el espacio en blanco) que la gramática pueda reconocer sin que constituya un
token en sí. Su principal función consiste en leer los caracteres de entrada y elaborar como
salida una secuencia de componentes léxicos que utiliza el analizador sintáctico para hacer el
análisis.
Posee algunos componentes tales como:
 Token: es un par que consiste en un nombre de token y un valor de atributo opcional. El

nombre del token es un símbolo abstracto que representa un tipo de unidad léxica; por
ejemplo, una palabra clave específica o una secuencia de caracteres de entrada que denotan
un identificador. Los nombres de los tokens son los símbolos de entrada que procesa el
analizador sin táctico. A partir de este momento, en general escribiremos el nombre de un
token en negrita. Con frecuencia nos referiremos a un token por su nombre.
 Patrón: es una descripción de la forma que pueden tomar los lexemas de un token. En el
caso de una palabra clave como token, e l patrón es sólo la secuencia de caracteres que
forman la palabra clave. Para los identificadores y algunos otros tokens, el patrón es una
estructura más compleja que se relaciona mediante muchas cadenas.
 Lexema: es una secuencia de caracteres en el programa fuente, que coinciden con el patrón
para un token y que el analizador léxico identifica como una instancia de ese token.
2. Cadenas y lenguajes:
El término alfabeto o clase de carácter denota cualquier conjunto finito de símbolos.

Ejemplos típicos de símbolos son las letras y los caracteres. El conjunto {0 , 1} es el 3
alfabeto binario. Los códigos ASSCII y EBCDIC son dos ejemplos de alfabetos de
computador.
Una cadena sobre algún alfabeto es una secuencia finita de símbolos tomados de ese
alfabeto. En teoría del lenguaje, los términos frase y palabra a menudo se utilizan como
sinónimos del término "cadena". La longitud de una cadena s, que suele escribirse lsl, es el
número de apariciones de símbolos en s. Por ejemplo, camino es una cadena de longitud
seis. La cadena vacía, representada por Є, es una cadena especial de longitud cero.
El término lenguaje se refiere a cualquier conjunto de cadenas de un alfabeto fijo. Esta

definición es muy amplia, y abarca lenguajes abstractos como Ǿ, el conjunto vacío, o {Є}
y el conjunto que sólo contiene la cadena vacía, así como al conjunto de todos los
programas de Pascal sintácticamente bien formados y el conjunto de todas las oraciones en
inglés gramaticalmente correctas, aunque los dos últimos conjuntos son mucho más
difíciles de especificar.
3. Expresiones regulares:
Son una forma de especificar patrones, entendiendo por patrón la forma de escribir cadena
de caracteres. Es la forma de definir los tokens o componentes léxicos.
4. Definiciones regulares:
Por conveniencia de notación, puede ser deseable dar nombres a las expresiones regulares
y definir expresiones regulares utilizando dichos nombres como si fueran símbolos.
Si ∑ es un alfabeto de símbolos básicos, entonces una definición regular es una secuencia
de definiciones de la forma:
d1->r1
d2->r2
…
dn->rn
Donde cada d1 es un nombre distinto, y cada r1 es una expresión regular sobre los símbolos
de∑ U {d1, d2, … , d1_1}, por ejemplo, los símbolos básicos y los nombres 4 previamente
definidos. Al limitar cada r1 a los símbolos de ∑ y a los nombres previamente definidos,
se puede construir una expresión regular en ∑ para cualquier r1, reemplazando una y otra
vez los nombres de las expresiones regulares por las expresiones que designan. Si r1
utilizara d¡ para alguna j≥ i, entonces ri se podría definir recursivamente y este proceso de
sustitución no tendría fin. Para distinguir los nombres de los símbolos, se imprimen en
negritas los nombres de las definiciones regulares.
5. Diagrama de transición:
Como paso intermedio en la construcción de un analizador léxico, primero se produce un

diagrama de flujo estilizado, llamado diagrama de transiciones. Los diagramas de
transiciones representan las acciones que tienen lugar cuando el analizador léxico es
llamado por el analizador sintáctico para obtener el siguiente componente léxico.
Se utiliza un diagrama de transición para localizar la información sobre los caracteres que
se detectan a medida que el apuntador delantero examina la entrada. Esto se hace
cambiando de posición en el diagrama según se leen los caracteres.
6. Autómatas finitos:
Un reconocedor de un lenguaje es un programa que toma como entrada una cadena x y

responde "sí" si x es una frase del programa, y "no", si no lo es. Se compila una expresión
regular en un reconocedor construyendo un diagrama de transiciones generalizado llamado
autómata finito. Un autómata finito puede ser determinista o no determinista, donde "no
determinista" significa que en un estado se puede dar el caso de tener más de una transición
para el mismo símbolo de entrada.
Tanto los autómatas finitos deterministas como los no deterministas pueden reconocer con
precisión a los conjuntos regulares. Por tanto, ambos pueden reconocer con precisión lo
que denotan las expresiones regulares. Sin embargo, hay un conflicto entre espacio y
tiempo; mientras que un autómata finito determinista puede dar reconocedores más rápidos
que uno no determinista, un autómata finito determinista puede ser mucho mayor que un
autómata no determinista equivalente. En la siguiente sección, se introducen métodos para
convertir expresiones regulares en ambas clases de autómatas finitos. La conversión en un
autómata no determinista es más directa, por lo que primero se estudia este caso.
7. Errores léxicos:
Los errores léxicos se detectan cuando el analizador léxico intenta reconocer componentes
léxicos y la cadena de caracteres de la entrada no encaja con ningún patrón. Son situaciones
en las que usa un carácter inválido (@, $,",>,...), que no pertenece al vocabulario del
lenguaje de programación, al escribir mal un identificador, palabra reservada u operador.
Algunos de los errores léxicos típicos son:
● Nombre ilegales de identificadores: un nombre contiene caracteres inválidos.
● Números incorrectos: un número contiene caracteres inválidos o no está formado

correctamente.
● Errores en palabras reservadas: caracteres omitidos, adicionales o cambiados de

sitio.
● Fin de archivo: se detecta un fin de archivo a la mitad de un componente léxico.
8. Analizador Sintáctico:
Un analizador sintáctico es una de las partes de un compilador que transforma su entrada

en un árbol de derivación.
El análisis sintáctico convierte el texto de entrada en otras estructuras (comúnmente

árboles), que son más útiles para el posterior análisis y capturan la jerarquía implícita de la
entrada. Un analizador crea tokens de una secuencia de caracteres de entrada y son estos
tokens los que son procesados por el analizador sintáctico para construir la estructura de
datos, por ejemplo un árbol de análisis o árboles de sintaxis abstracta.
9. Tipos de analizadores:
Hay básicamente dos métodos de análisis diferentes, análisis de arriba hacia abajo (top-
down) y análisis de abajo hacia arriba (bottom-up). Éstos difieren generalmente en el orden
en el que se crean los elementos del árbol sintáctico.
 De arriba a abajo: En el método top-down, el analizador trabaja en un método

orientado a objetivos, lo que significa que busca a partir del símbolo de inicio de la
sintaxis y busca una derivación sintáctica adecuada. Por lo tanto, el árbol de análisis
se desarrolla de arriba hacia abajo en la dirección de un desglose cada vez más
detallado.
 De abajo hacia arriba: El analizador ascendente comienza con el símbolo de la

cadena de entrada e intenta establecer relaciones sintácticas cada vez mayores. Esto
se hace hasta que el símbolo de inicio de la gramática se ha alcanzado.
10. Estructura del análisis sintáctico:
● Precedencia: Si dos operadores diferentes comparten un mismo operando, la precedencia

de los operadores decide cual tomará el operando. Esto es, 2+3*4 puede tener 2 árboles de
parseo, uno que corresponde a (2+3)*4 y otro que corresponda a 2+(3*4). Estableciendo la
precedencia entre operadores, este problema puede ser resuelto con facilidad. Como en este
ejemplo, matemáticamente la multiplicación tiene precedencia sobre la suma, entonces la
expresión 2+3*4 siempre será interpretada de la misma manera.
Esto reduce la posibilidad de tener una gramática ambigua.

● Asociatividad: Si un operando tiene operadores en ambos lados, el lado en el cual el
operador toma su operador se decide por la asociatividad de esos operadores. Si la
operación es asociativa por la izquierda, entonces el operando será tomado por la izquierda.
Si la operación es asociativa por la derecha tomamos el operador de la derecha.
● Ambigüedad: Una gramática G es ambigua cuando tiene mas de un arbol de parseo (ya
sea por la izquierda o por la derecha) para al menos una cadena de entrada.
● Escritura de una gramática: Toda construcción que se pueda describir mediante una
expresión regular también se puede describir por medio de una gramática, por lo tanto todo
conjunto regular es un lenguaje independiente de contexto.
Las reglas de sintaxis de un lenguaje a menudo son bastante sencillas, y para describirlas
no se necesita una notación tan poderosa como las gramáticas, por ello se utilizan reglas
de sintaxis de gramáticas para que se proporcione una notación más concisa y más fácil de
entender para los componentes léxicos y al mismo tiempo separar la estructura sintáctica
de un lenguaje en partes léxicas y no léxicas proporciona una forma conveniente de
modular la etapa inicial de un compilador en dos componentes de tamaño razonable y
además describir estructuras anidadas, estructuras de control, etc.
11. Árbol sintáctico descendente:
En el Análisis Sintáctico Descendente se va recorriendo el árbol sintáctico desde la raíz

hasta las hojas, llegando a generar la sentencia que se está analizando. La raíz representa
el símbolo inicial de la gramática.
12. Manejo de errores sintácticos:
El manejo de errores de sintaxis es el más complicado desde el punto de vista de la creación

de compiladores. Nos interesa que cuando el compilador encuentre un error, no cancele
definitivamente la compilación, sino que se recupere y siga buscando errores. Recuperar
un error no quiere decir corregirlo, sino ser capaz de seguir construyendo el árbol sintáctico
a pesar de los errores encontrados. En vista de esto, el manejador de errores de un
analizador sintáctico debe tener como objetivos:
 Indicar los errores de forma clara y precisa. Debe informar mediante los
correspondientes mensajes del tipo de error y su localización.
 Recuperarse del error, para poder seguir examinando la entrada.
 Distinguir entre errores y advertencias. Las advertencias se suelen utilizar

para informar sobre sentencias válidas pero que, por ser poco frecuentes,
pueden constituir una fuente de errores lógicos.
 No ralentizar significativamente la compilación. Un buen compilador debe

hacerse siempre teniendo también en mente los errores que se pueden
producir, con lo que se consigue simplificar su estructura.
Además, si el propio compilador está preparado para admitir incluso los errores más
frecuentes, entonces se puede mejorar la respuesta ante esos errores incluso corrigiéndolos.

Unidad Ii - Compiladores

Cargado por

Copyright:

Formatos disponibles

Unidad Ii - Compiladores

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Unidad Ii - Compiladores

Cargado por

Copyright:

Formatos disponibles

REPÚBLICA BOLIVARIANA DE VENEZUELA

UNIVERSIDAD ALONSO DE OJEDA

 WISTON SANCHEZ V-30.475.750.

CIUDAD OJEDA, NOVIEMBRE DEL 2022.

Es la primera fase de un compilador y consiste en un programa que recibe como entrada el

La especificación de un lenguaje de programación a menudo incluye un conjunto de reglas que

En algunos lenguajes de programación es necesario establecer patrones para caracteres

Posee algunos componentes tales como:

 Token: es un par que consiste en un nombre de token y un valor de atributo opcional. El

El término alfabeto o clase de carácter denota cualquier conjunto finito de símbolos.

El término lenguaje se refiere a cualquier conjunto de cadenas de un alfabeto fijo. Esta

Como paso intermedio en la construcción de un analizador léxico, primero se produce un

Un reconocedor de un lenguaje es un programa que toma como entrada una cadena x y

Algunos de los errores léxicos típicos son:

● Nombre ilegales de identificadores: un nombre contiene caracteres inválidos.

● Números incorrectos: un número contiene caracteres inválidos o no está formado

● Errores en palabras reservadas: caracteres omitidos, adicionales o cambiados de

● Fin de archivo: se detecta un fin de archivo a la mitad de un componente léxico.

Un analizador sintáctico es una de las partes de un compilador que transforma su entrada

El análisis sintáctico convierte el texto de entrada en otras estructuras (comúnmente

 De arriba a abajo: En el método top-down, el analizador trabaja en un método

 De abajo hacia arriba: El analizador ascendente comienza con el símbolo de la

10. Estructura del análisis sintáctico:

● Precedencia: Si dos operadores diferentes comparten un mismo operando, la precedencia

Esto reduce la posibilidad de tener una gramática ambigua.

11. Árbol sintáctico descendente:

En el Análisis Sintáctico Descendente se va recorriendo el árbol sintáctico desde la raíz

El manejo de errores de sintaxis es el más complicado desde el punto de vista de la creación

 Recuperarse del error, para poder seguir examinando la entrada.

 Distinguir entre errores y advertencias. Las advertencias se suelen utilizar

 No ralentizar significativamente la compilación. Un buen compilador debe

También podría gustarte