Content deleted Content added
→Unexpected behaviour: New section heading, splitting subsections off from "Disadvantages", since matters described are not disadvantages as such |
→Expressive power: Added worked example |
||
Line 262:
</syntaxhighlight>
Neither [[LL(k)]] nor LR(k) parsing algorithms are capable of recognizing this example. However, this grammar can be used by a general CFG parser like the [[CYK algorithm]]. However, the ''language'' in question can be recognised by all these types of parser, since it is in fact a regular language (that of strings of an odd number of x's).
It is instructive to work out exactly what a PEG parser does when attempting to match
<syntaxhighlight lang="peg">
S ← 'x' S 'x' / 'x'
</syntaxhighlight>
against the string <code>xxxxxq</code>. As expected, it recursively tries to match the nonterminal <code>S</code> at increasing positions in this string, until failing the match against the <code>q</code>, and after that begins to backtrack. This goes as follows:
Position: 123456
String: xxxxxq
Results: ↑ Pos.6: Neither branch of S matches
↑ Pos.5: First branch of S fails, second branch succeeds, yielding match of length 1.
↑ Pos.4: First branch of S fails, second branch succeeds, yielding match of length 1.
↑ Pos.3: First branch of S succeeds, yielding match of length 3.
↑ Pos.2: First branch of S fails, because after the S match at 3 comes a q.
Second branch succeeds, yielding match of length 1.
↑ Pos.1: First branch of S succeeds, yielding match of length 3.
Matching against a parsing expression is [[greedy algorithm|greedy]], in the sense that the first success encountered is the only one considered. Even if locally the choices are ordered longest first, there is no guarantee that this greedy matching will find the globally longest match.
It is an open problem to give a concrete example of a context-free language which cannot be recognized by a parsing expression grammar.<ref name="For04" /> In particular, it is open whether a parsing expression grammar can recognize the language of palindromes.<ref>{{cite arXiv |last1=Loff |first1=Bruno |last2=Moreira |first2=Nelma |last3=Reis |first3=Rogério |date=2020-02-14 |title=The computational power of parsing expression grammars |class=cs.FL |eprint=1902.08272 }}</ref>
| |||