| [imp-dev] LPG exponential runtime problem |
We are using LPG parser generator to generate C/C++ parsers. We found a C++ syntax which causes LPG runs in exponential order. The problem syntax is:
insert_sort<list<T0, anytype> > b;
......
insert_sort<list<T0, list<T1, list<T2, list<T3, list<T4, list<T5, list<T6, anytype> > > > > > > > b;
....
insert_sort<list<T0, list<T1, list<T2, list<T3, list<T4, list<T5, list<T6,... list<Tn, anytype > > > > > > > > ... > b
The template argument can be a type id or an _expression_.
I add a loop counter in the function backtrackParse of BacktrackingParser class and starting the test from T0 to T5, the parser can only be finished parsing up to T4 within 1 minute. The number of loops from T0 to T4 is as follows:
888, 5815, 34202, 183237, 944404
It looks like the runtime is in the order of 5^n.
I also test it with LPG 2.0.17 and the numbers of loops are reduced a bit but still in an exponential order.
832, 4737, 25070, 129127, 656556
Does anyone have a similar problem? Any suggestions to fix it?
Thanks,
John
----------------------------------------------------------------------
John Liu, Software Developer - RDp C/C++, Eclipse CDT/RDT