hal*_*leh 0 c# sparse-matrix transitions dfa compiler-optimization
我想第一次编写Compiler,我的参考文献是"编译器原理,技术和工具".对于词法设计,我写了我的语言标记的FA,现在我想从状态转换表编写C#代码,但它是一个40 X 30矩阵,在这个矩阵中只有50个条目!我想压缩这个稀疏矩阵!书中有一种方法说:
有一个更微妙的数据结构允许我们将数组访问的速度与默认的列表压缩相结合.我们可以将这个结构看作四个数组,如图3.66.5所示.基数组用于确定状态s的条目的基本位置,它们位于下一个和检查数组中.如果检查数组告诉我们base [s]给出的那个是无效的,则默认数组用于确定替代基本位置.为了计算nextState(s,a),输入a上状态s的转换,我们检查下一个并检查位置l = base [s] + a中的条目,其中字符a被视为整数,大概在0的范围内如果检查[l] = s,则此条目有效,输入a上状态s的下一个状态为next [l].如果检查[l]!= s,那么我们确定另一个状态t = default [s]并重复该过程,好像t是当前状态.更正式地说,函数nextstate定义如下:
Run Code Online (Sandbox Code Playgroud)int nextState(s, a) { if ( check[base[s] + a] = s ) return next[base[s] + a]; else return nextState(default[s], a); }
我不明白这四个数组是由什么组成的？任何人都能为我解释一下吗？你有另一个简单的算法来优化我的代码进行稀疏压缩吗？我知道CSR压缩但是我不知道如何使用它们在我的C#代码中编写nextState(s,a)!你有什么想法吗？
假设有六个输入符号:字母abcde和EOF.假设我们希望我们的语言包含七个字符串:ace添加坏床蜂房cab(并且每个必须由EOF终止).
存储DFA转换表的最简单方法是作为二维数组simpleNext.一个轴是状态编号,另一个轴是输入符号编号.当FA处于状态s并且看到符号时a,它移动到状态simpleNext[s][a].
这是一个simpleNext识别我们的示例字符串的DFA 的转换表:
st# a b c d e EOF
0 0 0 0 0 0 0
1 2 3 4 5 0 0
2 0 0 16 17 0 0
3 11 0 0 0 12 0
4 9 0 0 0 0 0
5 6 0 0 0 0 0
6 0 0 0 7 0 0
7 0 0 0 0 0 8
8 0 0 0 0 0 0
9 0 10 0 0 0 0
10 0 0 0 0 0 8
11 0 0 0 15 0 0
12 0 0 0 13 14 0
13 0 0 0 0 0 8
14 0 0 0 0 0 8
15 0 0 0 0 0 8
16 0 0 0 0 19 0
17 0 0 0 18 0 0
18 0 0 0 0 0 8
19 0 0 0 0 0 8
状态0是错误状态.如果FA到达此处,则在处于没有从该状态转换的状态时读取某个符号.状态8(唯一的其他全零行)是唯一的接受状态.
这里的问题simpleNext是大小|S| × ||(状态数乘以符号数)= 120.对于真正的DFA(如语言解析器中所见),有更多的状态和符号,它会更大.这些天RAM不是太大,但可能浪费了很多L1缓存行.大多数状态没有大多数符号的转换,因此表的很大一部分设置为0(错误状态).
我们想要一种方法来将转换表存储在更小的空间中,同时仍然允许我们非常快速地访问它.
让我们探讨一下本书中描述的类似但更简单的压缩技术版本.
让我们以不同的方式排列表格的行.从第0行和第1行开始:
0 0 0 0 0 0 0
1 2 3 4 5 0 0
然后将第2行移位直到其非零条目(16和17)上面只有零:
0 0 0 0 0 0 0
1 2 3 4 5 0 0
2 0 0 16 17 0 0
现在将第3行移到其非零条目(11和12)之上只有零:
0 0 0 0 0 0 0
1 2 3 4 5 0 0
2 0 0 16 17 0 0
3 11 0 0 0 12 0
(注意,我们必须假装每行都附加了无限数量的零.)
一个接一个地重复剩余的行.最后你有这个:
0 0 0 0 0 0 0
1 2 3 4 5 0 0
2 0 0 16 17 0 0
3 11 0 0 0 12 0
4 9 0 0 0 0 0
5 6 0 0 0 0 0
6 0 0 0 7 0 0
7 0 0 0 0 0 8
8 0 0 0 0 0 0
9 0 10 0 0 0 0
10 0 0 0 0 0 8
11 0 0 0 15 0 0
12 0 0 0 13 14 0
13 0 0 0 0 0 8
14 0 0 0 0 0 8
15 0 0 0 0 0 8
16 0 0 0 0 19 0
17 0 0 0 18 0 0
18 0 0 0 0 0 8
19 0 0 0 0 0 8
现在记下我们移动每行的数量:
st# off
0 0 0 0 0 0 0 0
1 0 2 3 4 5 0 0
2 2 0 0 16 17 0 0
3 6 11 0 0 0 12 0
4 7 9 0 0 0 0 0
5 8 6 0 0 0 0 0
6 6 0 0 0 7 0 0
7 6 0 0 0 0 0 8
8 0 0 0 0 0 0 0
9 11 0 10 0 0 0 0
10 8 0 0 0 0 0 8
11 11 0 0 0 15 0 0
12 12 0 0 0 13 14 0
13 12 0 0 0 0 0 8
14 13 0 0 0 0 0 8
15 14 0 0 0 0 0 8
16 15 0 0 0 0 19 0
17 16 0 0 0 18 0 0
18 17 0 0 0 0 0 8
19 18 0 0 0 0 0 8
现在将行折叠为一行,用非零覆盖零.将偏移量保持为单独的数组:
index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
nextState 2 3 4 5 16 17 11 9 6 7 12 8 10 8 15 13 14 8 8 8 19 18 8 8
state# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
stateBase 0 0 2 6 7 8 6 6 0 11 8 11 12 12 13 14 15 16 17 18
此时,我们可以使用这两个数组从原始数组中查找任何非零值.对于状态s和符号编号i,如果simpleNext[s][i]为非零,则表示相同的值nextState[stateBase[s] + i].
该方案唯一剩下的问题是我们不知道原始表中的哪些值为零.我们可以修复通过添加另一个阵列,checkState平行于nextState.对于每个元素nextState,相应的元素checkState告诉我们nextState最初复制的状态:
index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
nextState 2 3 4 5 16 17 11 9 6 7 12 8 10 8 15 13 14 8 8 8 19 18 8 8
checkState 1 1 1 1 2 2 3 4 5 6 3 7 9 10 11 12 12 13 14 15 16 17 18 19
现在,对于某些状态s和符号编号i,我们可以看到是否nextState[stateBase[s] + i]属于state s,或者原始表的状态s和符号是否为零i:
if (checkState[stateBase[s] + i] == s) {
return nextState[stateBase[s] + i];
} else {
return 0;
}
原始simpleNext表包含6*20 = 120个值.压缩表(的组合stateBase,nextState和checkState)包含2×23 + 20 = 66号.对于典型的DFA(如语言解析器中所见),具有更多状态和符号,压缩比要好得多.
在一个真正的实现中,我可能存储nextState并checkState作为单个结构数组,例如
typedef struct {
int nextState;
int checkState;
} TableEntry;
TableEntry table[NUM_ENTRIES];
无论如何,书中描述的压缩方案是一个更复杂的变化.这对我来说已经很晚了,所以我要离开这里,但我明天会回来解释这本书的方案与我上面解释的有何不同.