Find out till where a regex satisfies a sentence

user_4751842 0
Viewed 241

I have some sentence and a regular expression. Is it possible to find out till where in the regex my sentence satisfies. For example consider my sentence as MMMV and regex as M+V?T*Z+. Now regex till M+V? satisfies the sentences and the remaining part of regex is T*Z+ which should be my output.

My approach right now is to break the regex in individual parts and store that in a list and then match by concatenating first n parts till sentence matches. For example if my regex is M+V?T*Z+, then my list is ['M+', 'V?', 'T*', 'Z+']. I then match my string in loop first by M+, second by M+V? and so on till complete match is found and then take the remaining list as output. Below is the code

            re_exp = ['M+', 'V?', 'T*', 'Z+']
            for n in range(len(re_exp)):
                re_expression = ''.join(re_exp[:n+1])
                if re.match(r'{0}$'.format(re_expression), sentence_language):
                    return re_exp[n+1:]

Is there a better approach to achieve this may be by using some parsing library etc.

parsing python regex
2 Answers

Assuming that your regex is rather simple, with no groups, backreferences, lookaheads, etc., e.g. as in your case, following the pattern \w[+*?]?, you can first split it up into parts, as you already do. But then instead of iteratively joining the parts and matching them against the entire string, you can test each part individually by slicing away the already matched parts.

def match(pattern, string):
    res = pat = ""
    for p in re.findall(r"\w[+*?]?", pattern):
        m = re.match(p, string)
        if m:
            g = m.group()
            string = string[len(g):]
            res, pat = res + g, pat + p
        else:
            break
    return pat, res

Example:

>>> for s in "MMMV", "MMVVTTZ", "MTTZZZ", "MVZZZ", "MVTZX":
>>>     print(*match("M+V?T*Z+", s))
...
M+V?T* MMMV
M+V?T* MMV
M+V?T*Z+ MTTZZZ
M+V?T*Z+ MVZZZ
M+V?T*Z+ MVTZ

Note, however, that in the worst case of having a string of length n and a pattern of n parts, each matching just a single character, this will still have O(n²) for repeatedly slicing the string.

Also, this may fail if two consecutive parts are about the same character, e.g. a?a+b (which should be equivalent to a+b) will not match ab but only aab as the single a is already "consumed" by the a?.

You could get the complexity down to O(n) by writing your own very simple regex matcher for that very reduced sort of regex, but in the average case that might not be worth it, or even slower.

user_16396250

You can use () to enclose groups in regex. For example: M+V?(T*Z+), the output you want is stored in the first group of the regex.

I know the question says python, but here you can see the regex in action:

const regex = /M+V?(T*Z+)/;
const str = `MMMVTZ`;
let m = regex.exec(str);

console.log(m[1]);

user_44173060
Related