Content deleted Content added
→Top: Changed claim with poor support in source. Old text may have conflated two separate points. |
→Unexpected behaviour: Wrote section lead-in |
||
Line 265:
== Unexpected behaviour ==
A common first impression of PEGs is that they look like CFGs with certain convenience features — repetition operators <code>*+?</code> as in regular expressions and lookahead predicates <code>&!</code> — plus ordered choice for disambiguation. This understanding can be sufficient when one's goal is to create a parser for a language, but it is not sufficient for more theoretical discussions of the computational power of parsing expressions. In particular the [[Nondeterministic Turing machine|nondeterminism]] inherent in the unordered choice <code>|</code> of context-free grammars makes it very different from the deterministic ordered choice <code>/</code>.
=== The midpoint problem ===
PEG packrat parsers cannot recognize some unambiguous nondeterministic CFG rules, such as the following:<ref name="pegs"/>
| |||