Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1492

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

Show all headers | 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