moar-regex / moar Goto Github PK

[+-] means either + or - and not the meta characters.

If we recognize these while checking for determinism, should we merge them?

some examples were not correct. these have to be fixed.

Dominik sent these:
()|()
(a+)+
(a|())+

These are all wrongly recognized as non deterministic. This is probably due to the EdgeGraph currently using Lists to store the edges. Maybe a switch back to Sets is a good idea.

Currently only (?:(?:a*)*)* is allowed (but still non deterministic).

\r\n is not equal to \n.

Note to people coming accross this; This is no bug, but merely a flaw in how determinism is currently defined (it is too restrictive atm).

• (\w+)(\s+\1)+
  (Should be possible as the first matching group can never be empty)

For example < and > are only needed for capturing groups. Escaping them outside of capturing gruops is a bit weird, but can be kept for simplicity of the parser.

As MOAs are more expressive than the Deterministic Regexes, a tool to build MOAs in a GUI would be nice.

Features of such a tool would be:

• Loading a Regex/JSON representation
• Creation of new MOAs
• Manipulation of loaded Regexes/JSON-MOAs
• Storing the JSON representation of the modeled Graph
• Testing of the MOA against input strings (no need to define the input alphabet. Ours is always the whole UTF-16 range)
• Obligatory Determinism Check upon Export to JSON/Testing
• Optional removal of unneeded States (if the graph is not connected)

Behaviour:

Starting with an empty MOA that doesn't accept any input (L(A) = {}) the user can add states and edges to the graph. Edges are added by click dragging from the start to the end of the edge (a state). These edges then can be annotated with o(x),r(x),c(x) for variables. If the click drag ends on blank space a State is created automatically. (States should be able to be created on their own as well). States are marked with an equivalent representation as in the JSON format. (To see the format, try the cli tool and export a Regex containing all features and as much syntactic sugar as possible to a JSON file).

Translation into MOA:

The easiest way to translate this into a MOA would either be to create the JSON string and then building the MOA from that or by creating the MOA by putting everything into the internal data-structures by hand. The JSON version would require less tight coupling to the MOA internal API.

Possible APIs to use:

• JGraphX for visualization (or hand written visualization as we don't need all the features, and JGraphX's API seems outdated)
• JGraphT for representation of the Graph (otherwise, the Graph can easily be represented in a similar way as the internal EdgeGraph of the MOAs does it, no need for a fully fletched mathematical Graph API)

A cool use case for the regexes would be using them in a Lucene FullText Index. This can be achieved by modding the RegexQuery class from the original Lucene into an alternative version that works with this library instead of Java Patterns.

I have written a regex benchmark comparing different regex engines for Java. Lately I found your approach and would be curious how it performs compared to the other alternatives.

Yet I restricted the benchmark to projects that are available as maven library artifact. I am not certain whether your project may be distributed in such a way. If so, I would offer to integrate a new benchmark in regexbench (a pull request is also welcome).