KMP算法在词法分析中的应用

最近在学习编译原理，发现以前在数据结构中学习到的KMP算法在词法分析中使用到，词法分析中要识别词法单元，构建符号表，并将识别的词法单元返回给语法分析器来处理。在这个过程中有一个状态转化的过程，如下：

如要识别ababaa，状态转换图如下所示：

KMP提出了一种在文本串中搜索单个关键字b₁b₂....b_n的算法，为了快速处理文本串并在这些串中搜索一个关键字，针对关键字b₁b₂....b_n以及该关键字中的位置s(s表示关键字b1b2....bn中的状态转换图中的状态)定义了一个失效函数f(s)，f(s)的含义如下：

f(s)表示匹配到状态s，但是匹配不到状态s+1，下一次从状态f(s)开始匹配。比如文本串ababcdcd，关键子ababaa，abab能匹配，所以f(4)表示匹配到状态4，但是状态4到状态5过不去了，因为无法匹配a，但是由于对于abab这个关键字子串，ab是abab的最长的真前缀同时也是abab的后缀，所以下次对于文本串中c只要与b_f(4),即b₂，进行比较即可，无需从头开始比较。

如何证得以上结论呢？

假设有一文本串为a₁a₂a₃a₄a₅a₆a₇a₈a₉，关键字b₁b₂b₃b₄b₅，并且a₁a₂a₃a₄与b₁b₂b₃b₄匹配，但是a₅和b₅不匹配，那么常规情况下我们会从头将文本串第一个字符与关键字的第一个字符进行比较，并继续第二个字符，但是因为a₁a₂a₃a₄与b₁b₂b₃b₄匹配，并且假设b₁b₂与b₃b₄也匹配，且是最长的既是b₁b₂b₃b₄的真前缀又是b₁b₂b₃b₄的后缀的子串，那么我们就可以跳过a₂与b₁的比较，直接让a₅和b₃进行比较，为什么呢？首先因为a₃a₄必然与b₁b₂匹配，所以跳过这两次匹配，其次假设你能找到一个a₂a₃a₄a₅a₆与b₁b₂b₃b₄b₅匹配，必然能得到a₂a₃a₄等于b₁b₂b₃，又因为a₁a₂a₃等于b₁b₂b₃，所以b₁b₂b₃等于b₂b₃b₄，这与假设b₁b₂是最长的既是b₁b₂b₃b₄的真前缀又是b₁b₂b₃b₄的后缀的子串相矛盾，所以上述KMP算法成立。

由上可知，f(s)函数的目标是使得b₁b₂....b_f(s)是最长的既是b₁b₂....b_s的真前缀又是b₁b₂....b_s的后缀的子串。那么又如何针对一个关键字求得它的f(s)呢？

假设针对abababaab，首先我们看它的f(s)值如下：

s	1	2	3	4	5	6	7	8	9
f(s)	0	0	1	2	3	4	5	1	2

如果我们针对f(7)，求它的值该如何求呢？上述关键字的状态转换图如下：

假设我们已经知道f(1)到f(6)的值，因为f(6)的值等于4，可得知b₁b₂b₃b₄等于b₃b₄b₅b₆，如果b₅等于b₇，那么也就是说b₁b₂b₃b₄b₅等于b₃b₄b₅b₆b₇，则f(7)=f(6)+1=5，上述关键字成立。

如果我们针对f(8)，求它的值该如何求呢？

如果b₆等于b₈，则f(8)=f(7)+1，但是b₆=b，b₈=a，不想等，所以f(8)不能这么求，那么又该如何求呢？因为f(8)的值必然落在1到5之间，那么f(8)和f(5)的关系又如何呢？因为f(5)的值为3，则可推出b₁b₂b₃= b₃b₄b₅，且b₁b₂b₃b₄b₅等于b₃b₄b₅b₆b₇，，又因为b₃b₄b₅ = b₅b₆b₇，所以b₁b₂b₃ = b₅b₆b₇，所以只要判断b4与b8的值是否相同即可，若相同，则f(8)=f(5)+1，但是b4 = b与b8 = a，不相同，所以需要继续往下推断f(8)与f(3)的关系？因为b₁b₂b_{3 =} b₃b₄b₅ ，判断b₂的值是否等于b₈，不相同，最终若判断b1的值是否与b₈的值相同，相同，所以f(8)的值为1，否则为0。

关于f(s)的算法如下：

t = 0;
f(1) = 0;
for(s = 1; s < n; s++)
{
    while(t>0 && bs+1 != bt+1)  t = f(t);
    if(b

_s+1

 == b

_t+1

)  //如果不是t=0跳出来的
    {
        t = t+1;
        f(s+1) = t;
    }
    else f(s+1) = 0;  //如果t=0跳出来的
}