4 ms·
"context-free expression" = to context-free grammars as regular expression is to regular grammars
by nerfhammer 16y ago
"context-free expression" = to context-free grammars as regular expression is to regular grammars
- silentbicycle 16y agoI'm still not 100% sure, but I think LPEG (http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html) fits the bill. Ignore for now that it's a Lua library - there's nothing Lua-specific about its underlying design. There's a great paper (http://www.inf.puc-rio.br/~roberto/docs/peg.pdf http://www.inf.puc-rio.br/~roberto/docs/peg.pdf) about it. It's a PEG-based string pattern-matching engine. It can build parse trees out of strings or execute code on portions of them just as easily as it can validate their structure, though in the documentation that's a bit of an afterthought. It's also very fast, and integrates as nicely with Lua as regular expressions do in Perl. It's also just a smallish C library that could be (maybe already has) been ported to Python / Ruby / whatever.