Out of curiosity, how many people here know how regular expressions are compiled? [closed]

Question

I'm going over this in my theory class, and I'm curious as to how many people here know what regular expression compilation actually is. I've looked online, and it seems to me that this is a more archaic topic that I thought it was.

So yeah, who here knew before reading this question that a regular expression compile is performed by converting the regex to an epsilon-nondeterministic finite automaton? Who has no clue what that is?

Hokkaido

Possibly better on Programmers on account of being a poll of programmers rather than a question with a programming answer. – Overplus

Well, I don't think they'd like this question there either. "Who does not know this?" is a rather hard to answer meaningfully... – Copt

As a matter of fact most implementations actually don't compile to finite automata. Most regex dialects in use today can match languages that are not regular (and thus could not be matched by a finite automaton). – Aberrant

Answer 1

There's a very simple and elegant little regular expression compiler in C that Rob Pike wrote and Brian Kernighan describes in Chapter 1 of O'Reilly's Beautiful Code. It's pretty easy to learn from. Also compiler courses cover it: token types can be defined with regular expressions. So I imagine this knowledge isn't terribly rare.

Tussah

That was a backtracking interpreter -- it did not compile to an automaton. – Tilefish

Answer 2

Ok. I guess I'll be the first one to admit that, although I took a compiler's course a couple years ago and know the general principle of it, I think I would need to bring out the "Dragon Book" again and read up some more on the subject if I were actually asked to write the code that does this kind of thing.

Lollar

Answer 3

I knew it had something to do with finite state machines, but nothing beyond that. Not really a subject I wanted to delve into... I suspect it's nasty under the hood. Not many people on SO seems how to use regular expressions at all, nevermind understand how they work.

Alumina