I firmly disagree about the value of PEGs (and hence combinators) as a formalism that's ambiguous or hard to reason about. PEGs are as well-specified as CFGs, they just work in a different way. One of the strengths of PEGs is that they're never ambiguous. That does mean that order of alternates is important, and sometimes you do have to fiddle with that order when translating something like ABNF. But what you get in return is never having to deal with a parse forest, let alone punting on that problem by just reifying the greedy parse as the correct one.

I've written a tool that converts a declarative specification of a PEG grammar into a parser, although I haven't released it yet. It works great, I've used it on a number of real-world structured data formats.

Edit: cut out the first paragraph after checking the user name. Hi TQ.

"PEGs are never ambiguous" is equivalent to solving a problem by proclaiming the wrong solution to be correct.

In that sense, LALR parser generators (e.g. yacc) are also never ambiguous, because even if your grammar is ambiguous in the formal sense, yacc will produce a working parser with well-defined resolution of conflicts...

But the reality is,

    E = E `+` E

is intrinsically ambiguous, no matter how you want to spin it... the only difference is, that LALR generators point that out, whereas PEG generators sweep it under the rug.

I don't agree, as I've said, because PEG is a declarative formalism, and LALR is a parsing strategy. GLL implemented with graph-structured stacks can and will produce a parse forest for an ambiguous grammar, LALR will manifest one of those parses for the same grammar.

To lean on that means you have hidden information: your grammar is BNF + LALR, or BNF + GLL, not just BNF. PEGs, by contrast, are always PEGs. What you see is what you get.

A grammar in PEG format will always give you one parse, and which parse is predictable. If you want a different parse, you have to rewrite it. Indeed, as I'm sure you know, your example grammar isn't valid in the original PEG formalism, which prohibits immediate left recursion. Automatic rewrites into an intermediate rule are the leading method of allowing it.

Ambiguity is a well-defined concept in grammars, and PEGs aren't.

I've noticed that a lot of CFG enthusiasts don't like this about PEGs. They consider it inelegant, unprincipled. Some of that is aesthetic, some is unfamiliarity, and some is sunk cost: none of it actually engages with the formal expressive power of PEGs, nor their ergonomics as a practical tool for development.

Sure, I guess you're right, if you consider formal grammars as existing in their own abstract bubble removed from our reality.

I, on the other hand, am primarily interested in using grammars to parse programming languages, which are essentially a human form of communication (computers could use bitcode or lisp-style ASTs, no need for syntax).

I'm not an expert on PEGs, so this is copy-pasted from Wikipedia page on PEGs, I hope it's valid - the classical dangling else ambiguity.

     S ← 'if' C 'then' S 'else' S / 'if' C 'then' S

Now, there is an obvious ambiguity here, for a human reader (mediated, of course, by tabs). If you're using a formalism that wishes that ambiguity away, it just means that the formalism is a non-ideal one. What I like about LALR parser generators is, that they will explicitly alert you of this kind of human-level ambiguities.

It's okay that you aren't familiar with PEGs. I am familiar with PEGs, and so I know just by reading that, which way the ambiguity resolves. So for me, a human reader, there is no obvious ambiguity.

It's like saying there's an ambiguity in "not a and b". Sure, if you don't know the precedence assigned to 'not' and 'and' in your language. But you're supposed to learn those things.

Your not knowing how PEGs work is a weak argument against using them.

In my experience LPeg does a good job of being comprehensible for most reasonably-sized use cases. It can even parse the grammar of Lua itself. I've personally had not that much trouble translating BNF grammars to PEG, though the result is typically longer. It still satisfies the goal of separating parsing logic from data logic, which is a big step.

For more info on the issues with PEGs -- and a paper showing how to correctly translate general LL(1p) grammars to PEG -- see:

https://jeffreykegler.github.io/Ocean-of-Awareness-blog/indi...

LPeg also has what it calls match-time captures (http://www.inf.puc-rio.br/~roberto/lpeg/#matchtime), which can be used to parse non-context free grammars like common TLV (tag, length, value) formats. For example, I've written a pure LPeg parser for parsing PKIX objects like X.509 certificates. Example edited code snippets with some high-level and low-level bits:

  -- returns DER object pattern that captures inner value
  local function Cobject(identifier, patt)
    local match

    if lpeg.type(patt) then
      match = function (s)
        return lpeg.match(patt * -P(1), s)
      end
    elseif type(patt) == "function" then
      match = patt
    elseif patt == nil then
      match = function (s)
        return s
      end
    else
      error(sformat("expected function, pattern or nil, got %s", type(patt)), 2)
    end

    return Cmt(identifier, function (s, pos)
      local n, pos = assert(unpacklength(s, pos))
      local s1 = s:sub(pos, pos + n - 1)
      pos = pos + n

      return (function (pos, v, ...)
        if v then
          return pos, v, ...
        else
          return false
        end
      end)(pos, match(s1))
    end)
  end

  local BIT_STRING = Cobject(P"\x03", function (s)
    local pad = s:byte(1) -- first octet is number of padding bits
    assert(pad == 0, "BIT STRING not octet aligned") -- we only support DER
    return s:sub(2)
  end)

  local IA5String = Cobject(P"\x16")

  local OID = function (oid)
    if oid then
      local s = packoid(pkix.txt2oid(oid))
      return P(sformat("\x06%s%s", packlength(#s), s)) * Cc(oid)
    else
      return Cobject(P"\x06", function (s)
        return assert(unpackoid(s))
       end)
    end
  end

  local SEQUENCE = function (patt)
    return Cobject(P"\x30", patt)
  end

  local TBSCertificate = SEQUENCE(Ct(
    Cg(Version, "version") *
    Cg(CertificateSerialNumber, "serialNumber") *
    Cg(AlgorithmIdentifier, "signature") *
    Cg(Name, "issuer") *
    Cg(Validity, "validity") *
    Cg(Name, "subject") *
    Cg(SubjectPublicKeyInfo, "subjectPublicKeyInfo") *
    Cg(UniqueIdentifier(1), "issuerUniqueID")^-1 *
    Cg(UniqueIdentifier(2), "subjectUniqueID")^-1 *
    Cg(Extensions, "extensions")^-1 *
    Cg(P(1)^1, "trash")^-1
  ))

  local Signature = BIT_STRING

  local Certificate = SEQUENCE(Ct(
    Cg(TBSCertificate, "tbsCertificate") * 
    Cg(AlgorithmIdentifier, "signatureAlgorithm") * 
    Cg(Signature, "signature")
  ))