On 2014-10-07 22:48, jonathan.slend...@gmail.com wrote:
Logically, I'd think it should be possible by running the input
string against the state machine that the given regex describes,
and if at some point all the input characters are consumed, it's
a match. (We don't have to run the regex until the end.) But I
cannot find any library that does it...
Strictly speaking, a DFA or NFA always consumes the entire input;
the question of interest is whether it halts in an accepting state
or not.
It would be easy to transform a DFA or NFA in the manner that you
want, though. For each non-accepting state, determine whether it
has any transitions that lead in one or more steps to an accepting
state.
Modify the FSM so that each such state is also an accepting state.
Thanks, I'll make every state of the FSM an accepting state.
My use case is to implement autocompletion for a regular language.
So I think if the input is accepted by the FSM that I build, it's a
valid "prefix", and the autocompletion can be generated by looking
at which transitions are possible at that point.
More pointers are welcome, but I think that I have enough to start
the implementation.
If you're not interested in generating an actual regex, but only in
matching the prefix, then it sounds like you want "partial matching".
The regex module supports that:
https://pypi.python.org/pypi/regex
--
https://mail.python.org/mailman/listinfo/python-list
