[Boost-users] Xpressive, symantic actions and combination enumeration

Subject: [Boost-users] Xpressive, symantic actions and combination enumeration
From: Lee Simpson (L33Simpson+boostuser_at_[hidden])
Date: 2009-05-05 02:27:33

Hi,
First let me say. Awesome library and thanks for releasing it to the world.

I'm looking for a way to apply all the currently queued semantic actions
_without_ turning off backtracking.
So, as the manual suggests, keep manages to apply the queued actions but it
also turns off backtracking.

The reason I am doing this is simple though unusual.
I am trying to determine every possible match for a given input sequence,
recording and ranking each one individually.

A simple (contrived) example would be...

input = "abcd";
expression = apply(+alpha[save_lhs(_)] >> +alpha[save_rhs(_)] >> eos)

Ideally, applying the expression would yield the following combinations for
'lhs' and 'rhs'

   1. "a","bcd"
   2. "ab","cd"
   3. "abc","d"

The best solution I have come up with has an unacceptable time complexity.
In short, the solution is to have a match assertion at the end of the
expression which only succeeds on the nth try. I then use a while loop,
executing regex_match with increasing values of 'n' until no more matches
are found. Of course the problem with this solution is that the time
complexity goes to n!+(n-1)!+(n-2)!...

Any ideas?