Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #78816

Re: How do I check if a string is a prefix of any possible other string that matches a given regex.

Show all headers | View raw

On 2014-10-07 22:48, jonathan.slenders@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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

How do I check if a string is a prefix of any possible other string that matches a given regex. jonathan.slenders@gmail.com - 2014-10-07 09:15 -0700
  Re: How do I check if a string is a prefix of any possible other string that matches a given regex. Joshua Landau <joshua@landau.ws> - 2014-10-07 18:01 +0100
  Re: How do I check if a string is a prefix of any possible other string that matches a given regex. Ian Kelly <ian.g.kelly@gmail.com> - 2014-10-07 12:35 -0600
    Re: How do I check if a string is a prefix of any possible other string that matches a given regex. jonathan.slenders@gmail.com - 2014-10-07 14:48 -0700
      Re: How do I check if a string is a prefix of any possible other string that matches a given regex. MRAB <python@mrabarnett.plus.com> - 2014-10-08 00:39 +0100
        Re: How do I check if a string is a prefix of any possible other string that matches a given regex. jonathan.slenders@gmail.com - 2014-10-08 01:48 -0700
      Re: How do I check if a string is a prefix of any possible other   string that matches a given regex. Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-10-09 10:24 +1300

csiph-web