On 2014-05-26 8:30 AM, 罗勇刚(Yonggang Luo) wrote:
Sounds interesting algorithm, anyway, the worst case time complexity is not appealing enough, if the nbb can be reduced to |rules| then it's will be really good:)
I'm still working on experimental validation, but I believe that under some reasonably real-world constraints on the grammar and input the bounds drop to constant space/linear time, so I expect the real-world runtime to be linear in the input size, with polynomial worst case behaviour on the sort of pathological cases where the naive recursive algorithm takes exponential time, while at the same time having space usage more like the recursive algorithm then the linear space packrat uses.
If the amount of backtracking and the nesting depth of the grammar are both bounded by a constant I get those bounds; any LR(k) grammar should have the former property, and Mizushima et al. and Might et al. (cited in the paper) both have some experimental results suggesting a constant amount of backtracking for the Java, XML, JSON & Python tests they ran. As for constant nesting depth, I don't have the citation for it (any help, anyone?) but I'm pretty sure someone in software engineering has demonstrated that the statement nesting depth of source code (and maybe even machine generated data formats) tends to be bounded by a small constant.
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg