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

That approach is a search algorithm which spends a lot of time exploring dead ends, to solve a problem for which there are much better solutions. For some grammars, it looks like it will lead to combinatorial explosion. I did something like this in SNOBOL a long time ago. Someone commented "That's the slowest program I've ever seen that does something useful".


Well, in practice, it is a variant of recursive descent. It has pretty bad performance for certain grammars, but it is a perfectly good (and fast) alternative if you feel like spending time rewriting the grammar by hand to fit.

For example, nowadays gcc use recursive descent to parse C.

Also, not handling arbitrary CFG grammars well is extremely common, it is a feature that LL, LR, LALR, PEG and other all share. Is it obviously worse to have exponential time parsing something if compared to not parsing it at all? No, but if you need to handle ambiguity you probably should use a different algorithm.




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

Search: