tcc-01-intro.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introducción al diseño de lectores, generadores, traductores, interpretes y compiladores\n",
    "Notas de clase sobre Teoría de la Compilación"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Juan David Velásquez Henao**   \n",
    "jdvelasq@unal.edu.co  \n",
    "Universidad Nacional de Colombia, Sede Medellín  \n",
    "Facultad de Minas  \n",
    "Medellín, Colombia  \n",
    "\n",
    "[Licencia](https://github.com/jdvelasq/teoria-de-la-compilacion/blob/master/LICENCIA.txt)  \n",
    "[Readme](https://github.com/jdvelasq/teoria-de-la-compilacion/blob/master/readme.md)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Software utilizado**.\n",
    "\n",
    "> Este es un documento interactivo escrito como un notebook de [Jupyter](http://jupyter.org), en el cual se presenta una introducción al diseño de lectores, generadores, traductores, interpretes y compiladores. Los notebooks de Jupyter permiten incoporar simultáneamente código, texto, gráficos y ecuaciones. El código presentado en este notebook puede ejecutarse en los sistemas operativos Windows, Linux y OS X.\n",
    "\n",
    "> Haga click [aquí](https://github.com/jdvelasq/guias-de-instalacion) para obtener instrucciones detalladas sobre como instalar Jupyter en Windows y Mac OS X.\n",
    "\n",
    "> Haga clic [aquí](http://nbviewer.jupyter.org/github/jdvelasq/teoria-de-la-compilacion/blob/master/01-introduccion.ipynb) para ver la última versión de este documento en nbviewer.\n",
    "\n",
    "> Descargue la última versión de este documento, los archivos de datos y los programas en Python a su disco duro; luego, carguelos y ejecutelos en línea en [Try Jupyter!](https://try.jupyter.org)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Contenido"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">   * [Estructura del sistema de un computador](#Estructura-del-sistema-de-un-computador)\n",
    "  * [Desarrollo histórico](#Desarrollo-histórico)\n",
    "  * [Estructura típica de un compilador de 4 pasadas](#Estructura-típica-de-un-compilador-de-4-pasadas)\n",
    "  * [Fases típicas y aplicaciones](#Fases-típicas-y-aplicaciones)\n",
    "  * [Herramientas que usan la misma tecnología de los compiladores](#Herramientas-que-usan-la-misma-tecnología-de-los-compiladores)\n",
    "  * [Programas relacionados con los compiladores](#Programas-relacionados-con-los-compiladores)\n",
    "  * [Programas relacionados con las fases de la compilación](#Programas-relacionados-con-las-fases-de-la-compilación)\n",
    "    * [Preprocesadores](#Preprocesadores)\n",
    "    * [Analizador Léxico o scanner o lexer](#Analizador-Léxico-o-scanner-o-lexer)\n",
    "    * [Analizador sintáctico o parser](#Analizador-sintáctico-o-parser)\n",
    "    * [Tabla de Símbolos y Análisis Semántico](#Tabla-de-Símbolos-y-Análisis-Semántico)\n",
    "    * [Verificación de tipos](#Verificación-de-tipos)\n",
    "    * [Generación de código intermedio](#Generación-de-código-intermedio)\n",
    "    * [Optimización del código](#Optimización-del-código)\n",
    "    * [Generación de código máquina](#Generación-de-código-máquina)\n",
    "    * [Ensambladores de dos pasadas](#Ensambladores-de-dos-pasadas)\n",
    "  * [Herramientas para la construcción de compiladores](#Herramientas-para-la-construcción-de-compiladores)\n",
    "  * [Compiladores, traductores y emuladores](#Compiladores,-traductores-y-emuladores)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bibliografía**\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Recursos adicionales de aprendizaje**\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Estructura del sistema de un computador"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](images/tcc-01-1-EstrcuturaComp.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# Diferencia entre un interprete y un compilador"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](images/tcc-01-2-InterComp.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Desarrollo histórico"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Los primeros computadores fueron desarrollados en la década de los 40s. El primer lenguaje de programación es el Lenguaje Máquina. \n",
    "\n",
    "* 1951: Lenguaje Ensamblador.\n",
    "* 1952: Autocode\n",
    "* 1957: Fortran (programación imperativa)\n",
    "* 1958: Lisp  (programación funcional)\n",
    "* 1958: Algol.\n",
    "* 1959: COBOL \n",
    "* 1960: Simula (primer lenguaje orientado a objetos)\n",
    "* 1969: C (lenguaje orientado a la programación de sistemas)\n",
    "* 1972: Prolog.\n",
    "* 1978: SQL\n",
    "* 1980: C++\n",
    "* 1984: MatLab\n",
    "* 1988: Mathematica\n",
    "* 1991: Python \n",
    "* 1995: Java y PHP\n",
    "* ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Estructura típica de un compilador de 4 pasadas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](images/tcc-01-3-EstrComp.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fases típicas y aplicaciones"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*  Análisis léxico.  \n",
    "   > Software que usa expresiones regulares: `grep`, `tr`, `awk`, `perl`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Análisis sintáctico.  \n",
    "  > Intérpretes guiados por sintaxis.  \n",
    "  Calculadoras `bc` y `dc` de Unix  \n",
    "  Traductores guiados por sintaxis  \n",
    "  Generadores de código guiados por sintaxis  \n",
    "  Herramientas para web scrapping"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Análisis semántico.  \n",
    "  > Verificadores estáticos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Optimización.  \n",
    "  > Perfiladores de código"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Generación de código.  \n",
    "  > Traductores de código fuente.  \n",
    "  Generación de código para máquinas virtuales.    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Herramientas que usan la misma tecnología de los compiladores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Lectores: archivos de configuración, analizadores de programas, etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Editores de estructuras de datos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Generadores de código: generadores de código fuente, de páginas web, de GUIs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Verificadores estáticos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Traductores (lector + generador): f2c, impresoras estéticas, preprocesadores. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Lenguajes interpretados: SQL,  MATLAB, Scheme, Perl, Ruby."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Formateadores de texto: TeX, LaTeX, Markdown."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Intérpretes de consultas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Lenguajes de línea de comandos: AWK, Shells de Unix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Programas relacionados con los compiladores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*\tInterpretes\n",
    "*\tEnsambladores (assemblers)\n",
    "*\tEnlazadores (linkers)\n",
    "*\tCargadores\n",
    "*\tPreprocesadores\n",
    "*\tEditores\n",
    "*\tDepuradores\n",
    "*\tPerfiladores\n",
    "*\tManejadores de proyectos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Programas relacionados con las fases de la compilación"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Preprocesadores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Modifican el código fuente antes de pasarlo al compilador\n",
    "\n",
    "*  Definición y uso de macros\n",
    "*  Inclusión de archivos\n",
    "*  Preprocesadores racionales\n",
    "*  Mecanismo de extensión de lenguajes\n",
    "\n",
    "```\n",
    "    #include <stdio.h>\n",
    "    #define max(a, b) (a<b? b : a)\n",
    "    int main() { printf( \"El mayor entre 1 y 2 es \\%d\", max( 1, 2)); }\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analizador Léxico o scanner o lexer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "•\tToken: Elemento básico indivisible (unidad léxica básica, tipo)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "•\tLexema: Cadena de texto que representa un token"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](images/tcc-01-4-analisisLexico.tiff)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%%sh\n",
    "cat > example.txt <<EOF\n",
    "var z:num;\n",
    "z := 0;    \n",
    "while (z < 10) do \n",
    "    {\n",
    "    write 'do while (1 a 10) ==> ':  z;\n",
    "    z := z + 1;\n",
    "    } \n",
    "end\n",
    "EOF"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+-- TOKENTABLE\n",
      "    +-- VAR {lexeme: var, lineno: 0}\n",
      "    +-- ID {lexeme: z, lineno: 0}\n",
      "    +-- : {lexeme: :, lineno: 0}\n",
      "    +-- DATATYPE {lexeme: num, lineno: 0}\n",
      "    +-- ; {lexeme: ;, lineno: 0}\n",
      "    +-- ID {lexeme: z, lineno: 1}\n",
      "    +-- := {lexeme: :=, lineno: 1}\n",
      "    +-- NUM {lexeme: 0, lineno: 1}\n",
      "    +-- ; {lexeme: ;, lineno: 1}\n",
      "    +-- WHILE {lexeme: while, lineno: 2}\n",
      "    +-- ( {lexeme: (, lineno: 2}\n",
      "    +-- ID {lexeme: z, lineno: 2}\n",
      "    +-- < {lexeme: <, lineno: 2}\n",
      "    +-- NUM {lexeme: 10, lineno: 2}\n",
      "    +-- ) {lexeme: ), lineno: 2}\n",
      "    +-- DO {lexeme: do, lineno: 2}\n",
      "    +-- { {lexeme: {, lineno: 3}\n",
      "    +-- WRITE {lexeme: write, lineno: 4}\n",
      "    +-- STR {lexeme: 'do while (1 a 10) ==> ', lineno: 4}\n",
      "    +-- : {lexeme: :, lineno: 4}\n",
      "    +-- ID {lexeme: z, lineno: 4}\n",
      "    +-- ; {lexeme: ;, lineno: 4}\n",
      "    +-- ID {lexeme: z, lineno: 5}\n",
      "    +-- := {lexeme: :=, lineno: 5}\n",
      "    +-- ID {lexeme: z, lineno: 5}\n",
      "    +-- + {lexeme: +, lineno: 5}\n",
      "    +-- NUM {lexeme: 1, lineno: 5}\n",
      "    +-- ; {lexeme: ;, lineno: 5}\n",
      "    +-- } {lexeme: }, lineno: 6}\n",
      "    +-- END {lexeme: end, lineno: 7}\n",
      "    +-- END {lexeme: end, lineno: 1}\n"
     ]
    }
   ],
   "source": [
    "%%sh \n",
    "python yylex.py example.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analizador sintáctico o parser"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+-- SYNTAXTREE\n",
      "    +-- FUNCTIONDECL {lineno: 0}\n",
      "    +-- MAINPROG {lineno: 0}\n",
      "        +-- VAR {lineno: 0}\n",
      "        |   +-- ID {datatype: num, lineno: 0, scope: 0, value: z}\n",
      "        +-- ASSIGN {lineno: 1, scope: 0, value: z}\n",
      "        |   +-- NUM {datatype: num, lineno: 1, value: 0}\n",
      "        +-- WHILE {lineno: 2}\n",
      "        |   +-- < {datatype: bool, lineno: 2}\n",
      "        |   |   +-- ID {lineno: 2, scope: 0, value: z}\n",
      "        |   |   +-- NUM {datatype: num, lineno: 2, value: 10}\n",
      "        |   +-- BLOCK {lineno: 4}\n",
      "        |       +-- WRITE {lineno: 4}\n",
      "        |       |   +-- STR {datatype: str, lineno: 4, value: 'do while (1 a 10) ==> '}\n",
      "        |       |   +-- ID {lineno: 4, scope: 0, value: z}\n",
      "        |       +-- ASSIGN {lineno: 5, scope: 0, value: z}\n",
      "        |           +-- + {datatype: num, lineno: 5}\n",
      "        |               +-- ID {lineno: 5, scope: 0, value: z}\n",
      "        |               +-- NUM {datatype: num, lineno: 5, value: 1}\n",
      "        +-- END {lineno: 7}\n"
     ]
    }
   ],
   "source": [
    "%%sh \n",
    "python yyparse.py example.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Gramática (reglas para construir el árbol sintáctico)**\n",
    "\n",
    "```\n",
    "exp:  ID\n",
    "   |  NUM\n",
    "   |  exp ‘+’ exp\n",
    "   |  exp ‘*’ exp\n",
    "   |  ‘(’ exp ‘)’\n",
    "\n",
    "stmt: ID ‘:=’ exp\n",
    "   |  WHILE ‘(’ exp ‘)’ DO stmt\n",
    "   |  IF ‘(’ exp ‘)’ THEN stmt\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tabla de Símbolos y Análisis Semántico"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Es una estructura de datos que registra información sobre los atributos de cada identificador en el programa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*\tRegistra los identificadores usados en el programa fuente"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*\tRecopila información sobre los atributos de cada identificador\n",
    "   * Memoria asignada\n",
    "   * Tipo (entero, flotante, puntero, …)\n",
    "   * Ámbito (parte del programa donde tiene validez)\n",
    "   * Para las funciones: \n",
    "       * Número y tipo de los argumentos\n",
    "       * Método de paso de cada argumento\n",
    "       * Tipo de valor devuelto por la función"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+-- SYMBOLTABLE\n",
      "    +-- $chs {argstype: ['num'], datatype: num, kind: bfun, nargs: 1}\n",
      "    +-- $abs {argstype: ['num'], datatype: num, kind: bfun, nargs: 1}\n",
      "    +-- $sgn {argstype: ['num'], datatype: num, kind: bfun, nargs: 1}\n",
      "    +-- z {datatype: num, kind: uvar, location: 0, scope: 0}\n"
     ]
    }
   ],
   "source": [
    "%%sh \n",
    "python yysymboltab.py example.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Verificación de tipos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+-- SYNTAXTREE\n",
      "    +-- FUNCTIONDECL {lineno: 0}\n",
      "    +-- MAINPROG {lineno: 0}\n",
      "        +-- VAR {lineno: 0}\n",
      "        |   +-- ID {datatype: num, lineno: 0, scope: 0, value: z}\n",
      "        +-- ASSIGN {lineno: 1, scope: 0, value: z}\n",
      "        |   +-- NUM {datatype: num, lineno: 1, value: 0}\n",
      "        +-- WHILE {lineno: 2}\n",
      "        |   +-- < {datatype: bool, lineno: 2}\n",
      "        |   |   +-- ID {datatype: num, lineno: 2, scope: 0, value: z}\n",
      "        |   |   +-- NUM {datatype: num, lineno: 2, value: 10}\n",
      "        |   +-- BLOCK {lineno: 4}\n",
      "        |       +-- WRITE {lineno: 4}\n",
      "        |       |   +-- STR {datatype: str, lineno: 4, value: 'do while (1 a 10) ==> '}\n",
      "        |       |   +-- ID {datatype: num, lineno: 4, scope: 0, value: z}\n",
      "        |       +-- ASSIGN {lineno: 5, scope: 0, value: z}\n",
      "        |           +-- + {datatype: num, lineno: 5}\n",
      "        |               +-- ID {datatype: num, lineno: 5, scope: 0, value: z}\n",
      "        |               +-- NUM {datatype: num, lineno: 5, value: 1}\n",
      "        +-- END {lineno: 7}\n"
     ]
    }
   ],
   "source": [
    "%%sh \n",
    "python yytypecheck.py example.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generación de código intermedio"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Es una representación intermedia explícita del programa fuente que es fácil de producir y traducir al programa objeto. Puede considerarse como un programa para una máquina abstracta.\n",
    "*\tFácil de producir\n",
    "*\tFácil de traducir al programa objeto\n",
    "\n",
    "\n",
    "Código de tres direcciones:\n",
    "\n",
    "*\tCada instrucción tiene a lo sumo un operador\n",
    "*\tEl compilador decide el orden de ejecución de las instrucciones\n",
    "*\tEl compilador genera nombres temporales para almacenar cálculos\n",
    "*\tAlgunas instrucciones tienen menos de tres operandos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Código intermedio para una máquina de stack (pila)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%%sh \n",
    "python yysbm.py example.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "'do while (1 a 10) ==> '\n",
      "%%\n",
      "          0    \n",
      "          STO     0\n",
      "LBL 255\n",
      "          RCL     0\n",
      "          10   \n",
      "          <    \n",
      "          IFZ   254\n",
      "          STR     0\n",
      "          RCL     0\n",
      "          PRN  \n",
      "          RCL     0\n",
      "          1    \n",
      "          +    \n",
      "          STO     0\n",
      "          GTO   255\n",
      "LBL 254\n",
      "          HLT  \n"
     ]
    }
   ],
   "source": [
    "%%sh \n",
    "cat \"example.txt.sbm\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Código intermedio para una máquina de registros**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%%sh \n",
    "python yyrbm.py example.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "'do while (1 a 10) ==> '\n",
      "%%\n",
      "          ADD+    1   0   0\n",
      "          STO     1   0\n",
      "LBL 255\n",
      "          RCL     2   0\n",
      "          ADD+    3   0  10\n",
      "          <       1   2   3\n",
      "          IFZ     1 254\n",
      "          STR     0\n",
      "          RCL     1   0\n",
      "          PRN     1\n",
      "          RCL     2   0\n",
      "          ADD+    3   0   1\n",
      "          +       1   2   3\n",
      "          STO     1   0\n",
      "          GTO   255\n",
      "LBL 254\n",
      "          HLT  \n"
     ]
    }
   ],
   "source": [
    "%%sh\n",
    "cat \"example.txt.rbm\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Optimización del código"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Se busca que la ejecución del código máquina sea más rápida.\n",
    "\n",
    "```\n",
    "temp1 := 60                addi     $1  $0  60\n",
    "temp2 := id3               mem2reg  $2   3\n",
    "temp2 := temp2 * temp1     mlt      $2  $2  $1\n",
    "temp3 := id2               mem2reg  $3   2\n",
    "temp4 := temp3 + temp2     add      $4  $3  $2  \n",
    "id1   := temp4             reg2mem   1  $4 \n",
    "```\n",
    "\n",
    "Código optimizado:\n",
    "\n",
    "```\n",
    "temp2 := id3               mem2reg  $2   3\n",
    "temp2 := temp2 * 60        mlti     $2  $2  60\n",
    "temp3 := id2               mem2reg  $3   2\n",
    "temp4 := temp3 + temp2     add      $4  $3  $2  \n",
    "id1   := temp4\t           reg2mem   1  $4 \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Tipos de optimizaciones**\n",
    "\n",
    "* Optimizaciones tempranas.\n",
    "  * Evaluación de expresiones constantes\n",
    "  * Simplificación algebraica\n",
    "  * Propagación de copias\n",
    "  * Propagación de constantes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Eliminación de redundancias.\n",
    "  * Eliminación de subexpresiones comunes\n",
    "  * Movimiento de código invariante en ciclos\n",
    "  * Eliminación de verificación innecesaria de límites"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Optimización de subrutinas.\n",
    "  * Optimización Tail-Call y Tail-Recursion\n",
    "  * Integración de funciones\n",
    "  * Expansión en línea"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Otras.\n",
    "  * Código inalcanzable.\n",
    "  * Linealización (código espagueti)\n",
    "  * Simplificación de if con elementos vacíos\n",
    "  * Simplificación de ciclos\n",
    "  * Optimización de la memoria"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generación de código máquina"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Genera assembler o código de máquina:\n",
    "\n",
    "```\n",
    "MOVF id3, R2\n",
    "MULF #60.0, R2\n",
    "MOVF id2, R1\n",
    "ADDF R2, R1\n",
    "MOVF R1, id1\n",
    "```\n",
    "\n",
    "El lenguaje ensamblador es una versión nemotécnica del código-máquina propio de cada procesador."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ensambladores de dos pasadas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*\tPrimera pasada: se lee todo el archivo y se almacenan los identificadores en la tabla de símbolos (del back-end) y se asignan posiciones de memoria."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*\tSegunda pasada: traduce el código a lenguaje de máquina cambiando identificadores por su posición en memoria."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Herramientas para la construcción de compiladores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Generadores de analizadores léxicos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Generadores de analizadores sintácticos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Dispositivos de traducción dirigida por la sintaxis."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Generadores automáticos de código."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Dispositivos para el análisis de flujo de datos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Compiladores, traductores y emuladores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Notación**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](images/tcc-01-5-thompson.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Compilación**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](images/tcc-01-6-compilacion.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Compilación cruzada**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](images/tcc-01-7-compilacionCruzada.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Compilación de dos pasadas**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](images/tcc-01-8-compilacion2pas.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Compilación de un compilador a partir de un lenguaje de alto nivel**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](images/tcc-01-9-compilacionComp.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Compilación de un compilador a partir de un lenguaje de bajo nivel**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](images/tcc-01-10-compilacionComp.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Máquina real y máquina abstracta**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](images/tcc-01-11-maqRalAbs.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Compilador interpretativo**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](images/tcc-01-12-compInter.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Compilador portable**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](images/tcc-01-13-compPort.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Contenido](#Contenido)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}