Just Write the Parser

2) This looks more like Pratt parsing vs. the approach described in the article

3) I was asking the original author

  -- 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")
  ))

What I realized after writing most of my comment was that the author was primarily interested in explaining a recursive descent parser, and the arguments you quoted were simply a hook to get people interested.

That's why I phrased my objection to not _fully_ answering the question.

And it's a good question, so I thought the other side deserved some exploration.

> You should hand-roll a parser first, and then, when you see the limitations of your hand-rolled parser, adopt a parser generator, now with full understanding of what the generator is doing for you (and not doing for you).

Writing your own recursive descent parser only teaches you recursive descent. So, sure, you'll have a clear idea of what a parsec derivative is doing since that's also RD, but it won't help you understand what a LALR parser generated by yacc is doing.

The other problem is for someone to use your parser in another language, they have to port the whole thing and maintain that port as your language changes. Talking about "the first time you write it" and pedagogical uses is entirely fair, but it's only the beginning of the story.

> To be convincing, you'd need to do what the author did, (even though you say the author didn't): you'd need to justify your argument with specific examples.

Nope, never said the author didn't provide examples. To be clear, it's an excellent tutorial on how to write a RD parser.

I'm not prepared to rewrite a bunch of code in two styles, but you're welcome to take a look at the expression parser[1].

In this case, I didn't want to write a whole precedence scanner for expressions, and I wanted precedence to be clear to a reader.

So there's some nuance I didn't capture: in Haskell parsing, writing your own RD parser starts to look like parsec because it's such a natural expression of the problem.

If I was going to write my own parsec, I could still probably use an existing combinator[3] because the parsec model is so generic. That's why I wanted to use that to do a more human readable, and thus more complex, syntax.

But, as I mentioned above, recursive descent kinda sucks. As an example, take the parsing for the left-hand side of an assignment[2]. Sometimes I have 'try' calls, other times I don't. Sometimes the ordering around alternatives (the operator) matters, sometimes it doesn't.

I know in abstract why it works one way or another. But, honestly, most of that is in there because it got tests to pass. My interest is in writing a language, not a parser.

And that's really why I switched from megaparsec to a parser generator. Once I got my grammar to be (reasonably) unambiguous, my source was just the plain, trivially readable BNF rules, and I nuked those stupid tests.

[1]: https://gitlab.com/contravariance/tenet-haskell/-/blob/0640c...

[2]: https://gitlab.com/contravariance/tenet-haskell/-/blob/0640c...

[3]: https://hackage.haskell.org/package/parser-combinators-1.2.1...

My working approach is if you're writing a compiler, it wants to have an unambiguous grammar and shouldn't even attempt recovery. If input doesn't parse, the compiler can recommend (or just run) the linter. That keeps the common case fast and simple.

The linter/fixer can have a relaxed syntax specifically designed to handle messy code and suggest corrections. That comes from a philosophy of treating error correction and user assistance as a separate task.

But that's an approach I'm taking because I want to get a reference implementation together as quickly as possible. It's definitely not how modern IDEs work.

JetBrains GrammarKit uses a PEG[1] because they need strong support for error recovery[2] using hints. Another interesting library is Tree-sitter[3]; it does incremental parsing keeping an AST constantly up to date for you.

Relevant to this whole discussion, GvR wrote a series on PEG parsers[4] in which he starts out by writing one by hand and then shows how to write one that accepts a grammar.

[1]: https://github.com/JetBrains/Grammar-Kit

[2]: https://github.com/JetBrains/Grammar-Kit#attributes-for-erro...

[3]: https://tree-sitter.github.io/tree-sitter/

[4]: https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d...

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