4 ms·
Minor technical nitpick for the README: You're not moving up the Chomsky hierarchy but rather moving sideways ;). PEGs are non-Chomskyan parsing formalisms, in
by ulrikrasmussen 10y ago
Minor technical nitpick for the README: You're not moving up the Chomsky hierarchy but rather moving sideways ;). PEGs are non-Chomskyan parsing formalisms, in the sense that the family of languages describable by PEGs are not to be found in the Chomsky hierarchy.
For example, they are not regular, as they can match patterns such as a^n b^n. On the other hand, they are also not context-free, as they can also match non-context-free patterns such as a^n b^n c^n. Finally, since PEG can be parsed in linear time, there must also be some CFG which cannot be recognized by any PEG - this follows due to a result by Lee [1].
[1] L. Lee. Fast Context Free Grammar Parsing Requires Fast Boolean Matrix Multiplication. http://arxiv.org/pdf/cs/0112018.pdf http://arxiv.org/pdf/cs/0112018.pdf
- versteegen 10y agoInteresting. I see that the Wikipedia PEG article still states that the existence of CFG- but not PEG-parsable languages is an open problem.
- ulrikrasmussen 10y agoIt is! It is surprisingly difficult to come up with a grammar and a proof that it cannot be recognized by a PEG. Part of the reason is probably that PEGs and CFGs are quite different: A CFG is a set of generative rules which specify a set of strings, whereas a PEG is actually more like a recursive program. There's an open question on Stack Exchange for anyone who feel like taking a stab at the problem: http://cstheory.stackexchange.com/questions/34792/does-peg-contain-cfg http://cstheory.stackexchange.com/questions/34792/does-peg-c...
- versteegen 10y agoOK. I thought you meant that a non-constructive proof existed that there is such a CFG. That's how I interpreted "Finally, since PEG can be parsed in linear time, there must also be some CFG which cannot be recognized by any PEG". But I see that on cstheory you wrote instead (being more precise?) "most probably ... PEG does not contain CFG".
- ulrikrasmussen 10y agoAh, yes, that's because the non-linear complexity of binary matrix multiplication (which CFG parsing can be reduced to) is strongly suspected to be a lower bound, but I don't think that there is a formal proof of it (I am not an expert in complexity theory, so I am just basing this on what some authors seem to suggest). So, the non-constructive argument is a "proof" in the same sense that some results can be proved by first assuming that P /= NP.
- sebcat 10y agoI did not know that, thanks. Replaced it with a mentioning of regular and context-free grammars instead.