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

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]

Return to the comp.compilers page.
Search the comp.compilers archives again.