minipeg

defmodule Minipeg do
  @moduledoc ~S"""
  # Minipeg is a minimal _Parse Expression Grammars_ (PEG) Library

  Here is a first taste of how to use it:

      iex(1)> an_a_parser = char_parser("a")
      ...(1)> parse_string(an_a_parser, "a")
      {:ok, "a"}

      iex(2)> an_a_parser = char_parser("a")
      ...(2)> parse_string(an_a_parser, "b")
      {:error, "b not member of \"a\" in char_parser(\"a\")"}

  The first thing to note here is that in these doctests we have imported functions from
  Minipeg as follows, see the moduledocs of the corresponding modules for details

    ```elixir
      import Minipeg.Parser, only: [parse_string: 2]
      import Minipeg.{Combinators, Parsers}
    ```

  ## Basic Usage

  Quite a small subset of predefined [parsers](#module-definitions) and [combinators](#module-definitions)
  would suffice to parse any [context free language](https://en.wikipedia.org/wiki/Context-free_language), however many of the patterns used to parse
  programming languages, little languages or small languages that exceed the practicallity of [regular expressions](https://en.wikipedia.org/wiki/Regular_expression)
  are quite verbose.

  Therefore Minipeg predefines parsers that can be easily parametrized. These parsers will be described in the [utility parsers](#moduledoc-utility-parsers) section.


  ### Parsing Single Characters

  With a _character_ we do indeed mean a UTF-8 Code Point

  The most basic parser is the...

  #### `char_parser`

  ... which parses _any_ character

      iex(3)> parse_string(char_parser(), "h")
      {:ok, "h"}


      iex(4)> parse_string(char_parser(), "é")
      {:ok, "é"}


      iex(5)> parse_string(char_parser(), "✓")
      {:ok, "✓"}

      iex(6)> parse_string(char_parser(), "")
      {:error, "encountered end of input in char_parser()"}

  It can however be parametrized to parse only characters of a given set, this set can be provided as
  a `String` or an `Enumerable`


      iex(7)> parse_string(char_parser("ab"), "b")
      {:ok, "b"}

      iex(8)> parse_string(char_parser(["b", "c"]), "b")
      {:ok, "b"}


      iex(9)> parse_string(char_parser(["b", "c"]), "a")
      {:error, "a not member of \"bc\" in char_parser([\"b\", \"c\"])"}

  Often used charsets might be extremly large to be defined and therefore some more specialised parsers have been defined:

  #### Parsing POSIX character classes

  If instead of a string or list we pass an atom into `char_parser` it only parses a character if it matches a character class as defined in POSIX regular expressions,
  which are also described in the docs of the [`Regex`](https://hexdocs.pm/elixir/Regex.html#module-character-classes) module, here are the currently supported values:

  ```
    :alnum | :alpha | :blank | :cntrl | :digit | :graph | :lower | :print | :punct | :space | :upper | :word | :xdigit
  ```

      iex(10)> parser = char_parser(:alnum)
      ...(10)> "aD7_%"
      ...(10)> |> String.graphemes
      ...(10)> |> Enum.map(&parse_string(parser, &1))
      [
        ok: "a",
        ok: "D",
        ok: "7",
        error: "Regex ~r/[[:alnum:]]/ does not match \"_\" in char_parser(:alnum)",
        error: "Regex ~r/[[:alnum:]]/ does not match \"%\" in char_parser(:alnum)"
      ]


  #### `escaped_char_parser`

  this parser helps to parse escaped characters, while one could de this quite easily with the following example, one notices
  that in order to get just an escpaed character two combinators, `map` and `sequence` are needed

      iex(11)> escaped_quote_parser = sequence([
      ...(11)> char_parser("\\"), char_parser()])
      ...(11)> |> map(&Enum.at(&1, 1))
      ...(11)> { parse_string(escaped_quote_parser, "\\\""), parse_string(escaped_quote_parser, "\\'") }
      { {:ok, "\""}, {:ok, "'"} }

  Compare this to the provided `escaped_char_parser`:

      iex(12)> parse_string(escaped_char_parser(), "\\a")
      {:ok, "a"}

  We can also change the escape character

      iex(13)> parse_string(escaped_char_parser("%"), "%a")
      {:ok, "a"}

      iex(14)> parse_string(escaped_char_parser("%"), "\\a")
      {:error, "\\ not member of \"%\" in char_parser(\"%\") in escaped_char_parser(%)"}

  And furthermore we can restrict the set of which characters are allowed to be escaped

      iex(15)> parser = escaped_char_parser("\\", "escape only \\", "\\")
      ...(15)> { parse_string(parser, "\\\\"), parse_string(parser, "\\a") }
      { {:ok, "\\"}, {:error, "a not member of \"\\\\\" in char_parser(\"\\\\\") in escape only \\"} }

  ### Parsing sequences of characters

  #### Keywords: `keywords_parser`

  Does pretty much what is expected ;)

      iex(16)> kwd_parser = keywords_parser(["do", "else", "if"])
      ...(16)> ["do", "if", "for"]
      ...(16)> |> Enum.map(&parse_string(kwd_parser, &1))
      [
        ok: "do",
        ok: "if",
        error: "no alternative could be parsed in keywords_parser([\"do\", \"else\", \"if\"])"
      ]

  #### Identifiers: `ident_parser`
          
  An identifier is defined by a character class for its first character and a character class for its subsequent characters, so
  one could define it roughly as

          sequence([
            first_char_parser,
            many(second_char_paser)])

  And that is how the `ident_parser` is actually defined

      iex(17)> parse_string(ident_parser(), "hello_42")
      {:ok, "hello_42"}

      iex(18)> parse_string(ident_parser(), "42hello_world")
      {:error, "Regex ~r/[[:alpha:]]/ does not match \"4\" in char_parser(:alpha) in sequence"}

  In Lisp we prefer `-` to `_`, no problem

      iex(19)> parse_string(ident_parser("Lisp Style", additional_chars: "-"), "hello-42")
      {:ok, "hello-42"}

  But even the parser for the first character and the following characters can be defined

          iex(20)> register_parser = ident_parser(
          ...(20)>   "Uppercase and digit",
          ...(20)>   first_char_parser: char_parser(:upper),
          ...(20)>   rest_char_parser: char_parser(:digit),
          ...(20)>   additional_chars: nil, 
          ...(20)>   max_len: 2,
          ...(20)>   min_len: 2)
          ...(20)> [
          ...(20)>   parse_string(register_parser, "R2"),
          ...(20)>   parse_string(register_parser, "X_"),
          ...(20)>   parse_string(register_parser, "R12"),
          ...(20)>   parse_string(register_parser, "a2"),
          ...(20)>   parse_string(register_parser, "ab")
          ...(20)> ]
          [
            ok: "R2",
            error: "string \"X\" length 1 under required minimum 2",
            error: "string \"R12\" length 3 exceeds allowed 2",
            error: "Regex ~r/[[:upper:]]/ does not match \"a\" in char_parser(:upper) in sequence",
            error: "Regex ~r/[[:upper:]]/ does not match \"a\" in char_parser(:upper) in sequence"
          ]

  ## Predefined Combinators

  ### `sequence`

  Takes a list of `Parsers`, only parses if **all** of them parse subsequently on the given
  input and return a list of the results of each parser.

  Let us _remimplement_ the keywords parser

      iex(21)> if_parser = sequence([char_parser("i"), char_parser("f")])
      ...(21)> |> map(&Enum.join/1)
      ...(21)> ~w[if else]
      ...(21)> |> Enum.map(&parse_string(if_parser, &1))
      [ 
        ok: "if",
        error: "e not member of \"i\" in char_parser(\"i\") in sequence"
      ]

  This leads us directly to

  ### `map`

  Map, takes a parser and a _mapping function_. It returns a new parser that fails with exactly
  the same error message as its input parser, but succeeds with the result mapped by the _mapping function_.

      iex(22)> list_parser = many(char_parser()) |> map(&Enum.join(&1, ", "))
      ...(22)> parse_string(list_parser, "abc")
      {:ok, "a, b, c"}

  ### What about whitespace
          
  Oftentimes whitespace shall be ignored in the resulting ast, and sometimes in the input too. To be more precise
  when whitespace stops parsing of example a keyword then the subsequent patser often is not interested in$
  the left ofer ws preceeding its new input.

  Enter `ignore_ws`

  Here is the form that does not ignore newlines, which is the default:
      iex(23)> next_char_parser = ignore_ws(char_parser())
      ...(23)> parse_string(next_char_parser, " \ta")
      {:ok, "a"}

      iex(24)> next_a_parser = ignore_ws(char_parser("a"))
      ...(24)> parse_string(next_a_parser, " \na")
      {:error, "\n not member of \"a\" in char_parser(\"a\")"}

  But we can also use the newline allowing version

      iex(25)> next_a_parser = ignore_ws(char_parser("a"), "skip newlines", true)
      ...(25)> parse_string(next_a_parser, " \na")
      {:ok, "a"}


  ## Definitions

  ### Parser

  A `Parser` is a struct that parses an `Input` struct (with the `parse` function) and either returns a `Success` or `Failure` struct

  In order to abstract the internal representations of input and results  the `parse_string` function is provided as shown in the exampleas above.

  The `Success` struct contains the resulting Abstract Syntaxt Tree and the rest of the input as an `Input` struct.

  The `Failure` struct contains the original `Input` struct and an error message

  Internally a `Cache` is already returned (and passed into subsequent `parse` calls of the `Parser` module) but unless
  you are extending `Minipeg` itself by defining parsers by hand instead of using `Combinators` you can ignore this.

  ### Combinator

  A `Combibator` is a function that takes a `Parser` optionally some arguments and returns a new `Parser`
  """
end
# SPDX-License-Identifier: Apache-2.0