I'm writing a parser that is suppose to deal with context sensitive grammar a la XBNF, and so far it can deal with context free grammar (and does not fail where spirit parser library does on simple grammars like (ab|a)b due to its greedy algo.) However before I go on extending to XBNF, I wanted to implement the Kleene closure for convenience as it is quite inconvenient to deal with left recursion, and besides its suppose to do semantic actions in the same way spirit parser library does. The question is how can I make the implementation efficient? The closure can terminate at any time, even when its not suppose to, so it would seem that the greedy method is the most efficient at first, but then again how do you deal with something like a*ab? It could back off one step and exit the closure but then I'm not sure when is it suppose to try other alternatives as in (a|b)*. Supposedly I could do it by terminating the closure at first and then if it fails, go with the other alternatives, but does that not defeat the greediness of the algo?