Download Diseno Instruccional - Biblioteca de la UNS

Teoría de lenguajes y compiladores
Unidad I
Analizadores lexicográficos
Semana 4
Exploradores
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
Desarrollar un analizador
lexicográfico
3
Objetivos Instruccionales
Comprender el
funcionamiento de un
analizador lexicográfico.
Contenidos
Exploradores
¿Qué es un token?
Exploradores
• 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.
Tokens
Exploradores
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.
• Paréntesis apertura: un paréntesis izquierdo.
Exploradores
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.
Token, Patrones y Lexemas
Exploradores
• Ejemplo: Para el lenguaje c++
Token
Lexema
Const
const
Relación <,<=,!=
Id
x, y, cont
Patrón
const
<|<=|!=
letras, seguidas de
más letras y dígitos
Exploradores
ANALISIS LEXICO
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.)
Exploradores
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.
Exploradores
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?
Exploradores
Razones por las que es conveniente
separar el análisis léxico del
sintáctico
• 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.
Funciones principales
Exploradores
• 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.
• Listar el programa fuente, llegando en algún caso
a 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.
Exploradores
Reconocimiento de
componentes léxicos
• 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.
Exploradores
Diagrama de transición(1)
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(2)
Exploradores
A continuación se muestra un diagrama de transición para el
componente léxico oprel (operadores de relación).
0
<
=
1
2
Devuelve (oprel,MEI)
3
Devuelve (oprel,DIF)
>
Otro
=
>
4
5
Devuelve (oprel,IGU)
=
6
Devuelve (oprel,MEN)
Devuelve (oprel,MAI)
7
Otro
Devuelve (oprel,MAY)
8
Tabla de transición
Es un arreglo bidimensional cuyos elementos
proporcionan el resumen de un diagrama de
transición.
Exploradores
CARÁCTER LEIDO
ESTADO
<
=
>
OTRO
0
1
5
6
error
1
error
2
3
4
8
7
8
8
2
3
4
5
6
7
8
Teoría de lenguajes y compiladores
Unidad I
Analizadores lexicográficos
Semana 4
Exploradores