logoalt Hacker News

cbarrick • today at 1:26 PM • 1 reply • 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.


Replies

sparkie • today at 4:15 PM

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.

➕ show 1 reply