packrat parsing, left recursion must be eliminated. For example, in the arithmetic grammar above, it would be tempting to move some rules around so that the precedence order of products and sums could be expressed in one line: Value ← [0-9.]+ / '(' Expr ')' Product ← Expr (('*' / '/') Expr)* Sum ← Expr (('+' / '-') Expr)* Expr ← Product / Sum / Value In this new grammar, matching an Expr requires testing if a Product matches while matching a Product requires testing if an Expr 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. For example, the following left-recursive CFG rule: string-of-a ← string-of-a 'a' | 'a' can be rewritten in a PEG using the plus operator: string-of-a ← 'a'+ The process of rewriting 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, but doing so results in a loss of the linear-time parsing property which is generally the justification for using PEGs and packrat parsing in the first place. Only the OMeta parsing algorithm supports full direct and indirect left recursion without additional attendant complexity (but again, at a loss of the linear time complexity), whereas all GLR parsers support left recursion. Expressive power PEG packrat parsers cannot recognize some unambiguous nondeterministic CFG rules, such as the following: S ← 'x' S 'x' | 'x' 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 an open problem to give a concrete example of a context-free language which cannot be recognized by a parsing expression grammar. In particular, it is open whether a parsing expression grammar can recognize the language of palindromes. Ambiguity detection and influence of rule order on language that is matched LL(k) and LR(k) parser generators will fail to complete