RE: [imp-dev] LPG exponential runtime problem

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

I believe some people have used LPG to generate a C++ parser, but I don't know who they are or how far they got, sorry.

---

From: imp-dev-bounces@xxxxxxxxxxx [mailto:imp-dev-bounces@xxxxxxxxxxx] On Behalf Of John S Liu
Sent: Wednesday, June 23, 2010 11:49 AM
To: IMP Developers List
Cc: IMP Developers List; imp-dev-bounces@xxxxxxxxxxx
Subject: RE: [imp-dev] LPG exponential runtime problem

Thanks John for pointing this out, this seems like a very promising approach to solve template arguments problem, I will read the paper for more details.

Do you know anyone else uses LPG to generate C++ parser?


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


"Interrante, John A (GE, Research)" ---06/23/2010 11:36:57 AM---I would suggest changing the grammar. I recently read Ed Willink's PhD thesis (written in 2001) where he presented a new appro

From:	"Interrante, John A (GE, Research)" <interran@xxxxxxxxxxxxxxx>
To:	"IMP Developers List" <imp-dev@xxxxxxxxxxx>
Date:	06/23/2010 11:36 AM
Subject:	RE: [imp-dev] LPG exponential runtime problem
Sent by:	imp-dev-bounces@xxxxxxxxxxx

---

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" deleted by John S Liu/Toronto/IBM] _______________________________________________
imp-dev mailing list
imp-dev@xxxxxxxxxxx
https://dev.eclipse.org/mailman/listinfo/imp-dev

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