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

  • $\begingroup$ I've expanded the acronyms and added a full citation for the paper, I hope the question is better now. $\endgroup$ – AlexBG Jan 25 '16 at 10:31
  • 1
    $\begingroup$ As a reference request, this works; a person familiar with the body of work can start here. However, if you want people to tinker you should accomodate them by including the relevant definition and known results/conjectures so interested parties don't have to read the article. $\endgroup$ – Raphael Jan 25 '16 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.