I've been unable to find what class of languages is recognized by PEGs. The original paper [1] only conjectures that there are some Context-Free Grammars that are unrecognizable by PEGs. It also demonstrates how to construct a Top-Down Parsing Language grammar from PEG, but I've been unable to find what language is recognized by them either.[1] Bryan Ford. Parsing Expression Grammars: A Recognition Based Syntactic Foundation. In Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (2004) http://www.brynosaurus.com/pub/lang/peg.pdf
What kind of formal language is generated by Parsing Expression Grammars?
formal languages;reference request;formal grammars