[augeas-devel] A question about libfa

[David Lutterkort]

On Thu, 2010-04-22 at 12:58 -0500, Du Li wrote:
> I'm interested in libfa. I took a look at the source codes. I don't find
> a method like BasicOperations.run(Automaton a, String s) in
> dk.brics.automaton, which can check whether a string can be accepted by
> the automata or not. Does this libfa have this feature? I believe libfa
> has this feature since this is the basic operation of automata. Right?

No, libfa does not do matching of regular expressions - there are plenty
of libraries and implementations around that do that. libfa provides
various operations on regular languages that do _not_ have readily
available OSS implementations.

Augeas uses libfa for various computations on regular languages, like
intersection and ambiguity checks. For matching, it uses the GNU regex
routines from glibc/gnulib.

The regexp syntax for libfa makes sure that it interprets regular
expressions the same way as GNU regex does - for the details, have a
look at regexp_match and regexp_compile in src/regexp.c in the Augeas
git.

Having said all that, I'd be very interested in adding a regexp matcher
to libfa, especially one that is based on Turon's paper on
derivative-based regexp matching[1] (since the DFA construction from
that paper would be useful for quite a few other libfa internals)
 
David

[1] http://www.ccs.neu.edu/home/turon/re-deriv.pdf