path: root/cc/n2.lyx

#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\begin_preamble
\usepackage{tikz}
\end_preamble
\use_default_options true
\maintain_unincluded_children false
\language spanish
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style french
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Standard
Un 
\series bold
\emph on
token
\series default
\emph default
 es un par formado por un 
\series bold
nombre de 
\emph on
token
\series default
\emph default
, que representa un tipo de unidad léxica, y un atributo opcional, cuyo
 tipo depende del nombre de 
\emph on
token
\emph default
.
 Todo nombre de 
\emph on
token
\emph default
 lleva asociado un 
\series bold
patrón
\series default
, un lenguaje regular que describe las secuencias de caracteres que deben
 ser convertidas a un 
\emph on
token
\emph default
 con dicho nombre, llamadas 
\series bold
lexemas
\series default
.
 
\end_layout

\begin_layout Standard
Un 
\series bold
analizador léxico
\series default
 es un programa que separa una secuencia de caracteres de entrada en lexemas
 y genera una lista de 
\emph on
tokens
\emph default
, informando de errores y pudiendo hacer otras tareas como ignorar comentarios
 y caracteres de espaciado.
 
\end_layout

\begin_layout Standard
El analizador sintáctico usa los nombres de 
\emph on
token
\emph default
 como símbolos terminales de una gramática libre de contexto, pues aunque
 esta gramática podría incluir la definición de los 
\emph on
tokens
\emph default
, dividir el análisis en dos fases simplifica el diseño, y mejora la portabilida
d al no tener que preocuparse el analizador sintáctico de la codificación
 de caracteres.
 En general el analizador léxico está subordinado al sintáctico, ofreciéndole
 una interfaz de llamadas.
\end_layout

\begin_layout Section
Fundamentos teóricos
\end_layout

\begin_layout Standard
Dado un alfabeto 
\begin_inset Formula $V$
\end_inset

, los símbolos 
\begin_inset Formula $\lambda$
\end_inset

 y 
\begin_inset Formula $\emptyset$
\end_inset

 y los elementos de 
\begin_inset Formula $V$
\end_inset

 son 
\series bold
expresiones regulares
\series default
; también lo son 
\begin_inset Formula $(\alpha|\beta)$
\end_inset

, 
\begin_inset Formula $(\alpha\circ\beta)$
\end_inset

 y 
\begin_inset Formula $(\alpha^{*})$
\end_inset

 si 
\begin_inset Formula $\alpha$
\end_inset

 y 
\begin_inset Formula $\beta$
\end_inset

 son expresiones regulares, y solo son expresiones regulares las expresiones
 que se obtienen aplicando estas reglas.
 Se pueden omitir los paréntesis si no causa ambigüedad, entendiendo que
 
\begin_inset Formula $*$
\end_inset

 tiene más precedencia que 
\begin_inset Formula $\circ$
\end_inset

 y 
\begin_inset Formula $\circ$
\end_inset

 más que 
\begin_inset Formula $|$
\end_inset

 y que los tres operadores son asociativos por la izquierda, y se puede
 escribir 
\begin_inset Formula $\alpha\beta\coloneqq \alpha\circ\beta$
\end_inset

.
\end_layout

\begin_layout Standard
Toda expresión regular 
\begin_inset Formula $\alpha$
\end_inset

 lleva asociada un lenguaje 
\begin_inset Formula $L(\alpha)$
\end_inset

, dado por 
\begin_inset Formula $L(\emptyset)\coloneqq \emptyset$
\end_inset

; 
\begin_inset Formula $L(\lambda)\coloneqq \{\lambda\}$
\end_inset

; si 
\begin_inset Formula $a\in V$
\end_inset

, 
\begin_inset Formula $L(a)\coloneqq \{a\}$
\end_inset

, y si 
\begin_inset Formula $\alpha$
\end_inset

 y 
\begin_inset Formula $\beta$
\end_inset

 son expresiones regulares, 
\begin_inset Formula $L(\alpha|\beta)\coloneqq L(\alpha)\cup L(\beta)$
\end_inset

, 
\begin_inset Formula $L(\alpha\beta)\coloneqq L(\alpha)L(\beta)$
\end_inset

 y 
\begin_inset Formula $L(\alpha^{*})\coloneqq L(\alpha)^{*}$
\end_inset

