gta 发表于 2008-08-08 22:42

dfa 状态转换表压缩算法

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

prolj 发表于 2008-08-08 22:42

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 发表于 2008-08-09 09:26

看一下这个吧

gta 发表于 2008-08-09 11:10

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

比方说有3个regular expression：
end {return END}
else {return ELSE}
+ {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 发表于 2008-08-09 12:04

这个吧

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 发表于 2008-08-10 01:12

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

gta 发表于 2008-08-13 22:22

还是不懂，为什么有些项没有呢
页: [1]
查看完整版本: dfa 状态转换表压缩算法