From 4b30e6ec24b2786d7308e86a42c3c99ad71b3953 Mon Sep 17 00:00:00 2001 From: Juan Marín Noguera Date: Mon, 24 Feb 2020 17:23:53 +0100 Subject: Asignaturas actuales --- cc/n1.lyx | 1200 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1200 insertions(+) create mode 100644 cc/n1.lyx (limited to 'cc/n1.lyx') diff --git a/cc/n1.lyx b/cc/n1.lyx new file mode 100644 index 0000000..602e833 --- /dev/null +++ b/cc/n1.lyx @@ -0,0 +1,1200 @@ +#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 +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +def +\backslash +program#1#2{-- ++(1.5,0) -- ++(0,1) arc(-90:90:0.5) -- ++(-1.5,0) arc(90:270:0.5) + -- ++(0,-1) ++(0.75,0.5) node{#2} ++(0,1) node{#1} ++(-0.75,-1.5)} +\end_layout + +\begin_layout Plain Layout + + +\backslash +def +\backslash +translator#1#2#3{-- ++(1.5,0) -- ++(0,1) -- ++(0.7,0) -- ++(0,1) -- ++(-2.9,0) + -- ++(0,-1) -- ++(0.7,0) -- ++(0,-1) ++(0,1.5) node{#1} ++(0.75,0) node{$ +\backslash +longrightarrow$} ++(0.75,0) node{#2} ++(-0.75,-1) node{#3} ++(-0.75,-0.5)} +\end_layout + +\begin_layout Plain Layout + + +\backslash +def +\backslash +machine#1{-- ++(0.75,-0.5) -- ++(0.75,0.5) -- ++(0,1) -- ++(-1.5,0) -- ++(0,-1) + ++(0.75,0.5) node{#1} ++(-0.75,-0.5)} +\end_layout + +\begin_layout Plain Layout + + +\backslash +def +\backslash +run#1{++(0,1) #1 ++(0,-1)} +\end_layout + +\begin_layout Plain Layout + + +\backslash +def +\backslash +source#1{++(-2.2,1) #1 ++(2.2,-1)} +\end_layout + +\begin_layout Plain Layout + + +\backslash +def +\backslash +object#1{++(2.2,1) #1 ++(-2.2,-1)} +\end_layout + +\begin_layout Plain Layout + + +\backslash +def +\backslash +interpreter#1#2{-- ++(1.5,0) -- ++(0,2) -- ++(-1.5,0) -- ++(0,-2) ++(0.75,0.5) + node{#2} ++(0,1) node{#1} ++(-0.75,-1.5)} +\end_layout + +\begin_layout Plain Layout + + +\backslash +def +\backslash +interpret#1{++(0,2) #1 ++(0,-2)} +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Un +\series bold +lenguaje de programación +\series default + es una notación formal para expresar algoritmo. + 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, y que permiten usar abreviaturas mnemotécn +icas para representar las instrucciones de la máquina y códigos octales + o hexadecimales para valores. + También permiten crear 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 durante 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 +: Se 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 +: Se transforma un flujo de caracteres en un flujo de +\series bold +\emph on +tokens +\series default +\emph default +, que son identificadores de variables o funciones, palabras clave, constantes, + operadores, etc. +\end_layout + +\begin_layout Enumerate + +\series bold +Análisis sintáctico +\series default +: Se crea un árbol sintáctico que refleja la estructura gramatical del programa. + Si se parte del axioma de la gramática y se va construyendo el árbol de + análisis hacia abajo por derivaciones por la izquierda, se habla de análisis + +\series bold +descendente +\series default +, y si se parte de la entrada y se va generando el árbol hacia arriba por + reducciones por la izquierda, se habla de análisis +\series bold +ascendente +\series default +. + 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 +: Se verifican construcciones sintácticas que no se pueden tratar con gramáticas + libres de contexto y se calculan valores semánticos para garantizar la + generación de código correcto, 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 fuentes, 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 Itemize + +\series bold +Tipo 0 +\series default +, 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 +, 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 +, 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 +, 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 del lenguaje, 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 ejecuta 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, + las instrucciones se van a ejecutar frecuentemente o las instrucciones + 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 las instrucciones 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 en el código fuente. + 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 -- cgit v1.2.3