Huh, so you’d have to start the parser back up again, in another function, instead of just doing it in-position? o.O?
OvermindDL1
josevalim
Creator of Elixir
What would lookahead do in this case? Would it look if the combinator matches but without changing the accumulate state or the input and continue if so, otherwise it “denies”? And lookahead_not is the opposite? I think we can retire the current lookahead in favor of it. Especially as the current lookahead is really just a traverse.
Indeed. The current patch would be the starting point, not the destination.
I mean this is in the nicest way possible but don’t start this gate keeping non sense. 
I know there is a computer science background to all of this but catching up on it is not my priority as my CS reading time is usually focused elsewhere. I am doing it mostly for fun. If I had to do all of this research before, the idea would still be on paper, which would be a shame. It is open source, there are no warranties, warts and all.
0
mjadczak
Yes, exactly that. In fact, lookahead_not is the more fundamental one, since you could write def lookahead(c), do: c |> lookahead_not() |> lookahead_not() (although when compiled naively, it would require an extra case statement to execute). And I agree that the current lookahead could be retired and easily implemented using traverse when needed.
I agree that it’s probably not a good idea to require an academic paper before you start writing some code for fun But, let me offer an alternative perspective—for fields such as parsing, where there are decades of research out there, sometimes it’s really helpful to be able to pick up some fundamental properties of the thing you’re working with. It can definitely save a lot of time! For me, I spent a few hours trying to get lookahead-style parsing to work with NimbleParsec, before I ended up realising that it was actually a PEG parser with one combinator missing, and then I could immediately prove that it wasn’t possible. Also, for a side-project like this, with no comprehensive documentation or tutorials, being able to say “this is a PEG parser” lets people access all the different resources written about this style of parser. FWIW, I think having a fast PEG parser is a great asset to Elixir, and I’m also pretty certain that once negative lookahead is properly supported, we can confidently assert that NimbleParsec is at least as powerful as a PEG parser 
0
josevalim
Creator of Elixir
I totally agree. My point is that because I did not start by wanting to write a complete parser, but rather something that can convert to pattern matching, it never crossed my mind to write a complete parser. And even though now I am aware it could be a complete parser, I don’t have the time to pour into studying what a complete parser is, so I either continue evolving it piece by piece with fantastic input like yours or I don’t evolve it at all.
I completely understand this is not ideal and I completely understand that by saying this some people may not use nimble_parsec as they would prefer a parsing library built on proper foundations. That’s fine by me because that was never my concern.
In any case, I have lookahead ready for choice and lookahead_not should be an invert of that, I will push soon, but I need to understand how it works with things like traverse and repeat before I consider it done.
2
OvermindDL1
What do you need to know? I’ve worked on (both building and using) Full PEG parsers for nearing 20 years at this point. ^.^
0
josevalim
Creator of Elixir
@OvermindDL1 @mjadczak is the behaviour of my repeat correct?
Take the example below:
defparsecp :lookahead_not_with_repeat,
repeat(ascii_char([]) |> lookahead_not(ascii_char([?0..?9])))
I would expect it to return this:
assert lookahead_not_with_repeat("aa0") ==
{:ok, 'a', "a0", %{}, {1, 0}, 1}
But it returns:
{:ok, '', "aa0", %{}, {1, 0}, 1}
I.e. it is happy to parse nothing if it halts anywhere. However, if I use times(min: 1), then it works as expected but then it always aborts at the minimum. So it seems they are not greedy.
0
josevalim
Creator of Elixir
@mjadczak here is a commit with lookahead and lookahead_not: Add lookahead and negative lookahead · dashbitco/nimble_parsec@71663d1 · GitHub
I will wait for your feedback then I will tidy it up with docs and what not.
1
OvermindDL1
PEG is absolutely greedy, it has no non-greedy constructs, you have to be explicit.
So let’s see:
repeat(ascii_char([]) |> lookahead_not(ascii_char([?0..?9])))
Which repeats just
ascii_char([]) |> lookahead_not(ascii_char([?0..?9]))
Which will match a, aa, aaaaa, but not a0, thus the first loop matches out the aa0 and extracts the first a and returns 97/?a, leaving a0, it repeats again and fails to match a0 thus ending, so repeat returns [97]/[?a]/'a', thus the successful return value should return [97] with a leftover of "a0", and this is indeed what ExSpirit does:
iex(1)> defmodule Testing do
...(1)> use ExSpirit.Parser, text: true
...(1)> defrule lookahead_not_with_repeat(repeat(char()|>lookahead_not(char(?0..?9))))
...(1)> end
{:module, Testing,
<<70, 79, 82, 49, 0, 0, 111, 28, 66, 69, 65, 77, 65, 116, 85, 56, 0, 0, 3, 5,
0, 0, 0, 77, 14, 69, 108, 105, 120, 105, 114, 46, 84, 101, 115, 116, 105,
110, 103, 8, 95, 95, 105, 110, 102, 111, 95, ...>>,
{:lookahead_not_with_repeat, 1}}
iex(2)> import ExSpirit.Parser
ExSpirit.Parser
iex(3)> parse("aa0", Testing.lookahead_not_with_repeat)
%ExSpirit.Parser.Context{
column: 2,
error: nil,
filename: "<unknown>",
line: 1,
position: 1,
rest: "a0",
result: 'a',
rulestack: [],
skipper: nil,
state: %{},
userdata: nil
}
In addition to other useful data like the matching position/column/line and so forth. Making it able to parse out any length of chars that don’t contain numbers after the starting position could be enforced via an expectation as well:
iex(15)> defmodule Testing do
...(15)> use ExSpirit.Parser, text: true
...(15)> defrule lookahead_not_with_repeat(repeat(char()|>expect(lookahead_not(char(?0..?9)))))
...(15)> end
warning: redefining module Testing (current version defined in memory)
iex:15
{:module, Testing,
<<70, 79, 82, 49, 0, 0, 112, 12, 66, 69, 65, 77, 65, 116, 85, 56, 0, 0, 3, 23,
0, 0, 0, 78, 14, 69, 108, 105, 120, 105, 114, 46, 84, 101, 115, 116, 105,
110, 103, 8, 95, 95, 105, 110, 102, 111, 95, ...>>,
{:lookahead_not_with_repeat, 1}}
iex(16)> import ExSpirit.Parser
ExSpirit.Parser
iex(17)> parse("aaaaa", Testing.lookahead_not_with_repeat)
%ExSpirit.Parser.Context{
column: 6,
error: nil,
filename: "<unknown>",
line: 1,
position: 5,
rest: "",
result: 'aaaaa',
rulestack: [],
skipper: nil,
state: %{},
userdata: nil
}
iex(18)> parse("aa0", Testing.lookahead_not_with_repeat)
%ExSpirit.Parser.Context{
column: 3,
error: %ExSpirit.Parser.ExpectationFailureException{
context: %ExSpirit.Parser.Context{
column: 3,
error: nil,
filename: "<unknown>",
line: 1,
position: 2,
rest: "0",
result: 97,
rulestack: [:lookahead_not_with_repeat],
skipper: nil,
state: %{},
userdata: nil
},
extradata: %ExSpirit.Parser.Context{
column: 4,
error: nil,
filename: "<unknown>",
line: 1,
position: 3,
rest: "",
result: 48,
rulestack: [:lookahead_not_with_repeat],
skipper: nil,
state: %{},
userdata: nil
},
message: "Lookahead_not failed"
},
filename: "<unknown>",
line: 1,
position: 2,
rest: "0",
result: nil,
rulestack: [],
skipper: nil,
state: %{},
userdata: nil
}
iex(19)> parse("aa0aaa", Testing.lookahead_not_with_repeat)
%ExSpirit.Parser.Context{
column: 3,
error: %ExSpirit.Parser.ExpectationFailureException{
context: %ExSpirit.Parser.Context{
column: 3,
error: nil,
filename: "<unknown>",
line: 1,
position: 2,
rest: "0aaa",
result: 97,
rulestack: [:lookahead_not_with_repeat],
skipper: nil,
state: %{},
userdata: nil
},
extradata: %ExSpirit.Parser.Context{
column: 4,
error: nil,
filename: "<unknown>",
line: 1,
position: 3,
rest: "aaa",
result: 48,
rulestack: [:lookahead_not_with_repeat],
skipper: nil,
state: %{},
userdata: nil
},
message: "Lookahead_not failed"
},
filename: "<unknown>",
line: 1,
position: 2,
rest: "0aaa",
result: nil,
rulestack: [],
skipper: nil,
state: %{},
userdata: nil
}
The reason I point out except is it is also a very standard PEG operator in PEG libraries that allows you to ‘early kill’ something like an alt or so, like say you are parsing if, well if you put the rest of the parsing after if in an except(...) then if it fails to parse inside then you know the code is bad, you don’t need to test other alternatives like identifiers and so forth or you will just end up getting an error in another unrelated place. That should be added to NimbleParsec as well.
1
josevalim
Creator of Elixir
mjadczak
Nice! And yes, I agree with how @OvermindDL1 describes it.
I think something to keep in mind, which may be useful in working out how something “should” behave, is a standard model of whether a parser “fails” or “succeeds”. Once every single parser can be said to either “fail” or “succeed” given some input, potentially consuming some input if it succeeds, then it becomes clear—repeat(p) tries to let p consume as much input as possible, while it succeeds, and once it fails (necessarily not consuming any input), it goes to the next thing in the sequence. choice([a, b, c]) tries to apply a to the input, and if it succeeds, proceeds to the next parser in the sequence. If a fails (not consuming input), then b is tried instead (and then c, and if all choices fail, the whole choice combinator fails).
N.B. Typically these things are expressed in terms of “consuming input”, but in NimbleParsec/Elixir terms “input consumed” == “the next combinator in the chain is called with a binary which no longer includes the consumed input”.
Once you have a unified way in which all parsers either succeed or fail, you can then e.g. express repeat_until like I said: repeat(lookahead_not(until) |> to_repeat()). The inner parser p in this case is lookahead_not(until) |> to_repeat() (where we’ve assumed that to_repeat() will consume some input, like a string or whatever). The outer repeat passes its current input to this p. The lookahead_not checks whether the immediate input (i.e. whatever’s at the start of the current binary) matches until. Let’s say at first it doesn’t. So lookahead_not succeeds, but does not consume any input—it lets to_repeat() consume it instead. Now the binary has moved along, and repeat gives it to p again. lookahead_not passes this input to until, and it matches! lookahead_not discards the results (accumulator) and also pretends the input was never consumed, but fails. Now repeat knows to succeed (it always succeeds, because it’s a 0 or more repetition) instead of to keep repeating.
(I hope I got the above all right, @OvermindDL1 please correct me otherwise)
Now, obviously if you actually implemented it like this, you would no longer have a super-efficient pattern-matching parser, but just yet-another-PEG parser which needs to interpret all of this information at runtime. Hence, I’m not necessarily saying that each parser/combinator should actually explicitly return an :ok or :error which is matched on. Rather, I’m saying that this is a good mental model of what is happening, and should help to answer questions like “how should this combination of parsers behave”?
Regardless, the commit looks good, especially now you’ve got the behaviour with repeat worked out. I’m looking forward to trying it out! I’m currently tinkering with trying to implement a full-featured (spec-compliant) XML parser using NimbleParsec
0