Context free grammars were introduced as a formalism to specify context free languages by Chomsky and Schutzenberger¹. It is a structural description of strings that belong to a given language. Multiple can exist that specify the same context free language. More importantly, a given context free grammar can also be used as a recognizer for a given context free language. Numerous algorithms exist ^{2 3 4} that when given a context free grammar, can recognize whether any given string belongs to the corresponding context free language. A recognizer checks whether a given string is in a given language. A parser recovers the structure(s) of such a string if it is a member of such a language. A string may have multiple structures if the grammar is ambiguous. Ruzzo ⁵ shows how one can turn a recognizer into a parser (that recovers one parse of the string) with $O(log n)$ effort where $n$ is the length of the string.

Ruzzo further shows that the all-parses problem (Generating a convenient representation of a string parse from which all parses of the string can be obtained.) is solvable in linear time (in terms of the length of input) only if Boolean matrix multiplication of two $n\times n$ matrices can be done in $O(n^2)$ time. Valient ⁶ showed that context free recognition of $n$ character strings can be carried out at least as fast as multiplication of two $n\times n$ Boolean matrices.

Das et al.⁷ shows that the lower bound for multiplication of two $n\times n$ Boolean matrices is at least $\Omega(n^3/2^{O(\sqrt{log n})})$ which is greater than $O(n^2)$.

Parsing Expression Grammars (PEGs) are an alternative means of specifying the membership criteria for a language. It was formalized by Ford in 2004 ⁸. Note that while not formalized, it was recognized much earlier that limited backtracking can make parsing easy. For example, Aho et al.⁹ showed that recognition using TDPL/GTPL which are equivalent to PEGs in power can be done in $O(n)$ time where $n$ is the length of the input. Further, Burge¹⁰ – (Top down parsing with limited backtracking page 177) describes the ordered choice algorithm, and describes the limitations of this approach.

The question that one can now ask is, does there exist a context free language such that its recognition can be achieved only in greater than $O(n)$ time. If such a language exist, then a PEG representation cannot exist for that language.

Note that these results on parsing and recognition are all for context free grammars. So, can we translate our above question to context free grammars? Say we have an arbitrary context free grammar. Say, the recognition using this context free grammar can be done in $O(m)$ time which is greater than $O(n)$ time using a BMM encoding. Can there exist a different context free grammar that allows a polynomially faster recognition? If such a context free grammar exists, then we can solve an arbitrary BMM problem by finding a context free grammar that will solve it faster.

The other direction to go is to find a CFL that is not under PEG. The current best bet is the palindrome language. Given two alphabets 0 and 1, the palindrome language can be defined as:

The reason palindromes are interesting is that, it hits upon the central characteristic of PEGs and CFGs. Namely, PEGs require matching the longest prefix first, and the next prefix is checked if and only if the first prefix fails. CFGs on the other hand, have no defined ordering. To parse an arbitrary palindrome, CFG can start matching the shortest possible expansion, and then try with longer and longer expansions (with larger stacks of S). With PEG, to match a given palindrome, one needs some way to identify whether the next read symbol, say 0 is part of a recursion call 0S0 or the ending 0. This is because if we start matching 0S0, and it fails, a match with the single 0 will not be attempted. Complicating this picture is however the ability of PEG to cancel a match using & and !. The reason this is troublesome is that in the case of context-free grammars, the language is not closed under the operations of intersection and negation. Hence, these two operations increase the power of the representation, and it is not clear how much increase they provide. In fact, PEGs may be in some sense universal ¹¹.

Finally, Medeiros et al¹² show that any LL(1) grammar describes the same language irrespective of whether it is interpreted as PEG or a CFG. However, beyond LL(1) grammars, the language described by a PEG parser differ significantly from that described by a CFG parser.

References