前端搞编译——AST在前端的应用

前端搞编译-AST在PRO中的运用

AST(Abstract Syntax Tree, 抽象语法树),以树状形式表现编程语言的语法结构。

编译器

代码是写给人看的,顺便能给计算机执行。

在程序可以被计算机执行之前,需要先被翻译成计算机可以执行的形式。负责这项工作的软件系统被称为编译器。一个编译器就是一个程序,它可以阅读某一种语言编写的程序,并把该程序翻译成一个等价的、用另一个语言编写的程序。例如Babel。编译器的重要任务之一是报告它在翻译过程中发现的源程序中的错误。例如ESLint

image-20210810064538026

解释器

并不通过翻译的形式生成目标程序,直接使用用户的输入去执行指定的操作。(使用解释器的常见的编程语言有Python、JavaScript等)

image-20210810070514469

编译器的结构

  1. 词法分析

    词法分析器读入源程序的字符流,并且将它们组成有意义的词素序列,对于每个词素,词法分析器会生成词法单元作为输出。这一步也叫做分词。

  2. 语法分析

    语法分析器使用词法分析器生成的词法单元创建树形的中间表示(AST)。

  3. 语义分析

    使用语法树和符号表(用来记录源程序中使用的变量的名字)中的信息来检查源程序是否和语言定义的语义一致。它同时收集类型信息,存放在语法树或符号表中,以便在随后的中间代码生成过程中使用。

  4. 中间代码生成

    在语义分析之后,一些编译器会生成一个类机器语言的中间表示,该中间表示易于生成且能被轻松翻译成目标语言。

  5. 代码优化

    机器无关的代码优化步骤试图优化中间代码,以便生成更好的目标代码。

  6. 代码生成

    以源程序的中间表示形式作为输入,并把它映射到目标语言。

    image-20210810072810249

语法分析器(Parser)

  • 自顶向下

    构造过程从根节点开始,逐步向叶子节点推进。(简单高效)

  • 自底向上

    构造过程从叶子节点开始,逐步构造出根节点。(复杂)

AST在公式业务中的运用

所谓公式,其实就是一个个的JS函数。使用公式,在系统内部就是发起一次函数调用。具体参见这里

对于这种实现,我们很容易就能构造出以下字符串去执行任意代码:

1
''['sub']['constructor']('alert("这是一条警告:可以执行任意的js")')()
案例一:使用AST校验用户输入是否合法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
const types = {
CallExpression: 'CallExpression', // 函数调用表达式
BinaryExpression: 'BinaryExpression', // 条件表达式
Identifier: 'Identifier', // 标识符
Literal: 'Literal', // 字面量
Brackets: 'Brackets'
}
const rules = {
IF: ({ params }) => params.length === 3 && params[0].type === types.BinaryExpression && ['>', '<', '>=', '<=', '!=', '=='].includes(params[0].operator),
ADD: ({ params }) => params.length >= 2 && params.every(p => Object.keys(types).includes(p.type)),
SUBTRACT: ({ params }) => params.length >= 2 && params.every(p => Object.keys(types).includes(p.type)),
MULTIPLY: ({ params }) => params.length >= 2 && params.every(p => Object.keys(types).includes(p.type)),
DIVIDE: ({ params }) => params.length >= 2 && params.every(p => Object.keys(types).includes(p.type)),
SUM: ({ params }) => params.length >= 1 && params.every(p => Object.keys(types).includes(p.type)),
AVERAGE: ({ params }) => params.length >= 1 && params.every(p => Object.keys(types).includes(p.type)),
MAX: ({ params }) => params.length >= 1 && params.every(p => Object.keys(types).includes(p.type)),
MIN: ({ params }) => params.length >= 1 && params.every(p => Object.keys(types).includes(p.type)),
DATE_DIFF: ({ params }) => [2, 3].includes(params.length) && params.every(p => [types.Identifier, types.Literal].includes(p.type))
}

