[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
[
List Home]
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