PDF de programación - Análisis léxico - Formalización y desarrollo

Procesadores de Lenguajes

Ingeniería Técnica superior de Ingeniería Informática

Departamento de Lenguajes y Sistemas informáticos

Análisis léxico
Formalización y desarrollo

Javier Vélez Reyes
[email protected]
Departamento de Lenguajes Y Sistemas Informáticos
UNED

Análisis léxico. Formalización y desarrollo
Objetivos

Objetivos

› Conocer las responsabilidades de un analizador léxico

› Aprender cómo funciona
› Entender los diferentes tipos de patrones que reconoce

› Aprender a especificar formalmente analizadores léxicos

› A través de gramáticas formales
› A través de expresiones regulares
› A través de autómatas finitos

› Estudiar la implementación de analizadores léxicos

› Conocer las distintas estrategias de implementación
› Entender las posibles relaciones con la tabla de símbolos

› Estudiar la generación de errores léxicos

Javier Vélez Reyes [email protected]

Análisis léxico. Formalización y desarrollo
Índice

Índice

›

Introducción
› Token
› Patrón léxico
›
›

Lexema
Lenguaje regular

› Especificación de analizadores léxicos

Lenguajes regulares
›
› Gramáticas lineales
› Expresiones regulares
› Autómatas finitos
› Conversión de formalismos

›

Implementación de analizadores léxicos

›

basada en casos

›
›

dirigida por tabla
guiada por herramientas
› Estrategias de implementación
› Gestión de errores
› Construcción de A. léxicos en en la práctica

› ¿Qué es JFlex?
› ¿Cómo funciona JFlex?
› ¿Cómo se usa JFlex?
› Gestión de errores en JFlex
› Desarrollo paso a paso

› Bibliografía

Javier Vélez Reyes [email protected]

Análisis léxico. Formalización y desarrollo
Introducción

Introducción

El primer paso para procesar un programa es convertir la colección de caracteres del
mismo en una colección de componentes léxicos con significado único dentro del
lenguaje llamados tokens. De eso se encarga el analizador léxico o escáner

Foco de atención

El analizador sintáctico va
pidiendo nuevos tokens al
analizador
léxico y éste los
sirve bajo demanda

While ( a > b ) do

a := a + 1;

·

i

·


h

·

w

Analizador léxico

<WHILE, PR>

nextToken ()

Analizador sintáctico

¿Cómo se formaliza un
analizador léxico?
›
› Conversión entre formalismos

Formalismos

¿Cómo se implementa un
analizador léxico?

›
›

Estrategias de implementación
Buenas prácticas

Javier Vélez Reyes [email protected]

Análisis léxico. Formalización y desarrollo
Introducción

Introducción

El primer paso para procesar un programa es convertir la colección de caracteres del
mismo en una colección de componentes léxicos con significado único dentro del
lenguaje llamados tokens. De eso se encarga el analizador léxico o escáner

Definición de token

Categorías de token

Un token es una unidad léxica indivisible con
significado único dentro del lenguaje. Desde el punto
de vista tecnológico se trata de una estructura de
datos que contiene información sobre

ID: Tipo del token
›
› Número de línea
› Número de columna
›
›

Lexema
Valor…

Los tipos de tokens existentes en un lenguaje son
una característica intrínseca al mismo. No obstante,
pueden encontrarse categorías generales

Categoría

Ejemplos

Delimitadores

( ) , ; : [ ]

Palabras reservadas

while true do if for

Identificadores

Index f isEven

Números enteros

3 -4 55 0 7658

Números flotantes

4.5 .3 0.5 8.4e-5

Simbolos especiales

+ -* / . = < > <= >= != ++

Cadenas

“Hola mundo!”

Javier Vélez Reyes [email protected]

Análisis léxico. Formalización y desarrollo
Introducción

Introducción

Cada tipo de token representa a un conjunto de tokens (construcciones léxicas
diferentes) con unos mismos propósitos dentro del lenguaje. Estos tipos se definen a
través de un patrón léxico al que se adscriben los lexemas del tipo

Definición de patrón léxico

Definición de lexema

Un patrón léxico es una expresión abstracta llamada
expresión
identificar
unívocamente un tipo de token y referenciar al
conjunto de todos los tokens que se ajustan a él.

permite

regular

que

La cadena de caracteres específica de un token
que se ajusta al patrón léxico de su tipo se llama
lexema. Existen dos tipos de lexemas

› Cadena propia: lexema idéntica al patrón
› Cadena no propia: lexema encaja con patrón

Tipo de token

Patrón léxico

Ejemplos de lexema

Cadena propia

While

Enteros

División

while

digito+

/

while

12 123 0 45

/

Identificador

letra (letra |digito)*

Index f isEven

SI

NO

SI

NO

Javier Vélez Reyes [email protected]

Análisis léxico. Formalización y desarrollo
Introducción

Introducción

Desde la perspectiva léxica un programa es una familia ordenada de
tokens de varios tipos. Cada tipo, a través de su patrón léxico, define
un micro lenguaje formado por todos aquellos lexemas que encajan
con el patrón léxico. Este tipo de lenguajes sencillos se llaman
lenguajes regulares

Definición de lenguaje regular

Un lenguaje regular describe una familia de tokens
que se ajustan a un determinado patrón léxico.

Lenguaje de

delimitadores de Pascal

Lenguaje de palabras
reservadas de Pascal

