Yes, there O(1) parse tree nodes per character, you are correct. Thanks again for the great feedback, and for taking the time to read the paper!
On Fri, Jul 17, 2020, 8:22 PM Moss, Aaron <mo...@up.edu> wrote: > You said: "Given that recursion in the grammar may result in the same > clause matching multiple times at the same position (as long as the new > match is longer), I think the worst case-bound on h is O(n), not O(1), > which would make pika parsing’s worst-case time bound O(n^2)." Actually > this is not the case, otherwise recursive descent parsers would also be > O(n^2) if their grammar contained cycles. The reason is subtle: The size of > the parse tree produced by any parser is linearly correlated with the > length of the input, *regardless of the depth of the parse tree or the > number of loops around a cycle in the grammar*, because at the limit, > there would be one node in the parse tree per character, even if the parse > tree degenerated into a singly-linked list. This is why in the paper, I > always refer to recursive descent parsing as taking time "linear in the > length of the input and the depth of the parse tree", because actually > those two things represent the same thing. (i.e. you don't multiply the > length of the input by the depth of the parse tree to obtain the final time > complexity, you equate them to each other). > > > > Thanks for the correction, I appreciate the analysis technique. (Though I > think technically the bound is O(1) parse tree nodes per character rather > than 1 – if the parse tree was a complete binary tree there would be 2n-1 > parse tree nodes for an input of length n, and you could blow that up by a > further (# nonterminals in grammar) with rules of the form A <- B, B <- C, > …) > > > > Neat work again, > > Aaron >
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
