Re: [imp-dev] LPG exponential runtime problem

[John S Liu <jwsliu@xxxxxxxxxx>]

Thanks, Bob.

I will make a simplified driver for cdt and help you guys to reproduce the problem. Do you have a ftp server which I can upload the driver to you?


Thanks,

John

----------------------------------------------------------------------
John Liu, Software Developer - RDp C/C++, Eclipse CDT/RDT

IBM Canada Ltd.
8200 Warden Ave. Markham, Ontario, L6G 1C7
Internal mail: D3/201/8200 /MKM (D2-337)
Tel: (905) 413 2132


"Robert M. Fuhrer" ---06/28/2010 01:17:44 PM---Hi there, I haven't seent this problem before.

From:	"Robert M. Fuhrer" <rfuhrer@xxxxxxxxxxxxxx>
To:	IMP Developers List <imp-dev@xxxxxxxxxxx>
Date:	06/28/2010 01:17 PM
Subject:	Re: [imp-dev] LPG exponential runtime problem
Sent by:	imp-dev-bounces@xxxxxxxxxxx

---

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

IMP Project Lead (http://www.eclipse.org/imp)
X10: Productivity for High-Performance Parallel Programming (http://x10-lang.org)
_______________________________________________
imp-dev mailing list
imp-dev@xxxxxxxxxxx
https://dev.eclipse.org/mailman/listinfo/imp-dev