class Parser {
constructor(str) {
this.EOF = Symbol('EOF')
this.str = str
this.node = null
this.funcs = []
this.AST = {}
this.tempStr = ''
this.expression = null
}
getLastFunc() {
return this.funcs[this.funcs.length - 1]
}
start(s) {
if (/[A-Z_]/.test(s)) {
this.tempStr += s
return this.findLetter
}
return this.start
}
findLetter(s) {
if (/[A-Z_]/.test(s)) {
this.tempStr += s
return this.findLetter
} else if (s === '(') {
if (!rules[this.tempStr]) {
return this.EOF
}
this.funcs.push({
type: types.CallExpression,
name: this.tempStr,
params: []
})
this.tempStr = ''
return this.findFunc
}
}
findFunc(s) {
if (s === '{') {
this.node = {
type: types.Identifier,
name: ''
}
return this.findVar
} else if (s === ',') {
if (this.expression) {
this.expression.right = this.node
this.getLastFunc().params.push(this.expression)
this.expression = null
} else {
if (this.node) this.getLastFunc().params.push(this.node)
}
this.node = null
return this.findFunc
} else if (/[A-Z]/.test(s)) {
this.tempStr += s
return this.findLetter
} else if (s === '(') {
this.funcs.push({
type: types.Brackets,
name: null,
params: []
})
return this.findFunc
} else if (s === ')') {
if (this.node) {
this.getLastFunc().params.push(this.node)
this.node = null
}
const func = this.funcs.pop()
this.node = func
this.AST = func
return this.findFunc
} else {
if (/[a-zA-Z0-9_.]/.test(s)) {
if (!this.node) {
this.node = {
type: types.Literal,
name: ''
}
}
this.node.name += s
} else {
if (this.expression && !this.expression.right) {
this.expression.operator += s
} else {
this.expression = {
type: types.BinaryExpression,
left: this.getLastFunc().params.pop(),
operator: s,
right: ''
}
this.node = null
}
}
return this.findFunc
}
}
findVar(s) {
if (s === '}') {
this.getLastFunc().params.push(this.node)
this.node = null
return this.findFunc
}
this.node.name += s
return this.findVar
}
check() {
let state = this.start
for (let s of this.str) {
state = state.call(this, s)
if (state === this.EOF) return false
}
const BFS = tree => {
const queue = [tree]
while (queue.length) {
let n = queue.length
for (let i = 0; i < n; i++) {
const node = queue.pop()
if (node.type === types.CallExpression && rules[node.name] && !rules[node.name](node)) return false
if (node.type === types.Brackets && node.params.length > 1) return false
if (node.params) for (const p of node.params) queue.push(p)
}
}
return true
}
return BFS(this.AST)
}
}

const test = new Parser('ADD({4105.num_61},(({4105.num_61},23)))')
console.log(test.check(), 'test.check()')
案例二:使用AST实现公式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
const types = {
CallExpression: 'CallExpression', // 函数调用表达式
BinaryExpression: 'BinaryExpression', // 条件表达式
Identifier: 'Identifier', // 标识符
Literal: 'Literal', // 字面量
Brackets: 'Brackets'
}
const rules = {
IF: ({ params }) => params.length === 3 && params[0].type === types.BinaryExpression && ['>', '<', '>=', '<=', '!=', '=='].includes(params[0].operator),
ADD: ({ params }) => params.length >= 2 && params.every(p => Object.keys(types).includes(p.type)),
SUBTRACT: ({ params }) => params.length >= 2 && params.every(p => Object.keys(types).includes(p.type)),
MULTIPLY: ({ params }) => params.length >= 2 && params.every(p => Object.keys(types).includes(p.type)),
DIVIDE: ({ params }) => params.length >= 2 && params.every(p => Object.keys(types).includes(p.type)),
SUM: ({ params }) => params.length >= 1 && params.every(p => Object.keys(types).includes(p.type)),
AVERAGE: ({ params }) => params.length >= 1 && params.every(p => Object.keys(types).includes(p.type)),
MAX: ({ params }) => params.length >= 1 && params.every(p => Object.keys(types).includes(p.type)),
MIN: ({ params }) => params.length >= 1 && params.every(p => Object.keys(types).includes(p.type)),
DATE_DIFF: ({ params }) => [2, 3].includes(params.length) && params.every(p => [types.Identifier, types.Literal].includes(p.type))
}

