LawrencePeng's Blog

专注收集代码小精灵

DP your Parser

Packrat Parsing

前言

最近看Scala的Parser Generator库的实现，发现其支持记忆化的回溯解析，因为以前没有了解过这方面的知识，所以我就找到了其算法：Packrat Parsing好好研究了下。

What

Packrat Parsing是实现线性时间复杂度的回溯解析算法。

Why

很多递归下降时的算法有两种实现：

  1. 回溯法， 理论能力更强，但是最差时间复杂度为指数级别。
  2. 预测分析，通过peek等偷看后面的token，能达到线性的复杂度。

Packrat让回溯解析也能做到线性时间复杂度了。

How

记忆化是动态规划算法的本质，因为CFG属于无状态的解析过程，所以完全可以使用记忆化的策略来进行保存中间的计算结果。

1
2
3
4
5
6
7
8
var dv = {
'Additive':  ExprAdditive(dv),
'Multitive': ExprMultitive(dv),
'Primary':   ExprPrimary(dv),
'Number':    ExprNumber(dv),
'Char':      next_dv,
'str':       str,
};

定义一个类似链表的结构，每个结构结点为类似dv的结构，每个key为当前字符串位置进行解析的非终止符，不难想到，对于一个长度为m的字符串，假定有n个非终止符，最多有O(mn)个状态，所以能够达到O(n)的时间复杂度。

Packrat对回溯解析本身并没有太大的改动，仅仅是增加了记忆化的查询、添加，就成功达到了O(n)。

2*(3 + 4)的解析结果 。

js解析数值表达式的demo

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
function dvAdditive(dv){
if(!('Additive' in dv)){
dv.Additive=ExprAdditive(dv);
}
return dv.Additive;
}
function ExprAdditive(dv){
try{
var mul=dvMultitive(dv);
if(dvChar(mul.dv).value=='+'){
var add=dvAdditive(dvChar(mul.dv).dv);
return {
'value': mul.value+add.value,
'dv': add.dv,
};
} else {
throw {};
}
} catch(e) {
return dvMultitive(dv);
}
}
function dvMultitive(dv){
if(!('Multitive' in dv)){
dv.Multitive=ExprMultitive(dv);
}
return dv.Multitive;
}
function ExprMultitive(dv){
try{
var primary=dvPrimary(dv);
if(dvChar(primary.dv).value=='*'){
var mul=dvMultitive(dvChar(primary.dv).dv);
return {
'value': primary.value*mul.value,
'dv': mul.dv,
};
} else {
throw {};
}
} catch(e) {
return dvPrimary(dv);
}
}
function dvPrimary(dv){
if(!('Primary' in dv)){
dv.Primary=ExprPrimary(dv);
}
return dv.Primary;
}
function ExprPrimary(dv){
try{
if(dvChar(dv).value=='('){
var add=dvAdditive(dvChar(dv).dv);
if(dvChar(add.dv).value==')')
{
return {
'value': add.value,
'dv': dvChar(add.dv).dv,
};
} else {
throw {};
}
} else {
throw {};
}
} catch(e) {
return dvNumber(dv);
}
}
function dvNumber(dv){
if(!('Number' in dv)){
dv.Number=ExprNumber(dv);
}
return dv.Number;
}
function ExprNumber(dv){
var value=0;
while(!isNaN(dvChar(dv).value)){
value=value*10+parseInt(dvChar(dv).value);
dv=dvChar(dv).dv;
}
return {
'value': value,
'dv': dv,
};
}
function dvChar(dv){
if(!('Char' in dv)){
dv.Char={
'value': dv.str[0],
'dv': {
'str': dv.str.slice(1),
},
}
}
return dv.Char;
};
function Expr(str){
return ExprAdditive({
'str': str,
}).value;
}

Ref: https://zhuanlan.zhihu.com/p/25260077

AlgoDPParserScala