Does anyone have a good example of a parsing expression language that
*requires* exponential time to parse via recursive descent? I'm working
on a new algorithm, and I want to check my bounds on some tricky cases.
The best I can come up with is this:
S = A !.
A = ( a A b | a A c )?
which will take exponential time on any string of the form a^n c^n, but
is exactly equivalent to the following grammar, which is linear time on
all strings, and I'd like a case that isn't (trivially) transformable to
an easier grammar:
S = A !.
A = ( a A ( b | c ) )?
Thanks,
Aaron
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
