javascript编写一个简单的编译器(理解抽象语法树AST)
编译器 是一种接收一段代码，然后把它转成一些其他一种机制。
我们现在来做一个在一张纸上画出一条线，那么我们画出一条线需要定义的条件如下：
使用 Paper定义纸的颜色，Pen定义笔的颜色，Line指画出一条线，100指在颜色参数中代表100%的黑色 或 css中的rgb(0%,0%,0%). 那么生成的线使用灰色来表示，那么就是 50了，纸的面积是 100*100， 线条的宽度是1，线段的起点和终点是相对于左下角的x,y坐标来定义。
Paper 0 (含义是: 定义纸的颜色是白色)
Pen 100 (含义是: 定义笔的颜色是黑色)
Line 0 50 100 50 (含义是：x轴0到100，说明是横向从起点到终点，y轴是50到50，说明是一张纸的中点是一条直线)。
那么编译器是如何工作的？
编译器一般会经过如下几个步骤：
1. 词法分析
2. 语法分析
3. 转换
4. 代码生成
1-1 词法分析(也可以叫做标记)
词法分析将每个关键字(也可以叫标记)使用空格分开. 比如：
Paper 0
Pen 100
Line 0 50 100 50
如上，我们可以把 Paper， Pen，Line 的类型统一可以叫 word, 值就是各个单词了 那么 后面的数字类型我们可以统一叫 number；
比如我们输入 "Paper 0", 那么我们输出的话就变成如下：
[
{type: "word", value: "Paper"},
{type: "number", value: "100"}
]
代码如下：
function lexical (code) {
return code.split(/\s+/)
.filter(function(t) {
return t.length > 0
}).map(function(t) {
console.log(t);
return isNaN(t) ? {type: 'word', value: t} : {type: 'number', value: t}
});
}
var res = lexical("Paper 0");
console.log(res); // [{type: "word", value: "Paper"}, {type: "number", value: '100'}]
1-2 语法分析
语法分析是遍历每个标记，寻找语法信息，并且构建一个叫做AST(抽象语法树)的对象。
下面我们对上面词法分析生成的标记 [{type: "word", value: "Paper"}, {type: "number", value: '100'}] 这样的数据，使用语法分析
构建一个AST(抽象语法树)的对象。代码如下：
function parser(tokens) {
var AST = {
type: 'Drawing',
body: []
};
// 循环依次取出第一个元素，然后删除第一个元素
while (tokens.length > 0) {
var currentItem = tokens.shift();
// 判断类型，如果是单词的话，我们就分析它的语法
if (currentItem.type === 'word') {
switch(currentItem.value) {
case 'Paper' :
var expression = {
type: 'CallExpression',
name: 'Paper',
arguments: []
};
// 继续数组中字段的类型
var nextItem = tokens.shift();
if (nextItem.type === 'number') {
// 在expression对象内部加入参数信息
expression.arguments.push({
type: 'NumberLiteral',
value: nextItem.value
})
// 将expression对象放入我们的AST的body内
AST.body.push(expression);
} else {
throw 'Paper command must be followed by a number.'
}
break;
case 'Pen' :
/* 更多代码 */
break;
case 'Line':
/* 更多代码 */
break;
}
}
}
return AST;
}
var data = [
{ type: 'word', value: 'Paper'},
{ type: 'number', value: 100}
];
var output = parser(data);
console.log(output);
// 打印信息如下
/*
var output = {
'type': 'Drawing',
'body': [{
"type": "CallExpression",
"name": "Paper",
"arguments": [{
"type": "NumberLiteral",
"value": "100"
}]
}]
}
*/
1-3 转换器函数
我们在语法分析上面通过词法分析生成的对象后，在语法分析创建了一个AST(抽象语法树)结构，但是上面的AST结构对我们创建SVG文件没有什么用处，
在SVG中，我们可以使用元素(element)来表示一个Paper。那么转换器函数将AST转换成另一种对SVG友好的AST。代码如下：
function transformer(ast) {
var svg_ast = {
tag: 'svg',
attr: {
width: 100,
height: 100,
viewBox: '0 0 100 100',
xmlns: 'http://www.w3.org/2000/svg',
version: '1.1'
},
body: []
};
// 循环调用ast表达式
while (ast.body.length > 0) {
// 依次取出数组的第一个元素，然后在数组中删除该元素
var node = ast.body.shift();
switch (node.name) {
case 'Paper' :
var paper_color = 100 - node.arguments[0].value;
// 在svg_ast的body内加入rect元素信息
svg_ast.body.push({
tag: 'rest',
attr: {
x: 0,
y: 0,
width: 100,
height: 100,
fill: 'rgb(' + paper_color + '%,' + paper_color + '%,' + paper_color + '%)'
}
})
break;
case 'Pen' :
var pen_color = 100 - node.arguments[0].value;
/* 很多代码 */
break;
case 'Line' :
/* 很多代码 */
break;
}
}
return svg_ast;
}
var inputElem = {
'type': 'Drawing',
'body': [{
"type": "CallExpression",
"name": "Paper",
"arguments": [{
"type": "NumberLiteral",
"value": "100"
}]
}]
};
var output = transformer(inputElem);
console.log(output);
/*
打印信息如下：
var output = {
"tag": "svg",
"attr": {
"width": 100,
"height": 100,
"viewBox": "0 0 100 100",
"xmlns": "http://www.w3.org/2000/svg",
"version": "1.1"
},
"body": [{
"tag": "rect",
"attr": {
"x": 0,
"y": 0,
"width": 100,
"height": 100,
"fill": "rgb(0%, 0%, 0%)"
}
}]
}
*/
1-4 生成器函数
作为编译器的最后一步，生成器函数基于上一步产生的新AST来生成SVG代码。
代码如下：
function generator(svg_ast) {
/*
从attr 对象中创建属性字符串
{"width": 100, "height": 100} => 'width="100" height="100"'
*/
function createAttrString(attr) {
return Object.keys(attr).map(function(key) {
return key + '="'+attr[key]+'"'
}).join(' ');
}
// 为svg标签创建属性字符串
var svg_attr = createAttrString(svg_ast.attr);
// width="100" height="100" viewBox="0 0 100 100" xmlns="http://www.w3.org/2000/svg" version="1.1"
// console.log(svg_attr);
// 为每个 svg_ast body中的元素，生成svg标签
var elements = svg_ast.body.map(function(node) {
return '<' + node.tag + ' ' + createAttrString(node.attr) + '></' + node.tag + '>'
}).join('\n\t');
// 使用开和关的svg标签包装来完成svg代码
return '<svg '+ svg_attr +'>\n' + elements + '\n</svg>'
}
var svg_ast = {
"tag": "svg",
"attr": {
"width": 100,
"height": 100,
"viewBox": "0 0 100 100",
"xmlns": "http://www.w3.org/2000/svg",
"version": "1.1"
},
"body": [{
"tag": "rect",
"attr": {
"x": 0,
"y": 0,
"width": 100,
"height": 100,
"fill": "rgb(0%, 0%, 0%)"
}
}]
}
var g = generator(svg_ast);
console.log(g);
/*
打印输出如下：
<svg width="100" height="100" viewBox="0 0 100 100" xmlns="http://www.w3.org/2000/svg" version="1.1">
<rect x="0" y="0" width="100" height="100" fill="rgb(0%, 0%, 0%)"></rect>
</svg>
*/
1-5 把上面的 lexical.js , grammar.js, converter.js 和 generator.js 组装在一起，来作为一个编译器。
我们把这个编译器取个名字叫 svgCompile 编译器吧，我们逐步理解了编译器的步骤，先是创建 词法分析器，然后创建 语法分析器，接着是 转换器，最后就是生成器方法，现在我们需要添加一个 compile（编译）方法来链式调用这四个方法。
function svgCompile(code) {
return generator(transformer(parser(lexical(code))));
}
下面是compile.html代码如下：
<!DOCTYPE html>
<html>
<head>
<title></title>
<script src="./js/lexical.js"></script>
<script src="./js/parser.js"></script>
<script src="./js/transformer.js"></script>
<script src="./js/generator.js"></script>
<script src="./js/compile.js"></script>
</head>
<body>
<script>
// 调用svgCompile编译器
var code = 'Paper 0 Pen 100 Line 0 50 100 50';
var svg = svgCompile(code);
console.log(svg);
document.body.innerHTML = svg;
/*
打印信息如下：
<svg width="100" height="100" viewBox="0 0 100 100" xmlns="http://www.w3.org/2000/svg" version="1.1">
<rest x="0" y="0" width="100" height="100" fill="rgb(100%,100%,100%)"></rest>
<line x1="0" y1="50" x2="100" y2="50" stroke-linecap="round" stroke="rgb(0%,0%,0%)"></line>
</svg>
*/
</script>
</body>
</html>
下面就是实现使用svg 画一条线的demo.
Tips: 通过网上的资料学习的，关键是想先来理解如何编写一个简单的编译器，及简单的理解AST(抽象语法树)