<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">The simplest way to make a recogniser out of a RE is to use one of the available parsing libraries:<div><br></div><div><div>module RE where</div><div>import Text.ParserCombinators.UU</div><div>import Text.ParserCombinators.UU.Examples</div><div><br></div><div>data RE = Epsilon | Leaf Char | Selection RE RE | Sequence RE RE | Kleene RE | Optional RE | End</div><div><br></div><div><br></div><div>re_to_fsm :: RE -> Parser String</div><div>re_to_fsm re = case re of </div><div> Leaf c -> lift <$> pSym c</div><div> Selection re1 re2 -> re_to_fsm re1 <|> re_to_fsm re2</div><div> Sequence re1 re2 -> (++) <$> re_to_fsm re1 <*> re_to_fsm re2</div><div> Kleene re -> concat <$> pList (re_to_fsm re)</div><div><span class="Apple-tab-span" style="white-space: pre; ">        </span>Optional re -> re_to_fsm re `opt` ""</div><div> End -> pure ""</div><div><br></div><div>t = re_to_fsm ((Kleene (Leaf 'a') `Sequence` Kleene (Leaf 'b')) `Selection` (Kleene (Leaf 'a') `Sequence` (Kleene (Leaf 'c') )))</div><div><br></div><div>t1 = run t "aaabbb"</div><div>t2 = run t "aaaaccccccc"</div><div>t3 = run t "aaddcc"</div></div><div>test = run (re_to_fsm (Kleene (Leaf 'a') `Sequence` Kleen (Left 'b')) "aaabbb"</div><div><br></div><div><div>*RE> t1</div><div>--</div><div>-- > Result: "aaabbb"</div><div>-- </div><div>*RE> t2</div><div>--</div><div>-- > Result: "aaaaccccccc"</div><div>-- </div><div>*RE> t3</div><div>--</div><div>-- > Result: "aacc"</div><div>-- > Correcting steps: </div><div>-- > Deleted 'd' at position 2 expecting one of ['a', 'c', 'a', 'b']</div><div>-- > Deleted 'd' at position 3 expecting 'c'</div><div>-- </div><div>*RE> </div></div><div><br></div><div><br></div><div><div>On 22 jul 2010, at 20:51, Aaron Gray wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; ">Hi,<div><br></div><div>I am a Haskell newbie. I have coded a Regular Expression to Determinate Finite Automata translator. Algorithm from the Dragon Book.</div>
<div><br></div><div>Would someone eyeball the code and give me suggestions please. </div><div><br></div><div>I have not done anything on character classes yet though. And the parsing is a bit of a hack.</div><div><br></div>
<div>What I am not sure about is having to have multiple versions of similar datatype, each with variations in order to enumerate and generate followPos set.</div><div><br></div><div>Is there a better way of implementing this ?</div>
<div><br></div><div>Many thanks in advance,</div><div><br></div><div>Aaron</div><div><br></div></span>
<span><RE2DFA.hs></span>_______________________________________________<br>Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>http://www.haskell.org/mailman/listinfo/haskell-cafe<br></blockquote></div><br></body></html>