dfa 状态转换表压缩算法

gta

请问dfa 状态转换表应该怎么压缩啊？龙书第三章最后一小节讲了一个算法，不过很难看懂。请大家多多指教，谢谢

prolj

next和check两个数组，default和base两个数组。计算nextstate（s，a），计算出 状态s 表项 在next和check中的位置 l ， l=base【s】+a。如果check【l】==s，我们就取next【l】位 s 在输入 a 的下一个状态。如果check【l】！=s，就让q=default【s】，用q代替s继续递归。
有什么地方难理解啊？

prolj

看一下这个吧 dfa压缩.pdf (540.15 KB, 下载次数: 336)

2008-08-09 09:26 上传

点击文件名下载附件

gta

谢谢。
找到一篇帖子http://compilers.iecc.com/comparch/article/94-10-131，看了之后似乎明白了一些，但还是没全懂

比方说有3个regular expression：
end {return END}
else {return ELSE}
[endls]+ {return IDENTIFIER}

其对应的dfa状态转换表未压缩时是这样的

    state | e n d l s
----------------------------------------
        0 | 1 7 7 7 7
        1 | 7 2 7 4 7
        2 | 7 7 3 7 7
        3 | 7 7 7 7 7
        4 | 7 7 7 7 5
        5 | 6 7 7 7 7
        6 | 7 7 7 7 7
        7 | 7 7 7 7 7

相应的default,base,next,check这四个数组的内容是什么？另外，你能给出一段psedocode，从未压缩的表中直接生成这四个数组吗？谢谢。

prolj

state default base index next check
  ---------------------------------------------------------------
            0 3 5 0 7 3
            1 3 5 1 7 3
            2 2 7 3
            3 X 0 3 7 3
            4 4 7 3
            5 5 1 0
            6 3 X 6 2 1
            7 3 X 7 X X
                                                                              8 2 1
                                                                              9 X X

    token state default base index next check
----------------------------------------------------------------------
      IDENT 0 3 5 0 7 3
      IDENT 1 3 5 1 7 3
      IDENT 2 3 8 2 7 3
      END 3 X 0 3 7 3
      IDENT 4 3 5 4 7 3
      IDENT 5 3 7 5 1 0
      ELSE 6 3 X 6 2 1
      IDENT 7 3 X 7 6 5
                                                                                            8 2 1
                                                                                            9 5 4
                                                                                          10 3 2
                                                                                          11 X X
                                                                                          12 X X

space usage = 2*8 + 2*13 = 42 = default-base-size + next-check-size
size of Adjacency matrix = 8*5 = 40

mik

lz人家回答正确就给分呀，已选择一个

gta

还是不懂，为什么有些项没有呢