小编hal*_*leh的帖子

我想第一次编写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定义如下:

int nextState(s, a) {
if ( check[base[s] + a] = s ) return next[base[s] + a];
else return nextState(default[s], a);
}

Run Code Online (Sandbox Code Playgroud)

我不明白这四个数组是由什么组成的？任何人都能为我解释一下吗？你有另一个简单的算法来优化我的代码进行稀疏压缩吗？我知道CSR压缩但是我不知道如何使用它们在我的C#代码中编写nextState(s,a)!你有什么想法吗？