lisp
风格的函数调用转换为 C
风格//假设我们有两个函数,`add` 和 `subtract`,那么它们的写法将会是下面这样
LISP C
2 + 2 (add 2 2) add(2, 2)
4 - 2 (subtract 4 2) subtract(4, 2)
2 + (4 - 2) (add 2 (subtract 4 2)) add(2, subtract(4, 2))
token
的东西,这个过程是在词法分析器(Tokenizer或者Lexer)中完成的token
,把它们转换成一种抽象的表示,这种抽象的表示描述了代码语句中的每一个片段以及它们之间的关系。这被称为中间表示(intermediate representation)或抽象语法树(Abstract Syntax Tree, 缩写为AST)原始lisp
代码
(add 2 (subtract 4 2))
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: ')' }
]
抽象语法树(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
中有很多相似的元素,这些元素都有type
属性,它们被称为 AST
结点。这些结点含有若干属性,可以用于描述 AST 的部分信息NumberLiteral
结点{
type: 'NumberLiteral',
value: '2'
}
CallExpression
结点 {
type: 'CallExpression',
name: 'subtract',
params: [...nested nodes go here...]
}
{
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'
}]
}]
}]
}
Program - 从 AST 的顶部结点开始
CallExpression (add) - Program 的第一个子元素
NumberLiteral (2) - CallExpression (add) 的第一个子元素
CallExpression (subtract) - CallExpression (add) 的第二个子元素
NumberLiteral (4) - CallExpression (subtract) 的第一个子元素
NumberLiteral (2) - CallExpression (subtract) 的第二个子元素
var visitor = {
NumberLiteral() {},
CallExpression() {}
};
AST
的时候,如果遇到了匹配 type
的结点,我们可以调用 visitor
中的方法AST
打印
AST 中所有类型的结点,然后它会递归地调用自身,直到所有代码都被打印到一个很长的字符串中token
组成的数组 (add 2 (subtract 4 2)) => [{ type: 'paren', value: '(' }, ...]
main.js
let tokenizer = require('./tokenizer');
let tokens = tokenizer("(add 11 22)");
console.log(tokens);
tokenizer.js
let LETTERS = /[a-z]/i;
let WHITESPACE = /\s/;
let NUMBERS = /[0-9]/;
function tokenizer(input){
//current类似指标,用于记录我们在代码字符串中的位置
let current=0;
//tokens是一个数组,用来放置我们的token
let tokens = [];
//可能会在单个循环中多次增加current
while(current < input.length){
//char 指向当前字符串
let char = input[current];
//先检查是不是一个左圆括号
if(char === '('){
//如果是的话,我们往tokens里push一个type为paren,value为左圆括号的对象
tokens.push({
type:'paren',
value:'('
});
//自增current
current++;
//结束本次循环,进入下一个循环
continue;
//如果token是函数名,函数名是由一系列字母组成 比如 (add 11 22)
}else if(LETTERS.test(char)){
let value = '';
//用内层循环遍历所有的字母,把它们存入value中
while(LETTERS.test(char)){
value+=char;
char = input[++current];
}
//然后添加一个类型为name的token,进入下一个循环
tokens.push({
type:'name',
value
});
continue;
}else if(WHITESPACE.test(char)){
//token并不是有效的token,所以直接进入下一个循环
current++;
continue;
}else if(NUMBERS.test(char)){
let value = '';
//用内层循环遍历所有的数字,把它们存入value中
while(NUMBERS.test(char)){
value+=char;
char = input[++current];
}
//然后添加一个类型为number的token,进入下一个循环
tokens.push({
type:'number',
value
});
continue;
}else if(char === ')'){
tokens.push({
type: 'paren',
value: ')'
});
current++;
continue;
}
//如果没有匹配上任何类型的token,则抛出一个错误
throw new TypeError('I dont know what this character is '+ char);
}
return tokens;
}
module.exports = tokenizer;
token
数组,然后把它转化为 AST
let tokenizer = require('./tokenizer');
+let parser = require('./parser');
+let tokens = tokenizer("(add 11 (sub 3 1))");
console.log(tokens);
+let ast = parser(tokens);
+console.log(JSON.stringify(ast,null,2));
/**
* 语法分析器接受 token 数组,然后把它转化为 AST
* [{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] }
*/
//现在我们定义parser函数,接受tokens数组
function parser(tokens) { // (add 11 22) (add 2 (subtract 4 2))
//我们再次声明一个current变量指针
let current = 0;
//但是这次我们使用递归而不是 `while` 循环,所以我们定义一个 `walk` 函数
function walk() {
// walk函数里,我们从当前token开始
let token = tokens[current];
//我们检查是不是 CallExpressions 类型,我们从左圆括号开始
if (token.type === 'paren' && token.value == '(') {
// 我们会自增 `current` 来跳过这个括号,因为括号在 AST 中是不重要的
token = tokens[++current];
//我们创建一个类型为 `CallExpression` 的根节点,然后把它的 name 属性设置为当前token 的值
//因为紧跟在左圆括号后面的 token 一定是调用的函数的名字
let node = {
type: 'CallExpression',
name: token.value,
params: []
}
// 我们再次自增 `current` 变量,跳过当前的 token
token = tokens[++current];
//现在我们循环遍历接下来的每一个 token,直到我们遇到右圆括号,这些 token 将会是 `CallExpression` 的 `params`(参数)
//这也是递归开始的地方,我们采用递归的方式来解决问题,而不是去尝试解析一个可能有无限层嵌套的结点
//(add 2 (subtract 4 2))
//所以我们创建一个 `while` 循环,直到遇到类型为 `'paren'`,值为右圆括号的 token
while (token.type != 'paren' || token.type == 'paren' && token.value != ')') {
//我们调用 `walk` 函数,它将会返回一个结点,然后我们把这个节点放入 `node.params` 中
node.params.push(walk());
token = tokens[current];
}
// 我们最后一次增加 `current`,跳过右圆括号
current++;
// 返回结点
return node;
//检查是不是 `number` 类型
}else if(token.type === 'number'){
// 如果是,`current` 自增。
current++;
// 然后我们会返回一个新的 AST 结点 `NumberLiteral`,并且把它的值设为 token 的值。
return {
type: 'NumberLiteral',
value: token.value
};
}
//同样,如果我们遇到了一个类型未知的结点,就抛出一个错误。
throw new TypeError(token.type);
}
//现在,我们创建 AST,根结点是一个类型为 `Program` 的结点
var ast = {
type: 'Program',
body: []
};
//现在我们开始 `walk` 函数,把结点放入 `ast.body` 中
//之所以在一个循环中处理,是因为我们的程序可能在 `CallExpressions` 后面包含连续的两个参数,而不是嵌套的
//(add 2 2) (subtract 4 2)
while (current < tokens.length) {
ast.body.push(walk());
}
// 最后我们的语法分析器返回 AST
return ast;
}
module.exports = parser;
visitor
去遍历所有的结点。当遇到某个类型的结点时,我们需要调用 visitor
中对应类型的处理函数 traverse(ast, {
Program(node, parent) {
console.log(node);
},
CallExpression(node, parent) {
console.log(node);
},
NumberLiteral(node, parent) {
console.log(node);
},
});
let tokenizer = require("./tokenizer");
let parser = require("./parser");
+let traverser = require("./traverser");
let tokens = tokenizer("(add 11 (sub 3 1))");
console.log(tokens);
let ast = parser(tokens);
console.log(JSON.stringify(ast, null, 2));
+let vistor = {
+ Program(node, parent) {
+ console.log(node);
+ },
+ CallExpression(node, parent) {
+ console.log(node);
+ },
+ NumberLiteral(node, parent) {
+ console.log(node);
+ },
+};
+traverser(ast,vistor);
// 所以我们定义一个遍历器,它有两个参数,AST 和 vistor。在它的里面我们又定义了两个函数...
function traverser(ast, visitor) {
// `traverseArray` 函数允许我们对数组中的每一个元素调用 `traverseNode` 函数。
function traverseArray(array, parent) {
array.forEach(function(child) {
traverseNode(child, parent);
});
}
// `traverseNode` 函数接受一个 `node` 和它的父结点 `parent` 作为参数,这个结点会被
// 传入到 visitor 中相应的处理函数那里。
function traverseNode(node,parent){
// 首先我们看看 visitor 中有没有对应 `type` 的处理函数。
var method = visitor[node.type];
// 如果有,那么我们把 `node` 和 `parent` 都传入其中。
if (method) {
method(node, parent);
}
// 下面我们对每一个不同类型的结点分开处理。
switch (node.type) {
//我们从顶层的 `Program` 开始,Program 结点中有一个 body 属性,它是一个由若干个结点组成的数组,所以我们对这个数组调用 `traverseArray`
//记住 `traverseArray` 会调用 `traverseNode`,所以我们会递归地遍历这棵树。
case 'Program':
traverseArray(node.body, node);
break;
//下面我们对 `CallExpressions` 做同样的事情,遍历它的 `params`。
case 'CallExpression':
traverseArray(node.params, node);
break;
// 如果是 `NumberLiterals`,那么就没有任何子结点了,所以我们直接 break
case 'NumberLiteral':
break;
// 同样,如果我们不能识别当前的结点,那么就抛出一个错误。
default:
throw new TypeError(node.type);
}
}
// 最后我们对 AST 调用 `traverseNode`,开始遍历。注意 AST 并没有父结点。
traverseNode(ast, null);
}
module.exports = traverser;
let tokenizer = require("./tokenizer");
let parser = require("./parser");
let traverser = require("./traverser");
+let transformer = require("./transformer");
let tokens = tokenizer("(add 2 (subtract 4 2))");
console.log(tokens);
let ast = parser(tokens);
console.log(JSON.stringify(ast, null, 2));
let vistor = {
Program(node, parent) {
console.log(node);
},
CallExpression(node, parent) {
console.log(node);
},
NumberLiteral(node, parent) {
console.log(node);
},
};
//traverser(ast,vistor);
+var newAst = transformer(ast);
+console.log(JSON.stringify(newAst, null, 2));
let traverser = require('./traverser');
function transformer(ast) {
// 创建 `newAST`,它与我们之前的 AST 类似,有一个类型为 Program 的根节点。
var newAst = {
type: 'Program',
body: []
};//老的ast有一个属性_context指向新的ast的body
ast._context = newAst.body;
// 我们把 AST 和 visitor 函数传入遍历器
traverser(ast,{
NumberLiteral(node,parent){
// 我们创建一个新结点,名字叫 `NumberLiteral`,并把它放入父结点的 context 中。
parent._context.push({
type:'NumberLiteral',
value:node.value
});
},
CallExpression(node,parent){
//我们创建一个 `CallExpression` 结点,里面有一个嵌套的 `Identifier`
var expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.name
},
arguments: []
};
// 下面我们在原来的 `CallExpression` 结点上定义一个新的 context,它是 expression
// 中 arguments 这个数组的引用,我们可以向其中放入参数。
node._context = expression.arguments;
// 最后我们把 `CallExpression`放入父结点的 context 中。
parent._context.push(expression);
}
});
// 最后返回创建好的新 AST
return newAst;
}
module.exports = transformer;
let tokenizer = require("./tokenizer");
let parser = require("./parser");
let traverser = require("./traverser");
let transformer = require("./transformer");
let codeGenerator = require("./codeGenerator");
let tokens = tokenizer("(add 2 (subtract 4 2))");
console.log(tokens);
let ast = parser(tokens);
console.log(JSON.stringify(ast, null, 2));
let vistor = {
Program(node, parent) {
console.log(node);
},
CallExpression(node, parent) {
console.log(node);
},
NumberLiteral(node, parent) {
console.log(node);
},
};
//traverser(ast,vistor);
var newAst = transformer(ast);
console.log(JSON.stringify(newAst, null, 2));
let newCode = codeGenerator(newAst);
console.log(newCode);
function codeGenerator(node) {
// 对于不同 `type` 的结点分开处理。
switch (node.type) {
// 如果是 `Program` 结点,那么我们会遍历它的 `body` 属性中的每一个结点,并且递归地
// 对这些结点再次调用 codeGenerator,再把结果打印进入新的一行中。
case 'Program':
return node.body.map(codeGenerator)
.join('\n');
// 对于 `CallExpressions`,我们会打印出 `callee`,接着是一个左圆括号,然后对
// arguments 递归调用 codeGenerator,并且在它们之间加一个逗号,最后加上右圆括号。
case 'CallExpression':
return (
codeGenerator(node.callee) +
'(' +
node.arguments.map(codeGenerator)
.join(', ') +
')'
);
// 对于 `Identifiers` 我们只是返回 `node` 的 name。
case 'Identifier':
return node.name;
// 对于 `NumberLiterals` 我们只是返回 `node` 的 value
case 'NumberLiteral':
return node.value;
// 如果我们不能识别这个结点,那么抛出一个错误。
default:
throw new TypeError(node.type);
}
}
module.exports = codeGenerator;
const compier = require("./compiler");
let compiler = require('./compiler');
let output = compiler("(add 2 (subtract 4 2))");
console.log(output);
compiler\index.js
const tokenizer = require("./tokenizer");
const parser = require("./parser");
const transformer = require("./transformer");
const codeGenerator = require("./codeGenerator");
function compier(input){
let tokens = tokenizer(input);
let ast = parser(tokens);
let newAst = transformer(ast);
let output = codeGenerator(newAst);
return output;
}
module.exports = compier;
compiler\tokenizer.js
let LETTERS = /[a-z]/i;
let WHITESPACE = /\s/;
let NUMBERS = /[0-9]/;
function tokenizer(input){
//current类似指标,用于记录我们在代码字符串中的位置
let current=0;
//tokens是一个数组,用来放置我们的token
let tokens = [];
//可能会在单个循环中多次增加current
while(current < input.length){
//char 指向当前字符串
let char = input[current];
//先检查是不是一个左圆括号
if(char === '('){
//如果是的话,我们往tokens里push一个type为paren,value为左圆括号的对象
tokens.push({
type:'paren',
value:'('
});
//自增current
current++;
//结束本次循环,进入下一个循环
continue;
//如果token是函数名,函数名是由一系列字母组成 比如 (add 11 22)
}else if(LETTERS.test(char)){
let value = '';
//用内层循环遍历所有的字母,把它们存入value中
while(LETTERS.test(char)){
value+=char;
char = input[++current];
}
//然后添加一个类型为name的token,进入下一个循环
tokens.push({
type:'name',
value
});
continue;
}else if(WHITESPACE.test(char)){
//token并不是有效的token,所以直接进入下一个循环
current++;
continue;
}else if(NUMBERS.test(char)){
let value = '';
//用内层循环遍历所有的数字,把它们存入value中
while(NUMBERS.test(char)){
value+=char;
char = input[++current];
}
//然后添加一个类型为number的token,进入下一个循环
tokens.push({
type:'number',
value
});
continue;
}else if(char === ')'){
tokens.push({
type: 'paren',
value: ')'
});
current++;
continue;
}
//如果没有匹配上任何类型的token,则抛出一个错误
throw new TypeError('I dont know what this character is '+ char);
}
return tokens;
}
module.exports = tokenizer;
compiler\parser.js
/**
* 语法分析器接受 token 数组,然后把它转化为 AST
* [{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] }
*/
//现在我们定义parser函数,接受tokens数组
function parser(tokens) { // (add 11 22) (add 2 (subtract 4 2))
//我们再次声明一个current变量指针
let current = 0;
//但是这次我们使用递归而不是 `while` 循环,所以我们定义一个 `walk` 函数
function walk() {
// walk函数里,我们从当前token开始
let token = tokens[current];
//我们检查是不是 CallExpressions 类型,我们从左圆括号开始
if (token.type === 'paren' && token.value == '(') {
// 我们会自增 `current` 来跳过这个括号,因为括号在 AST 中是不重要的
token = tokens[++current];
//我们创建一个类型为 `CallExpression` 的根节点,然后把它的 name 属性设置为当前token 的值
//因为紧跟在左圆括号后面的 token 一定是调用的函数的名字
let node = {
type: 'CallExpression',
name: token.value,
params: []
}
// 我们再次自增 `current` 变量,跳过当前的 token
token = tokens[++current];
//现在我们循环遍历接下来的每一个 token,直到我们遇到右圆括号,这些 token 将会是 `CallExpression` 的 `params`(参数)
//这也是递归开始的地方,我们采用递归的方式来解决问题,而不是去尝试解析一个可能有无限层嵌套的结点
//(add 2 (subtract 4 2))
//所以我们创建一个 `while` 循环,直到遇到类型为 `'paren'`,值为右圆括号的 token
while (token.type != 'paren' || token.type == 'paren' && token.value != ')') {
//我们调用 `walk` 函数,它将会返回一个结点,然后我们把这个节点放入 `node.params` 中
node.params.push(walk());
token = tokens[current];
}
// 我们最后一次增加 `current`,跳过右圆括号
current++;
// 返回结点
return node;
//检查是不是 `number` 类型
}else if(token.type === 'number'){
// 如果是,`current` 自增。
current++;
// 然后我们会返回一个新的 AST 结点 `NumberLiteral`,并且把它的值设为 token 的值。
return {
type: 'NumberLiteral',
value: token.value
};
}
//同样,如果我们遇到了一个类型未知的结点,就抛出一个错误。
throw new TypeError(token.type);
}
//现在,我们创建 AST,根结点是一个类型为 `Program` 的结点
var ast = {
type: 'Program',
body: []
};
//现在我们开始 `walk` 函数,把结点放入 `ast.body` 中
//之所以在一个循环中处理,是因为我们的程序可能在 `CallExpressions` 后面包含连续的两个参数,而不是嵌套的
//(add 2 2) (subtract 4 2)
while (current < tokens.length) {
ast.body.push(walk());
}
// 最后我们的语法分析器返回 AST
return ast;
}
module.exports = parser;
let traverser = require('./traverser');
function transformer(ast) {
// 创建 `newAST`,它与我们之前的 AST 类似,有一个类型为 Program 的根节点。
var newAst = {
type: 'Program',
body: []
};//老的ast有一个属性_context指向新的ast的body
ast._context = newAst.body;
// 我们把 AST 和 visitor 函数传入遍历器
traverser(ast,{
NumberLiteral(node,parent){
// 我们创建一个新结点,名字叫 `NumberLiteral`,并把它放入父结点的 context 中。
parent._context.push({
type:'NumberLiteral',
value:node.value
});
},
CallExpression(node,parent){
//我们创建一个 `CallExpression` 结点,里面有一个嵌套的 `Identifier`
var expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.name
},
arguments: []
};
// 下面我们在原来的 `CallExpression` 结点上定义一个新的 context,它是 expression
// 中 arguments 这个数组的引用,我们可以向其中放入参数。
node._context = expression.arguments;
// 最后我们把 `CallExpression`放入父结点的 context 中。
parent._context.push(expression);
}
});
// 最后返回创建好的新 AST
return newAst;
}
module.exports = transformer;
function codeGenerator(node) {
// 对于不同 `type` 的结点分开处理。
switch (node.type) {
// 如果是 `Program` 结点,那么我们会遍历它的 `body` 属性中的每一个结点,并且递归地
// 对这些结点再次调用 codeGenerator,再把结果打印进入新的一行中。
case 'Program':
return node.body.map(codeGenerator)
.join('\n');
// 对于 `CallExpressions`,我们会打印出 `callee`,接着是一个左圆括号,然后对
// arguments 递归调用 codeGenerator,并且在它们之间加一个逗号,最后加上右圆括号。
case 'CallExpression':
return (
codeGenerator(node.callee) +
'(' +
node.arguments.map(codeGenerator)
.join(', ') +
')'
);
// 对于 `Identifiers` 我们只是返回 `node` 的 name。
case 'Identifier':
return node.name;
// 对于 `NumberLiterals` 我们只是返回 `node` 的 value
case 'NumberLiteral':
return node.value;
// 如果我们不能识别这个结点,那么抛出一个错误。
default:
throw new TypeError(node.type);
}
}
module.exports = codeGenerator;
// 所以我们定义一个遍历器,它有两个参数,AST 和 vistor。在它的里面我们又定义了两个函数...
function traverser(ast, visitor) {
// `traverseArray` 函数允许我们对数组中的每一个元素调用 `traverseNode` 函数。
function traverseArray(array, parent) {
array.forEach(function(child) {
traverseNode(child, parent);
});
}
// `traverseNode` 函数接受一个 `node` 和它的父结点 `parent` 作为参数,这个结点会被
// 传入到 visitor 中相应的处理函数那里。
function traverseNode(node,parent){
// 首先我们看看 visitor 中有没有对应 `type` 的处理函数。
var method = visitor[node.type];
// 如果有,那么我们把 `node` 和 `parent` 都传入其中。
if (method) {
method(node, parent);
}
// 下面我们对每一个不同类型的结点分开处理。
switch (node.type) {
//我们从顶层的 `Program` 开始,Program 结点中有一个 body 属性,它是一个由若干个结点组成的数组,所以我们对这个数组调用 `traverseArray`
//记住 `traverseArray` 会调用 `traverseNode`,所以我们会递归地遍历这棵树。
case 'Program':
traverseArray(node.body, node);
break;
//下面我们对 `CallExpressions` 做同样的事情,遍历它的 `params`。
case 'CallExpression':
traverseArray(node.params, node);
break;
// 如果是 `NumberLiterals`,那么就没有任何子结点了,所以我们直接 break
case 'NumberLiteral':
break;
// 同样,如果我们不能识别当前的结点,那么就抛出一个错误。
default:
throw new TypeError(node.type);
}
}
// 最后我们对 AST 调用 `traverseNode`,开始遍历。注意 AST 并没有父结点。
traverseNode(ast, null);
}
module.exports = traverser;
let LETTERS = /[a-z]/i;
let WHITESPACE = /\s/;
let NUMBERS = /[0-9]/;
let currentToken;
function start(char){
if(char === '('){
emit({ type: 'paren', value: '('});
return foundParen;
}else{
return start;
}
}
function foundParen(char){
if(LETTERS.test(char)){
currentToken = {
type:'name',
value:''
}
return name(char);
}
throw new TypeError('函数名必须是字符 '+ char);
}
function name(char){
if(char.match(/^[a-zA-Z]$/)){
currentToken.value += char;
return name;
}else if(char == " "){
emit(currentToken);
currentToken = {
type:'number',
value:''
}
return number;
}
throw new TypeError('函数名必须以空格结束 '+ char);
}
function number(char){
if(NUMBERS.test(char)){
currentToken.value += char;
return number;
}else if(char == " "){
emit(currentToken);
currentToken = {
type:'number',
value:''
}
return number;
}else if(char == ")"){
emit(currentToken);
emit({ type: 'paren', value: ')'});
return start;
}
throw new TypeError('参数必须是数字 '+ char);
}
function tokenizer(input){
let state = start;
for(let char of input){
state = state(char);
}
}
function emit(token){
console.log(token);
}
tokenizer('(add 45 23)');
let RegExpObject = /([0-9]+)|([ ])|(\+)|(\-)|(\*)|(\/)|([\(])|([\)])/g;
let names = ["Number","Space","+","-","*","/","(",")"];
function* tokenize(source){
let result = null;
while(true){
result = RegExpObject.exec(source);
if(!result) break;
let token = {type:null,value:null};
let index = result.find((item,index)=>index>0&&!!item);
token.type = names[index];
token.value = (result[0]);
yield token;
}
}
let tokens = [];
for(let token of tokenize("33+44-55*66*(77+55)")){
tokens.push(token);
}
console.log(tokens);