<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <!--Rendered using the Haskell Html Library v0.2--> <HTML ><HEAD ><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8" ><TITLE >Text.Regex.TDFA.TNFA</TITLE ><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css" ><SCRIPT SRC="haddock-util.js" TYPE="text/javascript" ></SCRIPT ><SCRIPT TYPE="text/javascript" >window.onload = function () {setSynopsis("mini_Text-Regex-TDFA-TNFA.html")};</SCRIPT ></HEAD ><BODY ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="topbar" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD ><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" " ></TD ><TD CLASS="title" >regex-tdfa-1.1.8: Replaces/Enhances Text.Regex</TD ><TD CLASS="topbut" ><A HREF="src/Text-Regex-TDFA-TNFA.html" >Source code</A ></TD ><TD CLASS="topbut" ><A HREF="index.html" >Contents</A ></TD ><TD CLASS="topbut" ><A HREF="doc-index.html" >Index</A ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="modulebar" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD ><FONT SIZE="6" >Text.Regex.TDFA.TNFA</FONT ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section1" >Description</TD ></TR ><TR ><TD CLASS="doc" ><P ><A HREF="Text-Regex-TDFA-TNFA.html" >Text.Regex.TDFA.TNFA</A > converts the CorePattern Q/P data (and its Pattern leafs) to a QNFA tagged non-deterministic finite automata. </P ><P >This holds every possible way to follow one state by another, while in the DFA these will be reduced by picking a single best transition for each (soure,destination) pair. The transitions are heavily and often redundantly annotated with tasks to perform, and this redundancy is reduced when picking the best transition. So far, keeping all this information has helped fix bugs in both the design and implementation. </P ><P >The QNFA for a Pattern with a starTraned Q/P form with N one character accepting leaves has at most N+1 nodes. These nodes repesent the future choices after accepting a leaf. The processing of Or nodes often reduces this number by sharing at the end of the different paths. Turning off capturing while compiling the pattern may (future extension) reduce this further for some patterns by processing Star with optimizations. This compact design also means that tags are assigned not just to be updated before taking a transition (PreUpdate) but also after the transition (PostUpdate). </P ><P >Uses recursive do notation. </P ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section1" >Synopsis</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="decl" ><A HREF="#v%3ApatternToNFA" >patternToNFA</A > :: <A HREF="Text-Regex-TDFA-Common.html#t%3ACompOption" >CompOption</A > -> (<A HREF="Text-Regex-TDFA-Pattern.html#t%3APattern" >Pattern</A >, (<A HREF="Text-Regex-TDFA-Common.html#t%3AGroupIndex" >GroupIndex</A >, <A HREF="Text-Regex-TDFA-Common.html#t%3ADoPa" >DoPa</A >)) -> ((<A HREF="Text-Regex-TDFA-Common.html#t%3AIndex" >Index</A >, <A HREF="/usr/share/doc/ghc/html/libraries/array-0.3.0.1/Data-Array.html#t%3AArray" >Array</A > <A HREF="Text-Regex-TDFA-Common.html#t%3AIndex" >Index</A > <A HREF="Text-Regex-TDFA-TNFA.html#t%3AQNFA" >QNFA</A >), <A HREF="/usr/share/doc/ghc/html/libraries/array-0.3.0.1/Data-Array.html#t%3AArray" >Array</A > <A HREF="Text-Regex-TDFA-Common.html#t%3ATag" >Tag</A > <A HREF="Text-Regex-TDFA-Common.html#t%3AOP" >OP</A >, <A HREF="/usr/share/doc/ghc/html/libraries/array-0.3.0.1/Data-Array.html#t%3AArray" >Array</A > <A HREF="Text-Regex-TDFA-Common.html#t%3AGroupIndex" >GroupIndex</A > [<A HREF="Text-Regex-TDFA-Common.html#t%3AGroupInfo" >GroupInfo</A >])</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >data</SPAN > <A HREF="#t%3AQNFA" >QNFA</A > = <A HREF="#v%3AQNFA" >QNFA</A > {<TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="recfield" ><A HREF="#v%3Aq_id" >q_id</A > :: <A HREF="Text-Regex-TDFA-Common.html#t%3AIndex" >Index</A ></TD ></TR ><TR ><TD CLASS="recfield" ><A HREF="#v%3Aq_qt" >q_qt</A > :: <A HREF="Text-Regex-TDFA-TNFA.html#t%3AQT" >QT</A ></TD ></TR ></TABLE >}</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >data</SPAN > <A HREF="#t%3AQT" >QT</A > </TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="decl" >= <A HREF="#v%3ASimple" >Simple</A > {<TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="recfield" ><A HREF="#v%3Aqt_win" >qt_win</A > :: <A HREF="Text-Regex-TDFA-Common.html#t%3AWinTags" >WinTags</A ></TD ></TR ><TR ><TD CLASS="recfield" ><A HREF="#v%3Aqt_trans" >qt_trans</A > :: <A HREF="Data-IntMap-CharMap2.html#t%3ACharMap" >CharMap</A > <A HREF="Text-Regex-TDFA-TNFA.html#t%3AQTrans" >QTrans</A ></TD ></TR ><TR ><TD CLASS="recfield" ><A HREF="#v%3Aqt_other" >qt_other</A > :: <A HREF="Text-Regex-TDFA-TNFA.html#t%3AQTrans" >QTrans</A ></TD ></TR ></TABLE >}</TD ></TR ><TR ><TD CLASS="decl" >| <A HREF="#v%3ATesting" >Testing</A > {<TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="recfield" ><A HREF="#v%3Aqt_test" >qt_test</A > :: <A HREF="Text-Regex-TDFA-Common.html#t%3AWhichTest" >WhichTest</A ></TD ></TR ><TR ><TD CLASS="recfield" ><A HREF="#v%3Aqt_dopas" >qt_dopas</A > :: <A HREF="Data-IntSet-EnumSet2.html#t%3AEnumSet" >EnumSet</A > <A HREF="Text-Regex-TDFA-Common.html#t%3ADoPa" >DoPa</A ></TD ></TR ><TR ><TD CLASS="recfield" ><A HREF="#v%3Aqt_a" >qt_a</A > :: <A HREF="Text-Regex-TDFA-TNFA.html#t%3AQT" >QT</A ></TD ></TR ><TR ><TD CLASS="recfield" ><A HREF="#v%3Aqt_b" >qt_b</A > :: <A HREF="Text-Regex-TDFA-TNFA.html#t%3AQT" >QT</A ></TD ></TR ></TABLE >}</TD ></TR ></TABLE ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >type</SPAN > <A HREF="#t%3AQTrans" >QTrans</A > = <A HREF="/usr/share/doc/ghc/html/libraries/containers-0.3.0.0/Data-IntMap.html#t%3AIntMap" >IntMap</A > [<A HREF="Text-Regex-TDFA-Common.html#t%3ATagCommand" >TagCommand</A >]</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >data</SPAN > <A HREF="#t%3ATagUpdate" >TagUpdate</A > </TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="decl" >= <A HREF="#v%3APreUpdate" >PreUpdate</A > <A HREF="Text-Regex-TDFA-Common.html#t%3ATagTask" >TagTask</A ></TD ></TR ><TR ><TD CLASS="decl" >| <A HREF="#v%3APostUpdate" >PostUpdate</A > <A HREF="Text-Regex-TDFA-Common.html#t%3ATagTask" >TagTask</A ></TD ></TR ></TABLE ></TD ></TR ></TABLE ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section1" >Documentation</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="topdecl" ><TABLE CLASS="declbar" ><TR ><TD CLASS="declname" ><A NAME="v:patternToNFA" ><A NAME="v%3ApatternToNFA" ></A ></A ><B >patternToNFA</B > :: <A HREF="Text-Regex-TDFA-Common.html#t%3ACompOption" >CompOption</A > -> (<A HREF="Text-Regex-TDFA-Pattern.html#t%3APattern" >Pattern</A >, (<A HREF="Text-Regex-TDFA-Common.html#t%3AGroupIndex" >GroupIndex</A >, <A HREF="Text-Regex-TDFA-Common.html#t%3ADoPa" >DoPa</A >)) -> ((<A HREF="Text-Regex-TDFA-Common.html#t%3AIndex" >Index</A >, <A HREF="/usr/share/doc/ghc/html/libraries/array-0.3.0.1/Data-Array.html#t%3AArray" >Array</A > <A HREF="Text-Regex-TDFA-Common.html#t%3AIndex" >Index</A > <A HREF="Text-Regex-TDFA-TNFA.html#t%3AQNFA" >QNFA</A >), <A HREF="/usr/share/doc/ghc/html/libraries/array-0.3.0.1/Data-Array.html#t%3AArray" >Array</A > <A HREF="Text-Regex-TDFA-Common.html#t%3ATag" >Tag</A > <A HREF="Text-Regex-TDFA-Common.html#t%3AOP" >OP</A >, <A HREF="/usr/share/doc/ghc/html/libraries/array-0.3.0.1/Data-Array.html#t%3AArray" >Array</A > <A HREF="Text-Regex-TDFA-Common.html#t%3AGroupIndex" >GroupIndex</A > [<A HREF="Text-Regex-TDFA-Common.html#t%3AGroupInfo" >GroupInfo</A >])</TD ><TD CLASS="declbut" ><A HREF="src/Text-Regex-TDFA-TNFA.html#patternToNFA" >Source</A ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="topdecl" ><TABLE CLASS="declbar" ><TR ><TD CLASS="declname" ><SPAN CLASS="keyword" >data</SPAN > <A NAME="t:QNFA" ><A NAME="t%3AQNFA" ></A ></A ><B >QNFA</B > </TD ><TD CLASS="declbut" ><A HREF="src/Text-Regex-TDFA-Common.html#QNFA" >Source</A ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="ndoc" >Internal NFA node type </TD ></TR ><TR ><TD CLASS="section4" >Constructors</TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="5" CELLPADDING="0" ><TR ><TD CLASS="arg" ><A NAME="v:QNFA" ><A NAME="v%3AQNFA" ></A ></A ><B >QNFA</B ></TD ><TD CLASS="rdoc" ></TD ></TR ><TR ><TD CLASS="body" COLSPAN="2" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="arg" ><A NAME="v:q_id" ><A NAME="v%3Aq_id" ></A ></A ><B >q_id</B > :: <A HREF="Text-Regex-TDFA-Common.html#t%3AIndex" >Index</A ></TD ><TD CLASS="rdoc" ></TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:q_qt" ><A NAME="v%3Aq_qt" ></A ></A ><B >q_qt</B > :: <A HREF="Text-Regex-TDFA-TNFA.html#t%3AQT" >QT</A ></TD ><TD CLASS="rdoc" ></TD ></TR ></TABLE ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="section4" ><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:QNFA')" ALT="show/hide" > Instances</TD ></TR ><TR ><TD CLASS="body" ><DIV ID="i:QNFA" STYLE="display:block;" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="decl" ><A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Text-Show.html#t%3AShow" >Show</A > <A HREF="Text-Regex-TDFA-TNFA.html#t%3AQNFA" >QNFA</A ></TD ></TR ></TABLE ></DIV ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="topdecl" ><TABLE CLASS="declbar" ><TR ><TD CLASS="declname" ><SPAN CLASS="keyword" >data</SPAN > <A NAME="t:QT" ><A NAME="t%3AQT" ></A ></A ><B >QT</B > </TD ><TD CLASS="declbut" ><A HREF="src/Text-Regex-TDFA-Common.html#QT" >Source</A ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="ndoc" >Internal to QNFA type. </TD ></TR ><TR ><TD CLASS="section4" >Constructors</TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="5" CELLPADDING="0" ><TR ><TD CLASS="arg" ><A NAME="v:Simple" ><A NAME="v%3ASimple" ></A ></A ><B >Simple</B ></TD ><TD CLASS="rdoc" ></TD ></TR ><TR ><TD CLASS="body" COLSPAN="2" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="arg" ><A NAME="v:qt_win" ><A NAME="v%3Aqt_win" ></A ></A ><B >qt_win</B > :: <A HREF="Text-Regex-TDFA-Common.html#t%3AWinTags" >WinTags</A ></TD ><TD CLASS="rdoc" >empty transitions to the virtual winning state </TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:qt_trans" ><A NAME="v%3Aqt_trans" ></A ></A ><B >qt_trans</B > :: <A HREF="Data-IntMap-CharMap2.html#t%3ACharMap" >CharMap</A > <A HREF="Text-Regex-TDFA-TNFA.html#t%3AQTrans" >QTrans</A ></TD ><TD CLASS="rdoc" >all ways to leave this QNFA to other or the same QNFA </TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:qt_other" ><A NAME="v%3Aqt_other" ></A ></A ><B >qt_other</B > :: <A HREF="Text-Regex-TDFA-TNFA.html#t%3AQTrans" >QTrans</A ></TD ><TD CLASS="rdoc" >default ways to leave this QNFA to other or the same QNFA </TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:Testing" ><A NAME="v%3ATesting" ></A ></A ><B >Testing</B ></TD ><TD CLASS="rdoc" ></TD ></TR ><TR ><TD CLASS="body" COLSPAN="2" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="arg" ><A NAME="v:qt_test" ><A NAME="v%3Aqt_test" ></A ></A ><B >qt_test</B > :: <A HREF="Text-Regex-TDFA-Common.html#t%3AWhichTest" >WhichTest</A ></TD ><TD CLASS="rdoc" >The test to perform </TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:qt_dopas" ><A NAME="v%3Aqt_dopas" ></A ></A ><B >qt_dopas</B > :: <A HREF="Data-IntSet-EnumSet2.html#t%3AEnumSet" >EnumSet</A > <A HREF="Text-Regex-TDFA-Common.html#t%3ADoPa" >DoPa</A ></TD ><TD CLASS="rdoc" >location(s) of the anchor(s) in the original regexp </TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:qt_a" ><A NAME="v%3Aqt_a" ></A ></A ><B >qt_a</B > :: <A HREF="Text-Regex-TDFA-TNFA.html#t%3AQT" >QT</A ></TD ><TD CLASS="rdoc" >use qt_a if test is True, else use qt_b </TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:qt_b" ><A NAME="v%3Aqt_b" ></A ></A ><B >qt_b</B > :: <A HREF="Text-Regex-TDFA-TNFA.html#t%3AQT" >QT</A ></TD ><TD CLASS="rdoc" >use qt_a if test is True, else use qt_b </TD ></TR ></TABLE ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="section4" ><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:QT')" ALT="show/hide" > Instances</TD ></TR ><TR ><TD CLASS="body" ><DIV ID="i:QT" STYLE="display:block;" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="decl" ><A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Eq.html#t%3AEq" >Eq</A > <A HREF="Text-Regex-TDFA-TNFA.html#t%3AQT" >QT</A ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Text-Show.html#t%3AShow" >Show</A > <A HREF="Text-Regex-TDFA-TNFA.html#t%3AQT" >QT</A ></TD ></TR ></TABLE ></DIV ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="topdecl" ><TABLE CLASS="declbar" ><TR ><TD CLASS="declname" ><SPAN CLASS="keyword" >type</SPAN > <A NAME="t:QTrans" ><A NAME="t%3AQTrans" ></A ></A ><B >QTrans</B > = <A HREF="/usr/share/doc/ghc/html/libraries/containers-0.3.0.0/Data-IntMap.html#t%3AIntMap" >IntMap</A > [<A HREF="Text-Regex-TDFA-Common.html#t%3ATagCommand" >TagCommand</A >]</TD ><TD CLASS="declbut" ><A HREF="src/Text-Regex-TDFA-Common.html#QTrans" >Source</A ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="doc" >Internal type to represent the tagged transition from one QNFA to another (or itself). The key is the Index of the destination QNFA. </TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="topdecl" ><TABLE CLASS="declbar" ><TR ><TD CLASS="declname" ><SPAN CLASS="keyword" >data</SPAN > <A NAME="t:TagUpdate" ><A NAME="t%3ATagUpdate" ></A ></A ><B >TagUpdate</B > </TD ><TD CLASS="declbut" ><A HREF="src/Text-Regex-TDFA-Common.html#TagUpdate" >Source</A ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="ndoc" >When attached to a QTrans the TagTask can be done before or after accepting the character. </TD ></TR ><TR ><TD CLASS="section4" >Constructors</TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="arg" ><A NAME="v:PreUpdate" ><A NAME="v%3APreUpdate" ></A ></A ><B >PreUpdate</B > <A HREF="Text-Regex-TDFA-Common.html#t%3ATagTask" >TagTask</A ></TD ><TD CLASS="rdoc" ></TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:PostUpdate" ><A NAME="v%3APostUpdate" ></A ></A ><B >PostUpdate</B > <A HREF="Text-Regex-TDFA-Common.html#t%3ATagTask" >TagTask</A ></TD ><TD CLASS="rdoc" ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="section4" ><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:TagUpdate')" ALT="show/hide" > Instances</TD ></TR ><TR ><TD CLASS="body" ><DIV ID="i:TagUpdate" STYLE="display:block;" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="decl" ><A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Eq.html#t%3AEq" >Eq</A > <A HREF="Text-Regex-TDFA-TNFA.html#t%3ATagUpdate" >TagUpdate</A ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Text-Show.html#t%3AShow" >Show</A > <A HREF="Text-Regex-TDFA-TNFA.html#t%3ATagUpdate" >TagUpdate</A ></TD ></TR ></TABLE ></DIV ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="botbar" >Produced by <A HREF="http://www.haskell.org/haddock/" >Haddock</A > version 2.6.1</TD ></TR ></TABLE ></BODY ></HTML >