dk.brics.automaton  |  dk.brics.grammar  |  dk.brics.schematools
JSRefactor  |  Artemis  |  TAJS  |  Java String Analyzer  |  XSLT Validator  |  WARlord  |  XSugar  |  Xact  |  JWIG
MONA  |  PALE

dk.brics.automaton

Frequently Asked Questions

Does this package use the same kind of "regular expressions" as Perl or java.util.regex?
No. This package uses deterministic finite-state automata (DFA), unlike most other regexp-packages that are based on nondeterministic automata (NFA). This means:
  • The notion of "regular expressions" used here has exactly the expressiveness of good old regular languages.
  • This package supports operations such as complement (the ~ operator) and intersection (the & operator).
  • The * operator is mathematically the Kleene star operator (i.e. we don't have greedy/reluctant/possesive variants).
  • The time for pattern matching is optimal: once the regular expression has been converted into an automaton, it takes linear time in the length of a string to check whether it matches the expression - independently of the complexity of the expression. (NFA-based packages use backtracking.)
  • There is no support for capturing groups.
Can you give an example of using the package to do simple pattern matching?
Here is a very simple example to get you started:
RegExp r = new RegExp("ab(c|d)*");
Automaton a = r.toAutomaton();
String s = "abcccdc";
System.out.println("Match: " + a.run(s)); // prints: true
Where is the description of the syntax of regular expressions being supported by this package?
Look in the javadoc for the RegExp class. Note that this is presumably not exactly the same syntax as you are used to!
How do I make really fast pattern matching with this package?
Convert your automaton to a RunAutomaton.
How do I use the pre-built automata in my regular expressions, as in "<URI>"?
Convert your expression x into an automaton using x.toAutomaton(new DatatypesAutomatonProvider()). Here is a list of the pre-built automata.
How do I refer to dk.brics.automaton in a publication?
Use this BibTeX entry.
Why is there no automata operation for [...]?
Because there hasn't been the need so far. If you make any extensions to the package or have some suggestions for improvements, send an email to amoeller@cs.au.dk.