[發明專利]用于正則表達式的編譯器

有效

• 申請號: 201710258370.9
• 申請日: 2012-06-20
• 公開（公告）號: CN107122221B
• 公開（公告）日: 2021-03-12
• 發明（設計）人: R·戈亞爾;S·L·比拉;K·A·布里斯
• 申請（專利權）人: 馬維爾亞洲私人有限公司
• 主分類號: G06F8/41
• 分類號: G06F8/41;G06F9/448;H04L29/06
• 代理公司: 北京市金杜律師事務所 11256
• 代理人: 王茂華

1.一種用于確定NFA狀態集合的埃普西隆終止的方法，所述方法包括：

在耦合到網絡的安全設備的處理器中：

接收NFA狀態集合，所述NFA狀態集合是針對由NFA圖形所識別的字母的字符的轉換狀態；以及

確定所接收的NFA狀態集合是否與埃普西隆終止(EC)高速緩存表中的NFA狀態集合匹配，所述EC高速緩存表將NFA狀態集合的埃普西隆終止與所述NFA狀態集合的哈希值進行映射。

2.根據權利要求1所述的方法，其中確定進一步包括：

計算所接收的NFA狀態集合的哈希值；以及

將所述哈希值與所述EC高速緩存表的哈希值條目進行匹配。

3.根據權利要求2所述的方法，進一步包括：

如果存在匹配，則將映射到所述EC高速緩存表中的匹配的哈希值的所述NFA狀態集合設置為所接收的NFA狀態集合的所述埃普西隆終止。

4.根據權利要求3所述的方法，進一步包括：

如果不存在匹配，則計算所接收的NFA狀態集合的埃普西隆終止；

將新的條目添加到所述EC高速緩存表，所述新的條目將所接收的NFA狀態集合的所述哈希值映射到所接收的NFA狀態集合的所述埃普西隆終止。

5.根據權利要求4所述的方法，其中添加條目包括：

確定是否存在用于添加新的條目的足夠的內存；以及

如果沒有足夠的內存，則根據替代策略來添加所述新的條目。

6.根據權利要求5所述的方法，其中，所述替代策略通過刪除所述EC高速緩存表的最近最少使用的條目來添加所述新的條目。

7.一種用于確定NFA狀態集合的埃普西隆終止的方法，所述方法包括：

在耦合到網絡的安全設備的處理器中：

接收NFA狀態集合，所述NFA狀態集合是針對由NFA圖形所識別的字母的字符的轉換狀態；以及

確定所接收的NFA狀態集合是否與埃普西隆終止(EC)高速緩存表中的NFA狀態集合匹配，所述EC高速緩存表將關聯于NFA狀態集合的埃普西隆終止的哈希值映射到DFA狀態。

8.根據權利要求7所述的方法，其中確定進一步包括：

計算所接收的NFA狀態集合的哈希值；以及

將所述哈希值與所述EC高速緩存表的哈希值條目匹配。

9.根據權利要求7所述的方法，進一步包括：

如果匹配存在，則將與匹配哈希值條目相關聯的所述DFA狀態設置為關于由NFA圖形所識別的字母的輸入字符的、從當前DFA狀態的轉換DFA狀態。

10.根據權利要求9所述的方法，進一步包括：

如果匹配不存在，則計算所接收的NFA狀態集合的埃普西隆終止；

計算所接收的NFA狀態集合的所述埃普西隆終止的哈希值；

將新的條目添加到所述EC高速緩存表，所述新的條目將所接收的NFA狀態集合的所述哈希值映射到新的DFA狀態；以及

將所述新的DFA狀態設置為關于由所述NFA圖形所識別的所述字母的所述輸入字符的、從當前DFA狀態的所述轉換DFA狀態。

11.根據權利要求10所述的方法，其中添加條目包括：

確定是否存在用于添加新的條目的足夠的內存；以及

如果沒有足夠的內存，則根據替代策略來添加新的條目。

12.根據權利要求11所述的方法，其中，所述替代策略通過刪除所述EC高速緩存表的最近最少使用的條目來添加所述新的條目。

13.一種用于確定NFA狀態集合的埃普西隆終止的安全設備，所述安全設備包括：

編譯器，所述編譯器被配置成：

接收NFA狀態集合，所述NFA狀態集合是由NFA圖形所識別的字母的字符的轉換狀態；以及

確定所接收的NFA狀態集合是否與埃普西隆終止(EC)高速緩存表中的NFA狀態集合匹配，所述EC高速緩存表將NFA狀態集合的埃普西隆終止與所述NFA狀態集合的哈希值進行映射。

14.根據權利要求13所述的安全設備，其中所述編譯器進一步被配置成：

計算所接收的NFA狀態集合的哈希值；以及

將所述哈希值與所述EC高速緩存表的哈希值條目進行匹配。