| Hi there,
I haven't seent this problem before.
Can you give me a pointer to the grammar in question and a sample input? I'll forward it to Philippe Charles, the main LPG developer. On Jun 23, 2010, at 10:58 AM, John S Liu wrote: 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?
-- Cheers, - Bob ------------------------------------------------- Robert M. Fuhrer Research Staff Member Programming Technologies Dept. IBM T.J. Watson Research Center
|
