How to implement NFA regex with character ranges?

Question

When you read messages like Regex: the NFA and Thompson algorithm , everything looks pretty simple until you realize that in real life you need not only direct characters like "7" or "b", but also:

[AZ] [^_] . 

namely character classes (or ranges). And so my question is how to build NFA using character ranges? Using metacharacters like "not A", "something else", and then calculating overlapping ranges? This will result in a tree structure when using a state machine instead of a table.

Update: Assume a non-trivial size (→ 256).

I ask about NFA, but later I would also like to convert NFA to DFA.

Answer 1

The easiest way:

• Use segments as labels for transitions in both NFA and DFA. For example, the range [az] will be represented as a segment [97, 122] ; the single character 'a' will become [97,97] ; and any character ". becomes [minCode, maxCode] .

• Each negative range [^ az] will lead to a transition from two transition states to the next state. In this example, two transitions [minCode, 96] and [123, maxCode] should be created.

• If a range is represented by listing all possible characters [abcz], you must create either a transition to a character or characters from the first code group into ranges in order to optimize the number of transitions. Thus, [abcz] becomes [ac]|z . Thus, two transitions instead of four.

That should be enough for the NFA. However, the classic power set construct for converting NFA to DFA will not work if there are transitions with intersecting character ranges. To solve this problem, only one additional generalization step is required. After creating a set of all entered characters, in our case it will be a set of segments, it should be converted into a set of disjoint segments. This can be done in O (n * Log (n)) time, where n is the number of segments in the set using priority equeue (PQ), in which the segments are ordered by the left component. Example:

  Procedure DISJOIN: Input <- [97, 99] [97, 100] [98, 108] Output -> [97, 97] [98, 99], [100, 100], [101, 108] 

Step 2. In order to create new transitions from the “given state”, the algorithm must be modified as follows:

  for each symbol in DISJOIN(input symbols) S <- empty set of symbols T <- empty "set state" for each state in "set state" for each transition in state.transitions I <- intersection(symbol, transition.label) if (I is not empty) { Add I to the set S Add transition.To to the T } for each segement from DISJOIN(S) Create transition from "set state" to T 

To speed up the coordination when searching for the transition symbol and input C, transitions to each state can be sorted by segments and a binary search is applied.