Hacker News Reader

“Org” in this context is emacs org mode. Seems odd in this day and age that anyone would see hierarchical text format and think “regex”!

View on HN

Indeed. Regexes are _regular_, which is non hierarchical by definition.

The two are useful for different layers of abstraction: regex is for lexing and PEG is for parsing.

Speaking of the Chomsky hierarchy, last I checked, it is still unproven whether or not PEGs can parse all context free languages. Intuitively, they're _probably_ weaker than CFGs, but no one has yet provided a counter example.

PEGs aren't contained within the context-free languages, so it's not really intuitive that they're weaker, particularly as nobody has yet come up with a context-free language that a PEG cannot parse. They're capable of parsing things context-free grammars cannot.

Ordered choice may cause a PEG parser to fail where a CFG parser would recognize the string.

Indeed you make a good point. My naive self thought it could work out, but actually the more you zoom out, the more tree-structures you see in many formats. And in my opinion, then it's time to sheathe Valyrian Steel of Lisp, IMHO the language to rule them all when it comes to working with tree based structures (Org, HTML, SXML, many more)

Reply on news.ycombinator.com