<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 -&gt; Parser String</div><div>re_to_fsm re = case re of&nbsp;</div><div>&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;Leaf c &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;-&gt; lift &lt;$&gt; pSym c</div><div>&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;Selection re1 re2 &nbsp; &nbsp; -&gt; re_to_fsm re1 &lt;|&gt; re_to_fsm re2</div><div>&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;Sequence re1 re2 &nbsp; &nbsp; &nbsp;-&gt; (++) &lt;$&gt; re_to_fsm re1 &lt;*&gt; re_to_fsm re2</div><div>&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;Kleene re &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; -&gt; concat &lt;$&gt; pList (re_to_fsm re)</div><div><span class="Apple-tab-span" style="white-space: pre; ">        </span>Optional re &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; -&gt; re_to_fsm re `opt` ""</div><div>&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;End &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; -&gt; 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&gt; t1</div><div>--</div><div>-- &gt; Result: "aaabbb"</div><div>--&nbsp;</div><div>*RE&gt; t2</div><div>--</div><div>-- &gt; Result: "aaaaccccccc"</div><div>--&nbsp;</div><div>*RE&gt; t3</div><div>--</div><div>-- &gt; Result: "aacc"</div><div>-- &gt; Correcting steps:&nbsp;</div><div>-- &gt; &nbsp; &nbsp;Deleted &nbsp;'d' at position 2 expecting one of ['a', 'c', 'a', 'b']</div><div>-- &gt; &nbsp; &nbsp;Deleted &nbsp;'d' at position 3 expecting 'c'</div><div>--&nbsp;</div><div>*RE&gt;&nbsp;</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.&nbsp;</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>&lt;RE2DFA.hs&gt;</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>