It looks like what you want to do is made more complex because of the fact that the sequence of # in the beginning must match the sequence of # at the end. That requires context-sensitive features, which are not possible on nimble_parsec as it currently works.

However, you can “cheat” your way out of context-sensitivity by relying on the fact that headers can’t go more than 6 levels deep. That way, you only need to handle 6 possibilities and it can be made to work with nimble_parsec.

For an example (which doesn’t handle markup inside the header), look at the following code:

defmodule CommonMark do
  import NimbleParsec

  ignored_whitespace =
    ascii_string([?\s], min: 1)
    |> ignore()
    |> optional()

  header_char = utf8_char(not: ?\n)

  headers =
    for n <- 6..1 do
      prefix = String.duplicate("#", n)
      suffix = " " <> prefix

      content =
        lookahead_not(string(suffix))
        |> concat(header_char)
        |> times(min: 1)
        |> reduce({List, :to_string, []})

      ignore(optional(ascii_string([?\s], max: 3)))
      |> string(prefix)
      |> concat(ignored_whitespace)
      |> concat(content)
      |> optional(ignore(string(suffix)))
      |> post_traverse(:tag_with_level)
    end

  @doc false
  def tag_with_level(_rest, [content, prefix] = _args, context, _line, _offset) do
    result = [{:header, [level: byte_size(prefix)], content}]
    {result, context}
  end

  defparsec(
    :atx_header,
    choice(headers)
  )
end

Example output:

iex(50)> CommonMark.atx_header("## abc ")
{:ok, [{:header, [level: 2], "abc "}], "", %{}, {1, 0}, 7}
iex(51)> CommonMark.atx_header("## abc #")
{:ok, [{:header, [level: 2], "abc #"}], "", %{}, {1, 0}, 8}
iex(52)> CommonMark.atx_header("# abc #")
{:ok, [{:header, [level: 1], "abc"}], "", %{}, {1, 0}, 7}
iex(53)> CommonMark.atx_header("## abc #")
{:ok, [{:header, [level: 2], "abc #"}], "", %{}, {1, 0}, 8}
iex(54)> CommonMark.atx_header("# abc")
{:ok, [{:header, [level: 1], "abc"}], "", %{}, {1, 0}, 5}
iex(55)> CommonMark.atx_header("## abc")
{:ok, [{:header, [level: 2], "abc"}], "", %{}, {1, 0}, 6}
iex(56)> CommonMark.atx_header("### abc")
{:ok, [{:header, [level: 3], "abc"}], "", %{}, {1, 0}, 7}
iex(57)> CommonMark.atx_header("### abc ###")
{:ok, [{:header, [level: 3], "abc"}], "", %{}, {1, 0}, 11}
iex(58)> CommonMark.atx_header("### abc ##")
{:ok, [{:header, [level: 3], "abc ##"}], "", %{}, {1, 0}, 10}
iex(59)> CommonMark.atx_header("# abc ##")
{:ok, [{:header, [level: 1], "abc"}], "#", %{}, {1, 0}, 7}
iex(60)> CommonMark.atx_header("####### abc")
{:ok, [{:header, [level: 6], "# abc"}], "", %{}, {1, 0}, 11}

There are some warts, but you get the idea. You have to ensure that the ### is followed by a space, that a new line or an oef() comes afterwards and stuff like that. Regarding the handling of markup inside a header, it might be better to do that in another path.

But I hope this can help you move forward.

EDIT: There are similar tricks for other context-sensitive features of markdown, which you can emulate with a simpler context-free grammar. For example, code delimited by a variable number of backticks.

On re-reading the spec, I’ve just noticed that the closing sequence of hashes doesn’t need to be the same sequence as the opening sequence. Which means I haven’t undertood your problem at all. Sorry.

@tmbb First of all, thanks for your feedback.

The specification does not mention this, I mean, the sequence of # at the end does not need to match with the sequence of # at the beginning, for example:

# foo ######
## foo #####
### foo ####
#### foo ###
##### foo ##
###### foo #

Is a valid input and it should produce something like this (if you transform the result into HTML for example):

<h1>foo</h1>
<h2>foo</h2>
<h3>foo</h3>
<h4>foo</h4>
<h5>foo</h5>
<h6>foo</h6>

But, if you provide a string like this: "### foo ### b\n" it should produce <h3>foo ### b</h3>\n as the result. That’s why I need to be sure that the optional closing sequence of #s must be preceded by a space and may be followed by spaces only (until I find the end of the string or the end of the line).

I don’t really know how to help you, except by showing you the code. You can find a working implementation here. It was written in about 15 mins and has no tests whatsoever.

It turns out the syntax is actually context-free, which is great. The way to implement such things in NimbleParsec (which is basically a PEG parser now) is to just transcribe into code the verbal description of what it should do using the available combinations.

The description in the CommonMark spec is not very easy, unfortunately, because it’s mostly a bunch of examples.

I’ve spent some time adding functionality to my markdown parser linked above. You might wish to reuse some of the rules.

Even more interestingly, I’ve build a test suite from the examples of the spec (there is a function to build that automatically if you eant to regenerate the test suite). The tests are grouped by section (sections are parsed using my AtxHeader parser) and all sections are skipped by default, but you can delete the :skip tag as you implement the functionality.

You might find that test suite useful.