Content deleted Content added
→More examples: Simplified Pascal comment example |
→Theory of parsing expression grammars: New section |
||
Line 347:
↑ 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>▼
=== Ambiguity detection and influence of rule order on language that is matched ===
Line 368 ⟶ 366:
S → start(G1) | start(G2)
</syntaxhighlight>
== Theory of parsing expression grammars ==
▲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>
The class of parsing expression languages is closed under set intersection and complement, thus also under set union.<ref name="For04" />{{rp|Sec.3.4}}
== Practical use ==
| |||