JavaScript编译原理 - qidao123.com技术社区-IT企服评测·应用市场

input => tokenizer => tokens; // 词法分析
tokens => parser => ast; // 语法分析，生成AST
ast => transformer => newAst; // 中间层代码转换
newAst => generator => output; // 生成目标代码

复制代码

const FN_NAME_TOKEN = /[a-zA-Z]/;
const NUMBER_TOKEN = /\d/;
const PAREN_TOKEN = /\(/;
const ATI_PAREN_TOKEN = /\)/;
const COMMA_TOKEN = /\,/;

复制代码

function tokenizer(expression) {
const tokens = [];
let current = 0;
while (current < expression.length) {
let char = expression[current];
// 先匹配数字
if (NUMBER_TOKEN.test(char)) {
let number = "";
// 一直往后找，直到不是数字为止
while (NUMBER_TOKEN.test(char)) {
number += char;
char = expression[++current];
}
// 将匹配到的 token 加入到 tokens 中
tokens.push({
type: "number",
value: parseInt(number),
});
continue;
}
// 匹配函数名
if (FN_NAME_TOKEN.test(char)) {
let fnName = "";
while (FN_NAME_TOKEN.test(char)) {
fnName += char;
char = expression[++current];
}
tokens.push({
type: "function",
value: fnName,
});
continue;
}
// 匹配括号和逗号
if (
PAREN_TOKEN.test(char) ||
ATI_PAREN_TOKEN.test(char) ||
COMMA_TOKEN.test(char)
) {
tokens.push({
type: char,
value: char,
});
current++;
continue;
}
// 处理空格
if (char === " ") {
current++;
continue;
}
throw new TypeError("I dont know what this character is: " + char);
}
return tokens;
}

复制代码

function parser(tokens) {
let current = 0;
// 递归解析
function walk() {
let token = tokens[current];
// 处理数字
if (token.type === "number") {
current++;
return {
type: "NumberLiteral",
value: token.value,
};
}
// 处理函数
if (token.type === "function") {
current++;
let node = {
type: "CallExpression",
name: token.value,
params: [],
};
token = tokens[++current];
// 一直循环往复的收集参数，知道遇到右括号位置
while (token.type !== ")") {
node.params.push(walk());
token = tokens[current];
// 注意一点，如果遇到了参数中间的逗号，也需要跳过
if (token.type === ",") {
current++;
}
}
current++; // 跳过右括号
return node;
}
throw new TypeError(token.type);
}
let ast = {
type: "Program",
body: [],
};
while (current < tokens.length) {
ast.body.push(walk());
}
return ast;
}

复制代码

ADD(1, MINUS(3, MULTIPLY(4, 2)))

复制代码

function interpret(ast) {
const operators = {
Add: (a, b) => a + b,
Subtract: (a, b, c) => a - b - c,
Multiply: (a, b) => a * b,
Divide: (a, b) => a / b,
};
function traverseNode(node) {
switch (node.type) {
case "NumberLiteral":
return node.value;
case "CallExpression":
const args = node.params.map(traverseNode);
const operator = operators[node.name];
if (!operator) {
throw new TypeError("Unknown function: " + node.name);
}
return operator(...args);
default:
throw new TypeError(node.type);
}
}
return traverseNode(ast.body[0]);
}

复制代码

const expression = "Subtract(Add(3, Multiply(4, 2)), Divide(6, 2), 1)";
const tokens = tokenize(expression);
const ast = parse(tokens);
const result = interpret(ast);
console.log(result);

复制代码

// 界说 token 类型const FN_NAME_TOKEN = /[a-zA-Z]/;
const NUMBER_TOKEN = /\d/;
const PAREN_TOKEN = /\(/;
const ATI_PAREN_TOKEN = /\)/;
const COMMA_TOKEN = /\,/;// 界说 tokenizer 函数，将表达式转换为 token 数组function tokenizer(expression) { const tokens = []; let current = 0; while (current < expression.length) { let char = expression[current]; // 先匹配数字 if (NUMBER_TOKEN.test(char)) { let number = ""; // 一直往后找，直到不是数字为止 while (NUMBER_TOKEN.test(char)) { number += char; char = expression[++current]; } // 将匹配到的 token 加入到 tokens 中 tokens.push({ type: "number", value: parseInt(number), }); continue; } // 匹配函数名 if (FN_NAME_TOKEN.test(char)) { let fnName = ""; while (FN_NAME_TOKEN.test(char)) { fnName += char; char = expression[++current]; } tokens.push({ type: "function", value: fnName, }); continue; } // 匹配括号和逗号 if ( PAREN_TOKEN.test(char) || ATI_PAREN_TOKEN.test(char) || COMMA_TOKEN.test(char) ) { tokens.push({ type: char, value: char, }); current++; continue; } // 处理空格 if (char === " ") { current++; continue; } throw new TypeError("I dont know what this character is: " + char); } return tokens;}// 界说 parser 函数，将 token 数组转换为 ASTfunction parser(tokens) { let current = 0; // 递归解析 function walk() { let token = tokens[current]; // 处理数字 if (token.type === "number") { current++; return { type: "NumberLiteral", value: token.value, }; } // 处理函数 if (token.type === "function") { current++; let node = { type: "CallExpression", name: token.value, params: [], }; token = tokens[++current]; // 一直循环往复的收集参数，知道遇到右括号位置 while (token.type !== ")") { node.params.push(walk()); token = tokens[current]; // 注意一点，假如遇到了参数中心的逗号，也必要跳过 if (token.type === ",") { current++; } } current++; // 跳过右括号 return node; } throw new TypeError(token.type); } let ast = { type: "Program", body: [], }; while (current < tokens.length) { ast.body.push(walk()); } return ast;}// 界说 transformer 函数，将 AST 转换为新的 ASTfunction interpret(ast) { const operators = { Add: (a, b) => a + b, Subtract: (a, b, c) => a - b - c, Multiply: (a, b) => a * b, Divide: (a, b) => a / b, }; function traverseNode(node) { switch (node.type) { case "NumberLiteral": return node.value; case "CallExpression": const args = node.params.map(traverseNode); const operator = operators[node.name]; if (!operator) { throw new TypeError("Unknown function: " + node.name); } return operator(...args); default: throw new TypeError(node.type); } } return traverseNode(ast.body[0]);}// 解析运算表达式const expression = "Subtract(Add(3, Multiply(4, 2)), Divide(6, 2), 1)";
const tokens = tokenize(expression);
const ast = parse(tokens);
const result = interpret(ast);
console.log(result);

复制代码