.
 Un lenguaje es regular si es el asociado a alguna expresión regular.
 Dos expresiones regulares son 
\series bold
equivalentes
\series default
, 
\begin_inset Formula $\alpha=\beta$
\end_inset

, si 
\begin_inset Formula $L(\alpha)=L(\beta)$
\end_inset

.
\end_layout

\begin_layout Standard
Un 
\series bold
AFD
\series default
 es una tupla 
\begin_inset Formula $(Q,V,\delta,q_{0},F)$
\end_inset

 formada por un conjunto finito de 
\series bold
estados
\series default
 
\begin_inset Formula $Q$
\end_inset

, un alfabeto 
\begin_inset Formula $V$
\end_inset

, un 
\series bold
estado inicial
\series default
 
\begin_inset Formula $q_{0}\in Q$
\end_inset

, un conjunto de 
\series bold
estados finales
\series default
 
\begin_inset Formula $F\subseteq Q$
\end_inset

 y una 
\series bold
función de transición
\series default
 
\begin_inset Formula $\delta:D\subseteq(Q\times V)\to Q$
\end_inset

.
\end_layout

\begin_layout Standard
Un 
\series bold
AFND
\series default
 es una tupla 
\begin_inset Formula $(Q,V,\delta,q_{0},F)$
\end_inset

, definida como un AFD salvo que 
\begin_inset Formula $\delta:Q\times(V\dot{\cup}\{\lambda\})\to{\cal P}(Q)$
\end_inset

.
\end_layout

\begin_layout Section
Diseño
\end_layout

\begin_layout Standard
Para diseñar un analizador léxico usamos 
\emph on
Flex
\emph default
, una herramienta multiplataforma que genera código en C basándose en un
 fichero de especificación de expresiones regulares, sucesora de 
\emph on
Lex
\emph default
 para Unix.
 Los ficheros de especificación suelen tener extensión 
\family typewriter
.l
\family default
 y constan de 3 partes separadas por una línea 
\family typewriter
%%
\family default
:
\end_layout

\begin_layout Enumerate
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{sloppypar}
\end_layout

\end_inset


\series bold
Definiciones
\series default
: Macros para expresiones regulares auxiliares con formato 
\family typewriter
\emph on
nombre expresión
\family default
\emph default
 en una línea.
 Código C, entre una línea 
\family typewriter
%{
\family default
 y una 
\family typewriter
}%
\family default
.
 Opciones con 
\family typewriter
%option 
\emph on
opción
\family default
\emph default
.
 Condiciones de contexto, tablas, etc.
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
end{sloppypar}
\end_layout

\end_inset


\end_layout

\begin_layout Enumerate

\series bold
Reglas
\series default
: Con forma 
\family typewriter
\emph on
expresión código
\family default
\emph default
, donde 
\family typewriter
\emph on
expresión
\family default
\emph default
 es una expresión regular que puede incluir macros con formato 
\family typewriter
{
\emph on
nombre
\emph default
}
\family default
 y 
\family typewriter
\emph on
código
\family default
\emph default
 es una línea de C o un bloque código entre llaves que se ejecuta cuando
 se reconoce un lexema asociado a la expresión regular.
 Si en el código hay una sentencia 
\family typewriter
return
\family default
, esta sale del analizador léxico devolviendo el entero indicado, normalmente
 el código de 
\emph on
token
\emph default
.
 De lo contrario sigue leyendo, por lo que es habitual usar reglas para
 espacios y comentarios con la sentencia vacía (
\family typewriter
;
\family default
).
\end_layout

\begin_layout Enumerate

\series bold
Subrutinas de usuario
\series default
: Código C auxiliar que se añade al final del fichero generado.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{sloppypar}
\end_layout

\end_inset

La orden 
\family typewriter
flex [-o 
\emph on
SALIDA
\emph default
] 
\emph on
FICHERO
\family default
\emph default
 genera un analizador léxico 
\family typewriter
\emph on
SALIDA
\family default
\emph default
 (por defecto, 
\family typewriter
lex.yy.c
\family default
) desde la especificación 
\family typewriter
\emph on
FICHERO
\family default
\emph default
.
 Este debe enlazarse a la biblioteca 
\family typewriter
fl
\family default
, lo que en 
\family typewriter
gcc
\family default
 se hace con la opción 
\family typewriter
-lfl
\family default
.
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
end{sloppypar}
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Identificar los 
\emph on
tokens
\emph default
 y definir los patrones
\end_layout

\begin_layout Standard
Se suelen considerar 
\emph on
tokens
\emph default
:
\end_layout

\begin_layout Itemize
Los identificadores.
\end_layout

\begin_layout Itemize
Las 
\series bold
palabras clave
\series default
.
 Están 
\series bold
reservadas
\series default
 si usuario no puede modificar su significado, en cuyo caso el analizador
 léxico puede reconocerlas directamente.
 Si no lo están, el analizador léxico debe reconocerlas como identificadores
 para que una fase posterior las distinga.
\end_layout

\begin_layout Itemize
Los operadores y signos de puntuación.
\end_layout

\begin_layout Itemize
Las constantes simples, como reales o enteros sin el signo, caracteres o
 cadenas de caracteres.
\end_layout

\begin_layout Itemize
Los espacios en blanco y comentarios, aunque en general el analizador léxico
 los ignora, no los devuelve.
\end_layout

\begin_layout Standard
Las expresiones regulares en 
\emph on
Flex
\emph default
 se forman combinando símbolos y operadores.
 Los operadores son, en orden de prioridad:
\end_layout

\begin_layout Enumerate

\family typewriter
?
\family default
, 
\family typewriter
*
\family default
 y 
\family typewriter
+
\family default
: respectivamente, de 0–1, 0 o más y 1 o más repeticiones de lo anterior.
 
\end_layout

\begin_layout Enumerate
Concatenación de símbolos.
\end_layout

\begin_layout Enumerate

\family typewriter
{
\family default
...
\family typewriter
}
\family default
, de repetición.
\end_layout

\begin_layout Enumerate

\family typewriter
^
\family default
, de comienzo de línea, y 
\family typewriter
$
\family default
, de final.
\end_layout

\begin_layout Enumerate

\family typewriter
|
\family default
 de disyunción entre los elementos a izquierda y derecha.
\end_layout

\begin_layout Enumerate

\family typewriter
/
\family default
, para reconocer la expresión regular de la izquierda solo si va seguida
 de la de la derecha (
\emph on
look-ahead
\emph default
).
\end_layout

\begin_layout Standard
También se puede agrupar con paréntesis 
\family typewriter
(
\family default
...
\family typewriter
)
\family default
, preceder un símbolo de 
\family typewriter

\backslash

\family default
 para evitar que se trate como un operador o indicar una cadena de caracteres
 literal con 
\family typewriter
"
\family default
...
\family typewriter
"
\family default
.
 Otros operadores:
\end_layout

\begin_layout Enumerate

\family typewriter
[
\family default
...
\family typewriter
]
\family default
 indica disyunción entre los caracteres del conjunto indicado: 
\family typewriter
\emph on
a
\emph default
-
\emph on
b
\family default
\emph default
 indica todos los caracteres entre 
\family typewriter
\emph on
a
\family default
\emph default
 y 
\family typewriter
\emph on
b
\family default
\emph default
, inclusive; 
\family typewriter
^
\family default
 al principio complementa el conjunto; 
\family typewriter

\backslash

\family default
 permite indicar caracteres de escape; 
\family typewriter
[:
\family default
...
\family typewriter
:]
\family default
 indica una clase de caracteres como 
\family typewriter
[:digit:]
\family default
 o 
\family typewriter
[:alnum:]
\family default
, y cualquier otro caracter dentro de los corchetes se indica a sí mismo.
\end_layout

\begin_layout Enumerate

\family typewriter
.

\family default
 indica cualquier caracter salvo salto de línea.
\end_layout

\begin_layout Enumerate

\family typewriter
<<EOF>>
\family default
 indica final de fichero.
\end_layout

\begin_layout Standard
Llamamos 
\series bold
caracteres de anticipación
\series default
 a los que se leen al hacer 
\emph on
look-ahead
\emph default
 para determinar el final de un 
\emph on
token
\emph default
, lo que hace falta cuando hay reglas que acaban en 
\family typewriter
+
\family default
, 
\family typewriter
*
\family default
, 
\family typewriter
?
\family default
, 
\family typewriter
$
\family default
 y 
\family typewriter
/
\family default
..., y cuando un lexema de una expresión regular puede ser prefijo de uno de
 otra.
 
\emph on
Flex
\emph default
 maneja esto de forma automática, devolviendo a la entrada los caracteres
 no usados (
\emph on
push back
\emph default
).
 
\end_layout

\begin_layout Standard
En caso de ambigüedad en las reglas, 
\emph on
Flex
\emph default
 reconoce el lexema más largo posible que pueda estar asociado a una expresión
 regular, y si este puede corresponder a varias, se asocia a la que aparezca
 antes.
 Así, las palabras reservadas deben estar antes que la expresión regular
 que reconoce los identificadores.
\end_layout

\begin_layout Subsection
Construcción e implementación del autómata
\end_layout

\begin_layout Standard
Se podría obtener un AFD correspondiente a las expresiones regulares directament
e, pero esto es difícil, por lo que se obtiene un AFND y, como su simulación
 es costosa, se construye entonces un AFD equivalente y se minimiza.
 Podemos simular directamente la tabla de transiciones con los estados o
 simular el diagrama de transiciones mediante código específico.
 De esto se encarga 
\emph on
Flex
\emph default
.
\end_layout

\begin_layout Subsection
Diseño de la interfaz de entrada y salida
\end_layout

\begin_layout Standard
Para la entrada, es muy ineficiente leer el código de caracter a caracter,
 por lo que se lee en bloques que se guardan en 
\emph on
buffers
\emph default
, que deben diseñarse permitiendo secuencias largas de caracteres de anticipació
n.
 La salida suele ser una o varias funciones que el analizador sintáctico
 llama para obtener el siguiente 
\emph on
token
\emph default
.
 
\emph on
Flex
\emph default
 proporciona la siguiente interfaz:
\end_layout

\begin_layout Description

\family typewriter
yytext
\family default
 Último lexema leído.
\end_layout

\begin_layout Description

\family typewriter
yyleng
\family default
 Longitud de 
\family typewriter
yytext
\family default
.
\end_layout

\begin_layout Description

\family typewriter
yylineno
\family default
 Activando la opción 
\family typewriter
yylineno
\family default
, número de línea actual.
\end_layout

\begin_layout Description

\family typewriter
yymore()
\family default
 Indica a 
\emph on
Flex
\emph default
 que, la próxima vez que se lea un lexema, este se debería concatenar al
 actual (
\family typewriter
yytext
\family default
) en vez de reemplazarlo.
\end_layout

\begin_layout Description

\family typewriter
yyless(int)
\family default
 Retrasa el puntero de lectura para que apunte al caracter de 
\family typewriter
yytext
\family default
 con el índice dado.
\end_layout

\begin_layout Description

\family typewriter
yywrap()
\family default
 Se ejecuta al alcanzarse el final del fichero.
\end_layout

\begin_layout Description

\family typewriter
yyin
\family default
 Descriptor de fichero de donde se lee.
\end_layout

\begin_layout Description

\family typewriter
yyout
\family default
 Descriptor de fichero al que se escribe al usar la opción 
\family typewriter
echo
\family default
.
\end_layout

\begin_layout Description

\family typewriter
input()
\family default
 Lee el siguiente caracter del flujo de entrada.
\end_layout

\begin_layout Description

\family typewriter
output(char)
\family default
 Escribe el caracter dado en la salida.
\end_layout

\begin_layout Description

\family typewriter
unput(char)
\family default
 Coloca el caracter dado en el flujo de entrada, para que sea el primero
 leído en la próxima ocasión.
\end_layout

\begin_layout Subsection
Manejo de errores
\end_layout

\begin_layout Standard
Una forma sencilla es la 
\series bold
recuperación en modo pánico
\series default
: ignorar caracteres hasta encontrar un caracter válido para un nuevo 
\emph on
token
\emph default
.
 Para implementarlo es necesaria una expresión regular capaz de reconocer
 un conjunto de caracteres erróneos antes del comienzo de un nuevo lexema.
 Otras técnicas permiten borrar un caracter extraño, insertar uno que falta,
 reemplazar un caracter incorrecto por otro correcto o intercambiar caracteres
 adyacentes.
\end_layout

\end_body
\end_document