hxy的博客

Mia san Mia!

0%

前端与编译原理

发表于 更新于 分类于 Valine：

实习前临时抱佛脚研究下编译原理，其实前端近些年不少重要的新技术其实是跟编译原理关系非常大。React在实现上有两个亮点：JSX、Virtual Dom，其中JSX就跟编译原理息息相关。想要提高自己的层次，未来定会好好补补基础。

1.编译原理基础内容

1.1 编译过程

词法分析 => 语法分析 => 语义分析 （前端）=> 中间代码生成 => 代码优化 => 目标代码生成 （后端）

1.2 词法分析 => Token序列

以乘法计算代码分析为例

1
var answer = 6 * 7;

将用到的词列成表格，分别写出各部分的值和类型

type value
Keyword var
Identifier answer
Punctuator =
Numeric 6
Punctuator *
Numeric 7
Punctuator ;

1.3 语法分析 => AST（抽象语法树）

还是上述乘法计算

1
var answer = 6 * 7;

这次将其展开成为AST抽象语法树

ast

1.4 语法解析器算法

分析形式包括

CSG、CFG

Top-Down Paring、Bottom-Up Parsing

Recursive Descent、Shift Reduce

LL(1)(GCC) 、LR(0)、LALR(1)、SLR(1)

parsing

1.5 JS文法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Literal
    : NULLTOKEN
    | TRUETOKEN
    | FALSETOKEN
    | NUMBER
    | STRING
    | '/'
    | DIVEQUAL
    ;

Property
    : IDENT ':' AssignmentExpr
    | STRING ':' AssignmentExpr
    | NUMBER ':' AssignmentExpr
    | IDENT IDENT '(' ')' OPENBRACE FunctionBody CLOSEBRACE
    | IDENT IDENT '(' FormalParameterList ')' OPENBRACE FunctionBody CLOSEBRACE
    ;

PropertyList
    : Property
    | PropertyList ',' Property
    ;

1.6 其他待补充内容

语义检查

  1. 变量是否声明
  2. 变量类型
  3. 类是否重定义
  4. 类里面的方法是否重定义
  5. 标识符里是否使用了保留字
  6. …

中间代码生成

代码优化

目标代码生成

前端到底跟编译原理有哪些关系？

2.模板引擎：Jade

受Haml的影响以JavaScript实现用于node的高性能模板引擎

1
2
3
4
5
6
7
8
h1 Jade - node template engine
#container.col
    p.
        Jade is a terse and simple
        templating language with a
        strong focus on performance
        and powerful features.

html文件

1
2
3
4
5
6
7
8
9
<h1>Jade - node template engine</h1>
<div id="container" class="col">
    <p>
        Jade is a terse and simple
        templating language with a
        strong focus on performance
        and powerful features.
    </p>
</div>

2.1 词法分析：字符扫描器

2.2 语法分析：Recursive Descent

jade-ast

建立类似于DOM树的AST，结点上附带相关信息，如属性，名称等

2.3 代码生成

遍历上文中生成的AST树，生成JS代码。传入运行时环境，执行生成的函数，得到最终的模板输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function (locals, jade)
{
    var buf = [];
    var jade_mixins = {};
    var jade_interp;

    jade_debug.unshift(new jade.DebugItem(0, "jade.jade"));
    jade_debug.unshift(new jade.DebugItem(1, "jade.jade"));
    buf.push("<h1>");
    jade_debug.unshift(new jade.DebugItem(undefined, jade_debug[0].filename));
    jade_debug.unshift(new jade.DebugItem(1, jade_debug[0].filename));
    buf.push("Jade - node template engine");
    jade_debug.shift();
    jade_debug.shift();
    buf.push("</h1>");
    ...
    buf.push("</div>");
    jade_debug.shift();
    jade_debug.shift();

    return buf.join("");
}

3.代码验证：JSHint

Javascript代码验证工具，可以检查你的代码并提供相关的代码改进意见

1
2
3
4
5
6
7
8
function add(a, b)
{
    var b = b || 0;

    return a + b;
}

add(5, 7);

jshint.js: line 3, col 9, ‘b’ is already defined.

词法分析：字符扫描器

语法分析：Top Down Operator Precedence

3.1 JSHint AST

jshint-ast

自顶向下，解析时检查代码错误

4.代码压缩：UglifyJS

使用JavaScript编写的JavaScript代码压缩器

  1. 解析器，通过JavaScript代码产生AST(parse-js)
  2. 代码生成器，通过AST生成JavaScript代码
  3. 压缩器，通过转换器对AST进行优化
  4. 变量名压缩器，将变量名转换为单个字母
  5. 作用域分析器，在AST上提供变量作用域相关信息
  6. 树遍历器，对AST的节点进行遍历操作
  7. 树转换器，对AST的树型结构进行转换
