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

One good reason (at least in the olden days, where lex and yacc come from) is efficiency. I wrote a compiler for a made-up programming language for a very slow CPU, with a recursive-descent parser, and it spends almost all of its time re-examining characters that have already been examined, checking if they match a new rule, then giving up, backtracking, and trying the exact same characters again in the next rule.

If it was looking at tokens instead of characters this would go a lot faster, because examining characters is O(n) in the number of characters.



This is probably the best argument I've seen here. Everyone else is just saying "well, we always just did it that way".

I wonder however: would it be possible to combine lexers and parsers into a single logical construct, but rely on caching to get the same effect?




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

Search: