资 源 简 介
A hybrid regular expression evaluator for xsd:pattern combines memoization with features from the DFA and NFA approaches to provide excellent run-time characteristics with time O(mn) and space O(mn) where m is the pattern size and n is the source length.
The project is written in C and consists of 750 lines of code and comments.
Expression Compiler
The regular expression is first compiled into a tree of pattern and expression nodes.
There are three types of nodes in the compiled tree: patterns, parenthesis expressions, and "or" expressions.
Each node contains a required minimum number of matches and a maximum number of matches. The expression quantifier + means 1 minimum and unlimited maximum, * means 0 minimum and unlimited maximum, ? means 0 minimum and 1 maximum, or the quantifiers specified under {n,m} means n minimum and m maximum. The default quantifier is 1
