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

Parsing with derivatives has been around for a long time, at least for regular languages.


Yes, the technique was introduced in 1964 by Brzozowski. But the Brzozowski derivative (as it is now known) was generalized to handle all CFGs (instead of only REs) in the 2011 Might et al paper titled "Parsing with Derivatives". This work was then refined this year with "Parsing with Zippers", which generalizes Huet's Zipper data structure to represent CFGs (instead of acyclical, deterministic tree structures) and uses that to re-build the 2011 algorithm with a better representation, achieving greater performance with a small algorithm.


Thanks! I'll check out the papers.




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

Search: