Download Diseno Instruccional - Biblioteca de la UNS

Teoría de lenguajes y compiladores
Unidad I
Analizador lexicográfico
Semana 4
Temas
Funcionamiento de un analizador lexicográfico. 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
• 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.
Temas
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.
• Open par: 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
Const
Relación
Id
Lexema
const
<,<=,!=
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.)
Implementación del analizador
léxico
Exploradores
• 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.
• 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.
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
Siguiente Semana
Segunda practica calificada.
Teoría de lenguajes y compiladores
Unidad I
Analizador lexicográfico
Semana 4
Temas
Funcionamiento de un analizador lexicográfico. Exploradores