Re: Lex scanner

"Sönke Kannapinn" <soenke.kannapinn@wincor-nixdorf.com>
17 Nov 2000 23:48:01 -0500

          From comp.compilers

Related articles
Lex scanner cafelito@yahoo.com (Jorge) (2000-11-16)
Re: Lex scanner vannoord@let.rug.nl (2000-11-17)
Re: Lex scanner soenke.kannapinn@wincor-nixdorf.com (Sönke Kannapinn) (2000-11-17)
| List of all articles for this month |

From: "Sönke Kannapinn" <soenke.kannapinn@wincor-nixdorf.com>
Newsgroups: comp.compilers
Date: 17 Nov 2000 23:48:01 -0500
Organization: Siemens Inc.
References: 00-11-119
Keywords: lex
Posted-Date: 17 Nov 2000 23:48:01 EST

> I'm doing some research in lexical scanners, and it was nice if
> someone can tell me any reference about algorithms that match if two
> regular expressions generate the same language.


An obvious method using standard techniques is:
1. generate NFAs for both regular expressions
2. make DFAs out of the NFAs
3. minimize both DFAs; the result is unique up to isomorphism
4. check whether the two minimized DFAs are isomorphic


There are efficient algorithms for steps 1, 3, and 4. Step 2 is doomed to
have exponential worst-case complexity because the resulting DFA
(even the one with the minimal number of states) may have an exponential
number of states. However, that exponential complexity is unusual for
practical regular expressions.
I believe Aho/Sethi/Ullman's good old "dragon book" describes algorithms
for steps 1, 2, and 3.


Soenke.


Post a followup to this message

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