Analizador Lexico

1

Programa Fuente

Analizador
Léxico

Componente léxico
Obtén otro
otro
componente léxico

Analizador
Sintáctico

Tabla de
Símbolos

ANÁLISIS LÉXICO

Funciones del Análisis Léxico
2

Leer los caracteres de la entrada
Generar una secuencia de componentes léxicos
(TOKENS)
Eliminar comentarios, delimitadores (espacios,
símbolos de puntación, fin de línea)
Relacionar losmensajes de error con las líneas del
programa fuente
Introducir los identificadores en la tabla de
símbolos

1

Aspectos del Análisis Léxico
3

Diseño más sencillo
Los símbolos que trata el scanner se describe con una gramática
más simple que la del parser, gramática regular

Mejora la eficiencia
Gran parte del tiempo de compilación se consume en la lectura y
exploración decaracteres

Mejora la transportabilidad
Se pueden tener varias versiones del scanner una para distintos
códigos (EBCDID, ASCII, ...), con el mismo parser

Descarga el análisis sintáctico
Ejemplo; no puedo distinguir en FORTRAN hasta después del 1
DO 5 I=1.25
DO 5 I=1,25

Funciones Principales de AL
4

Formación y entrega al parser de los tokens
Manejar el fichero del programa fuenteExplorar los literales
Listar el programa fuente
Manejar las macros
Controlar si es de formato libre o no
Libre: PASCAL, ALGOL
No libre: FORTRAN, BASIC

2

Tokens, patrones y lexemas, I
5

Un token es un símbolo terminal de la gramática del
analizador
analizador sintáctico
Varias cadenas diferentes en la entrada pueden
dar el mismo token a la salida
Un token se describe mediante unpatrón
Un lexema es un conjunto de caracteres que
concuerdan
concuerdan con el patrón de un token
En la mayoría de lenguajes son tokens:
Palabras clave, operadores, identificadores, constantes,
cadenas literales y signos de puntación

Tokens, patrones y lexemas, II
6

Existen una serie de palabras clave (reservadas) en muchos
lenguajes que conviene introducir directamente en la tabla desímbolos
símbolos:
Tokens
Lexemas
if

if x1>3 then a:=b+x1

if

id

x1,a,b

relación

>

op

+

asign

Atributos:

:=

then

then

num

3

Los atributos de los identificadores se pueden guardar en la tabla de
símbolos
Los otros se pueden guardar en otra tabla o devolverlos junto al token

3

Tokens, patrones y lexemas, III
7

Componente LéxicoLéxico

Lexemas de Ejemplo
de Ejemplo

Descripción del
del
Patrón

Const

Const

Const

If

If

If

Relación



< O = o >

Identificador

Pi, cuenta, D2

[a-zA-z]+

Número

3.1416, 0

[0-9]?\.[0-9]+

Literal

“el resultado:”

Cualquier carácter
entre “” menos “

Análisis Léxico, representación
8

Expresión Regular
[a-zA-Z][a-zA-Z0-9]*

Autómata finito(diagrama o tabla de transición)
a

...

z

A

...

Z

0

...

9

→q0 q1 ... q1

q1

...

q1

φ

...

φ

*q1

q1

...

q1

q1

...

q1

q1 ... q1

Gramática Lineal (regular)
S::= aR | ... | zR | AR | ... | ZR
R::= aR | ... | zR | AR | ... | ZR | 0R | ... | 9R | λ

4

Analizador de relaciones matemáticas
9

<

q0

otro

otro

q5
q6=

q7

Devuelve
=>

q8

Devuelve


=
>

q2

Devuelve


q4

q1

Devuelve


otro
q9

Implementación de un AL
10

Utilizando un lenguaje de alto nivel
Programación
Tabla compacta
Hasing
Autómata programado

Utilizando ensamblador
Más eficiente
Más difícil

Utili
Utilizando un generador de Analizadores Léxicos (LEX)
Lé
(LEX)
Más cómodo

Consejo:Ordenar las reglas/transiciones de acuerdo a la
frecuencia de utilización

5

Programación de un AL
11

Dos punteros de lectura:
Puntero actual (PA, “current pointer”): El último carácter aceptado
Puntero de búsqueda (PB, “lookahead pointer”): El último carácter leído

Funciones de lectura:
GetChar: mueve el PB hacia delante y devuelve el siguiente carácter
Fail: mueve el PB a donde...