#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\coloneqq (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}\coloneqq \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)\coloneqq \{\alpha\in(V_{N}\cup V_{T})^{*}\mid S\Rightarrow^{*}\alpha\}$ \end_inset , y una \series bold sentencia \series default es un elemento de \begin_inset Formula ${\cal L}(G)\coloneqq 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