Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I'm not sure the Earley paper "is full of bugs" - to the best of my knowledge, it has only one bug (albeit a biggy), which is in its description of how to create a parse tree.


it isn't cubic time either iirc


Yes, that's part of the same bug, as I understand it anyway (to be clear: I'm not sure that anyone's claiming that there are problems with Earley's recogniser, which is really the core of his paper). Scott's "SPPF-Style Parsing From Earley Recognisers" gives an overview of the bug and its implications.


I can't remember off hand if it dealt with nullable terms or hidden left recursion properly either.

don't get me wrong: I like the earley parser :-) I just think the original paper has some omissions and the treatment of earley parsing in 'parsing techniques 2nd ed' is thorough and includes substantial references and explanations of further work.




Consider applying for YC's Fall 2026 batch! Applications are open till July 27.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: