La mayoría de los compiladores tienen la siguiente arquitectura:
En este artículo, voy a diseccionar esta arquitectura en detalle, elemento por elemento.
Podemos decir que este artículo es una adición a la gran cantidad de recursos existentes sobre el tema de los compiladores. Es una fuente autónoma que le permitirá comprender los conceptos básicos de diseño e implementación de lenguajes de programación.
El público objetivo del artículo son las personas cuya idea del trabajo de los compiladores es extremadamente limitada (el máximo es que están involucrados en la compilación). Sin embargo, espero que el lector entienda las estructuras de datos y los algoritmos.
El artículo no está dedicado en modo alguno a los compiladores de producción modernos con millones de líneas de código; no, este es un curso corto de "compiladores para tontos" que ayuda a comprender qué es un compilador.
Introduccion
Actualmente estoy trabajando en el lenguaje del sistema
Krug inspirado en Rust and Go. En el artículo me referiré a Krug como un ejemplo para ilustrar mis pensamientos. Krug está en desarrollo, pero ya está disponible en
https://github.com/krug-lang en los repositorios
caasper y
krug . El lenguaje no es del todo típico en comparación con la arquitectura habitual de los compiladores, lo que en parte me inspiró a escribir un artículo, pero más sobre eso más adelante.
¡Me apresuro a informarles que no soy especialista en compiladores! No tengo un doctorado y no recibí ningún entrenamiento formal: estudié todo lo descrito en el artículo por mi cuenta en mi tiempo libre. También debo decir que no estoy describiendo el enfoque real y único para crear un compilador, sino que presento los métodos básicos adecuados para crear un pequeño compilador de "juguetes".
Frontend
Volvamos al diagrama de arriba: las flechas a la izquierda dirigidas al campo frontend son lenguajes conocidos y amados como C. El frontend se parece a esto: análisis léxico -> analizador sintáctico.
Análisis léxico
Cuando comencé a estudiar compiladores y diseño de lenguaje, me dijeron que el análisis léxico es lo mismo que la tokenización. Usaremos esta descripción. El analizador toma datos de entrada en forma de cadenas o una secuencia de caracteres y reconoce patrones en ellos, que corta en tokens.
En el caso de un compilador, recibe un programa escrito como entrada. Se lee en una cadena desde un archivo, y el analizador tokeniza su código fuente.
enum TokenType { Identifier, Number, }; struct Token { std::string Lexeme; TokenType type; // ... // It's also handy to store things in here // like the position of the token (start to end row:col) };
En este fragmento, escrito en un lenguaje en forma de C, puede ver la estructura que contiene el lexema mencionado anteriormente, así como TokenType, que sirve para reconocer este token.
Nota: el artículo no es una instrucción para crear un lenguaje con ejemplos, pero para una mejor comprensión, insertaré fragmentos de código de vez en cuando.
Los analizadores suelen ser los componentes más simples del compilador. Toda la interfaz, de hecho, es bastante simple en comparación con el resto de las piezas del rompecabezas. Aunque depende mucho de tu trabajo.
Tome la siguiente pieza de código C:
int main() { printf("Hello world!\n"); return 0; }
Después de leerlo de un archivo a una línea y realizar un escaneo lineal, es posible que pueda cortar tokens. Identificamos tokens de forma natural, ya que int es una "palabra" y 0 en la declaración de retorno es un "número". El analizador léxico realiza el mismo procedimiento que nosotros: luego examinaremos este proceso con más detalle. Por ejemplo, analice los números:
0xdeadbeef — HexNumber ( ) 1231234234 — WholeNumber ( ) 3.1412 — FloatingNumber ( ) 55.5555 — FloatingNumber ( ) 0b0001 — BinaryNumber ( )
Definir palabras puede ser difícil. La mayoría de los idiomas definen una palabra como una secuencia de letras y números, y un identificador generalmente debe comenzar con una letra o un guión bajo. Por ejemplo:
123foobar := 3 person-age := 5 fmt.Println(123foobar)
En Go, este código no se considerará correcto y se analizará en los siguientes tokens:
Number(123), Identifier(foobar), Symbol(:=), Number(3) ...
La mayoría de los identificadores encontrados se ven así:
foo_bar __uint8_t fooBar123
Los analizadores tendrán que resolver otros problemas, por ejemplo, con espacios, comentarios multilínea y de una sola línea, identificadores, números, sistemas numéricos y formato de números (por ejemplo, 1_000_000) y codificaciones (por ejemplo, soporte para UTF8 en lugar de ASCII).
Y si crees que puedes recurrir a expresiones regulares, mejor no vale la pena. Es mucho más fácil escribir un analizador desde cero, pero recomiendo leer
este artículo de nuestro rey y dios Rob Pike. Las razones por las cuales Regex no es adecuado para nosotros se describen en muchos otros artículos, por lo que omitiré este punto. Además, escribir un analizador es mucho más interesante que atormentarse con largas expresiones detalladas cargadas en regex101.com a las 5:24 a.m. En mi primer idioma, utilicé la función
split(str) para la tokenización, y no fui muy lejos.
Analizando
El análisis es algo más complicado que el análisis léxico. Hay muchos analizadores y generadores de analizadores: aquí el juego comienza a lo grande.
Los analizadores en los compiladores usualmente toman la entrada en forma de tokens y construyen un árbol específico: un árbol de sintaxis abstracta o un árbol de análisis. Por su naturaleza, son similares, pero tienen algunas diferencias.
Estas etapas se pueden representar como funciones:
fn lex(string input) []Token {...} fn parse(tokens []Token) AST {...} let input = "int main() { return 0; }"; let tokens = lex(input); let parse_tree = parse(tokens); // ....
Por lo general, los compiladores se compilan a partir de muchos componentes pequeños que toman entradas, las cambian o las convierten a diferentes salidas. Esta es una de las razones por las cuales los lenguajes funcionales son adecuados para crear compiladores. Otras razones son excelentes evaluaciones comparativas y bibliotecas estándar bastante extensas. Dato curioso: la primera implementación del compilador
Rust fue en Ocaml.
Le aconsejo que mantenga estos componentes lo más simples y autónomos posible: la modularidad facilitará enormemente el proceso. En mi opinión, lo mismo se puede decir sobre muchos otros aspectos del desarrollo de software.
Arboles
Árbol de análisis
¿Qué demonios es esto? También conocido como árbol de análisis, este árbol grueso sirve para visualizar el programa fuente. Contienen toda la información (o la mayor parte) sobre el programa de entrada, generalmente la misma que se describe en la gramática de su idioma. Cada nodo del árbol será final o no final, por ejemplo, NumberConstant o StringConstant.
Árbol de sintaxis abstracta
Como su nombre lo indica, el ASD es un
árbol de sintaxis
abstracta . El árbol de análisis contiene mucha información (a menudo redundante) sobre su programa y, en el caso de un ASD, no es obligatorio. ASD no necesita información inútil sobre la estructura y la gramática, lo que no afecta la semántica del programa.
Supongamos que su árbol tiene una expresión como ((5 + 5) -3) +2. En el árbol de análisis, lo almacenaría por completo, junto con los corchetes, los operadores y los valores 5, 5, 3 y 2. Pero simplemente puede asociarse con el ASD: solo necesitamos conocer los valores, los operadores y su orden.
La imagen a continuación muestra el árbol para la expresión a + b / c.
ASD se puede representar de la siguiente manera:
interface Expression { ... }; struct UnaryExpression { Expression value; char op; }; struct BinaryExpression { Expression lhand, rhand; string op; // string because the op could be more than 1 char. }; interface Node { ... }; // or for something like a variable struct Variable : Node { Token identifier; Expression value; };
Esta vista es bastante limitada, pero espero que pueda ver cómo se estructurarán sus nodos. Para analizar, puede recurrir al siguiente procedimiento:
Node parseNode() { Token current = consume(); switch (current.lexeme) { case "var": return parseVariableNode(); // ... } panic("unrecognized input!"); } Node n = parseNode(); if (n != null) { // append to some list of top level nodes? // or append to a block of nodes! }
Espero que comprenda la esencia de cómo procederá el análisis paso a paso de los nodos restantes, comenzando con construcciones de lenguaje de alto nivel. Cómo se implementa exactamente un analizador sintáctico con un descenso recursivo, debe estudiar usted mismo.
Gramática
Analizar un ADS de un conjunto de tokens puede ser difícil. Por lo general, debe comenzar por la gramática de su idioma. En esencia, la gramática determina la estructura de su idioma. Hay varios idiomas para definir idiomas que pueden describirse (o analizarse) por sí mismos.
Un ejemplo de un idioma para determinar idiomas es una
forma extendida de Backus-Naur (RBNF). Es una variación de
BNF con menos paréntesis angulares. Aquí hay un ejemplo de RBNF de un artículo de Wikipedia:
digit excluding zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; digit = "0" | digit excluding zero ;
Las reglas de producción están definidas: indican qué plantilla de terminal es "no terminal". Los terminales son parte del alfabeto, por ejemplo, el token if o 0 y 1 en el ejemplo anterior son terminales. Los no terminales son su opuesto, están en el lado izquierdo de las reglas de producción, y pueden considerarse como variables o "punteros con nombre" para grupos de terminales y no terminales.
Muchos idiomas tienen especificaciones que contienen gramática. Por ejemplo, para
Go ,
Rust y
D.Analizadores recursivos de descenso
El descenso recursivo es el más fácil de muchos enfoques de análisis.
Analizadores de descenso recursivo: descendente, basado en procedimientos recursivos. Es mucho más fácil escribir un analizador sintáctico, porque su gramática no ha
dejado recursividad . En la mayoría de los lenguajes de "juguetes", esta técnica es suficiente para analizar. GCC usa un analizador descendente escrito a mano, aunque antes se usaba YACC.
Sin embargo, analizar estos idiomas puede causar problemas. En particular, C, donde
foo * bar
puede ser interpretado como
int foo = 3; int bar = 4; foo * bar; // unused expression
o como
typedef struct { int b; } foo; foo* bar; bar.b = 3;
La implementación de Clang también usa un analizador de descenso recursivo:
Como se trata de un código C ++ normal, un descenso recursivo facilita que los principiantes lo entiendan. Admite reglas personalizadas y otras cosas extrañas que requiere C / C ++ y le ayuda a diagnosticar y corregir errores fácilmente.También vale la pena prestar atención a otros enfoques:
- LL descendente, descenso recursivo
- LR ascendente, cambio, descenso ascendente
Generadores de analizadores
Otra buena manera. Por supuesto, también hay desventajas, pero esto se puede decir sobre cualquier otra opción que los programadores hagan al crear software.
Los generadores de analizadores funcionan muy rápido. Usarlos es más fácil que escribir su propio analizador y obtener un resultado de calidad, aunque no son muy fáciles de usar y no siempre muestran mensajes de error. Además, tendrá que aprender a usar el generador de analizadores y, cuando promocione el compilador, probablemente tenga que desenrollar el generador de analizadores.
Un ejemplo de un generador de analizador es
ANTLR , hay muchos otros.
Creo que esta herramienta es adecuada para aquellos que no quieren pasar tiempo escribiendo una interfaz y que preferirían escribir en el medio y el backend del compilador / intérprete y analizar cualquier cosa.
Aplicación de análisis
Si aún no te entiendes a ti mismo. Incluso la interfaz del compilador (lex / parse) se puede usar para resolver otros problemas:
- resaltado de sintaxis
- Análisis HTML / CSS para motor de renderizado
- transpilers: TypeScript, CoffeeScript
- enlazadores
- REGEX
- análisis de datos de interfaz
- Análisis de URL
- herramientas de formateo como gofmt
- Análisis de SQL y más.
Mediados
Análisis semántico! El análisis de la semántica del lenguaje es una de las tareas más difíciles al crear un compilador.
Debe asegurarse de que todos los programas de entrada funcionen correctamente. En mi lenguaje Krug, los aspectos relacionados con el análisis semántico aún no se han incluido, y sin él, el programador siempre tendrá que escribir el código correcto. En realidad, esto es imposible, y siempre escribimos, compilamos, a veces corremos, corregimos errores. Esta espiral es interminable.
Además, la compilación de programas es imposible sin el análisis de la corrección de la semántica en la etapa apropiada de compilación.
Una vez me encontré con un gráfico sobre el porcentaje de front-end, midland y backend. Entonces parecía
F: 20% M: 20%: B: 60%
Hoy es algo como
F: 5% M: 60% B: 35%
El frontend se ocupa principalmente del generador, y en los lenguajes sin contexto que no tienen la dualidad de la gramática, se pueden completar con bastante rapidez; un descenso recursivo ayudará aquí.
Con la tecnología LLVM, la mayor parte del trabajo de optimización se puede cargar en el marco, que presenta una serie de optimizaciones listas para usar.
El siguiente paso es el análisis semántico, una parte esencial de la fase de compilación.
Por ejemplo, en Rust, con su modelo de administración de memoria, el compilador actúa como una máquina grande y poderosa que realiza varios tipos de análisis estáticos en formas introductorias. Parte de esta tarea es convertir los datos de entrada en una forma más conveniente para el análisis.
Por esta razón, el análisis semántico juega un papel importante en la arquitectura del compilador, y el agotador trabajo preparatorio como optimizar el ensamblaje generado o leer los datos de entrada en el ASD se realiza por usted.
Pasos Semánticos
En el curso del análisis semántico, la mayoría de los compiladores realizan una gran cantidad de "pases semánticos" en el SDA u otra forma abstracta de expresión de código.
Este artículo proporciona detalles sobre la mayoría de los pases realizados en el compilador .NET C #.
No consideraré cada pasaje, especialmente porque varían según el idioma, pero a continuación se describen varios pasos en Krug.
Anuncio de nivel superior
El compilador revisará todos los anuncios de "nivel superior" en los módulos y estará al tanto de su existencia. No profundizará en los bloques, simplemente declarará qué estructuras, funciones, etc. están disponibles en uno u otro módulo.
Resolución de nombre / símbolo
El compilador revisa todos los bloques de código en funciones, etc. y los resuelve, es decir, encuentra caracteres que requieren permiso. Este es un paso común, y es a partir de aquí que el error
XYZ de tal símbolo no suele aparecer al compilar el código Go.
Realizar este pase puede ser muy difícil, especialmente si hay dependencias circulares en su diagrama de dependencia. Algunos idiomas no los permiten, por ejemplo, Go arrojará un error si uno de sus paquetes forma un bucle, como mi lenguaje Krug. Las dependencias cíclicas pueden considerarse un efecto secundario de una arquitectura pobre.
Los bucles se pueden determinar modificando DFS en el diagrama de dependencia, o usando
el algoritmo de Tarjan (como lo hizo Krug) para definir (múltiples) bucles.
Inferencia de tipo
El compilador revisa todas las variables y muestra sus tipos. La inferencia de tipos en Krug es muy débil; simplemente genera variables basadas en sus valores. De ninguna manera es un sistema extraño, como los que puedes encontrar en lenguajes funcionales como Haskell.
Los tipos pueden derivarse mediante el proceso de "unificación" o "unificación de tipos". Para sistemas de tipo más simple, se puede utilizar una implementación muy simple.
Los tipos se implementan en Krug así:
interface Type {}; struct IntegerType : Type { int width; bool signed; }; struct FloatingType : Type { int width; }; struct ArrayType : Type { Type base_type; uint64 length; };
También puede tener una inferencia de tipo simple, en la que asigna un tipo a nodos de expresión, por ejemplo,
IntegerConstantNode puede ser de tipo IntegerType (64). Y luego puede obtener la función
unify(t1, t2) , que seleccionará el tipo más amplio que puede usarse para deducir el tipo de expresiones más complejas, por ejemplo, las binarias. Entonces se trata de asignar una variable a la izquierda a los valores de los tipos dados a la derecha.
Una vez escribí un simple
tipo de reparto en Go, que se convirtió en un prototipo de implementación para Krug.
Pase de mutabilidad
Krug (como Rust) es, por defecto, un lenguaje inmutable, es decir, las variables permanecen sin cambios a menos que se especifique lo contrario:
let x = 3; x = 4; // BAD! mut y = 5; y = 6; // OK!
El compilador revisa todos los bloques y funciones y comprueba que sus "variables son correctas", es decir, no cambiamos lo que no sigue, y que todas las variables pasadas a ciertas funciones son constantes o modificables cuando sea necesario.
Esto se hace con la ayuda de información simbólica que se ha recopilado en pases anteriores. Una tabla de símbolos basada en los resultados del paso semántico contiene nombres de tokens y signos de variabilidad variable. Puede contener otros datos, por ejemplo, en C ++ una tabla puede almacenar información sobre si un símbolo es externo o estático.
Tablas de personajes
Una tabla de caracteres, o "puñalada", es una tabla para encontrar los caracteres que se utilizan en su programa. Se crea una tabla para cada ámbito, y todos contienen información sobre los caracteres presentes en un ámbito particular.
Esta información incluye propiedades tales como el nombre del símbolo, el tipo, el signo de mutabilidad, la presencia de comunicación externa, la ubicación en la memoria estática, etc.
Alcance
Este es un concepto importante en los lenguajes de programación. Por supuesto, su idioma no tiene que hacer posible crear ámbitos anidados, ¡todo se puede colocar en un espacio de nombres común!
Aunque representar el alcance es una tarea interesante para la arquitectura del compilador, en la mayoría de los lenguajes tipo C, el alcance se comporta (o es) como una estructura de datos de pila.
Por lo general, creamos y destruimos ámbitos, y generalmente se usan para administrar nombres, es decir, nos permiten ocultar (sombrear) variables:
{ // push scope let x = 3; { // push scope let x = 4; // OK! } // pop scope } // pop scope
Se puede representar de manera diferente:
struct Scope { Scope* outer; SymbolTable symbols; }
Un tema pequeño, pero recomiendo leer sobre la
pila de espaguetis . Esta es una estructura de datos que se utiliza para almacenar áreas de visibilidad en los nodos ASD de bloques opuestos.
Sistemas de tipo
Muchas de las siguientes secciones se pueden desarrollar en artículos separados, pero me parece que este título merece más. Hoy en día hay mucha información disponible sobre los sistemas de tipos, así como sobre las variedades de los sistemas mismos, alrededor de los cuales se rompen muchas copias. No
profundizaré en este tema, solo dejaré un enlace al
excelente artículo de Steve Klabnik .
Un sistema de tipos es lo que se proporciona y define semánticamente en el compilador utilizando representaciones del compilador y análisis de estas representaciones.
Posesión
Este concepto se usa en la programación cada vez más. Los principios de la semántica de propiedad y movimiento están integrados en el lenguaje
Rust , y espero que aparezcan en otros idiomas. Rust realiza muchos tipos diferentes de análisis estático, que verifica si la entrada satisface un conjunto de reglas con respecto a la memoria: quién posee qué memoria, cuándo se destruye la memoria y cuántas referencias (o préstamos) existen a estos valores o memoria.
La belleza de Rust radica en el hecho de que todo esto se hace durante la compilación, dentro del compilador, para que el programador no tenga que lidiar con la recolección de basura o el conteo de enlaces. Todas estas semánticas están relacionadas con el sistema de tipos y se pueden proporcionar incluso antes de que el programa se presente como un archivo binario completo.
No puedo decir cómo funciona todo bajo el capó, pero todo esto es el resultado de un análisis estático y una investigación maravillosa por parte del equipo de Mozilla y los participantes del proyecto
Cyclone .
Gráficos de control de flujo
Para representar los flujos del programa, utilizamos gráficos de flujo de control (CFG), que contienen todas las rutas que puede seguir la ejecución del programa. Esto se utiliza en el análisis semántico para excluir secciones inactivas de código, es decir, bloques, funciones e incluso módulos que nunca se lograrán durante la ejecución del programa. Los gráficos también se pueden usar para identificar ciclos que no se pueden interrumpir. O para buscar un código inaccesible, por ejemplo, cuando llamas a un "pánico" (llamar a un pánico), o regresas en un bucle, y el código fuera del bucle no se ejecuta.
El análisis del flujo de datos juega un papel importante durante la fase semántica del compilador, por lo que le recomiendo leer sobre los tipos de análisis que puede realizar, cómo funcionan y qué pueden hacer las optimizaciones.
Backend
La parte final de nuestro esquema de arquitectura.Hemos realizado la mayor parte del trabajo de generar binarios ejecutables. Esto se puede hacer de varias maneras, que discutiremos a continuación.
- , . , , «».
, . , , . , , , . , .
, . , ++ — Cfront — C.
JavaScript. TypeScript , , , , .
«» , , , , « » . — , , .
LLVM
LLVM: Rust, Swift, C/C++ (clang), D, Haskell.
« », , . , LLVM . , . , , , , 1, 4, 8 16-. , , - .
-
— , — , .
Go — , LLVM ( ). Go , Windows, Linux MacOS. , Krug -.
. , LLVM, , , LLVM , .
, , , LLVM, IR, , , , ( ).
. , , , . IR ( ) «» fprintf .
8cc .
. — Java: ,
JVM , , Kotlin.
, Java . , . , .
, JVM JIT , JIT-, .
, ! , , . - , , .
Godbolt — , , . , , .
, , (strip the debug symbols), , GCC. , - .
. . , . production-.
rwmj , 8 , 80% . 1971-!
, Rust.
IR
(intermediate representation, IR) , . , , .
IR . , , , .
IR, «», IR . , SSA — Static Single Assignment, , .
Go IR SSA. IR LLVM SSA, .
SSA , , (constant propagation), ( ) .
, . , , , , . ( 16 32), , (spill to the stack).
— ( ). , , .
:
- (graph colouring) — (NP- ). , (liveness ranges) .
- — .
. , . , , .
-, , . , .
fn main() int { let x = 0; { let x = 0; { let x = 0; } } return 0; }
, ( - :) ) , . , .
LLDB
DWARF . LLVM , DWARF GNU-. , , , .
(Foreign Function Interface, FFI )
libc , , . , ?
— . , ( .s/.asm)? ? ,
Jai . , .
(CaaS)
API-. , Krug-, . , , .
, , , . , API-.
production- CaaS. Microsofts Roslyn, , . , , , , API-, , , Rust
RLS .
Krug — — Caasper CaaS-.
Caasper (, , ), , krug, . , , (bootstrap) , .
Krug JavaScript, Go*, , , Krug. JavaScript , yarn/npm.
* Go () , JS.Caasper
.
Github Krug, D LLVM. YouTube-
.
Krug ()
.
Enlaces utiles