Olá pessoal! Como programador, estou sempre procurando maneiras de melhorar minhas habilidades. Numa sexta-feira à noite, o pensamento veio à minha cabeça - "Eu não escreveria um compilador?"
Quem se importa em descobrir o que aconteceu, bem-vindo ao gato.
Com base na "teoria clássica do compilador" V. E. Karpov, podemos distinguir 5 estágios principais da compilação:
- Análise lexical
- Análise
- Geração de código do meio
- Otimização
- Geração de final, objeto, código
Sobre tudo, cinco partes, você pode escrever muitas frases e artigos. Hoje, porém, falaremos sobre os dois primeiros e como selecionei sua estrutura em uma biblioteca separada.
Quando decidi escrever, mesmo que em pequena parte, do compilador, não pensei em qual idioma estava escrevendo, por esse motivo, o resultado foi uma biblioteca para análise lexical e sintática de qualquer idioma.
Tokenização
Antes de criar uma árvore sintaxe e lexical, gerar o código resultante e fazer outras coisas saborosas, você precisa dividir o código fonte em linhas, caracteres, números.
Onde cada elemento terá um tipo definido com precisão. Tokens de tipo indefinido serão considerados como erros de sintaxe durante a análise.
No contexto da compilação, o código-fonte é considerado como um mapa-fonte; é uma boa prática armazená-lo no processo de léxico e análise para obter feedback do programador e indicar erros de sintaxe no código-fonte.
Você pode dividir o código-fonte em uma matriz de tokens usando uma expressão regular simples:
/\S+/gm
Pode mudar dependendo das condições de análise adicionais, como: análise de quebra de linha, análise de tabulação, análise de espaço.
O resultado da separação será uma matriz de palavras do código fonte, com as palavras analisando de um espaço para o outro, ou seja, este design:
let hello = 'world';
Ele será convertido no seguinte conjunto de tokens:
["let", "hello", "=", "'world';"]
Para obter o conjunto final de tokens, você precisa passar por cada um deles com uma expressão regular adicional:
/(\W)|(\w+)/gm
O resultado será o conjunto de tokens que precisamos:
["let", "hello", "=", "'", "world", "'", ";"]
Todos os tokens que recebemos, escrevemos na matriz, junto com seus índices no mapa de origem
Análise lexical
Agora que temos uma matriz de tokens, precisamos determinar seu tipo para passá-los para análise.
O algoritmo que define os tokens e seus tipos é chamado - Lexer
O token e seu tipo, definidos pela Lexer, são chamados de token
Cada token pode ter um tipo definido exclusivamente, por exemplo:
['let', 'const', 'var']
No entanto, implementei um esquema para determinar os tipos de tokens, usando o chamado Solver'ov.
Funciona da seguinte maneira:
1. Você define constantes para tipos de token:
const DefaultTokenTypes = { KEYWORD: "Keyword", IDENTIFIER: "Identifier", OPERATOR: "Operator", DELIMITER: "Delimiter", LINEBREAK: "Linebreak", STRING: "String", NUMERIC: "Numeric", UNKNOWN: 'Unknown' };
2. Em seguida, é necessário determinar o chamado 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 você pode ver, os tokens podem ter configurações diferentes:
include - Uma matriz de palavras, por coincidência com a qual, o tipo de token pode ser determinado.
regexp - Uma expressão regular, por coincidência com a qual, o tipo de token pode ser determinado.
padrão - o tipo padrão para tokens indefinidos.
Você também pode observar o parâmetro
type , que indica que esse solucionador deve ser herdado daquele especificado no
tipoNesse caso, o solucionador define cadeias que estão entre um dos caracteres especificados nos
delimitadores3. Usamos solucionadores para a matriz de tokens e obtemos uma matriz de tokens digitados. Para um determinado código-fonte:
let a = 50;
Temos a seguinte árvore:
[ { "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] } ]
Onde
range é o começo e o fim do fragmento no código-fonte.
Análise
Depois de receber uma matriz de tokens, você deve analisá-los e determinar a estrutura sintática (árvore) do código-fonte.
Existem várias opções para análise, mas eu escolhi um algoritmo direto, de cima para baixo.
Os tokens são analisados um por um usando uma matriz de modelos. Se o modelo corresponder à sequência atual de tokens - na árvore de sintaxe, um novo ramo será criado.
Um exemplo de um modelo de uma 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 - Descreve o token a partir do qual iniciar a verificação de uma correspondência.
type - Descreve o tipo de nó, todos os tipos também devem ser definidos, semelhantes aos tipos de token.
sequência - Uma matriz de uma sequência, contém tipos de tokens, valores específicos ou outros nós da árvore de sintaxe.
onError - retorno de chamada, que funcionará quando
ocorrer um erro de sintaxe, ao analisar esse nó, ele retornará o tipo de erro + seu lugar no código-fonte.
Vamos analisar a
sequência deste nó:
[ {type: MyTokenTypes.KEYWORD},
Eu implementei várias variações de nós, para diferentes propósitos: definindo sequências de tokens, definindo um grupo de elementos (Argumentos, blocos). Isso permite analisar funções de seta sem problemas.
Você pode ler sobre todas as variações de Solvers e Nós que implementei na documentação desta biblioteca.
Materiais
→ Link da fonte:
Tyk→
Teoria Clássica do Compilador