¿Cómo convierte un compilador los lenguajes de programación de alto nivel en ensamblador? ¿Cómo se traducen los idiomas y se optimiza el código?

Voy a dar un golpe en esto, pero rellene su taza primero, porque va a ser un poco larga.

Al principio, el programa fuente es solo una secuencia de caracteres individuales, leídos uno a la vez. Antes de que el compilador pueda entenderlo, debe dividirse en palabras, lo que para un compilador es una secuencia de pares con un valor de token y un lexema . Para saber cuántos caracteres van en la siguiente palabra, el front-end del compilador contendrá un escáner , que es más fácil de crear a partir de una combinación de un conjunto de autómatas finitos deterministas (DFA). Para darle una idea de cómo son, aquí hay una imagen de uno que reconoce números, en forma de una parte entera, y una parte decimal opcional, por lo que “142” y “3.141593” son números de acuerdo con este.

Los círculos verdes (estados) están marcados de esa manera porque están “aceptando” estados, es decir, si llegamos a ellos y sucede algo más, sabemos que lo que sucedió antes era al menos un número. Comenzando desde (inicio), un rastro de la ruta tomada al leer “42.15” sería (1,2,2,3,3,3), y dado que eso termina en un estado de aceptación, esa cadena se puede emitir como un par (NÚMERO, 42.15) cuando finaliza la cadena de dígitos. Aquí, NUMBER es un token entero arbitrario que se utiliza para indicar que hemos encontrado números, y el texto real “42.15” es el lexema que coincide con el token, que es necesario para distinguir un número de otro.

Se pueden hacer pequeñas máquinas de estado como esta para todo tipo de clases de palabras, los nombres de las variables se pueden especificar como cadenas de letras y guiones bajos, los operadores pueden ser cosas como “+ =” y “->”, las palabras clave son cosas como ” if “y” while “, los especificadores de tipo pueden ser” int “y” char “y what-have-you. Al hacer un DFA que acepta cada clase de palabras, se pueden fusionar en una más grande que acepta múltiples clases. Podemos representar DFA usando tablas en software, por lo que la construcción del DFA gigante para todas las clases de palabras en un idioma completo puede hacerse mediante un generador de escáner automático que tome descripciones de las clases y produzca un programa que las conozca todas entre sí. Ese fue el paso 1, llamado análisis léxico . Lo que obtienes de él es una nueva secuencia de datos, pero ya no son caracteres, son pares (token, lexeme) que se pueden manejar más fácilmente.

Tomemos una declaración simple como
if (x == 2) {x = a + b; }
y conviértalo en un ejemplo de flujo de tokens y lexemas:
(PALABRA CLAVE, “if”), (IDENTIFICADOR, “x”), (OPERADOR, “==”), (NÚMERO, “2”), (DELIMITADOR, “{“), (IDENTIFICADOR, “x”), ( OPERADOR, “=”), (IDENTIFICADOR, “a”), (OPERADOR, “+”), (IDENTIFICADOR, “b”), (DELIMITER, “;”), (DELIMITER, “}”).
Este es un poco más detallado de lo necesario, pero entiendes la idea.

El siguiente es el análisis sintáctico (también conocido como análisis ), que tiene el objetivo de convertir esta secuencia en un árbol de sintaxis, como este:

La cantidad de formas de producir esta transformación puede llenar un libro, pero una muy simple es mediante el análisis predictivo, lo que básicamente significa que comienza desde un extremo de la secuencia, crea un árbol temporal con marcadores de posición para todas las cosas que no tiene visto todavía, y espero completarlos a medida que continúe leyendo desde la transmisión (preparado con precaución para detener un “error de sintaxis” si lo que viene después no encaja después de todo).

Para nuestro pequeño if-tree, eso podría proceder de la siguiente manera:

Dejo de lado el resto de este proceso, porque probablemente puedas ver a dónde va en este momento.

