The NFA Segments Scan Algorithm

Barkol, Omer ; Lehavi, David

HP Development Company

关键词: formal languages;    regular expression;    automata;   

RP-ID  :  HPL-2014-10

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

We present a novel way for parsing text with non deterministic finite automatons. For "real life" regular expressions and text, our algorithm scans only a fraction of the characters, and performs a small number of operations for each of these characters (for synthetic worse case scenarios, it would perform worse than classical algorithms). Although there are similar approaches, our algorithm is far simpler and less resource consuming than the alternatives we are aware of.