Lenguaje de

identificadores Pascal

;
=
,
:
[
..
]
(
)
...

do
downti
if
then
End
...

program
uses
const
var
intger
of
array
begin
for
to

burbuja
ctr
n
i
j
temp
a
readln
writeln
...

program burbuja;
uses crt;
const

n = 5;

var

i,j,temp:integer;
a:array[1..n] of integer;

begin

for i := 1 to n do

readln(a[i]);

for j := (n - 1) downto 1 do

for i := 1 to j do

if (a[i])>(a[i+1]) then
begin

temp := a[i];
a[i] := a[i+1];
a[i+1] := temp;

end;

writeln ('El resultado es:');
for i := 1 to n do
writeln (a[i]);

readln;

end.

Javier Vélez Reyes [email protected]

Análisis léxico. Formalización y desarrollo
Especificación formal de analizadores léxicos

Especificación de lenguajes regulares

Además de la declaración extensiva – sólo viable en los lenguajes finitos – existen 3
diferentes maneras de definir formalmente un lenguaje regular. A lo largo de esta
sección estudiaremos cada una de ellas en detalle y veremos cómo se puede pasar de
cada una a las otras 2

Gramáticas

lineales

Lenguajes
regulares

Expresiones
regulares

Autómatas

finitos

›

Elementos

› Gramáticas lineales
›
›

Expresiones regulares
Autómatas finitos

›

Transformaciones

› De gramáticas a expresiones
› De gramáticas a autómatas
› De expresiones a gramáticas
› De expresiones a autómatas
› De autómatas a gramáticas
› De autómatas a expresiones

Javier Vélez Reyes [email protected]

Análisis léxico. Formalización y desarrollo
Especificación formal de analizadores léxicos

Especificación mediante gramáticas lineales

Una forma de definir formalmente un lenguaje regular es utilizar una gramática lineal,
que describe todas las reglas que se pueden aplicar para la construcción de lexemas
que pertenecen al lenguaje regular

Definición de gramática lineal
Una gramática lineal es un conjunto de 4 elementos
G = (T, N, S, P) donde:

Tipos de gramáticas lineales
Existen en realidad 2 tipos de gramáticas lineales. En
función de la forma del conjunto de reglas de
producción podemos distinguir entre:

T es un conjunto de símbolos terminales

›
› N es un conjunto de símbolos no terminales
›
›

S Є N axioma gramatical
P un conjunto de reglas de producción de la forma

1. A ::= B x donde A, B Є N y x Є T
2. A ::= x B donde A, B Є N y x Є T
3. A ::= x donde x Є T U {

}

A veces T se elide, N se deduce de los antecedentes de
las reglas de P y se asume que el antecedente de la
primera regla es S con lo G sólo a través de P

representa la cadena vacía (ausencia de terminal)

› Gramáticas lineales por la izquierda

› Usan reglas A ::= B x
› Usan reglas A ::= x

› Gramáticas lineales por la derecha

› Usan reglas A ::= x B
› Usan reglas A ::= x

Dada una gramática G lineal por la izquierda siempre
se puede encontrar una gramática G’
lineal por la
derecha y recíprocamente

Javier Vélez Reyes [email protected]

Análisis léxico. Formalización y desarrollo
Especificación formal de analizadores léxicos

Especificación mediante gramáticas lineales

Una forma de definir formalmente un lenguaje regular es utilizar una gramática lineal,
que describe todas las reglas que se pueden aplicar para la construcción de lexemas
que pertenecen al lenguaje regular

Derivación gramatical
Una gramática debe interpretarse como un conjunto de reglas de reescritura o
transformación de elementos no terminales en elementos terminales o no
terminales.

Ejemplo

LG = {a b*}
Sea G = (T, N A, P) con

›
›

La primera transformación parte del axioma
En cada paso se aplica una única regla

›
›
›

Las reglas pueden extender la transformación ( A::= B x / A ::= x B)
Las reglas pueden ser recursivas (A ::= A x / A ::= x A)
Las reglas pueden ser terminales (A ::= x)

›

El proceso debe ser convergente

T = {a, b}
N = {A, B}
P = {

A ::= a B
A ::= a
B ::= b B
B ::= b

}

Javier Vélez Reyes [email protected]

Análisis léxico. Formalización y desarrollo
Especificación formal de analizadores léxicos

Especificación mediante gramáticas lineales

Una forma de definir formalmente un lenguaje regular es utilizar una gramática lineal,
que describe todas las reglas que se pueden aplicar para la construcción de lexemas
que pertenecen al lenguaje regular

Derivación gramatical
El problema ahora se traduce en, dada una cadena formada por una secuencia de
elementos terminales de T, demostrar que dicha cadena pertenece al
lenguaje
definido por la gramática

Ejemplo

LG = {a b*}
Sea G = (T, N A, P) con

Cadena de
derivación

axioma

asidero

A → aB → abB → abbB → abbb

Paso de
derivación

Forma
de frase

Frase

T = {a, b}
N = {A, B}
P = {

A ::= a B
A ::= a
B ::= b B
B ::= b

}

Javier Vélez Reyes [email protected]

Análisis léxico. Formalización y desarrollo
Especificación formal de analizadores léxicos

Especificación mediante gramáticas lineales

Una forma de definir formalmente un lenguaje regular es utilizar una gramática lineal,
que describe todas las regl