This is a short note inspired by some ideas and results from [3, 6-8]. It is about Parsing Expression Grammars (PEGs) introduced by Ford in [1]. PEG specifies a language by defining for it a parser with limited backtracking. All of the quoted papers contain a detailed introduction to PEG, so it is not repeated here. Backtracking means that if e1 in a choice expression e1=e2 fails, the parser returns to the position it had before the attempt at e1, and tries e2 on the same input. Limited backtracking means that once e1 succeeded, e2 will not be tried on the same input upon a subsequent failure. In some cases, a failure of e1 may mean that e2 is also bound to fail, so there is no need to try it; one can terminate e1=e2 straight away and return failure. As an example, consider this grammar:
S = E $ E = T +E / T T = a / b
E = T # + " E / T Suppose that at some point during the parse of S, expression E is applied to input w. It starts by calling T. Clearly, if T fails, w does not start with a or b, so the second alternative, being the same T, must also fail. Suppose now that T + succeeds, after which E fails. One can easily see that the only thing that can follow E in the parse of S is $. Thus, applying the second alternative to w will result in a successful parse only if w = a$ or w = b$. But T + succeeding on w means that w is none of these. So, trying the second alternative will not result in a successful parse.
We have identified two points in the expression for E, indicated below by # and ", such that you do not need to backtrack if you fail before # or after ".
Thanks to the backtracking being limited, one can use the so-called ”packrat” technology to run the PEG parser in a linear time. The technology consists in saving all results to be reused in the case of backtracking. It means buying speed at the cost of large memory consumption.
Mizushima et al. [6] noted that after passing a " cut point, one can discard the saved results that would be needed by e2. In this way, one can greatly reduce the memory requirement.
In a recent paper [3], Maidl et al. discuss the way in which a PEG parser may provide meaningful information on why it failed to parse a given input. The traditional way is to report the failure that occurred farthest down in the input. But, some failures may be quite innocent, such as a failure of e1 in e1=e2 that is followed by a success of e2. In section 5 of [3], the authors present an extension to PEG to help reporting ”real” failures. Its use suggests that a ”real” failure is one occurring in the ”no return” zone, such as before # and after " in the example above. 2
As follows from the above, i is interesting to find cut points in a given grammar. To see how this can be done, we consider a minimal grammar without iteration and predicates as used in [7, 8]. It has starting symbol S and end-of-input marker $. As in [7, 8], we denote by Tail(e) the set of all terminated strings that can follow an application of e in a parse starting with S. For convenience, we consider choice expressions of the form e0 e1=e2 that can be easily desugared to the primitive form used in [7, 8]. The input alphabet is denoted by .
The grammar may be alternatively interpreted as a grammar in Backus-Naur Form (BNF), with "/" denoting the unordered choice. We denote by L(e) the language defined by e when interpreted as BNF.
The following has been shown in [5] (the proof is found also in [4, 7, 8]): Proposition 1. If expression e succeeds on input w, it consumes a string belonging to L(e), meaning that w 2 L(e) ∗.
To say something about w in case of failing e requires that each sequence
expression e1e2 satisfies this condition:
8x;y xy 2 L(e1e2) ∗ ^ x 2 L(e1) ) y 2 L(e2) ∗:
(
Proposition 3. A sufficient condition for " after e0 in A = e0 e1=e2 is:
L(e0) ∗ \ L(e2) Tail(A) = ∅:
Proposition 4. A sufficient condition for # after e0 in e0 e1=e2 in a grammar
satisfying (
L(e0) ∗:
(
As the inclusion and emptiness of intersection of context-free languages are in
general undecidable, there is no mechanical way to to represent a given expression
as e0 e1 satisfying (
Given A = e1=e2, suppose there exist first expressions first1; first2 such that:
L(e1)
L(first1) ∗; L(e2) Tail(A)
L(first2) ∗;
L(first1) ∗ \ L(first2) ∗ = ∅:
One can easily see that L(first1) ∗ \ L(e2) Tail(A) = ∅. If e1 = first1 e1′ for
some e1′, we have, according to (
Suppose that instead of (
L(first2)
L(first1) ∗:
We have then L(e2) Tail(A) L(first1) ∗. If e1 = first1 e1′ for some e1′, we
have, according to (
For E in our example, the conditions are satisfied by first1 = first2 = T , identifying the # cut point after T .
A special case of first1 and first2 are the sets of ”first terminals” used in [6].
In that special case, (
It is often difficult to represent e1 as first1 e1′. This is solved in [6] by replacing A = e1=e2 with:
A = (! first2) e1 = e2:
(
Assuming that the grammar satisfies (
In the standard version of PEG, a failing expression returns just an indication that it failed. In the modification suggested in Section 5 of [3], failing expression returns a label which may conveniently be a complete error message. One distinguished such label is just ”fail”. A failing terminal returns ”fail” by default. Other labels are created by the new expression *l which forces an immediate failure with label l. The meaning of choice e1=e2 is redefined so that if e1 fails with label ”fail”, e2 is tried in the normal way and the expression terminates with the result of e2. If e1 fails with label other than ”fail”, the whole expression fails immediately with that label without trying e2. Of course, this can only be safe before # and after ".
The technique can be used in our example like this:
E = (T / *t) + (E / *e) / T where t may be the message ”Term expected” and e the message ”Expression expected”. The result is the message ”Term expected” for a failure before # and ”Expression expected” for a failure after ". 6
The sets of ”first terminals” of e can be mechanically computed by restricting
to terminals the set First∗(e) where First is the relation describing which
expressions appear as first in the definition of a given expression. Condition (
It is suggested in [7, 8] how to find first1; first2 satisfying (
An anonymous reviewer pointed out that manually inserted cut points and labeled failures make the grammar completely unreadable. One has to find a way of conveying the information in another way. This can, for example, be done in semantic procedures, which in some parser generators (such as the author’s ”Mouse”) are separated from the grammar.
A recent note [2] to the PEG discussion forum pointed out an important fact: cut points are local to a specific expression. Their use for discarding saved results and for generating diagnostics must be considered in the context in which the expression is invoked. Suppose expression e invoked e′. Passing a cut point in e′ does not mean that e passed its cut point; e may still need its saved results. Similarly, a ”serious” termination of e′ may turn out to be an ”innocent” one in e. This must be taken into account when designing any scheme using cut points.