RE: [imp-dev] LPG exponential runtime problem

["Interrante, John A (GE, Research)" <interran@xxxxxxxxxxxxxxx>]

I would suggest changing the grammar.  I recently read Ed Willink's PhD thesis (written in 2001) where he presented a new approach to parsing C++ that defers the use of type and template information to semantic processing and AST tree rewriting, which leads to a simpler grammar implementation that still covers the C++ syntax with fewer ambiguities.  That approach may be too much re-work for you to implement in Eclipse CDT (if that's what you're working on), but it's an interesting approach anyway.  You can read his thesis at http://www.computing.surrey.ac.uk/research/dsrg/fog/FogThesis.html (you only need to read one or two chapters and the appendices).

 

John

 

John Interrante

Computer Scientist

GE Global Research

Computing and Decision Sciences

 

interran@xxxxxx

www.research.ge.com

 

One Research Circle

Niskayuna, NY 12309 USA

 

GE imagination at work

---

From: imp-dev-bounces@xxxxxxxxxxx [mailto:imp-dev-bounces@xxxxxxxxxxx] On Behalf Of John S Liu
Sent: Wednesday, June 23, 2010 10:58 AM
To: imp-dev@xxxxxxxxxxx
Subject: [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

Attachment: smime.p7s
Description: S/MIME cryptographic signature