9
$\begingroup$

Parsing expression grammars (PEGs) are unambiguous and have a superficially similar syntax to BNF, but include three important differences:

  1. The ordered choice operator e1 / e2 / e3.
  2. The and predicate &.
  3. The not operator !.

I have a few questions:

  1. Are the languages recognized by PEGs all context-free?
  2. If the answer to (1) is no, are there any expressive grammar formalisms guaranteed to produce only unambiguous grammars? In particular, would dropping & and ! yield only context-free grammars?
  3. If all PEGs are context-free, can they converted into an equivalent BNF via an algorithm?

The context is that I'd like to compute generating functions for a PEG library using the Chomsky–Schützenberger enumeration theorem. This seems to require a specification of the grammar in a standard form similar to BNF.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$
  1. Are the languages recognized by PEGs all context-free?

No, as is pointed out by Brian Ford in his 2004 paper introducing PEGs, from which is the following short quote:

Theorem: The class of PELs includes non-context-free languages.

Proof: The classic example language $a^nb^nc^n$ is not context-free, but we can recognize it with a PEG $G = (\{A, B, D\}, \{a, b, c\}, R, D)$, where R contains the following definitions: $$A \leftarrow aAb / ε$$ $$B \leftarrow bBc / ε$$ $$D \leftarrow \&(A !b) a^∗ B !.$$

 

  1. If the answer to (1) is no, are there any expressive grammar formalisms guaranteed to produce only unambiguous grammars? In particular, would dropping $\&$ and $!$ yield only context-free grammars?

Even without $!$ (and therefore without $\&$, since it is formally defined in terms of $!$), you would still have to deal with the implicit complement hidden in the definition of ordered choice. I don't have a concrete example of ordered choice leading to a non-CFL, but I would try to find one by starting with two CFGs $L_1$ and $L_2$ whose difference is not a CFL and which can be converted to PEGs $P_1$ and $P_2$. Now, if $\mathbb{c}$ is some symbol not in either language, then the PEG $P_2 / P_1\mathbb{c}$ should recognize $L_2 \cup (L_1- L_2)\mathbb{c}$, which is not a CFL.

  1. If all PEGs are context-free, can they converted into an equivalent BNF via an algorithm?

If my conjecture above is correct, then this question is not applicable, but in any case there is no algorithm I know of to convert between PEGs and CFGs, and I believe that equivalence of a PEG and a CFG is undecidable. This fact complicates the proof procedure I propose above. :)

Improve this answer
$\endgroup$
5
  • $\begingroup$ I'm not sure I follow your $P_1/P_2\mathbb{C}$ example. From the paper "PEGs use a prioritized choice operator ‘/’. This operator lists alternative patterns to be tested in order, unconditionally using the first successful match." Any string including $\mathbb{C}$ would fail the first condition, so the language recognized is $L_1\cup (L_2\mathbb{C})$, which is clearly context-free. $\endgroup$
    – Lucas Wiman
    Feb 23, 2017 at 18:00
  • $\begingroup$ "I believe that equivalence of a PEG and a CFG is undecidable" That's likely true but irrelevant. Many procedures generate equivalent specifications (e.g. conversion to Chomsky Normal Form) even if deciding the equivalence of arbitrary grammars is undecidable. $\endgroup$
    – Lucas Wiman
    Feb 23, 2017 at 18:02
  • 1
    $\begingroup$ @recursively: that's not how PEG ordered choice works. The fallback to $L_2\mathbb{c}$ only happens if $L_1$ doesn't match. If it does match, the fact that the pattern subsequently fails does not cause a fallback. Ordered choice is not just a way of disambiguating parses. $\endgroup$
    – rici
    Feb 23, 2017 at 20:10
  • 1
    $\begingroup$ Ah OK, TIL. Wouldn't the language then be $L_1\cup (L_2 - L_1)\mathbb{c}$? In any case, your underlying point seems correct, so the Chomsky–Schützenberger theorem doesn't apply. I'll need to switch my project to support a more standard parsing library based on CFGs. Thanks! $\endgroup$
    – Lucas Wiman
    Feb 23, 2017 at 22:37
  • $\begingroup$ @RecursivelyIronic: Yes, you're right, I should have written it as set difference, and I've fixed the answer. Thanks. (I personally find PEG semantics hard to reason about, but some of that is lack of experience. Which is all very circular. But I wouldn't use them in a context where I wanted to analyse or transform the grammar, precisely because of the difficulty of analysing and/or transforming PEG grammars.) $\endgroup$
    – rici
    Feb 24, 2017 at 4:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.