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'}]

打开控制台查看demo输出

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"

      }]

   }]

 }

*/

打开控制台查看demo输出

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.

查看效果：

git上的代码

Tips: 通过网上的资料学习的，关键是想先来理解如何编写一个简单的编译器，及简单的理解AST(抽象语法树)

巴特西

javascript编写一个简单的编译器(理解抽象语法树AST)

最新文章

热门文章