3
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ I've expanded the acronyms and added a full citation for the paper, I hope the question is better now. $\endgroup$
    – AlexBG
    Commented Jan 25, 2016 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
    Commented Jan 25, 2016 at 11:49

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.