const Calculator = {
ADD: (...args) => args.reduce((a, b) => +a + +b)
}
const varNames = {
'4105.num_61': 1
}


class Parser {
constructor(str) {
this.EOF = Symbol('EOF')
this.str = str
this.node = null
this.funcs = []
this.AST = {}
this.tempStr = ''
this.expression = null
}
getLastFunc() {
return this.funcs[this.funcs.length - 1]
}
start(s) {
if (/[A-Z_]/.test(s)) {
this.tempStr += s
return this.findLetter
}
return this.start
}
findLetter(s) {
if (/[A-Z_]/.test(s)) {
this.tempStr += s
return this.findLetter
} else if (s === '(') {
if (!rules[this.tempStr]) {
return this.EOF
}
this.funcs.push({
type: types.CallExpression,
name: this.tempStr,
params: []
})
this.tempStr = ''
return this.findFunc
}
}
findFunc(s) {
if (s === '{') {
this.node = {
type: types.Identifier,
name: ''
}
return this.findVar
} else if (s === ',') {
if (this.expression) {
this.expression.right = this.node
this.getLastFunc().params.push(this.expression)
this.expression = null
} else {
if (this.node) this.getLastFunc().params.push(this.node)
}
this.node = null
return this.findFunc
} else if (/[A-Z]/.test(s)) {
this.tempStr += s
return this.findLetter
} else if (s === '(') {
this.funcs.push({
type: types.Brackets,
name: null,
params: []
})
return this.findFunc
} else if (s === ')') {
if (this.node) {
this.getLastFunc().params.push(this.node)
this.node = null
}
const func = this.funcs.pop()
this.node = func
this.AST = func
return this.findFunc
} else {
if (/[a-zA-Z0-9_.]/.test(s)) {
if (!this.node) {
this.node = {
type: types.Literal,
name: ''
}
}
this.node.name += s
} else {
if (this.expression && !this.expression.right) {
this.expression.operator += s
} else {
this.expression = {
type: types.BinaryExpression,
left: this.getLastFunc().params.pop(),
operator: s,
right: ''
}
this.node = null
}
}
return this.findFunc
}
}
findVar(s) {
if (s === '}') {
this.getLastFunc().params.push(this.node)
this.node = null
return this.findFunc
}
this.node.name += s
return this.findVar
}
run() {
let state = this.start
for (let s of this.str) {
state = state.call(this, s)
if (state === this.EOF) return false
}
const callStack = [];
const pushCallStack = tree => {
const { name, type, params } = tree;
if ([types.CallExpression, types.Brackets].includes(type)) {
if (type === types.CallExpression) callStack.push({ name, type })
for (const arg of params) {
if (arg.type === types.CallExpression || arg.type === types.Brackets) {
pushCallStack(arg)
} else {
callStack.push(arg)
}
}
}
}
pushCallStack(this.AST)
let args = [];
while (callStack.length) {
const current = callStack.pop();
if (current.type === types.Literal) {
args.unshift(current.name)
} else if (current.type === types.Identifier) {
args.unshift(varNames[current.name])
} else if (current.type === types.CallExpression) {
const res = Calculator[current.name](...args);
args = [];
callStack.push({
type: types.Literal,
name: res
})
}
if (callStack.length === 1 && callStack[0].type === types.Literal) return callStack.pop().name
}
}
}



const test = new Parser('ADD({4105.num_61},(ADD({4105.num_61},23)))')
console.log(test.run(), 'test.run()')
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2019-2021 musi

请我喝杯咖啡吧~

支付宝
微信