1

1. 背景

在上一篇自己实现一个简陋的webpack中，我们用到了esprima来parse js代码。具体我大学非cs科班，parser相关的没有啥概念，总之parser估计就是把某种格式的代码转化成另外一种表达吧，esprima在parse的时候，接受js字符串，然后根据js的语法定义进行分析，得到了一个js 程序的内部表达。在esprima的官网可以看到这样的例子:

输入:

var answer = 6 * 7;

没看parse结果之前个人的理解是分两部分:

变量声明 var answer
表达式 6 * 7

实际的结果是:

{
    "type": "Program",
    "body": [
        {
            "type": "VariableDeclaration",
            "declarations": [
                {
	                "type": "VariableDeclarator",
	                "id": {
	                    "type": "Identifier",
	                    "name": "answer"
	                },
	                "init": {
	                    "type": "BinaryExpression",
	                    "operator": "*",
	                    "left": {
	                        "type": "Literal",
	                        "value": 6,
	                        "raw": "6"
	                    },
	                    "right": {
	                        "type": "Literal",
	                        "value": 7,
	                        "raw": "7"
	                    }
	                }
                }
            ],
            "kind": "var"
        }
    ],
    "sourceType": "script"
}

也就是说得到了一个VariableDeclaration，这个声明的init初始化是一个BinaryExpression。另外可以看到Identifier是answer，kind是 var , 直观印象是，非常细碎。如果要写一个js的parser的话，需要清楚定义js的各个语法， oh my god

2. parser可以干嘛

像上篇文章进行代码分析，根据各个语法做各自的变化得到想要的结果，这就是parser的主要作用吧应该。esprima的官网上提供了一个重写的例子，比如把单引号改为双引号之类的，以及一个minification的例子，minification的话，主要是变量名重写，感觉可以检查var等的使用，然后根据字母顺序进行替换就可以吧？嗯，暂时还没试过。

parser是compiler的一部分。哎呀呀，真是麻烦，总之compiler有以下一些概念
:

lexer - 将代码分解为单词
parser - 单词组合为语句
semantic Analysis - 检查语句的组合是否ok
optimizer - 优化
code generator - 输出code，和输入code意义一样但是有不同表述

上述概念看了，也有点懵，所以webpack属于一个compiler了嗯。为了加深理解，直接看compiler源代码吧（网上找到了一个the super tiny compiler)

3. the super tiny compiler

这个作者在源代码中写了很丰富的comment，强力建议去阅读试试。如果你比较偷懒的，可以看我在这里的学习笔记。

3.1 目标

这个compiler目标是转换LISP风格的语句为c风格的代码（我不会LISP。。。）:

 *                  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))

嘛，看了这个感觉像写个简单的计算器？ compiler可以分三部分 parsing(建立语法树）)，transformation（做需要的变形)，code生成。

3.2 parsing

parsing分两步，第一步是取词(lexical analysis)，将代码分解成一个一个token（像单词那样），然后第二步是语义分析(Syntactic Analysis)，接受第一步的一个个token，然后组合成一个抽象语法输(Abstract Syntax Tree)

比如原来的语句

(add 2 (subtract 4 2))

抽词过后

   [
     { 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',
         }]
       }]
     }]
   }

3.2.1 tokenizer

如何抽词，感觉比较简单，直接一个一个字符读入就行了：

如果是括号，就判定为一个paren
如果是空白，就将连续的空白跳过
如果是数字，将连续的数字判定为一个number
如果遇到了双引号，双引号之内的判定为一个string
剩余的就是方法名了，比如add，这些连续的字符判定为一个name
其他的情况，报错

这个感觉还是很容易实现的，源文件的实现采用了while循环检测的方式，没毛病。不过其中关于连续的检测经常用到，可以单独抽离出来我觉得，后面自己写parser的时候试一试。

3.2.2 parser

上述tokenizer给了我们一堆单词(token)，现在进行语法分析。目标语言非常简单，只有CallExpression:(add a b)这一种形式，复杂的地方在于其可以嵌套，如何处理呢？

首先CallExpression有2三部分:

name: add substract等
params: 两个参数

其中参数可以是数字，或者又一个CallExpression，CallExpression的开始标志就是一个paren+name。源代码使用了一个递归的walk()方法，这个方法返回下一个ast节点。

依次取得下一个token，如果token是数字，则返回一个NumberLiteral

if (token.type === 'number') {
  return {
    type: 'NumberLiteral',
    value: token.value,
  };
}

如果是string，返回一个StringLiteral

if (token.type === 'string') {
  return {
    type: 'StringLiteral',
    value: token.value,
  };
}

如果是起始括号，则创建CallExpression，params则用下一个walk()来补充

if (token.type === 'paren' && token.value === '(') {
	token = tokens[++current];
	let node = {
		type: 'CallExpression',
		name: token.value,
		params: [],
	};

	// 这里tick下一次walk(), 在遇到闭合括号之前，都可以当做params来处理
	while (
		(token.type !== 'paren') ||
		(token.type === 'paren' && token.value !== ')')
	) {
		// we'll call the `walk` function which will return a `node` and we'll
		// push it into our `node.params`.
		node.params.push(walk());
		token = tokens[current];
	}
	return node;
}

其他情况下报错，最后wrap一下，返回一个根结点

let ast = {
	type: 'Program',
	body: [],
};

// 程序可能有多行
while (current < tokens.length) {
	ast.body.push(walk());
}
return ast;

parser部分也比较简单，不过感觉写法上可以更加自然一些，后面再看。

3.3 traversing 遍历

AST是个树形结构，所遍历也用递归好了，最终会形成深度优先。遍历只是一种方式，具体目的的话还是得看遇到了某一个语法需要做什么事情，源代码的travers方法支持传入一个visiter参数，这个visiter可以定义enter, exit两个hook，供节点进入和退出的时候调用。

而hook是为了改变自身，在json的情况下，需要保持一个对父节点的引用，所以hook的参数是(node, parent)。

3.4 变形

有了上述遍历方法，我们可以给代码变形了。代码中的例子是把CallExpression

{
	type: 'CallExpression'
	name: String
	params: Array
}

变为

{
	type: 'CallExpression'
	callee: {
		type: 'Identifier',
		name: String
	}
	params: Array
}

感觉上就是从一棵树，构建出另外一棵树。所以保持两个cursor，复制和替换就好了。源代码看这里。

如果要求值的话？可以看出可以写一个类似于reduce的visiter，把ast转换为一个值。

3.5 代码生成器

这个感觉还是很容易实现的。ast的生成是按照文本先后顺序生成的深度优先。所以深度优先遍历然后根据node不通种类生成字符串就ok，需要注意的是换行的处理。代码

3.6 compiler

最后，wrap成一个compiler

function compiler(input) {
  let tokens = tokenizer(input);
  let ast    = parser(tokens);
  let newAst = transformer(ast);
  let output = codeGenerator(newAst);

  // and simply return the output!
  return output;
}

结束。感觉上还是可以hold住的，compiler的学习可以继续进行下去。

sunderls / blog Goto Github PK

blog's People

Watchers

blog's Issues

1

1. 背景

2. parser可以干嘛

3. the super tiny compiler

3.1 目标

3.2 parsing

3.2.1 tokenizer

3.2.2 parser

3.3 traversing 遍历

3.4 变形

3.5 代码生成器

3.6 compiler

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent