Post on 06-Jan-2016
description
Teoría de lenguajes y compiladores
Unidad I
Analizador lexicográfico
Funcionamiento de un analizador lexicográfico. Exploradores
Temas
Semana 4
Objetivo General
El alumno al finalizar el curso podrá desarrollar aplicaciones que le permitan determinar si una estructura gramatical corresponde a una sentencia valida en la definición de un lenguaje en particular, teniendo en cuenta el contexto sintáctico y semántico. Así mismo estará capacitado para proponer nuevas formas estructurales en la definición de lenguajes de programación.
Objetivos Específicos
• Diseñar e implementar un analizador lexicográfico.
• Diseñar e implementar un analizador sintáctico.
• Diseñar e implementar un analizador semántico.
Objetivos Instruccionales
Comprender el funcionamiento de un analizador lexicografico.
¿Qué es un token?
• La salida del analizador léxico es un conjunto de tokens.
• Un token es una categoría sintáctica– En Español:
• Nombres, verbos, adjetivos, …
– En un lenguaje de programación• Identificadores, Enteros, palabras reservadas, espacios en
blanco, …
• La siguiente etapa, toma los tokens.– Ejemplo: Los identificadores se tratan diferente que
las palabras reservadas.
Exp
lora
do
res
Tokens• Los token corresponden a conjuntos de cadenas.
• Identificadores: cadenas de letras o dígitos que comienzan con una letra.
• Enteros: una cadena de dígitos.
• Palabras reservadas: else, if, begin, …
• Espacios en blanco: una secuencia de espacios, nuevas líneas, tabuladores.
• Open par: un paréntesis izquierdo.
Exp
lora
do
res
Tokens, Patrones y Lexemas
• Lexema.- Es la palabra encontrada en el código fuente
• Token.- Es la representación usada en el lenguaje
• Patrón.- Es el conjunto de reglas asociadas a un token.
Exp
lora
do
res
Token, Patrones y Lexemas• Ejemplo: Para el lenguaje c++
Token Lexema PatrónConst const constRelación <,<=,!= <|<=|!=Id x, y, cont letras, seguidas de
más letras y dígitos
Exp
lora
do
res
El explorador, analizador lexicográfico o “scanner” es la parte del compilador que lee los caracteres del programa fuente y que construye unos símbolos intermedios (que llamaremos “tokens”), por ejemplo las variables, los enteros, palabras reservadas y los delimitadores ( +, - , *, espacio en blanco, etc.)
ANALISIS LEXICOE
xplo
rad
ore
s
Implementación del analizador léxico
• Una implementación debe hacer dos cosas:
– Reconocer las subcadenas que corresponden a tokens.
– Regresar el valor o lexema de un token• El lexema es la subcadena.
Exp
lora
do
res
Implementación del analizador léxico
• El Analizador léxico por lo regular descarta tokens que no son "importantes“, tokens que no contribuyen a generar el árbol.
• Ejemplos: Espacios en blanco, comentarios.
• Pregunta: ¿Qué pasa si quitamos todos los espacios en blanco y comentarios antes de realizar el análisis léxico?
Exp
lora
do
res
• Una parte muy elevada del tiempo de compilación se consume en la lectura y exploración de los caracteres del programa fuente.
• La sintaxis de los símbolos que trata el explorador se describe con una gramática más simple (regular o tipo 3),
mucho más simple que la del lenguaje a compilar.
• En lugar de tener compiladores separados para cada caso, bastara tener exploradores diferentes, pero el resto del compilador seria el mismo.
Razones por las que es conveniente separar el análisis léxico del sintáctico
Exp
lora
do
res
• Formación y entrega al parser de los tokens. Estos tokens que entrega formaran los terminales del analizador sintáctico.
• Manejar el fichero del programa fuente, es decir abrirlo, a continuación leer sus caracteres y cerrarlo.
• Explorar los literales
• Listar el programa fuente, llegando en algún caso llevar el control exacto de cada carácter leído para señalar el carácter ofensivo en caso de error.
• Manejar las macros. Sabemos que una macro es la expansión del texto fuente, de una manera independiente.
Funciones principales E
xplo
rad
ore
s
• El problema al que se enfrenta un compilador es detectar si una cadena del programa fuente representa o no un nombre de variable aceptable.
• Además cualquier estructura léxica en un lenguaje de programación termina con un conjunto de símbolos reconocido como fin de la estructura. A estos símbolos llamaremos marcas de fin de cadena.
• En el caso de nombres de variables, estas marcas podrían ser espacios, punto y coma, retorno de carro, operadores, etc.
Reconocimiento de componentes léxicos
Exp
lora
do
res
Como paso intermedio en la construcción de un analizador léxico, primero se produce un diagnostico de estado estilizado, llamado diagrama de transición.
Diagrama de transición(1) E
xplo
rad
ore
s
A continuación se muestra un diagrama de transición para el componente léxico oprel (operadores de relación).
Diagrama de transición(2)
0 1 2
3
4
5
7
86
< =>
Otro=>
=Otro
Devuelve (oprel,MEI)
Devuelve (oprel,DIF)
Devuelve (oprel,MEN)
Devuelve (oprel,IGU)
Devuelve (oprel,MAI)
Devuelve (oprel,MAY)
Exp
lora
do
res
Es un arreglo bidimensional cuyos elementos proporcionan el resumen de un diagrama de transición.
Tabla de transición
CARÁCTER LEIDO
ESTADO < = > OTRO
0 1 5 6 error
1 error 2 3 4
2
3
4
5
6 8 7 8 8
7
8
Exp
lora
do
res
Siguiente Semana
Segunda practica calificada.
Teoría de lenguajes y compiladores
Unidad I
Analizador lexicográfico
Temas
Semana 4
Funcionamiento de un analizador lexicográfico. Exploradores