Violencia

1

Programa Fuente g

Analizador Léxico Lé i

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

Analizador Sintáctico Si á i

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 de caracteresMejora 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 f M f fuente Explorarlos 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 sintáctico Varias cadenas diferentes en la entrada pueden dar el mismo token a la salida Un token se describe mediante un patrón Un lexema es unconjunto de caracteres que 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 de símbolos: símbolos Tokens Lexemas
if idif x1,a,b > + := then 3 relación op asign then

if x1>3 then a:=b+x1

Atributos:

num

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éxico Const If Relación Identificador Número Literal

Lexemas de Ejemplo Const If Pi, cuenta,D2 3.1416, 0 “el resultado:”

Descripción del Patrón Const If < O = o > [a-zA-z]+ [0-9]?\.[0-9]+ 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 *q1 ... z A q1 q1 ... ... ... Z q1 q1 0
φ

... ... ...

9
φ

→q0 q1 ... q1 q1 ... q1

q1

q1

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

4

Analizador de relaciones matemáticas
9

q0 = > otro

<

q1

= >

q2 q3 q4

Devuelve

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ícilUtilizando Utili d un generador de Analizadores Léxicos (LEX) d d A li d Lé i
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 está el PA Retract: mueve el PB un carácter hacia atrás Accept: mueve el PA a donde está el PB

Predicados:
IsLetter(x):= x∈ [A..Za..z] IsDigit(x):= x∈ [0..9] IsDelimiter(x):= x∈ [.,;]

Acciones:
InstallName(id): introduce un nombre en la tabla de símbolos

Ejemplo con Identificador
12...