Habiendo obtenido todo el árbol de sintaxis, necesitamos construir una tabla de símbolos , para decidir lugares para todo en la memoria. Esto significa ir a través del árbol y colocar todos los diferentes nombres de variables en ubicaciones de memoria que sabemos que están disponibles. El compilador decide cómo se gasta la memoria asignada a un programa, por lo que es solo cuestión de encontrar algunas direcciones que aún no se han utilizado para nada, empiezo en 2000 porque es un buen número:

Básicamente, esto es lo que hace que ‘x’ se refiera al mismo número en ambos lugares del árbol donde aparece. Esto es suficiente para una simple traducción al ensamblaje; yendo a través del árbol de izquierda a derecha y de arriba a abajo nuevamente, encontrando un nodo “si” siempre resulta en el mismo patrón, un nodo “verificar igual” siempre da lo mismo, y “asignación”, y así sucesivamente:

Primero, encuentra las expresiones más pequeñas …

… fusionarlos con lo que los rodea …

… y al final, todo se puede aplanar en una secuencia de instrucciones de montaje:

… que se envía al ensamblador para traducir cosas como ‘cargar’, ‘agregar’, etc. a la representación binaria del procesador.

Esto se simplifica enormemente, y el lenguaje ensamblador inexistente se inventa para mantenerlo fácil, pero así es aproximadamente como funciona un esquema de traducción simple, conceptualmente hablando.

Voy a omitir las optimizaciones, porque cada una de las que se me ocurre requiere al menos 3 veces más material de fondo que el que está aquí. Espero que tenga más o menos sentido, para todos los temas pasados; cubriendo todo es un libro con cientos de páginas.

Como ya hay excelentes respuestas generales, pensé que diría un poco sobre la parte de optimización de la pregunta. La optimización es donde mucha de la innovación en compiladores ocurre en estos días; puede lex y analizar con herramientas que han existido durante décadas (por ejemplo, lex / flex o yacc / bison).

La apariencia del código “óptimo” depende de su aplicación. Por lo general, significa “lo más rápido posible”, pero podría significar “usa menos memoria” o “ocupa menos espacio” (como para el código incrustado). También podría depender de qué tipo de arquitectura de procesador está utilizando, o si está utilizando un sistema multinúcleo. Entonces es difícil ser general.

La optimización generalmente se lleva a cabo con lo que se llama análisis de flujo de datos, que identifica regiones de código que pueden reescribirse de manera más eficiente.

Ya se han mencionado algunas optimizaciones, pero una muy importante es la optimización de bucle. Si su programa pasa casi todo su tiempo en un bucle anidado, querrá que ese código sea óptimo. Algunas técnicas útiles son (y no se limitan a):

-Eliminación de llamadas de cola: si lo último que hace un bloque de código es llamarse recursivamente, puede reemplazar esa llamada de función con esencialmente una instrucción goto. Esto es realmente importante en lenguajes como Scheme o Haskell que no tienen explícitos bucles. (En general, estas técnicas pueden llamarse optimizaciones de cola)

-La variable de contador en un bucle (como “i” en “for (i = 0, …)”) solo cuenta las iteraciones en un bucle; puede ser posible transformar este ciclo en algo más eficiente

-Si en un ciclo while, estás calculando alguna cantidad, como en “while (x> n + 1)”, un compilador puede mover ese n + 1, como en “t = n + 1; while (x> t ) “; Este es un ejemplo de movimiento de código.

Si algunos de estos parecen triviales, ¡imagine su efecto acumulado sobre, digamos, un millón de iteraciones en un bucle anidado!

Aquí hay muchas respuestas excelentes, pero me gustaría subrayar un punto clave:
la traducción ocurre gradualmente, en pasos pequeños y tangibles. El compilador generalmente no resuelve ningún gran problema, y ​​es todo menos magia. Un compilador es complicado porque hace muchas cosas diferentes, no porque las cosas que hace son muy complicadas.

En un nivel alto, el compilador traduce lenguajes de alto nivel en una representación intermedia, trabaja para transformar la representación intermedia (por ejemplo, reescribir operaciones que son ineficientes o no están disponibles en el ensamblaje como una secuencia de otras operaciones), y luego traduce inequívocamente la representación intermedia a código específico de la máquina.

En pocas palabras: divide las operaciones de alto nivel en operaciones simples más pequeñas que las máquinas entienden. Por ejemplo, los bucles “for” y “while” se traducen al código “branch”. Por lo general, los compiladores funcionan con una descripción de máquina de uso general, luego intentan ajustar ese código al procesador específico. Se puede ver que toma el código de alto nivel y lo convierte en un conjunto de macros de bajo nivel, luego esas macros se traducen al código de ensamblaje que necesita.

Para los analizadores prefiero la tokenización y el descenso recursivo: he hecho los de Verilog-AMS y C ++ (parallel.cc), los analizadores gramaticales son difíciles de depurar y chupar en función del contexto.

Esto es quizás un error, pero la salida de un compilador es a menudo “código objeto” o “código máquina”, no “ensamblado” (o “lenguaje ensamblador”).

El lenguaje ensamblador es una representación simbólica del código de máquina, para consumo humano. Un “ensamblador” también genera código de máquina.

El código de ensamblaje simbólico podría o no generarse como un paso intermedio en la compilación. Algunos compiladores generaron código de ensamblaje simbólico, que luego se entrega a un ensamblador para su conversión a código de máquina (gcc hace esto, al menos la última vez que busqué); o el compilador solo puede generar código objeto directamente.

Un compilador también podría generar código de ensamblaje, además del código de objeto, por ejemplo, como entrada a un depurador simbólico. Y un depurador puede desmontar el código objeto en código ensamblador.

Hay muchas respuestas detalladas aquí, pero esta transformación de la que estás hablando realmente no necesita ser tan complicada de explicar. Cualquier lenguaje de programación tiene representación y manipulación de datos. El ensamblaje también es uno de esos lenguajes de programación. Entonces, lo que hace un compilador es una traducción (aunque es complicado si quieres entrar en detalles). Básicamente analiza su código, construye gráficos de flujo de control (que indican cómo se ejecutará el programa bajo qué entradas) y gráficos de flujo de datos (qué datos se utilizan mientras se ejecuta qué parte del código). Además de estos dos, realiza optimizaciones para reducir variables y crea variables intermedias cuando es necesario (si tiene a + b + c, necesita almacenar la salida de a + b y luego agregarla a c, suponiendo que su ensamblaje pueda tener solo 2 entradas adicionales, que generalmente es el caso). Después de estas optimizaciones, el flujo final del programa se representa esencialmente en estos gráficos y, según las operaciones representadas, se genera un código de ensamblaje respectivo. Esto se logra ya que el lenguaje de alto nivel o la representación intermedia del programa tienen un rango limitado de operaciones, que pueden asignarse directamente a instrucciones de nivel de ensamblaje.

De hecho, muchos compiladores cambian solo el front-end para convertir diferentes idiomas en ensamblador. Por front end, me refiero a la parte del compilador que convierte el lenguaje de alto nivel en el lenguaje intermedio representado por varios gráficos. El back-end que convierte estos gráficos en ensamblaje no cambia mucho.

Hay otras cosas importantes, como el manejo de la asignación dinámica de variables, las operaciones de disco, las operaciones de E / S, etc., que se descargan al sistema operativo a través de llamadas al sistema. Pero esencialmente lo anterior es el proceso en términos simples.

También puede observar que los procesadores como Intel x86, toman el lenguaje ensamblador y los separan aún más antes de usarlos (llamados micro-ops).

Escribí un compilador para una máquina virtual una vez. Los pasos básicos son los siguientes:

1. Averigua todos los nombres de funciones y clases que puedes usar. En un lenguaje como C, puede omitir este paso ya que debe declarar explícitamente cada función antes de poder llamarla. Sin embargo, hacer esto automáticamente hace que el pelaje sea mucho más fácil de escribir.
2. Para cada función, analiza la expresión. Mi lenguaje tiene operaciones integradas que sé cómo hacer, como *, + o una llamada de función. Todos estos toman argumentos, que pueden ser otras expresiones. Esta parte es una de las partes más difíciles de depurar del programa, especialmente sobre paréntesis y cadenas. No es tan fácil de encontrar si un + específico es la operación de nivel superior, parte de una subexpresión entre paréntesis o parte de una cadena, especialmente cuando puede tener) caracteres dentro de cadenas o \ “secuencias de escape que hacen que las cadenas sean más largas. Al principio intenté usar expresiones regulares, pero las reglas son demasiado complicadas.
3. Convierta cada operación en ensamblaje. Para cada operación, tengo un conjunto codificado de líneas de ensamblaje que corresponden. Por ejemplo, * sería MULL input1 input2 output1. Para las expresiones anidadas, empujo la salida de la expresión más interna a la pila, de derecha a izquierda, luego la saco de la pila para la siguiente operación. El ensamblado producido es algo que yo llamo “ensamblaje no sustituido”, ya que tengo secuencias de bytes especiales como “poner la referencia a esa función aquí” o “poner un puntero al final del bucle aquí” que todavía necesitan ser reemplazados por un valor actual.
4. Si está creando varios archivos, guarde este resultado y cargue todos los conjuntos sustituidos. Ahora todas mis funciones, datos y otras cosas deben escribirse en un archivo. También escribe un encabezado, decide cuánta memoria necesitará su programa (en su mayoría una suposición afortunada) y sustituye todas sus expresiones. Tadaa, tu montaje ha terminado.

Hay muchas cosas más avanzadas. Por ejemplo, si las instrucciones y los bloques de código anidados se complican muy rápido. Un compilador optimizador reemplaza automáticamente ciertas secuencias de ensamblaje ineficientes conocidas con versiones más eficientes, o elimina las funciones getter y setter a favor del direccionamiento directo más rápido. Un compilador de recolección de basura puede insertar código de recolección de basura en lugares aleatorios. No es tan fácil, pero bastante factible.

un poco fuera de tema, pero no por mucho.

Pasé un tiempo en la industria de los videojuegos. En ese momento todo el código se hizo en lenguaje ensamblador. Sega fue el procesador 68000, Super Nintendo usó el 65816, etc.

Uno de mis hacks favoritos fue de un amigo que fue acusado de portar un juego de Sega a Super Nintendo. Lo hizo mediante la creación de macros en el breve editor que utilizamos, que generó directamente las instrucciones de ensamblaje en el procesador de destino a partir de las instrucciones (ahora Macros) en el código de “ensamblaje” del procesador fuente. No conozco todos los detalles, como cuánto tuvo que manipular el código fuente, pero fue un truco genial. Pasó la mayor parte del tiempo creando todas las macros, pero después de eso, generó todo el código para el procesador de destino automáticamente.

Este es un proceso diferente al que usa un compilador (he escrito compiladores) pero análogo.

Un compilador generalmente funciona en un archivo de texto llamado código fuente. La salida puede ser lenguaje ensamblador que tiene mnemónicos uno por uno para códigos de máquina individuales que luego puede ensamblar un ensamblador en código de objeto binario.

El compilador es lo que estás preguntando.

Los compiladores generalmente tienen dos pases. Tienen una función llamada analizador que escanea el texto buscando separadores como final de línea, comentarios, operadores y cadenas que pueden evaluarse como números, constantes, palabras clave, etc. En un primer paso, el compilador utiliza el analizador para hacer un lista de variables y sus tipos y etiquetas que indican la presencia de funciones invocables y direcciones puenteables.

En la segunda pasada, el compilador analiza el código real. Encontrará palabras clave. Romperá las declaraciones de asignación que contienen matemáticas y variables y números en una serie de operaciones que realizan operaciones en dos números a la vez, incluidas las operaciones de carga de registros matemáticos con los operandos y la operación para realizar las matemáticas. Por lo general, hay reglas para seguir el orden de operación o, de lo contrario, buscar y usar paréntesis. Una simple adición de dos elementos de matriz puede llevar a cabo muchos pasos, incluido el cálculo del desplazamiento del elemento de matriz a partir de sus (posiblemente múltiples) subíndices, cargar un puntero a la variable real, obtener datos de la ubicación del puntero y cargarlo en un registro, y eso es solo para un operando. Como puede esperar, una sola ecuación puede resultar en una gran cantidad de operaciones de ensamblaje.

El analizador utiliza las palabras clave para crear operaciones para condicionales y bucles estructurados, subrutinas, llamadas a funciones del sistema y del usuario e incluso gotos simples. La E / S puede ser simple desde establecer ubicaciones de memoria individuales hasta llamar a funciones enlatadas grandes para generar cadenas y / o números con formato ASCII a la consola o impresora. Finalmente, la lista ordenada de operaciones como mnemónicos se genera como un programa de ensamblaje completo.

Durante los dos pasos del análisis del código fuente original, el compilador debe verificar que la sintaxis o las reglas para el uso de signos de puntuación, ecuaciones, formatos de números, nombres variables y palabras clave se hayan seguido exactamente para evitar cualquier ambigüedad. Deben emitirse errores o advertencias y los errores críticos deben detener el progreso de la compilación.

Esa es una especie de respuesta corta. Obviamente, hay más variaciones sobre esto, pero espero haber tocado los puntos principales.

Le recomiendo que lea los lenguajes de programación: diseño e implementación por Terrence W. Pratt, Marvin V. Zelkowitz. Es el mejor libro en este campo, creo.

• Lenguajes de programación

El funcionamiento interno de un compilador puede ser bastante complejo, esto depende del idioma de origen que se esté traduciendo.

Entonces, dado cualquier HLPL (lenguajes de programación de alto nivel), el compilador usa reglas complejas en un proceso de traducción

En el primer paso, el compilador escaneará el programa fuente, como si leyeramos un documento o libro y tradujera las letras a lo que los humanos llamamos palabras. El término utilizado para este proceso en los compiladores se llama “tokenizar”.

Tenga en cuenta que el compilador puede conocer de antemano los tokens, pero también el programador o el propio programa pueden introducir nuevos tokens.

Al igual que en el lenguaje natural, un programa de computadora se crea de acuerdo con una sintaxis.

Entonces, después de crear los tokens, el compilador comenzará a analizar las oraciones a medida que las escribe el programador.

Si el compilador encuentra errores en las oraciones, enviará mensajes de error para que el programador sepa lo que debe corregirse. El compilador también puede informar al programador con advertencias, esto depende mucho del lenguaje fuente que se está compilando.

Suponiendo que el programa no tenga errores, el compilador traducirá cada oración al llamado ‘lenguaje ensamblador’. También es posible que el compilador se traduzca a otro idioma de alto nivel o a algún otro idioma de destino

Traducir es como traducir en un idioma normal cuando traduce, por ejemplo, inglés a chino u holandés a ruso. El lenguaje ensamblador es un paso entre el programa de alto nivel y las instrucciones que una computadora puede “entender” y que los humanos aún pueden leer.

El lenguaje ensamblador se traduce (mediante un compilador de ensamblaje específico) al código de la máquina, instrucciones (representadas por una serie de números) que un procesador puede manejar y ejecutar

El paso final es recopilar todos los programas ensamblados y el proceso de software estándar que llamamos vinculación.

El resultado de este proceso de vinculación es un programa que puede ejecutar.

Este proceso puede variar dependiendo de muchos factores. Algunos lenguajes como C #
o Python se manejan de una manera diferente.

Bueno, el escenario se llama asamblea. Aquí es donde el compilador puede reducir su código fuente a la primitiva apropiada del lenguaje ensamblador. Esto se hace usando un mecanismo de mapeo. Entonces su compilador sabe cuáles son los comandos equivalentes para la plataforma de destino adecuada.

