Algorithm(s) to convert textual regular expressions to a transition table?

"Costello, Roger L." <costello@mitre.org>Tue, 20 Jan 2015 16:08:06 +0000

From comp.compilers

Related articles
Algorithm(s) to convert textual regular expressions to a transition ta costello@mitre.org (Costello, Roger L.) (2015-01-20)
Re: Algorithm(s) to convert textual regular expressions to a transitio niciodata.eu@gmail.com (ioan) (2015-01-21)
Re: Algorithm(s) to convert textual regular expressions to a transitio jeremy.p.wright@gmail.com (2015-01-21)
Re: Algorithm(s) to convert textual regular expressions to a transitio kaz@kylheku.com (Kaz Kylheku) (2015-01-22)
| List of all articles for this month |

 From: "Costello, Roger L." Newsgroups: comp.compilers Date: Tue, 20 Jan 2015 16:08:06 +0000 Organization: Compilers Central Keywords: lex, question, comment Posted-Date: 20 Jan 2015 13:27:56 EST

Hi Folks,

I have read the section in Modern Compiler Design that discusses lexical
analysis. I understand the subset algorithm it describes (neat algorithm!).
With pencil and paper I can take a set of regular expressions and follow the
subset algorithm to generate a transition table. But writing actual code to do
this conversion will require more algorithms, I think. Is there an algorithm
that describes how to read in a set of strings that represent regular
expressions and create data structures that are well-suited to processing by
the subset algorithm? More broadly, what are the set of algorithms needed to
go from a set of strings that represent regular expressions to the precomputed
transition table? Can you refer me to a book or article that does a good job
in describing this?

/Roger
[Unless I misunderstand your question, this is exactly what lexer generators
like lex and flex do. You give it a set of regular expressions, it generates
tables that their state machine uses to match the RE's. -John]

Post a followup to this message