path: root/cc/n1.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
\input{spec}
\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
lenguaje de programación
\series default
 es una notación formal para expresar algoritmos.
 Distinguimos lenguajes:
\end_layout

\begin_layout Enumerate

\series bold
De primera generación
\series default
 o 
\series bold
lenguajes máquina
\series default
, código binario entendible directamente por un procesador y dependiente
 de la máquina.
 Los programas son difíciles de leer, escribir, modificar y corregir, por
 lo que el desarrollo es lento y propenso a fallos.
 
\end_layout

\begin_layout Enumerate

\series bold
De segunda generación
\series default
 o 
\series bold
ensambladores
\series default
, creados al comienzo de los años 50, permiten usar abreviaturas mnemotécnicas
 para representar las instrucciones de la máquina y códigos octales o hexadecima
les para valores.
 También permiten macros, secuencias de instrucciones parametrizadas para
 uso frecuente.
\end_layout

\begin_layout Enumerate

\series bold
De tercera generación
\series default
 o 
\series bold
de alto nivel
\series default
, que permiten usar estructuras de control basadas en objetos lógicos y
 especificar los datos, funciones o procesos de forma independiente de la
 máquina.
 Fortran, Cobol, C, C++, Java.
\end_layout

\begin_layout Enumerate

\series bold
De cuarta generación
\series default
, para problemas específicos, como SQL para bases de datos o PostScript
 para dar formato a texto.
\end_layout

\begin_layout Enumerate

\series bold
De quinta generación
\series default
 o 
\series bold
declarativos
\series default
, como Prolog o Haskell, con los que se especifica el cálculo que se quiere
 realizar más que cómo debe realizarse.
\end_layout

\begin_layout Section
Traductores
\end_layout

\begin_layout Standard
Un 
\series bold
traductor
\series default
 es un programa que acepta textos en un lenguaje de programación 
\series bold
fuente
\series default
 (
\series bold
programa fuente
\series default
) y genera otro semánticamente equivalente en un lenguaje de programación
 
\series bold
destino
\series default
 (
\series bold
programa objeto
\series default
).
 Tipos:
\end_layout

\begin_layout Itemize

\series bold
Preprocesador
\series default
: traductor de una forma extendida de un lenguaje de alto nivel a su forma
 estándar.
 Reúne el programa fuente, a menudo dividido en módulos en ficheros distintos.
\end_layout

\begin_layout Itemize

\series bold
Compilador
\series default
: de un lenguaje de alto nivel a otro de bajo nivel, informando también
 de cualquier error detectado en el programa fuente.
\end_layout

\begin_deeper
\begin_layout Itemize

\series bold
Cruzado
\series default
 (
\emph on
cross-compiler
\emph default
): se ejecuta sobre una 
\series bold
máquina huésped
\series default
 pero genera código para una 
\series bold
máquina destino
\series default
 distinta.
\end_layout

\begin_layout Itemize

\series bold
\emph on
Just-in-time
\series default
\emph default
 (
\series bold
JIT
\series default
): Traduce código de una máquina abstracta a código de una máquina real
 según se necesite en la ejecución de dicho código.
\end_layout

\begin_layout Itemize

\series bold
Optimizador
\series default
: modifica el código intermedio o el código objeto para mejorar su eficiencia,
 sin alterar la funcionalidad del programa original.
\end_layout

\end_deeper
\begin_layout Itemize

\series bold
Ensamblador
\series default
: de un lenguaje ensamblador a su correspondiente código máquina.
\end_layout

\begin_layout Itemize

\series bold
Traductor de alto nivel
\series default
: la fuente y el destino son lenguajes de alto nivel.
\end_layout

\begin_layout Itemize

\series bold
Desensamblador
\series default
: de un código máquina a su correspondiente lenguaje ensamblador.
\end_layout

\begin_layout Itemize

\series bold
Descompilador
\series default
: de un lenguaje de bajo nivel a otro de alto nivel.
\end_layout

\begin_layout Standard
Un 
\series bold
traductor de 
\begin_inset Formula $n$
\end_inset

 etapas
\series default
 es el traductor resultante de componer 
\begin_inset Formula $n$
\end_inset

 traductores, manejando 
\begin_inset Formula $n-1$
\end_inset

 lenguajes intermedios.
 Un traductor es 
\series bold
de una pasada
\series default
 si genera el código objeto realizando una única lectura del código fuente,
 o 
\series bold
de múltiples pasadas
\series default
 si procesa varias veces el código fuente o alguna representación intermedia
 de este.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{center}
\end_layout

\begin_layout Plain Layout


\backslash
begin{tikzpicture}
\backslash
draw (0,0) 
\backslash
program{$P$}{$L$};
\backslash
end{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
hfil
\end_layout

\begin_layout Plain Layout


\backslash
begin{tikzpicture}
\backslash
draw (0,0) 
\backslash
translator{$S$}{$D$}{$I$};
\backslash
end{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
hfil
\end_layout

\begin_layout Plain Layout


\backslash
begin{tikzpicture}
\backslash
draw (0,0) 
\backslash
machine{$M$};
\backslash
end{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
end{center}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:diag"

\end_inset

De izquierda a derecha, diagrama de un programa común, de un traductor y
 de una máquina.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Representamos programas, traductores (que también son programas) y máquinas
 como se muestra en la figura 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:diag"
plural "false"
caps "false"
noprefix "false"

\end_inset

, donde 
\begin_inset Formula $P$
\end_inset

 es el nombre del programa, 
\begin_inset Formula $L$
\end_inset

 es el lenguaje en que está representado, 
\begin_inset Formula $S$
\end_inset

 es el lenguaje fuente del traductor, 
\begin_inset Formula $D$
\end_inset

 es el lenguaje destino, 
\begin_inset Formula $I$
\end_inset

 es el 
\series bold
lenguaje de implementación
\series default
, en el que está representado el traductor, y 
\begin_inset Formula $M$
\end_inset

 es el lenguaje máquina aceptado.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{center}
\backslash
begin{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
draw (0,0) 
\backslash
machine{$M$} 
\backslash
run{
\backslash
translator{$S$}{$D$}{$M$}
\backslash
source{
\backslash
program{$P$}{$S$}}
\backslash
object{
\backslash
program{$P$}{$D$}}};
\end_layout

\begin_layout Plain Layout


\backslash
end{tikzpicture}
\backslash
end{center}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:trans"

\end_inset

Proceso de traducción.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Para indicar que un programa se ejecuta sobre una cierta máquina, lo situamos
 encima, y para indicar que un traductor traduce un programa de un lenguaje
 fuente a uno destino, situamos el programa fuente, cuyo lenguaje es el
 lenguaje fuente del traductor, a la izquierda del mismo, y el destino,
 de mismo nombre pero lenguaje el de destino del traductor, a la derecha.
 Así, un proceso traductor se representa como en la figura 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:trans"
plural "false"
caps "false"
noprefix "false"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Section
Compiladores
\end_layout

\begin_layout Standard
Un compilador se divide en fases:
\end_layout

\begin_layout Enumerate
Fase de 
\series bold
análisis
\series default
 o 
\series bold
\emph on
front-end
\series default
\emph default
: Determina la estructura y el significado de un código fuente creando una
 representación intermedia.
\end_layout

\begin_deeper
\begin_layout Enumerate

\series bold
Análisis léxico
\series default
: Transforma un flujo de caracteres en un flujo de 
\series bold
\emph on
tokens
\series default
\emph default
, identificadores de variables o funciones, palabras clave, constantes,
 operadores, etc.
\end_layout

\begin_layout Enumerate

\series bold
Análisis sintáctico
\series default
: Crea un árbol sintáctico que refleja la estructura gramatical del programa.
 Se usan autómatas con pila para reconocer una gramática libre de contexto
 normalmente recursiva, si bien la mayoría de lenguajes de programación
 son dependientes del contexto.
\end_layout

\begin_layout Enumerate

\series bold
Análisis semántico
\series default
: Realiza verificaciones que no se pueden incluir en gramáticas libres de
 contexto y calcula valores semánticos, creando un 
\series bold
árbol semántico
\series default
.
 La semántica se especifica con métodos formales.
\end_layout

\begin_layout Enumerate

\series bold
Generación de código intermedio
\series default
 en un lenguaje de bajo nivel, que debe ser fácil de producir y de traducir
 a código objeto.
\end_layout

\end_deeper
\begin_layout Enumerate

\series bold
Optimización de código intermedio
\series default
, resultando en un código semánticamente equivalente pero con menor consumo
 de memoria o tiempo de ejecución.
 No se suele producir código óptimo, pues este es un problema NP-completo.
 Como esta fase requiere tiempo, el compilador suele ofrecer la opción de
 desactivarla para el desarrollo o la depuración de programas.
\end_layout

\begin_layout Enumerate
Fase de 
\series bold
síntesis
\series default
 o 
\series bold
\emph on
back-end
\series default
\emph default
: Convierte el código intermedio en un programa objeto semánticamente equivalent
e.
\end_layout

\begin_deeper
\begin_layout Enumerate

\series bold
Generación de código
\series default
: Traducción dirigida por la sintaxis, basada en la gramática del lenguaje
 intermedio.
\end_layout

\begin_layout Enumerate

\series bold
Optimización
\series default
 de código dependiente de la máquina.
\end_layout

\end_deeper
\begin_layout Standard
En la práctica, algunas de estas fases se agrupan, sin construir los datos
 intermedios de forma explícita.
 
\end_layout

\begin_layout Standard
Cuando el lenguaje de implementación y el lenguaje fuente del compilador
 coinciden, el compilador puede compilarse a sí mismo, y hablamos de 
\series bold
arranque
\series default
 o 
\emph on
bootstrapping
\emph default
.
 El primer compilador capaz de compilarse a sí mismo fue credo para Lisp
 por Hart y Levin en el MIT en 1962, y desde 1970 esto es habitual, aunque
 Pascal y C son alternativas muy usadas.
\end_layout

\begin_layout Standard
Cuando un programa se divide en varios ficheros fuente, en general la compilació
n de cada uno produce un fichero objeto con código reubicable.
 El 
\series bold
enlazador
\series default
 une todos estos ficheros, así como el de las bibliotecas estáticas usadas,
 y el 
\series bold
cargador
\series default
, parte del sistema operativo, carga en memoria el ejecutable resultante
 con las bibliotecas dinámicas usadas, uniéndolos, y salta al punto de entrada
 del programa.
\end_layout

\begin_layout Section
Jerarquía de lenguajes de Chomsky
\end_layout

\begin_layout Standard
Una 
\series bold
gramática
\series default
 es una tupla 
\begin_inset Formula $G:=(V_{N},V_{T},P,S)$
\end_inset

 donde 
\begin_inset Formula $V_{N}$
\end_inset

 es un alfabeto de símbolos 
\series bold
no terminales
\series default
, 
\begin_inset Formula $V_{T}$
\end_inset

 es un alfabeto de 
\series bold
símbolos terminales
\series default
 disjunto de 
\begin_inset Formula $V_{N}$
\end_inset

, 
\begin_inset Formula $P$
\end_inset

 es un conjunto finito de 
\series bold
reglas de producción
\series default
 de la forma 
\begin_inset Formula $\alpha\to\beta$
\end_inset

 con 
\begin_inset Formula $\alpha,\beta\in(V_{N}\cup V_{T})^{*}$
\end_inset

 y 
\begin_inset Formula $S\in V_{N}$
\end_inset

 es el 
\series bold
símbolo inicial
\series default
.
 
\end_layout

\begin_layout Standard
Para 
\begin_inset Formula $\alpha,\beta\in(V_{N}\cup V_{T})^{*}$
\end_inset

, 
\begin_inset Formula $\alpha$
\end_inset

 
\series bold
deriva directamente
\series default
 en 
\begin_inset Formula $\beta$
\end_inset

, 
\begin_inset Formula $\alpha\Rightarrow\beta$
\end_inset

, si existen 
\begin_inset Formula $\delta,\gamma,\mu,\sigma\in(V_{N}\cup V_{T})^{*}$
\end_inset

 tales que 
\begin_inset Formula $\alpha=\delta\gamma\mu$
\end_inset

, 
\begin_inset Formula $\beta=\delta\sigma\mu$
\end_inset

 y 
\begin_inset Formula $\gamma\to\sigma\in P$
\end_inset

.
 Si 
\begin_inset Formula $\alpha=:\gamma_{0}\Rightarrow\dots\Rightarrow\gamma_{n}:=\beta$
\end_inset

, 
\begin_inset Formula $(\gamma_{0},\dots,\gamma_{n})$
\end_inset

 es una 
\series bold
derivación
\series default
 de 
\series bold
longitud
\series default
 
\begin_inset Formula $n$
\end_inset

 de 
\begin_inset Formula $\alpha$
\end_inset

 a 
\begin_inset Formula $\beta$
\end_inset

, y en particular 
\begin_inset Formula $(\alpha)$
\end_inset

 es una derivación de longitud 0 de 
\begin_inset Formula $\alpha$
\end_inset

 a 
\begin_inset Formula $\alpha$
\end_inset

.
 Decimos que 
\begin_inset Formula $\alpha$
\end_inset

 deriva en 
\begin_inset Formula $\beta$
\end_inset

, 
\begin_inset Formula $\alpha\Rightarrow^{*}\beta$
\end_inset

, si existe una derivación de 
\begin_inset Formula $\alpha$
\end_inset

 a 
\begin_inset Formula $\beta$
\end_inset

, y que 
\begin_inset Formula $\alpha\Rightarrow^{+}\beta$
\end_inset

 si dicha derivación se puede tomar de longitud positiva.
 
\end_layout

\begin_layout Standard
Una 
\series bold
forma sentencial
\series default
 es un elemento de 
\begin_inset Formula $D(G):=\{\alpha\in(V_{N}\cup V_{T})^{*}:S\Rightarrow^{*}\alpha\}$
\end_inset

, y una 
\series bold
sentencia
\series default
 es un elemento de 
\begin_inset Formula ${\cal L}(G):=D(G)\cap V_{T}^{*}$
\end_inset

, el 
\series bold
lenguaje definido
\series default
 por la gramática.
\end_layout

\begin_layout Standard
Tipos de lenguajes:
\end_layout

\begin_layout Itemize

\series bold
Tipo 0
\series default
, definidos por gramáticas 
\series bold
sin restricciones
\series default
 o 
\series bold
con estructura de frase
\series default
, con reglas 
\begin_inset Formula $\alpha X\beta\to\gamma$
\end_inset

, siendo 
\begin_inset Formula $X$
\end_inset

 cualquier símbolo, terminal o no.
 Reconocidos por máquinas de Turing.
\end_layout

\begin_layout Itemize

\series bold
Tipo 1
\series default
, definidos por gramáticas 
\series bold
dependientes del contexto
\series default
, con reglas 
\begin_inset Formula $\alpha A\beta\to\alpha\gamma\beta$
\end_inset

, siendo 
\begin_inset Formula $A$
\end_inset

 no terminal.
 Reconocidos por autómatas linealmente acotados.
\end_layout

\begin_layout Itemize

\series bold
Tipo 2
\series default
, definidos por gramáticas 
\series bold
libres de contexto
\series default
, con reglas 
\begin_inset Formula $A\to\alpha$
\end_inset

 siendo 
\begin_inset Formula $A$
\end_inset

 no terminal.
 Reconocidos por autómatas con pila.
\end_layout

\begin_layout Itemize

\series bold
Tipo 3
\series default
, definidos por gramáticas 
\series bold
regulares
\series default
, con reglas 
\begin_inset Formula $A\to a$
\end_inset

, 
\begin_inset Formula $A\to aB$
\end_inset

 o 
\begin_inset Formula $A\to\lambda$
\end_inset

, siendo 
\begin_inset Formula $A$
\end_inset

 y 
\begin_inset Formula $B$
\end_inset

 no terminales y 
\begin_inset Formula $a$
\end_inset

 terminal.
 Reconocidos por autómatas finitos.
\end_layout

\begin_layout Standard
Los lenguajes de un tipo también son de todos los tipos anteriores, aunque
 muchos lenguajes no son de tipo 0.
 La mayoría de lenguajes de programación son de tipo 1, aunque muchas de
 sus reglas gramaticales pueden reducirse al tipo 2 y, para los símbolos
 básicos, al tipo 3.
\end_layout

\begin_layout Section
Intérpretes
\end_layout

\begin_layout Standard
Un 
\series bold
intérprete
\series default
 es un programa que acepta un 
\series bold
programa fuente
\series default
 en un 
\series bold
lenguaje fuente
\series default
 y lo ejecuta inmediatamente, sin traducirlo a un código objeto.
 Es un buen método cuando el programador está trabajando de forma interactiva;
 el programa se va a utilizar pocas veces, con lo que el rendimiento no
 es importante; se espera que cada instrucción se ejecute una sola vez,
 y las instrucciones tienen un formato simple.
 
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{center}
\end_layout

\begin_layout Plain Layout


\backslash
begin{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
draw (0,0) 
\backslash
interpreter{$S$}{$M$};
\end_layout

\begin_layout Plain Layout


\backslash
end{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
hfil
\end_layout

\begin_layout Plain Layout


\backslash
begin{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
draw (0,0) 
\backslash
machine{$M$}
\backslash
run{
\backslash
interpreter{$S$}{$M$}
\backslash
interpret{
\backslash
program{$P$}{$S$}}};
\end_layout

\begin_layout Plain Layout


\backslash
end{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
end{center}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:interpreter"

\end_inset

Intérprete (izquierda) e interpretación de un programa (derecha).
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Un intérprete muy usado es el intérprete de comandos de Unix, la 
\emph on
shell
\emph default
.
 Los intérpretes los representamos como en la figura 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:interpreter"
plural "false"
caps "false"
noprefix "false"

\end_inset

, donde 
\begin_inset Formula $S$
\end_inset

 es el lenguaje fuente y 
\begin_inset Formula $M$
\end_inset

 es la máquina sobre la que se ejecuta el intérprete.
\end_layout

\begin_layout Standard
La interpretación de un programa en un lenguaje de alto nivel es unas 100
 veces más lenta que la ejecución de un programa equivalente en código máquina,
 por lo que esto no interesa cuando el programa se va a ejecutar en producción
 ni cuando las instrucciones se van a ejecutar frecuentemente o tienen formatos
 complicados.
\end_layout

\begin_layout Standard
Un 
\series bold
emulador
\series default
 es un intérprete cuyo lenguaje fuente es de bajo nivel, útil para verificar
 un diseño hardware.
 Así, podemos ver una máquina como un intérprete implementado en hardware,
 un intérprete como una máquina implementada en software y un código máquina
 como un lenguaje para el que existe un intérprete hardware.
 A veces llamamos 
\series bold
máquinas abstractas
\series default
 a los intérpretes para diferenciarlos de las máquinas reales.
\end_layout

\begin_layout Standard
Un 
\series bold
compilador interpretado
\series default
 es un traductor de un lenguaje fuente a un lenguaje intermedio diseñado
 para que la traducción sea rápida, el nivel de abstracción sea intermedio
 entre el lenguaje fuente y el código maquina y las instrucciones tengan
 un formato simple, facilitando su interpretación.
 
\end_layout

\begin_layout Standard
El código de la máquina virtual de Java (
\series bold
JVM
\series default
) es un lenguaje de este tipo, pues proporciona instrucciones que corresponden
 directamente a operaciones como creación de objetos, llamadas a métodos
 e indexado de matrices, facilitando la traducción de Java a código intermedio,
 pero estas tienen un formato sencillo como las instrucciones máquina, con
 campos de operación y operandos, facilitando la interpretación.
 El kit de desarrollo de Java (
\series bold
JDK
\series default
) contiene un traductor de Java a código JVM, un intérprete de código JVM
 y un compilador JIT que complementa al intérprete.
\end_layout

\begin_layout Section
Portabilidad
\end_layout

\begin_layout Standard
Un programa es 
\series bold
portable
\series default
 si puede ser compilado y ejecutado en cualquier máquina.
 La 
\series bold
portabilidad
\series default
 de un programa es la porción de código que no haría falta cambiar cuando
 el programa se mueve entre máquinas diferentes.
\end_layout

\begin_layout Standard
Para el código ensamblador, la portabilidad es, en general, del 
\begin_inset Formula $\unit[0]{\%}$
\end_inset

, mientras que para un lenguaje de alto nivel, es del 
\begin_inset Formula $\unit[\text{95--100}]{\%}$
\end_inset

.
 Los procesadores de lenguajes se escriben en lenguajes de alto nivel, aunque
 los compiladores no pueden ser totalmente portables si queremos que compilen
 al lenguaje de la implementación.
\end_layout

\end_body
\end_document