bitwalker / combine Goto Github PK

I am using Combine to parse arbitrary user input, which involves sometimes to deal with unicode characters (for instance, quotes such as “ and ”).
However, Combine doesn't seem to like them much…

17:37:20.242 [error] Process #PID<0.335.0> raised an exception
** (FunctionClauseError) no function clause matching in Combine.Parsers.Text.char_impl/2
    lib/combine/parsers/text.ex:67: Combine.Parsers.Text.char_impl(%Combine.ParserState{column: 43, error: nil, input: <<128, 156, 73, 39, 109, 32, 103, 111, 105, 110, 103, 32, 116, 111, 32, 107
, 105, 108, 108, 32, 121, 111, 117, 33, 226, 128, 157, 34>>, line: 1, results: [], status: :ok}, 34)
    lib/combine/parsers/base.ex:172: Combine.Parsers.Base.do_pipe/3
    lib/combine/parsers/base.ex:161: Combine.Parsers.Base.pipe_impl/3
    lib/combine/parsers/base.ex:172: Combine.Parsers.Base.do_pipe/3
    lib/combine/parsers/base.ex:161: Combine.Parsers.Base.pipe_impl/3
    lib/combine/parsers/base.ex:69: Combine.Parsers.Base.map_impl/3
    lib/combine/parsers/base.ex:172: Combine.Parsers.Base.do_pipe/3
    lib/combine/parsers/base.ex:161: Combine.Parsers.Base.pipe_impl/3

Hello, Paul! I may have found a bug, but I also might be using the library wrong. Either way, I don't know if it's write for Combine to throw an error like this.

I ran into the following problem:

iex(1)> str = """
...(1)> PANDA "bamboo", CURRY "noodle"
...(1)> """
"PANDA \"bamboo\", CURRY \"noodle\"\n"
iex(2)> Combine.parse(str, Example.separated_property_pairs())
** (FunctionClauseError) no function clause matching in anonymous fn/1 in Combine.Parsers.Base.pair_right_impl/3

    The following arguments were given to anonymous fn/1 in Combine.Parsers.Base.pair_right_impl/3:

        # 1
        [:__ignore, :__ignore, ["CURRY", "noodle"]]

    (combine) lib/combine/parsers/base.ex:234: anonymous fn/1 in Combine.Parsers.Base.pair_right_impl/3
    (combine) lib/combine/parsers/base.ex:154: Combine.Parsers.Base.pipe_impl/3
    (combine) lib/combine/parsers/base.ex:315: Combine.Parsers.Base.many1_impl/2
    (combine) lib/combine/parsers/base.ex:347: Combine.Parsers.Base.many_impl/2
    (combine) lib/combine/parsers/base.ex:163: Combine.Parsers.Base.do_pipe/3
    (combine) lib/combine/parsers/base.ex:152: Combine.Parsers.Base.pipe_impl/3
    (combine) lib/combine.ex:52: Combine.parse/2

The parser code looks like this:

defmodule Example do
  @moduledoc "Module showing off an issue I've encountered with `Combine`"

  use Combine

  @doc "Entrypoint here!"
  def separated_property_pairs do
    sep_by1(property_pair(), comma_and_whitespace())
  end
  
  def property_pair do    
    sequence([property_name(), ignore(whitespace()), property_value()])
  end

  def property_value do
    quoted_string()
    |> label("PropertyValue")
  end
  
  def property_name do
    ~r{[A-Z]}
    |> word_of()
    |> label("PropertyName")
  end
  
  def comma_and_whitespace do
    ","
    |> char()
    |> ignore()
    |> many(whitespace())
    |> ignore()
  end

  def quoted_string(previous \\ nil) do
    previous
    |> between(char("\""), words(), char("\""))
    |> label("QuotedStringValue")
    |> map(&Enum.join(&1, ""))
  end

  def words do
    many(either(word(), whitespace()))
  end
  
  def whitespace do
    [space(), tab(), newline()] |> choice()
  end
end

There doesn't seem to be a way to differentiate inputs where there was some extra characters at the end from inputs where the whole string was consumed.

iex(16)> Combine.parse("aaaaa", many(char("a")))
[["a", "a", "a", "a", "a"]]
iex(17)> Combine.parse("aaaaab", many(char("a")))
[["a", "a", "a", "a", "a"]]

Is this by design? If yes then maybe there should be another parsing function that rejects such strings.

I'm building a compiler using this awesome lib, then sometimes I need get a error message from on parser inside of many, sequence or something like it.

For example, in this situation it works:

