предисловие
На коде компилируется через серию статей [общественное число: фронт-конечный новичок 001] Введение и практика, мы должны реализовать и выполнять компилятор [компилятор] иметь определенные знания и понимание.
Давайте дальше рассмотрим это.编译器是怎么实现不同语言之间的转换的.
(Язык А => Язык Б и не влияет на корректный результат выполнения программы)
текст
Чтобы лучше понять, как компилятор реализует преобразование языка А в язык Б, для иллюстрации будут использованы следующие диаграммы.
(Для удобства язык A обозначается аббревиатурой L-A, а язык B обозначается аббревиатурой L-B)
-
1. L-A / L-B
Во-первых, давайте представим разницу между исходным языком A и целевым языком B, который необходимо преобразовать:
// L-A
(add 2 (subtract 4 2))
// L-B
add(2, subtract(4, 2))
Соответствующая структура дерева синтаксиса AST:
Умные люди должны видеть, что в процессе реализации преобразования кода для разных языков, помимо обычно используемого лексического анализа и синтаксического анализа, основной работой является преобразование AST и генерация целевого кода вновь сгенерированного AST. . . . Каждый шаг описан ниже.
-
2. Лексический анализ (токенизатор)
Процесс лексического анализа был представлен и неоднократно практиковался в предыдущих статьях.
Мы не будем обсуждать это подробно здесь.
токены выглядят так:
const input = '(add 2 (subtract 4 2))';
const tokens = [
{ type: 'paren', value: '(' },
{ type: 'name', value: 'add' },
{ type: 'number', value: '2' },
{ type: 'paren', value: '(' },
{ type: 'name', value: 'subtract' },
{ type: 'number', value: '4' },
{ type: 'number', value: '2' },
{ type: 'paren', value: ')' },
{ type: 'paren', value: ')' }
];
function tokenizer(input) {
let tokens = []
let current = 0;
while(current < input.length) {
let char = input[current]
// '(' ')' 括号
if(char === '(' || char === ')') {
tokens.push({
type: 'para',
value: char
})
current++;
continue;
}
// 空格
let WHITESPACE = /\s/;
if(WHITESPACE.test(char)) {
current++;
continue;
}
// 0-9 数字
let NUMBERS = /[0-9]/;
if(NUMBERS.test(char)) {
//...
let value = '';
while(NUMBERS.test(char)) {
value += char;
char = input[++current]
}
tokens.push({
type: 'number',
value
})
continue;
}
// string "xx" 字符串
if(char === '"') {
// ...
}
// name
let LETTERS = /[a-z]/i;
if(LETTERS) {
// ...
}
throw new TypeErroe(char)
}
return tokens
}
-
3. Синтаксический анализ (парсер)
В соответствии с токенами, полученными в результате лексического анализа, и описанной выше грамматической структурой АСТ L-A, синтаксический анализатор может быть запрограммирован на преобразование токенов в синтаксическое дерево АСТ, соответствующее L-A.
function parser(tokens) {
const current = 0;
// 定义 ast 根结点
let ast = {
type: 'Program',
body: [],
};
while(current < tokens.length) {
ast.body.push(walk());
}
// 定义一个递归调用的`walk`函数
function walk() {
// 获取当前要处理的 token
let token = tokens[current];
// 如果当前值是 number 或者 string 则返回一个ast节点
if (token.type === 'number') {
current++；
return {
type: 'NumberLiteral',
value: token.value,
};
}
if (token.type === 'string') {
current++;
return {
type: 'StringLiteral',
value: token.value,
};
}
// 如果是 '(' 括号则创建一个 `CallExpression` ast 节点
if (token.type === 'paren' && token.value === '(') {
// 获取'('括号后面的 token
token = tokens[++current];
// 创建一个 `CallExpression` ast节点，并把当前token设置为其name
let node = {
type: 'CallExpression',
name: token.value,
params: [],
};
// 获取 name 后面的 token
token = tokens[++current];
// 处理 `CallExpression` 节点的后代节点
while ((token.type !== 'paren') ||
(token.type === 'paren' && token.value !== ')')
) {
// 递归调用`walk`函数，将其返回的节点并挂到node.params
node.params.push(walk());
token = tokens[current];
}
// 跳过 ')' 括号
current++;
return node;
}
}
return ast;
}
// 最终 ast 结果
const ast = {
type: 'Program',
body: [{
type: 'CallExpression',
name: 'add',
params: [{
type: 'NumberLiteral',
value: '2'
}, {
type: 'CallExpression',
name: 'subtract',
params: [{
type: 'NumberLiteral',
value: '4'
}, {
type: 'NumberLiteral',
value: '2'
}]
}]
}]
};
На данный момент мы получили AST L-A, и позже мы войдем в чрезвычайно важную ссылку преобразования.
-
4. Трансформатор
Фаза преобразования, которая берет AST из последнего шага выше и изменяет его. Он может манипулировать AST, как если бы это был тот же самый язык, или может переводить его на совершенно новый язык.
Давайте посмотрим, как конвертировать AST.
Возможно, вы обнаружили, что в AST есть элементы, которые выглядят очень похожими, эти объекты имеют атрибут типа, каждый принадлежит узлу AST, и эти узлы, определяющие атрибут, описывают дерево независимой части.
При преобразовании AST узлами можно манипулировать, добавляя/удаляя/заменяя атрибуты, можно добавлять новые узлы, узлы можно удалять или отбрасывать существующий AST и создавать на его основе новый AST.
Поскольку целью здесь является преобразование на новый язык, основное внимание уделяется созданию совершенно нового AST для целевого языка.
Чтобы иметь возможность посетить все узлы, необходимо пройти весь AST, используя алгоритм поиска в глубину.
Если мы напрямую манипулируем этим AST вручную (добавляем, удаляем и модифицируем) вместо того, чтобы создавать отдельный AST, могут быть введены различные абстракции, но для работы, которую мы собираемся здесь выполнить, нам нужно посетить только каждый узел в дереве. по одному. .
Конкретное определение посетителя выглядит следующим образом:
// 定义一个带有 node-types处理的 visitor, 为了更有效这里添加了对父节点的引用
var visitor = {
NumberLiteral(node, parent) {},
CallExpression(node, parent) {},
};
// ast 结构
- Program
- CallExpression
- NumberLiteral
- CallExpression
- NumberLiteral
- NumberLiteral
// ast深度优先算法处理 //回溯
-> Program (enter)
-> CallExpression (enter)
-> Number Literal (enter)
<- Number Literal (exit)
-> Call Expression (enter)
-> Number Literal (enter)
<- Number Literal (exit)
-> Number Literal (enter)
<- Number Literal (exit)
<- CallExpression (exit)
<- CallExpression (exit)
<- Program (exit)
// 为了支持 enter/exit处理，最终将 visitor定义成这样
var visitor = {
NumberLiteral: {
enter(node, parent) {},
exit(node, parent) {},
}
// ...
};
Теперь с посетителем мы можем обрабатывать различные типы узлов AST,
Ниже мы определяем функцию обхода, которая может принимать AST и посетителя.
function traverser(ast, visitor) {
// 支持数组类型的遍历
function traverseArray(array, parent) {
array.forEach(child => {
traverseNode(child, parent);
});
}
//
function traverseNode(node, parent) {
let methods = visitor[node.type];
// 节点enter时钩子
if (methods && methods.enter) {
methods.enter(node, parent);
}
switch (node.type) {
case 'Program':
traverseArray(node.body, node);
break;
//
case 'CallExpression':
traverseArray(node.params, node);
break;
// `NumberLiteral` 和 `StringLiteral` 类型不做任何 node 处理
case 'NumberLiteral':
case 'StringLiteral':
break;
}
// 节点exit 时钩子
if (methods && methods.exit) {
methods.exit(node, parent);
}
}
// 遍历 ast 节点
traverseNode(ast, null);
}
Затем реализуйте трансформатор, чтобы построить новый AST
function transformer(ast) {
// 创建新的 ast根结点
let newAst = {
type: 'Program',
body: [],
};
// 为了方便，这里将 body的引用 copy到 ast._context
ast._context = newAst.body;
// 遍历 ast
traverser(ast, {
NumberLiteral: {
enter(node, parent) {
parent._context.push({
type: 'NumberLiteral',
value: node.value,
});
},
},
StringLiteral: {
enter(node, parent) {
parent._context.push({
type: 'StringLiteral',
value: node.value,
});
},
},
CallExpression: {
enter(node, parent) {
// 创建一个 'CallExpression'
let expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.name,
},
arguments: [],
};
// 在'CallExpression' 节点上 定义一个新的引用
node._context = expression.arguments;
//
if (parent.type !== 'CallExpression') {
// 用`ExpressionStatement`包装一下`CallExpression`节点。
expression = {
type: 'ExpressionStatement',
expression: expression,
};
}
parent._context.push(expression);
}
}
})
return newAst;
}
const newAst = {
type: 'Program',
body: [{
type: 'ExpressionStatement',
expression: {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: 'add'
},
arguments: [{
type: 'NumberLiteral',
value: '2'
}, {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: 'subtract'
},
arguments: [{
type: 'NumberLiteral',
value: '4'
}, {
type: 'NumberLiteral',
value: '2'
}]
}]
}
}]
};
-
5. Генерация кода (Генератор кода)
На последнем этапе генерации кода генератор кода рекурсивно вызывает сам себя для вывода каждого узла в дереве в виде длинной строки.
function codeGenerator(node) {
switch (node.type) {
// 如果是 'Program'， 将会 map 遍历其 body 属性，并插入换行符
case 'Program':
return node.body.map(codeGenerator)
.join('\n');
// 如果是`ExpressionStatement` 用括号包装并且嵌套调用代码生成器表达式，并加上分号
case 'ExpressionStatement':
return (
codeGenerator(node.expression) +
';'
);
// 对于`CallExpression`，则打印 `callee`并添加一个左括号，
// 然后将遍历`arguments`数组中的每个节点，并通过代码生成器运行它们，
// 然后用逗号将它们连接起来，然后添加右括号。 用括号对其包装
case 'CallExpression':
return (
codeGenerator(node.callee) +
'(' +
node.arguments.map(codeGenerator)
.join(', ') +
')'
);
case 'Identifier':
return node.name;
// 对于 `NumberLiteral` 直接返回
case 'NumberLiteral':
return node.value;
// 对于 `StringLiteral`， 用 “ ” 包装
case 'StringLiteral':
return '"' + node.value + '"';
}
}
const output = "add(2, subtract(4, 2))";
На данный момент компилятор полностью оснащен всеми функциями преобразования L-A в L-B. От ввода до вывода он прошел четыре этапа и, наконец, завершил преобразование кода компилятора.
1. input => tokenizer => tokens
2. tokens => parser => ast
3. ast => transformer => newAst
4. newAst => generator => output
Если вы видели это, поздравляю, вы превзошли 80% ваших читателей.
Эпилог
На данный момент серия предварительных компиляций кода подошла к концу.Я думаю, если вы сможете понять все эти четыре статьи и вручную внедрить задействованные коды, у вас обязательно появится новое понимание повседневной фронтенд-разработки, будь то инженерная или В преобразовании используется babel или eslint, базовые принципы очень похожи.
использованная литература:
пс: если есть неточности, поправьте
Маленький новичок в области фронтенда | Жажда знаний | Мечты и любовь нельзя подвести