Editing Parsing expression grammar (section)

==== Non-repetition left-recursion ====

For example, in the arithmetic grammar above, it could seem tempting to express operator precedence as a matter of ordered choice — <code>Sum / Product / Value</code> would mean first try viewing as <code>Sum</code> (since we parse top–down), second try viewing as <code>Product</code>, and only third try viewing as <code>Value</code> — rather than via nesting of definitions. This (non-well-formed) grammar seeks to keep precedence order only in one line:

<syntaxhighlight lang="peg">
Value   ← [0-9.]+ / '(' Expr ')'
Product ← Expr (('*' / '/') Expr)+
Sum     ← Expr (('+' / '-') Expr)+
Expr    ← Sum / Product / Value
</syntaxhighlight>

Unfortunately matching an <code>Expr</code> requires testing if a <code>Sum</code> matches, while matching a <code>Sum</code> requires testing if an <code>Expr</code> matches. Because the term appears in the leftmost position, these rules make up a [[circular definition]] that cannot be resolved.  (Circular definitions that can be resolved exist—such as in the original formulation from the first example—but such definitions are required not to exhibit pathological recursion.)  However, left-recursive rules can always be rewritten to eliminate left-recursion.<ref name="pegs" /><ref name="AhoSethiUllman 1986">{{cite book |last1=Aho |first1=A.V. |last2=Sethi |first2=R. |last3=Ullman |first3=J.D. |date=1986 |title=Compilers: Principles, Techniques, and Tools |publisher=[[Addison-Wesley Longman]] |place=Boston, MA, USA |url=https://archive.org/details/compilersprincip0000ahoa/ |url-access=registration |isbn=0-201-10088-6}}</ref> For example, the following left-recursive CFG rule:
<syntaxhighlight lang="peg">
string-of-a ← string-of-a 'a' | 'a'
</syntaxhighlight>

can be rewritten in a PEG using the plus operator:
<syntaxhighlight lang="peg">
string-of-a ← 'a'+
</syntaxhighlight>

The process of rewriting [[Left recursion#Indirect left recursion|''indirectly'' left-recursive]] rules is complex in some packrat parsers, especially when semantic actions are involved.

With some modification, traditional packrat parsing can support direct left recursion,<ref name="ford02"/><ref name="warth08">
{{cite conference
|first1=Alessandro |last1=Warth |first2=James R. |last2=Douglass |first3=Todd |last3=Millstein
| title = Packrat Parsers Can Support Left Recursion
| conference = PEPM '08
| book-title = Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation
| pages = 103&ndash;110
| date = January 2008
| url = http://www.vpri.org/pdf/tr2007002_packrat.pdf
| publisher = [[Association for Computing Machinery|ACM]]
| doi = 10.1145/1328408.1328424
|isbn=9781595939777 | access-date = 2008-10-02}}
</ref><ref name="ruediste09">
{{cite web
 |first= Ruedi |last=Steinmann
 |title       = Handling Left Recursion in Packrat Parsers
 |date        = March 2009
 |url         = http://n.ethz.ch/~ruediste/packrat.pdf
 |website     = n.ethz.ch
 |url-status  = dead
 |archive-url  = https://web.archive.org/web/20110706232049/http://n.ethz.ch/~ruediste/packrat.pdf
 |archive-date = 2011-07-06
}}
</ref> but doing so results in a loss of the linear-time parsing property<ref name="warth08"/> which is generally the justification for using PEGs and packrat parsing in the first place.  Only the [[OMeta]] parsing algorithm<ref name="warth08"/> supports full direct and indirect left recursion without additional attendant complexity (but again, at a loss of the linear time complexity), whereas all [[GLR parser]]s support left recursion.