NimbleParsec and formal grammars

I’d like to bring together NimbleParsec and the remnants of my knowledge of grammars.

NimbleParsec can obviously parse a regular language (what regular expressions can parse). But can it also parse context-free languages? For example this one (from wikipedia)

S → SS
S → (S)
S → ()

which produces all strings with balanced parentheses, like () or ((())).

When I have production rules (eg in BNF), are there clear steps to get a NimbleParsec-parser from them?

What about “mild” context sensitive features, like remembering the name of a xml-tag to decide if the closing tag matches?

1 Like

It can by the use of post traversal and other similar functions. For example, see the XML example in the source repository.


Its really all in the examples, stupid me just looked in hexdocs.
I have to say this is more fun than writing push-down-automata in Modula-3. :nerd_face:

example how to do parentheses and also convert a production rule to a parser:

  # factor := ( expr ) | nat

  factor =
    |> choice(
        |> concat(parsec(:expr))
        |> ignore(ascii_char([?)])),

example how to be a little sensitive.

  defp match_and_emit_tag(_rest, [tag, [tag, text]], context, _line, _offset), do: ...

  defp match_and_emit_tag(_rest, [opening, [closing | _]], _context, _line, _offset),
    do: {:error, "closing tag #{inspect(closing)} did not match opening tag #{inspect(opening)}"}

thats really cool. If i remember correctly this is a real pain in theory.

1 Like