Re: Generate text, given a regex
- From: "Russ Cox" <rsc@xxxxxxxxx>
- Date: Fri, 11 Apr 2008 16:59:01 -0400
Nonetheless, it's an interesting exercise. Will probably use it in a
data structures course some time in the future. If you want to
implement the "obvious" recursive solution and still generate every
possible string, you effectively need coroutines to do alternation.
Or lazy evaluation (same thing). Doug McIlroy's functional pearl
"Enumerating the strings of regular languages" in JFP (preprint at
http://www.cs.dartmouth.edu/~doug/nfa.ps.gz) gives elegant Haskell
code to generate texts both directly from the regular expression (the
grammar route) and from the equivalent automaton.
Russ
.
- Prev by Date: Re: Popularity of compiler tools, was LRgen
- Next by Date: Re: corrections on a dfa's input strings?
- Previous by thread: corrections on a dfa's input strings?
- Next by thread: ANN: Tom 2.6
- Index(es):
Relevant Pages
|
|