1
2
3
4
5
function sum(first, second)
{
    return first + second;
}
function sum(e,t){return e+t};

Input - Tokenize => Tokens - Parse => AST - Mangle => AST - Squeeze => AST（移除多余代码块、变量声明合并、改变语句写法）- Generate => Result

uglifyjs-ast

5.CSS预处理

5.1 以Less.js为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@base: #f938ab;
.box-shadow(@style, @c) when (iscolor(@c)) {
  -webkit-box-shadow: @style @c;
  box-shadow: @style @c;
}
.box-shadow(@style, @alpha: 50%) when (isnumber(@alpha)) {
  .box-shadow(@style, rgba(0, 0, 0, @alpha));
}
.box {
  color: saturate(@base, 5%);
  border-color: lighten(@base, 30%);
  div { .box-shadow(0 0 5px, 30%) }
}
/* 编译结果 */
.box {
  color: #fe33ac;
  border-color: #fdcdea;
}
.box div {
  -webkit-box-shadow: 0 0 5px rgba(0, 0, 0, 0.3);
  box-shadow: 0 0 5px rgba(0, 0, 0, 0.3);
}

5.2 编译过程

Input - parser => AST （注：Lexer被包含在Parser中）

Ruleset -> Rule -> Value -> Expression -> Entity

1
2
3
4
5
6
7
8
9
10
11
12
.class {
    color: #fff;
    border: 1px solid #000;
    width: @w + 4px;
    > .child {...}
}
/* 对应的AST树 */
Ruleset (Selector '.class', [    Rule ("color", Value ([Expression [Color #fff]]))
    Rule ("border", Value ([Expression [Dimension 1px][Keyword "solid"][Color #000]]))
    Rule ("width", Value ([Expression [Operation " + " [Variable "@w"][Dimension 4px]]]))
    Ruleset (Selector [Element '>', '.child'], [...])
])

之后程序遍历AST，根据AST的内容同时进行函数注册，表达式求值等操作，生成新的AST，再根据新的AST树生成最终的CSS代码

6.转译语言：CoffeeScript

CoffeeScript是一套JavaScript的转译语言，会将类似 Ruby 语法的代码编译成 JavaScript，而且大部分结构都相似，但不同的是 CoffeeScript 拥有更严格的语法

1
2
3
4
5
6
7
8
9
10
11
square = (x) -> x * x
cube = (x) -> square(x) * x
var cube, square;

square = function(x) {
    return x * x;
};

cube = function(x) {
    return square(x) * x;
};

6.1 不同之处

Lexer相比前文介绍的工具，加入了少量正则表达式；

Parser使用语法解析器自动生成工具Jsion（bison的Javascript版）

CoffeeScript文法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Root: [
    o '',
    o 'Body'
]
Body: [
    o 'Line',
    o 'Body TERMINATOR Line',
    o 'Body TERMINATOR'
]
Line: [
    o 'Expression'
    o 'Statement'
]
Statement: [
    o 'Return'
    o 'Comment'
    o 'STATEMENT'
]
...

7.混写语言：React JSX

JSX语法，像是在Javascript代码里直接写XML的语法，实质上这只是一个语法糖，每一个XML标签都会被JSX转换工具转换成纯Javascript代码

1
2
3
4
5
6
7
8
9
10
11
12
var HelloMessage = React.createClass({
    render: function() {
        return <div>Hello {this.props.name}</div>;
    }
});
React.render(<HelloMessage name="John" />, mountNode);
var HelloMessage = React.createClass({displayName: "HelloMessage",
    render: function() {
        return React.createElement("div", null, "Hello ", this.props.name);
    }
});
React.render(React.createElement(HelloMessage, {name: "John"}), mountNode);

使用开源JavaScript语法解析器esprima，在源码中加入JSX相关的解析代码

使用修改后的JavaScript语法解析器来生成AST，再遍历AST结点生成最终转换后的Js代码

1
2
3
4
5
6
<X> </X> => React.createElement(X, null)
<X prop="1" /> => React.createElement(X, {prop: '1'}, null)
<X prop="2"><Y /></X> => React.createElement(X, {prop:'2'},
    React.createElement(Y, null)
)
<div /> => React.createElement("div", null)

其它应用方向

  1. 游戏引擎脚本语言
  2. Markdown转换
  3. …

拓展

  1. V8 Lexer、Parser
  2. Rhino Lexer、Parser
-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道