Hola a todos! Como programador, siempre estoy buscando formas de mejorar mis habilidades. Un viernes por la noche, se me ocurrió la idea: "¿No escribiría un compilador?"
¿A quién le importa saber qué salió de él? Bienvenido a Cat.
Basado en la "Teoría clásica del compilador" V. E. Karpov, podemos distinguir 5 etapas principales de compilación:
- Análisis léxico
- Analizando
- Generación de código medio
- Optimización
- Generación de código final, objeto.
Sobre todo, cinco partes, puedes escribir muchas oraciones y artículos. Pero hoy hablaremos sobre los dos primeros y cómo seleccioné su estructura en una biblioteca separada.
Cuando decidí escribir, aunque fuera una pequeña parte, del compilador, no pensé en qué idioma estaba escribiendo, por esta razón, el resultado fue una biblioteca para el análisis léxico y sintáctico de cualquier idioma.
Tokenización
Antes de construir un árbol sintáctico y léxico, generar el código resultante y hacer otras cosas sabrosas, debe dividir el código fuente en líneas, caracteres y números.
Donde cada elemento tendrá un tipo definido con precisión. Los tokens de tipo indefinido se considerarán errores de sintaxis durante el análisis.
En el contexto de la compilación, el código fuente se considera como un mapa fuente, es una buena práctica almacenarlo en el proceso de léxico y análisis para obtener retroalimentación del programador e indicar errores de sintaxis en el código fuente.
Puede dividir el código fuente en una matriz de tokens utilizando una expresión regular simple:
/\S+/gm
Puede cambiar dependiendo de las condiciones de análisis adicionales, tales como: análisis de salto de línea, análisis de tabulación, análisis de espacio.
El resultado de la separación será una serie de palabras del código fuente, y las palabras se analizan de espacio en espacio, es decir. este diseño:
let hello = 'world';
Se convertirá al siguiente conjunto de tokens:
["let", "hello", "=", "'world';"]
Para obtener el conjunto final de tokens, debe revisar cada uno de ellos con una expresión regular adicional:
/(\W)|(\w+)/gm
El resultado será el conjunto de tokens que necesitamos:
["let", "hello", "=", "'", "world", "'", ";"]
Todos los tokens que recibimos los escribimos en la matriz, junto con sus índices en el mapa fuente.
Análisis léxico
Ahora que tenemos una variedad de tokens, necesitamos determinar su tipo para pasarlos al análisis.
El algoritmo que define los tokens y sus tipos se llama - Lexer
El token y su tipo, que Lexer define, se llama Token
Cada token puede tener un tipo definido de forma única, por ejemplo:
['let', 'const', 'var']
Sin embargo, implementé un esquema para determinar los tipos de tokens, utilizando el llamado Solver'ov.
Funciona de la siguiente manera:
1. Define constantes para los tipos de token:
const DefaultTokenTypes = { KEYWORD: "Keyword", IDENTIFIER: "Identifier", OPERATOR: "Operator", DELIMITER: "Delimiter", LINEBREAK: "Linebreak", STRING: "String", NUMERIC: "Numeric", UNKNOWN: 'Unknown' };
2. A continuación, es necesario determinar el llamado Solver'y:
const solvers = {}; solvers[MyTokenTypes.KEYWORD] = { include: [ 'const', 'let' ] }; solvers[MyTokenTypes.NUMERIC] = { regexp: /^[0-9.]*$/gm }; solvers[DefaultTokenTypes.STRING] = { type: StringSolver, delimiters: ['"', "'", '`'] }; solvers[MyTokenTypes.IDENTIFIER] = { regexp: /^[a-zA-Z_][a-zA-Z_0-9]*$/gm }; solvers[MyTokenTypes.DELIMITER] = { default: true };
Como puede ver, los tokens pueden tener diferentes configuraciones:
include : conjunto de palabras, por coincidencia con las cuales, se puede determinar el tipo de token.
regexp - Una expresión regular, por coincidencia con la cual, se puede determinar el tipo de token.
default : el tipo estándar para tokens indefinidos.
También puede observar el parámetro
type , que indica que este solucionador debe heredarse del especificado en
typeEn este caso, el solucionador define cadenas que están encerradas en uno de los caracteres especificados en
delimitadores3. Utilizamos solucionadores para la matriz de tokens y obtenemos una matriz de tokens escritos. Para un código fuente dado:
let a = 50;
Obtenemos el siguiente árbol:
[ { "type": "Keyword", "value": "let", "range": [0, 3] }, { "type": "Identifier", "value": "a", "range": [4, 5] }, { "type": "Delimiter", "value": "=", "range": [6, 7] }, { "type": "Numeric", "value": "50", "range": [8, 10] }, { "type": "Delimiter", "value": ";", "range": [10, 11] } ]
Donde
rango es el principio y el final del fragmento en el código fuente.
Analizando
Después de recibir una serie de tokens, debe analizarlos y determinar la estructura sintáctica (árbol) del código fuente.
Hay varias opciones para analizar, pero elegí un algoritmo directo de arriba hacia abajo.
Los tokens se analizan uno por uno utilizando una matriz de plantillas. Si la plantilla coincide con la secuencia actual de tokens, en el árbol de sintaxis, se crea una nueva rama.
Un ejemplo de una plantilla de una matriz:
let declaration = new SequenceNode({ tokenType: MyTokenTypes.KEYWORD, type: MyNodeTypes.DECLARATION, sequence: [ {type: MyTokenTypes.KEYWORD}, {type: MyTokenTypes.IDENTIFIER}, {type: MyTokenTypes.DELIMITER}, {type: [MyTokenTypes.NUMERIC, MyTokenTypes.STRING]}, ';' ], onError: (e) => {
tokenType : describe el token desde el que comenzar a buscar una coincidencia.
tipo : describe el tipo de nodo, todos los tipos también deben definirse, de forma similar a los tipos de token.
secuencia : una matriz de una secuencia, contiene tipos de tokens, valores específicos u otros nodos del árbol de sintaxis.
onError - Callback, que funcionará cuando
ocurra un error de sintaxis, mientras analiza este nodo, devuelve el tipo de error + su lugar en el código fuente.
Analicemos la
secuencia de este nodo:
[ {type: MyTokenTypes.KEYWORD},
Implementé varias variaciones de nodos, para diferentes propósitos: definir secuencias de tokens, definir un grupo de elementos (Argumentos, bloques). Eso permite analizar las funciones de flecha sin ningún problema.
Puede leer sobre todas las variaciones de solucionadores y nodos que implementé en la documentación de esta biblioteca.
Materiales
→ Enlace fuente:
Tyk→
Teoría del compilador clásico