tag:blogger.com,1999:blog-28320851.post2960630182481344826..comments2023-06-21T03:36:37.585-07:00Comments on Uncut blocks of wood: Yacc is of the Living DeadBurak Emirhttp://www.blogger.com/profile/01651698653168460072noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-28320851.post-26258289602833941122010-12-09T09:20:42.896-08:002010-12-09T09:20:42.896-08:00Thanks for the insightful comment and the helpful ...Thanks for the insightful comment and the helpful pointers.<br /><br />Needless to say, David and I were touched by all the attention (both positive and critical) the draft received.<br /><br />The community feedback has been outstanding, and we're well on our way toward a thoughtful revamp.<br /><br />To be clear, we were aware of the exponential complexity, but felt this wasn't important since it never showed up when we used it in practice.<br /><br />Moreover, we had also discovered a few optimizations that appear to bring the complexity down to polynomial, but ran out of time to flush them out for the submission last year.<br /><br />It looks like derivative-based parsing will be the usual O(n^3) in general, and O(n^2) for unambiguous grammars in the worst case. And, of course, fast in practice.<br /><br />Thanks to all the attention, we're moving forward on the idea again, and we're hoping to publish a significantly expanded and cleaned up draft in the near future.<br /><br />-MattMatthttps://www.blogger.com/profile/05481739222422277274noreply@blogger.com