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
