INSTITUTO DE ESTUDIOS SUPERIORES SOR JUANA INES DE LA CRUZ

ALUMNO: ERACLIO CASTILLO VIDAL

16 DE MAYO 2014

EJEMPLO

Análisis lexicográfico

Estudia la primera fase de un compilador, es decir su análisis lexicográfico, también denominado abreviadamente análisis léxico. Las técnicas utilizadas para construir analizadores léxicos también se pueden aplicar a otras áreas como, por ejemplo, a lenguajes de consulta y sistemas de recuperación de información.

Concepto de analizador léxico

Se encarga de buscar los componentes léxicos o palabras que componen el programa fuente, según unas reglas o patrones.

La entrada del analizador léxico podemos definirla como una secuencia de caracteres, que pueda hallarse codificada según cualquier estándar El analizador léxico divide esta secuencia en palabras con significado propio y después las convierte a una secuencia de terminales desde el punto de vista del analizador sintáctico. Dicha secuencia es el punto de partida para que el analizador sintáctico construya el árbol sintáctico que reconoce la/s sentencia/s de entrada.

EJEMPLO

Token

También llamado componente léxico. Es la categoría léxica asociada a un patrón. Cada token se convierte en un número o código identificador único. En algunos casos, cada número tiene asociada información adicional necesaria para las fases posteriores de la etapa de análisis. El concepto de token coincide directamente con el concepto de terminal desde el punto de vista de la gramática utilizada por el analizador sintáctico.

Reconocimiento de Token.

En un estado determinado, todas las expresiones regulares se consideran posibles tokens. Consume el número máximo de caracteres de la cadena de entrada que coincida con alguna de las expresiones regulares, el token manager prefiere el match más largo que sea posible. Si existieran múltiples matches (de la misma longitud), se elige la expresión regular que ocurre antes en el archivo de la gramática.

Una vez que el token manager determina un match, los diferentes tipos de expresiones regulares especifican las acciones que deben realizarse cuando una expresión regular ha sido reconocida:

Funciones principales de unanalizador lexicográfico Necesidad del analizador léxico

Simplificación del diseño

Eficiencia

Portabilidad

Patrones complejos

Funciones del analizador léxico

El analizador léxico es la primera fase de un compilador. 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.

Además de esta función principal, el analizador léxico también realiza otras de gran importancia: Eliminar los comentarios del programa.

Eliminar espacios en blanco, tabuladores, retorno de carro, etc., y en general, todo aquello que carezca de significado según la sintaxis del lenguaje.

Reconocer los identificadores de usuario, números, palabras reservadas del lenguaje, etc.

Llevar la cuenta del número de línea por la que va leyendo, por si se produce algún error, dar información acerca de dónde se ha producido.

Avisar de errores léxicos. Por ejemplo, si el carácter ‘@’ no pertenece al lenguaje, se debe emitir un error. • También puede hacer funciones de preprocesador.

Autómatas de Estado Finitos

Este mecanismo consiste en construir los patrones necesarios para cada categoría léxica, construir sus automátas finitos individuales, fusionarlos por opcionalidad y, finalmente, implementar los autómatas resultantes. Aunque la construcción de analizadores mediante este método es sistemática y no propensa a errores, cualquier actualización de los patrones reconocedores implica la modificación del código que los implementa, por lo que el mantenimiento se hace muy costoso.

Diagrama de transición

Introducción a la teoría de lenguajes

Cualquier comunicación se realiza mediante cadenas de símbolos que corresponden a un lenguaje.

Lenguajes son conjuntos de cadenas de símbolos (palabras, oraciones, textos o frases).

El estudio de los lenguajes se reduce, básicamente, a: Sintaxis: (gramática)

define las secuencias de símbolos que forman cadenas válidas deun lenguaje

Gramática: Descripción formalizada de las oracionesde un lenguaje. Una gramática genera o describe un lenguaje.

Semántica:

significado de las cadenas que componen un lenguaje.

autómatas de Estados finitos no determinísticos

Un autómata finito no determinista (abreviado AFND) es un autómata finito que, a diferencia de los autómatas finitos deterministas (AFD), posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.

En un AFND puede darse cualquiera de estos dos casos:

Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;

Que existan transiciones del tipo δ(q, ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados.

Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones vacías o transiciones ε (abreviado AFND-ε). Estas transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada. Considérese una modificación al modelo del autómata finito para permitirle ninguna, una o más transiciones de un estado sobre el mismo símbolo de entrada.