Entonces, la clave es optimizar (muchas etapas), luego reducir y luego generar código objeto. Normalmente, no hay necesidad de generar código de ensamblaje legible por humanos.

El único punto que agregaré a esto es que gran parte de la construcción de un analizador es una traducción puramente mecánica de la gramática del lenguaje al código que ha habido herramientas para escribir esta parte durante mucho tiempo.

Mi favorito actual (y es gratis) es ANTLR

También recomiendo el boosk de Terrance Par para usar ANTLR:
The Definitive ANTLR 4 Referencia: Terence Parr: 9781934356999: Amazon.com: Libros
y
Patrones de implementación del lenguaje: cree sus propios lenguajes de programación generales y específicos de dominio (programadores pragmáticos): Terence Parr: 9781934356456: Amazon.com: Libros

La forma del libro de texto es hacer muchos pases sobre el código fuente, traduciéndolo poco a poco en declaraciones, analizar árboles, bloques básicos y masajearlo lentamente en código máquina.

También es posible hacerlo todo de una vez, muchos compiladores notables del pasado hicieron esto. La ventaja es que no necesita un lugar para almacenar las representaciones intermedias, y elimina todo el código que genera y luego reinterpreta cada representación. No puede hacer mucha optimización, pero a menudo los beneficios de un compilador pequeño y rápido superan los beneficios de un programa cuidadosamente optimizado. Los viejos compiladores Turbo Pascal y Turbo C fueron de una sola pasada, y corrieron como 100 veces más rápido que la competencia.

En su forma más simple, un compilador toma un archivo de código fuente a través de una serie de traducciones. Como primer paso, traduce el archivo fuente a una serie de tokens, y luego ensambla esa serie de tokens en un árbol de sintaxis abstracta. En cada paso del camino, la representación actual del programa de código fuente original está un poco más alejada de ese código fuente que el paso anterior y, en consecuencia, un poco más cerca de la representación que precede a la transformación final en código máquina.

Daré una respuesta corta. La categoría más amplia para esto es “analizar” y “vincular”. Hay esencialmente 3 etapas:

1) recopilar referencias. Ya se trate de referencias a datos o referencias a código. El compilador acumuló una estructura de datos que vincula todas las referencias al mismo punto de código o datos.
2) convertir a un gráfico de instrucciones. Hay muchas formas de hacer esto en la práctica, pero todas comparten en común que básicamente está tomando el formato legible por humanos y convirtiéndolo en un gráfico que describe la secuencia de operaciones y las diferentes formas en que puede ramificarse en función de los datos referencias (como se describe en el paso 1.).
3) Los 2 pasos anteriores producen lo que se llama “código objeto”. El paso final es “vincularlo” junto con otro “código objeto”. Y esa es la belleza del “código objeto” es que todavía tiene las referencias a esos puntos en los datos o el código que pueden “enlazar”. Básicamente, haces que todas las referencias apunten al mismo lugar. Una vez hecho esto, entonces tienes algo por lo que estás secuencialmente y haces un reemplazo uno por uno uno por uno. Cuando encuentre una “referencia” como se menciona en el paso 1 o 2, simplemente reemplácela con ese punto compartido. Esto se llama la etapa de “ensamblaje”. La salida son bytes que se pueden alimentar directamente a una CPU en particular. Supongo que deberían haber sido 4 etapas: recopilar (referencias), compilar (convertir a “código objeto”), vincular (conectar las “referencias” en el “código objeto” juntas), ensamblar (traducir el resultado al “nativo” lenguaje de la CPU.

Mike Colislaw, el autor de rexx, escribió artículos sobre el cálculo en decimal en el compilador. Otras personas también han hecho números racionales.

Los números ingresados ​​ya tienen codificación, por ejemplo, 9 = 0x39, uno de los errores de Y2k es que las personas leen los números más allá del 9 nuevamente, por ejemplo, 0x3a =: y 0x3b =; así que este año es 19; 4, 19114, 1914 y 2014.

Entonces, los diferentes idiomas se leen de manera diferente.