[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [List Home]
Re: [imp-dev] LPG exponential runtime problem

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?

  - Bob
Robert M. Fuhrer
Research Staff Member
Programming Technologies Dept.
IBM T.J. Watson Research Center

IMP Project Lead (http://www.eclipse.org/imp)
X10: Productivity for High-Performance Parallel Programming (http://x10-lang.org)