Hello,
is there any way to detect at runtime or compile time whether Boost.Spirit needs backtracking? It would be nice to be alerted to the fact that the grammar is not LL(1) and thus has potential for optimization.
Regards,
Arno [snip] I'm not that familiar with spirit; however, I just can't imagine how it would be practical (i.e. doesn't take sooo long) to calculate
On 03/07/11 10:53, Arno Schödl wrote: this information at compile time. I base this conclusion on the outline for calculating just the lookahead sets for a simple gramar. This outline is located in the boost vault directory: http://www.boostpro.com/vault/index.php?&directory=Strings%20-%20Text%20Processing in zip file: LewiLL1.lhs_rhs.zip According to that file, it requires converging 3 times over a complete traversal of the grammar. Obviously, to do that at compile time, based on reports of the difficulty of doing subrules, it would take much too much time. OTOH, you could calculate the information offline using the code (or rather an updated version of the code) in this other zip file: cfg_lookahead_extends.zip Of course that still wouldn't give you the final answer. You'd finally have to, again, traverse the grammar tree, testing each alternative to see if the lookahead sets intersect for any pair of elements in an alternative. Of course someone may have thought of alternative, but that's how discouraging it looks to me ATM. -Larry