Combine.parse("ABC", fatal("something wrong happened!")) # {:error, "something wrong happened!"}

But, if I use many, for example, I can't get this error message

Combine.parse("ABC", many(fail("something wrong happened!"))) # [[]]

How to get the error message?

A very strange thing happens when using either(float, integer). I don't know if this is a bug, or if I am doing something wrong.

My very simple parser module

defmodule Jux do

  use Combine

  def parse(str) do
    Combine.parse(str, parser())
  end

  def parser do
    whitespace()
    |> many1(sequence([term(), whitespace()]))
  end

  def whitespace do
    ignore(option(spaces()))
  end

  def term do
    number()
  end

  def number do
    either(float(), integer())
  end

end

This crashes if there is a non-floating-point number somewhere before the end of the parsed statement.

Inputs that work:

iex> Jux.parse("2.0")
[[2.0]]
iex> Jux.parse("    2.0")
[[2.0]]
iex> Jux.parse("2.0   3")
[[2.0, 3]]
iex> Jux.parse("3")
[[3]]

Inputs that do not work:

iex> Jux.parse("2.0 3 ")
** (ArgumentError) argument error
    :erlang.binary_to_float("3")
    lib/combine/parsers/text.ex:568: Combine.Parsers.Text.float_impl/1
    lib/combine/parsers/base.ex:105: Combine.Parsers.Base.either_impl/3
    lib/combine/parsers/base.ex:163: Combine.Parsers.Base.do_pipe/3
    lib/combine/parsers/base.ex:152: Combine.Parsers.Base.pipe_impl/3
    lib/combine/parsers/base.ex:330: Combine.Parsers.Base.many1_loop/5
    lib/combine/parsers/base.ex:316: Combine.Parsers.Base.many1_impl/2
    lib/combine.ex:52: Combine.parse/2
iex> Jux.parse("2 3")
** (ArgumentError) argument error
    :erlang.binary_to_float("2")
    lib/combine/parsers/text.ex:568: Combine.Parsers.Text.float_impl/1
    lib/combine/parsers/base.ex:105: Combine.Parsers.Base.either_impl/3
    lib/combine/parsers/base.ex:163: Combine.Parsers.Base.do_pipe/3
    lib/combine/parsers/base.ex:152: Combine.Parsers.Base.pipe_impl/3
    lib/combine/parsers/base.ex:330: Combine.Parsers.Base.many1_loop/5
    lib/combine/parsers/base.ex:316: Combine.Parsers.Base.many1_impl/2
    lib/combine.ex:52: Combine.parse/2

What is going wrong here?

Hi, first of all thanks for the great library :)

I was trying to parse simple hyphenated words but apparently word is not the right choice. Example:

Interactive Elixir (1.3.4) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> use Combine
Combine.Parsers.Binary
iex(2)> Combine.parse("foo-bar", word)
["foo"]  # I was expecting ["foo-bar"]

Is this intentional?

I am not getting the expected behavior with take_while -- but perhaps it is just me:-)

When I do the following, according to the examples in the docs, I get what is expected:

iex(3)> parser = take_while(fn ?a -> true; _ -> false end)
#Function<34.105957604/1 in Combine.Parsers.Text.take_while/2>
iex(4)> Combine.parse("aaaaabbbbb", parser)
['aaaaa']

Now I want to accept strings that do not have characters in a specific list:

iex(5)> parser2 = take_while(fn a -> !Enum.member?(['-', '='], a) end)
#Function<34.105957604/1 in Combine.Parsers.Text.take_while/2>
iex(6)> Combine.parse("aaaaabbbbb", parser2)                          
['aaaaabbbbb']
iex(7)> Combine.parse("aaaaa-bbbbb", parser2)
['aaaaa-bbbbb']

The first string above should be accepted, but in the second
case, one should get just ['aaaaa']

I tried a few more tests to see what I was missing:

iex(8)> foo = fn a -> !Enum.member?(['-', '='], a) end
#Function<6.52032458/1 in :erl_eval.expr/5>
iex(9)> foo.('G')
true
iex(10)> foo.('-')
false
iex(11)> parser3 = take_while(foo)
#Function<34.105957604/1 in Combine.Parsers.Text.take_while/2>
iex(12)> Combine.parse("aaaaa-bbbbb", parser3)         
['aaaaa-bbbbb']
iex(13)> Combine.parse("aaaaabbbbb", parser3) 
['aaaaabbbbb']

Might have missed this, but the library seems to be missing a feature for chaining sequential operations?
Something along the lines of an and_then function/parser?

The parser would take as input the parser to chain a sequential computation with; and a function that would take the results of previously said parser, and returns another parser for further parsing.

This could be for example useful when later parsed input depends on earlier parsed input.
e.g. XML: checking if closing tag is same as opening tag.

Some pseudo-code (out of a lib I'm working on atm) that hopefully showcases the use-case where this could be used, closing_tag is a helper function that returns a parser based on a string input argument (the opening tag):

def tag_with_content_parser() do
    tag_with_attributes = sequence([tag(), many(attribute())])
    between(char("<"), tag_with_attrs, char(">"))
    |> and_then(fn [tag, attributes] ->
        sequence([value_parser(), ignore(closing_tag(tag))])
        |> map(fn [inner_contents] ->
            %XML.Tag{name: tag, attributes: attributes, value: inner_contents}
        end)
    end)
end

Side note: in Haskell this kind of function is heavily used when utilizing the monad interface of the parser type, a.k.a. the >>=/bind/flat_map operator.

For now, I will do it with a work-around, but this would be a very powerful feature to have since it allows specifying dependencies between multiple parsing steps.

Hello,

I would like to migrate from leex and yecc (Erlang's versions of the famous lex and yacc LALR parsing toolset) to this library but I'm concerned about the time complexity of top-down recursive descent parsing because my Elixir program needs to parse input files that can be several gigabytes in size. 😱

I skimmed through this library's code and didn't find any use of backtracking, which is the main cause of exponential time complexity in recursive descent parsers, so it appears that this library can determine whether a given input string (1) parses correctly or (2) has errors in linear time. 🏃💨

Is this correct? How would you characterize the time and space complexity of the parsers generated by this library? Could they benefit from any further optimization, such as packrat memoization? 🐀 (Edit: Oops, of course memoization wouldn't help when there's no backtracking! 😥)

Thanks for your consideration.

On erlang 19, elixir 1.3, I get this error:

== Compilation error on file lib/combine/parsers/text.ex ==
** (CompileError) Elixir.Combine.Parsers.Text: function float_impl/1+43:
  Internal consistency check failed - please report this bug.
  Instruction: {call,4,{f,129}}
  Error:       {multiple_match_contexts,[{x,0},1]}:

    (stdlib) lists.erl:1338: :lists.foreach/2
    (stdlib) erl_eval.erl:670: :erl_eval.do_apply/6

I'm trying to apply custom error on satisfy parser by using satisfy(...) |> label(...). This basically works, but the reported column number is not correct.

If a predicate fails the parser state is at the position after the failed term, since the term has been properly matched by the inner parser. The lineno/col is properly included in the generated error, but if I want to customize error using label, then the new parser state will be used, and thus contain a wrong error number.

As far as I can tell, a proper fix would be to reset line and column to initial values here. I tried it locally and it works.

I can prepare the pull if you agree, but wanted to check first if you agree this is the proper way to go? I'm fairly new to combinators, so I might be missing something here.

I think it might be more convenient to play around Keyword rather than List

While working with the Combine parser, I've found the strange behaviour presented below:

import Combine.Parsers.Base; import Combine.Parsers.Text
p = many char
Combine.parse "abcde", p
> [["a", "b", "c", "d", "e"]]
Combine.parse "aaaaa", p
> [["a", "a", "a"]]

p = many char("a")
Combine.parse "abcde", p
> [["a"]]
Combine.parse "aaabb", p
> [["a", "a"]]
Combine.parse "aaaaa", p
> [["a", "a", "a"]]

Is this correct? (If so, why? I expected all the "a"s to be parsed...)

I use Elixir 1.1.1 (Erlang/OTP 18), and Combine 0.6.0.

Using sep_by with a simple parser works fine...

test "sep_by with single parser (passes)" do
  multiple = sep_by(string("txt"), char(","))
  assert [["txt", "txt"]] == Combine.parse("txt,txt", multiple)
end

... but using it with a composed parser fails with an exception. Am I missing something?

test "sep_by with parser composition (fails)" do
  composed_parser = string("txt") |> string("2")
  multiple = sep_by(composed_parser, char(","))
  assert [[["txt", "2"], ["txt", "2"]]] == Combine.parse("txt2,txt2", multiple)
end

** (FunctionClauseError) no function clause matching in anonymous fn/1 in Combine.Parsers.Base.pair_right_impl/3
     stacktrace:
       (combine) lib/combine/parsers/base.ex:234: anonymous fn([",", "txt", "2"]) in Combine.Parsers.Base.pair_right_impl/3
       (combine) lib/combine/parsers/base.ex:154: Combine.Parsers.Base.pipe_impl/3
       (combine) lib/combine/parsers/base.ex:315: Combine.Parsers.Base.many1_impl/2
       (combine) lib/combine/parsers/base.ex:347: Combine.Parsers.Base.many_impl/2
       (combine) lib/combine/parsers/base.ex:163: Combine.Parsers.Base.do_pipe/3
       (combine) lib/combine/parsers/base.ex:152: Combine.Parsers.Base.pipe_impl/3
       (combine) lib/combine/parsers/base.ex:385: Combine.Parsers.Base.sep_by_impl/3
       (combine) lib/combine.ex:52: Combine.parse/2

Currently, defparser is not a part of the public api. However, we have encountered some situations where we needed to create additional parsers. Would you mind if this API was documented and officially supported?

Some of these parsers might be in fact useful for the Combine itself, but it's too early to tell. So I'd like to have an option to first create such parsers in our project (which resolves our immediate problems), and then once/if they prove useful, send a PR upstream.

Recently, in commit 27b0253, typspecs have been added. One of them specifies that the input in %ParserState{} is always supposed to be a string. It is true that some parsers (e.g. Parsers.String and Parsers.Binary) require string input. However, I think most/all in Parsers.Base don't care about the input type. Moreover, in our project, we're actually using non-string inputs (list of custom tokens), and easily process them with our custom parsers + the ones from Parsers.Base. Unfortunately, due to current typespec in Combine, we get a lot of dialyzer errors.

So I'd like to propose relaxing typespec for the input. One option is to allow binary | [any], another is to just use any. For our case, I think the former option will suffice. If you're fine with this, I'll be happy to prepare a PR.

I have another, more complex question. Would you be open to the idea of supporting inputs which are not strings?

The main thing I'd like to have is a list of terms as input. Basically, I'd like to use say leex to tokenize the input, and then combine to work on the grammar. Currently, the code is a bit clunky for more complex grammars, since tokenizing and parsing is conflated. For example, working with whitespaces is a bit hard, because we need to ignore them in many different places.

So the question is would you consider such option?

I'll cc my colleague @obrok here, as he also might find this discussion interesting :-)

It's a sad day when all error messages say line 1.

  defparser correct_newline(%ParserState{} = state) do
   do_newline(state)
  end
  defp do_newline(%ParserState{status: :ok, line: line, input: <<?\n::utf8,rest::binary>>, results: results} = state) do
   %{state | :column => 0, :line => line + 1, :input => rest, :results => ["\n"|results]}
  end
  defp do_newline(%ParserState{status: :ok, line: line, input: <<?\r::utf8,?\n::utf8,rest::binary>>, results: results} = state) do
    %{state | :column => 0, :line => line + 1, :input => rest, :results => ["\n"|results]}
  end
  defp do_newline(%ParserState{status: :ok, line: line, column: col, input: <<?\r::utf8,c::utf8,_::binary>>} = state) do
    %{state | :status => :error, :error => "Expected CRLF sequence, but found `\\r#{<<c::utf8>>}` at line #{line}, column #{col + 1}."}
  end
  defp do_newline(%ParserState{status: :ok, input: <<?\r::utf8>>} = state) do
    %{state | :status => :error, :error => "Expected CRLF sequence, but hit end of input."}
  end
  defp do_newline(%ParserState{status: :ok, line: line, column: col, input: <<c::utf8,_::binary>>} = state) do
    %{state | :status => :error, :error => "Expected newline but found `#{<<c::utf8>>}` at line #{line}, column #{col + 1}."}
  end
  defp do_newline(%ParserState{status: :ok, input: <<>>} = state) do
    %{state | :status => :error, :error => "Expected newline, but hit end of input."}
  end

Here's what I had to do in my project.

== Compilation error on file lib/combine/parsers/text.ex ==
** (CompileError) Elixir.Combine.Parsers.Text: function float_impl/1+43:
  Internal consistency check failed - please report this bug.
  Instruction: {call,4,{f,129}}
  Error:       {multiple_match_contexts,[{x,0},1]}:

    (stdlib) lists.erl:1338: :lists.foreach/2
    (stdlib) erl_eval.erl:670: :erl_eval.do_apply/6

I'm getting this error which I believe is due to Erlang 19 breaking something. I'm actually having quite a few problems with OTP 19.

I've got no idea on what information to give. I'm on Ubuntu 16.04 64-bit. Elixir version is 1.3

First off - is there a better forum for my questions? They are not issues with Combine, but rather are problems due to my lack of experience. I very much appreciate your help and will try to keep questions to a bare minimum as I learn Combine.

The problem. The parsing functions that I write work in isolation but not when I combine them. Here is an example (in module MU.Parse):

  def str2(input) do
    parser = take_while(fn(a) -> !Enum.member?('-=+*\n\r', a) end)
    input |> Combine.parse(parser)
  end

And here is verification that it works:

iex(6)> MU.Parse.str2("foo\nbar")
['foo']

But when I try to use Parse.str2 inside Combine.parse, I get an error:

iex(1)> use Combine
Combine.Parsers.Binary

iex(2)> MU.Parse.str2("foo-bar")
['foo']

iex(4)> Combine.parse("[foo bar]", sequence([char("["), MU.Parse.str2(), char("]")]))
** (UndefinedFunctionError) function MU.Parse.str2/0 is undefined or private. Did you mean one of:

      * str2/1

    (mu_server) MU.Parse.str2()

There seems to be an arity problem, but MU.Parse.str2 in place of MU.Parse.str2() doesn't work either.

This definitely surprised me. The checks are just for == against String.upper and String.lower, which don't do anything with symbols...

iex(3)> "[Option" |> Combine.parse(Combine.Parsers.Text.upper())
["["]
iex(4)> "[Option" |> Combine.parse(Combine.Parsers.Text.lower())
["["]

I would expect, at least, for those parsers to admit mutually exclusive items.

Something like StreamData would be great for this library.

The documentation link in the README file that is shown on GitHub still links to the old 0.5.0 version of the documentation.

The new version of the documentation can be found when going through the Hex.pm page; I suspect that the link in the Readme is outdated.

Hi!

I don't know if this is the right place to be asking this question, so if it needs to be moved somewhere else let me know.

My question is regarding the parsing of the following format:

#Can be either
node (x, y) -> node (x, y)
# or (x, y) are optional
node -> node

I have some rules set up, the most important being:

defp node_parser(prev \\ nil) do
    prev
    |> label(word(), "name")
    |> skip(spaces())
    |> position_parser()
  end

  defp position_parser(previous) do
    previous
    |> option(
        ignore(char("("))
        |> int_parser("x")
        |> ignore(char(","))
        |> skip(spaces())
        |> int_parser("y")
        |> ignore(char(")")))
  end

  defp relation_parser(prev) do
    prev
    |> skip(spaces())
    |> option(ignore(string("->")) |> skip(spaces) |> node_parser())
  end

  defp int_parser(prev, name) when is_binary(name) do
    prev
    |> label(integer, name)
  end

When parsing the desired output this works:

iex(1)> Parser.parser("foo (175, 164) -> bar (100, 0)")
["foo", 175, 164, "bar", 100, 0]

However when making an error:

iex(8)> Parser.parser("foo (175, ) -> bar (100, 0)")
["foo", nil, nil]

Which is caused by the failing optional, what would be the best way to parse such a sequence? And failing when it encounters an erroneous situation like the above?

I know that with the default mechanics the parsing returns a nil when failing and that this is caught by the optional. However, I am wondering if a workaround would be available?

Cheers :)

I'm getting a compilation error with a project that uses combine.

Elixir 1.2.6
Erlang 19

== Compilation error on file lib/combine/parsers/text.ex ==
** (FunctionClauseError) no function clause matching in :elixir_errors.handle_file_error/2
    (elixir) src/elixir_errors.erl:186: :elixir_errors.handle_file_error("Elixir.Combine.Parsers.Text", {:beam_validator, {{Combine.Parsers.Text, :float_impl, 1}, {{:call, 4, {:f, 50}}, 43, {:multiple_match_contexts, [{:x, 0}, 1]}}}})
    (stdlib) lists.erl:1338: :lists.foreach/2
    (stdlib) lists.erl:1338: :lists.foreach/2
    (stdlib) erl_eval.erl:670: :erl_eval.do_apply/6

could not compile dependency :combine, "mix compile" failed. You can recompile this dependency with "mix deps.compile combine", update it with "mix deps.update combine" or clean it with "mix deps.clean combine"

So I was thinking about combine a bit recently and it seems to me unlike its haskell older brother it has a problem parsing recursive grammars. Take this example of a parenthesis matching parser that's "translated" from parsec's documentation:

defmodule Parens do
  use Combine

  def parser, do: many(parens())
  defp parens, do: sequence([char("("), many(parens()), char(")")])
end

Parens.parser of course results in an infinite loop. I think this works in parsec, because everything is a thunk in haskell so the particular parsers are only evaluated as needed. In this case however we're trying to build a whole infinite parser at once. Or maybe there's a way to achieve this currently?