node type in a syntax tree for implementing NFA is described as follow:
| symbol | node type |
|---|---|
dot(.) |
Leaf Node |
^ |
Head Node |
$ |
Tail Node |
[] |
O-Node, option node. |
* |
Star Node |
+ |
Star Node |
? |
Star Node |
{} |
Star Node |
r1r2 |
Cat Node |
r1|r2 |
Or Node |
() |
represent a unit, it will be set as an attribute in the tree node. |
\1 |
leaf node, for back reference. |
char |
leaf node represents normal character. |
syntaxs of the regular expression supported by my implementation.
- all the syntaxs supported are as mentioned in the previous section.
- for [], support range and negation, [a-f], [2-9], [^abc].
- for back reference, referencing index starts from 0, this is quite different from what you usually see. eg, given pattern: ((ab)cd), for testing string abcd, we get: \0 == ab, \1 == abcd. so, group capturing works inside out.
- use {2, 4} to make repetition of the previous unit. eg, (ab){2, 4} means repeating ab 2 to 4 times(inclusive)