[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
[
List Home]
RE: [imp-dev] LPG exponential runtime problem
|
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
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