Tue, 20 Jan 2015 16:08:06 +0000

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) |

From: | "Costello, Roger L." <costello@mitre.org> |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.