converting regex string to automaton

Frank Tetzel

unread,

Jul 27, 2016, 7:49:04 PM7/27/16

to

Hello,

does anybody know of any library transforming a regular expression as
a string to an equivalent automaton (minimized DFA preferable)? I don't
want to do string matching directly, so most of the regex library
can't really help me. I want access to the automaton. Does anybody know
of a library or framework providing this?

Regards,
Frank

Mr Flibble

unread,

Jul 27, 2016, 8:18:31 PM7/27/16

to

Sausages.

Seriously though, sausages.

Really seriously though don't get hung up finite state machines; they
are usually a generalization on something that doesn't need generalizing.*

/Flibble

* Just finished my third double vodka.

Alain Ketterlin

unread,

Jul 28, 2016, 4:31:44 AM7/28/16

to

Some of my students have used
http://hackingoff.com/compilers/regular-expression-to-nfa-dfa
I don't know if its available for download.

But then, it is not a bad exercise to do it yourself... Especially if
you have special requirements on characters, etc.

(This has little to no relation to C++, you may get more help from
comp.theory or comp.compilers I guess.)

-- Alain.

Frank Tetzel

unread,

Jul 28, 2016, 11:23:29 AM7/28/16

to

> > does anybody know of any library transforming a regular expression
> > as a string to an equivalent automaton (minimized DFA preferable)?
> > I don't want to do string matching directly, so most of the regex
> > library can't really help me. I want access to the automaton. Does
> > anybody know of a library or framework providing this?
>
> Some of my students have used
> http://hackingoff.com/compilers/regular-expression-to-nfa-dfa
> I don't know if its available for download.

It doesn't look like there's a download somewhere but it's a nice
visualization. Thanks.

> But then, it is not a bad exercise to do it yourself... Especially if
> you have special requirements on characters, etc.

Yeah, i probably have to do that. For my current project it would just
be a nice-to-have, a simple string interface. Let's see if i find the
time for that. A nice description:
https://swtch.com/~rsc/regexp/regexp1.html

> (This has little to no relation to C++, you may get more help from
> comp.theory or comp.compilers I guess.)

I might ask there when i have more specific questions during
implementing it. Thanks for the pointers.

Regards,
Frank

Ramine

unread,

Jul 28, 2016, 1:52:23 PM7/28/16

to

I have worked with the following program, and it works great:

http://max99x.com/school/automata-editor

Thank you,
Amine Moulay Ramdane.

Alf P. Steinbach

unread,

Jul 28, 2016, 7:35:25 PM7/28/16

to

On 28.07.2016 01:48, Frank Tetzel wrote:
>
> does anybody know of any library transforming a regular expression
> as a string to an equivalent automaton (minimized DFA preferable)?

std::regex

> I don't want to do string matching directly, so most of the regex
> library can't really help me. I want access to the automaton. Does
> anybody know of a library or framework providing this?

Nope, sorry.

But why exactly doesn't std::regex fit your use case (i.e., what
/exactly/ is your use case)?

Cheers,

- Alf

Christian Gollwitzer

unread,

Jul 29, 2016, 3:52:35 AM7/29/16

to

Am 28.07.16 um 01:48 schrieb Frank Tetzel:

> does anybody know of any library transforming a regular expression as
> a string to an equivalent automaton (minimized DFA preferable)? I don't
> want to do string matching directly, so most of the regex library
> can't really help me. I want access to the automaton.

Hmm, why is it not possible to inspect the internals of a library? Too
much detail?

Maybe this site is helpful to you: https://swtch.com/~rsc/regexp/
The details of the transformation are explained in the first link
https://swtch.com/~rsc/regexp/regexp1.html
and an implementation is linked from the main page. I haven't studied it
in detail, but it looks close to what you are looking for.

Christian

Frank Tetzel

unread,

Jul 29, 2016, 5:59:45 AM7/29/16

to

> > I don't want to do string matching directly, so most of the regex
> > library can't really help me. I want access to the automaton. Does
> > anybody know of a library or framework providing this?
>
> Nope, sorry.
>
> But why exactly doesn't std::regex fit your use case (i.e., what
> /exactly/ is your use case)?

My usecase are regular path queries (RPQ) on directed, labeled graphs.
Basically you want to check if a vertex pair is connected by a path
whose label (concatenation of the edge labels) satisfies a regular
expression. The alphabet for the regular expression is the set of edge
labels.

Yeah, that's a very special usecase. So, i think, i need direct access
to the automaton as i have to take transitions more directly (during
traversing the graph). I don't think one can use std::regex for that.
Is it even possible to define an aplhabet for std::regex?

Regards,
Frank

Frank Tetzel

unread,

Jul 29, 2016, 5:59:47 AM7/29/16

to

> > does anybody know of any library transforming a regular expression
> > as a string to an equivalent automaton (minimized DFA preferable)?
> > I don't want to do string matching directly, so most of the regex
> > library can't really help me. I want access to the automaton.
>
> Hmm, why is it not possible to inspect the internals of a library?
> Too much detail?

It is probably possible to rip the specific parts out of the library. I
was just wondering if there was something more readily available.

> Maybe this site is helpful to you: https://swtch.com/~rsc/regexp/
> The details of the transformation are explained in the first link
> https://swtch.com/~rsc/regexp/regexp1.html
> and an implementation is linked from the main page. I haven't studied
> it in detail, but it looks close to what you are looking for.

I found this site too and i plan to use it as a reference for my own
implementation. Thanks for pointing out that there's also an
implementation available on the site. I missed that before.

Regards,
Frank