StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHow to implement regular expression assertions/lookaround (i.e. \b style word boundary) using a DFA regular expression matcher
text
Body
copied!<p>I would like to implement "word boundary" matches within a DFA based regular expression matcher. Can someone tell me how this is done?</p> <p>To give some background, I'm currently using the "dk.brics.automaton" library, but it does not support assertions (e.g. <code>\b</code>, word boundary). I need to use a DFA based engine because my main goal is actually determining equivalence of regular expressions, not doing the actual matching.</p> <p>Additionally, the answer to the following question seems to indicate this is possible: <a href="https://stackoverflow.com/questions/1217189/dfa-based-regular-expression-matching-how-to-get-all-matches">DFA based regular expression matching - how to get all matches?</a> by saying</p> <blockquote> <p>"Again, we manage this by adding an epsilon transition with special instructions to the simulator. If the assertion passes, then the state pointer continues, otherwise it is discarded."</p> </blockquote> <p>I can't quite figure out what this means, however. Is it suggesting that it can only be done with a special type of epsilon transition that looks at its endpoints and can only be traversed if its endpoint meet the assertion, or can it be done with "normal" epsilon transitions configured in some way? If I need these "special" type of epsilon transitions, then how can these be determinized (i.e. converted to a standard DFA)?</p> <p>Pointers to any descriptions of how to actually implement this are greatly appreciated.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload