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

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!news.misty.com!news.iecc.com!.POSTED!nerds-end
From	"Costello, Roger L." <costello@mitre.org>
Newsgroups	comp.compilers
Subject	Algorithm(s) to convert textual regular expressions to a transition table?
Date	Tue, 20 Jan 2015 16:08:06 +0000
Organization	Compilers Central
Lines	18
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<15-01-035@comp.compilers> (permalink)
NNTP-Posting-Host	news.iecc.com
Mime-Version	1.0
Content-Type	text/plain; charset="us-ascii"
Content-Transfer-Encoding	8bit
X-Trace	miucha.iecc.com 1421778476 29785 2001:470:1f07:1126:0:676f:7373:6970 (20 Jan 2015 18:27:56 GMT)
X-Complaints-To	abuse@iecc.com
NNTP-Posting-Date	Tue, 20 Jan 2015 18:27:56 +0000 (UTC)
Keywords	lex, question, comment
Posted-Date	20 Jan 2015 13:27:56 EST
X-submission-address	compilers@iecc.com
X-moderator-address	compilers-request@iecc.com
X-FAQ-and-archives	http://compilers.iecc.com
Xref	csiph.com comp.compilers:1492

Show key headers only | View raw

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]

Back to comp.compilers | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Algorithm(s) to convert textual regular expressions to a transition table? "Costello, Roger L." <costello@mitre.org> - 2015-01-20 16:08 +0000
  Re: Algorithm(s) to convert textual regular expressions to a transition table? ioan <niciodata.eu@gmail.com> - 2015-01-21 01:46 -0800
  Re: Algorithm(s) to convert textual regular expressions to a transition table? jeremy.p.wright@gmail.com - 2015-01-21 01:05 -0800
  Re: Algorithm(s) to convert textual regular expressions to a transition table? Kaz Kylheku <kaz@kylheku.com> - 2015-01-22 01:35 +0000

csiph-web