自動產生硬體描述語言實現正規表示法比對

Abstract

正規表示法比對是一個很重要的問題，在科學和資訊處理領域上有很多相關的應用。在這篇論文裡，我們設計一個C程式，這個C程式讀正規表示法然後輸出一個以verilog語言描述的NFA。將字串輸入此NFA電路後，此電路可以檢查字串裡是否有符合正規表示法描述的子字串。使用我們提出的方法，硬體需求的成長將正比於正規表示法的長度。若使用GNU grep(DFA)的方法，記憶體需求將以O(2^n) 成長(n 是正規表示法的長度);使用[1](NFA)所提出來的方法需要O(n^2) 的硬體面積。除了面積的改善以外，在這篇論文裡介紹的新方法在偵錯、適用硬體、最佳化、電路修改、以及面積的使用效率上皆有不錯的表現。我們提出的方法利用Pentium 4的中央處理器和APEX EP20K600EBC-6521X型號的FPGA來評估。

The regular expression matching is an important problem that occurs in many areas of science and information processing. In this paper, we design a C code which accepts the regular expression and then outputs a NFA described by verilog language. By means of the NFA circuit, the circuit can read the string and examine whether the substring matches the regular expression or not. Using our approach, the area of the hardware used grow in O(n) , where n is the length of the regular expression. To match a regular expression, GNU grep (DFA) requires O(2^n) memory and approaches using the NFA in [1] require O(n^2) area. Beside the improvement of the area, this new design has not bad performance on debug, suitable device, optimization, easily modifying the circuit. We evaluate our approach on the machine which has a processor of the Pentium 4 and the target device is the APEX EP20K600EBC-6521X.