3 ms·

I agree with everything you say, except your advice to use a parser combinator library, because most implement PEGs. Hammer is, of course, an exception to this,

I agree with everything you say, except your advice to use a parser combinator library, because most implement PEGs. Hammer is, of course, an exception to this, as long as you call `h_compile` to tell it to use a different backend. Why not use PEGs? In short, they don't actually remove ambiguity from your grammar, but rather hide it in ways that are difficult to reason about. You're still dependent on code as a definition of the language that you accept, and worse, that code is very fragile in the face of refactoring. Further, the lexical analysis step is generally the source of most ambiguity, and most parser combinator libraries make it extremely inconvenient to parse something that isn't a character stream. (Hammer is actually worse than most here; it's not possible to use it to parse anything other than streams of bytes, though perhaps it can be excused because of the limitations of C)

samatman 6y ago
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.
- tomp 6y ago
  "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.
  - samatman 6y ago
    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.
    - tomp 6y ago
      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.
      - samatman 6y ago
        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.
scythe 6y ago
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/individual/2015/03/peg.html https://jeffreykegler.github.io/Ocean-of-Awareness-blog/indi...
- wahern 6y ago
  LPeg also has what it calls match-time captures (http://www.inf.puc-rio.br/~roberto/lpeg/#matchtime 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") ))

samatman 6y ago

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.

tomp 6y ago
"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.
- samatman 6y ago
  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.
  - tomp 6y ago
    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.
    - samatman 6y ago
      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.

scythe 6y ago

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/individual/2015/03/peg.html https://jeffreykegler.github.io/Ocean-of-Awareness-blog/indi...

wahern 6y ago
LPeg also has what it calls match-time captures (http://www.inf.puc-rio.br/~roberto/lpeg/#matchtime 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") ))