Having trouble with a grammar that has a choice that varies only deeper in the parse tree

[nicklan]

Hopefully the title makes sense. I have a grammar which I've simplified to this:

module.exports = grammar({
  name: 'buglang',

  conflicts: $ => [
    [$.with_foo, $.with_foo]
  ],

  rules: {
    source_file: $ => $.expr,

    expr: $ =>  choice(
      $.txt,
      $.without_foo,
      $.with_foo
    ),

    txt: $ => "txt",

    hsep: $ => /:{1,3}/,

    without_foo: $ => seq(
      $.expr,
      $.hsep,
      $.txt,
    ),

    foo: $ => "foo",
    bar: $ => "bar",

    with_foo: $ => seq(
      optional(seq($.bar, ",")),
      $.expr,
      ":",
      $.txt,
      $.foo,
    ),
  }
});

Here are two test files which SHOULD both parse:

This one should parse as a without_foo

txt: txt

and this one as a with_foo

txt: txt foo

However, only the second one will actually parse, I think because it goes down the without_foo path too far and never recovers, but I'm not clear on that.

The error when parsing the first file is:

(source_file [0, 0] - [1, 0]
  (expr [0, 0] - [0, 8]
    (with_foo [0, 0] - [0, 8]
      (expr [0, 0] - [0, 3]
        (txt [0, 0] - [0, 3]))
      (txt [0, 5] - [0, 8])
      (foo [0, 8] - [0, 8]))))
test-file	0 ms	(MISSING foo [0, 8] - [0, 8])

Anyway, a couple of things:

1. I can't just factor this into "one" rule with an optional foo at the end, because with_foo also has an optional bar at the front which without_foo doesn't (i.e. without_foo should NOT parse if it starts with a bar)
2. it's suspicious that I have to declare with_foo as conflicting with itself, but I can't see how to resolve that otherwise
3. If I comment out one or the other of with_foo/without_foo in the expr->choice, then each of the two files can parse (but obviously not with the same parser), so I know that the definition of each path is correct.
4. Something about the hsep rule is important, because if I change without_foo to just use ':', everything works (but then it doesn't match the full language I want).

I'd appreciate any insight on how to write a parser to handle this kind of case.

Thanks in advance!

[sogaiu]

I haven't wrapped my head around the details, but I tried tweaking the grammar a bit.

For with_foo, instead of a new anonymous node ":", I tried $.hsep:

    with_foo: $ => 
        seq(optional(seq($.bar, ",")),
            $.expr,
            //":",
            $.hsep,
            $.txt,
            $.foo),

The following shows invocations [1] and corresponding results:

$ echo "txt: txt" | tree-sitter.ahlinc parse -
(source_file [0, 0] - [1, 0]
  (expr [0, 0] - [0, 8]
    (without_foo [0, 0] - [0, 8]
      (expr [0, 0] - [0, 3]
        (txt [0, 0] - [0, 3]))
      (hsep [0, 3] - [0, 4])
      (txt [0, 5] - [0, 8]))))

$ echo "txt: txt foo" | tree-sitter.ahlinc parse -
(source_file [0, 0] - [1, 0]
  (expr [0, 0] - [0, 12]
    (with_foo [0, 0] - [0, 12]
      (expr [0, 0] - [0, 3]
        (txt [0, 0] - [0, 3]))
      (hsep [0, 3] - [0, 4])
      (txt [0, 5] - [0, 8])
      (foo [0, 9] - [0, 12]))))

Neither seems to have any ERROR or MISSING nodes.

Sorry I'm not really answering your specific questions -- just sharing what some tinkering turned up here. Possibly it gives some additional information related to 4 though?

---

[1] I used ahlinc's alpha from here for convenience of posting, but I also verified with the tree-sitter at commit c6d663f.

[nicklan]

Thanks for looking at this. Yeah, I think it's because if you use $.hsep then the two rules have equal precedence.

Using just : means that the : get's higher precedence based on rule 6 for conflicting tokens: "Match Specificity - If there are two valid tokens with the same precedence and which both match the same number of characters, Tree-sitter will prefer a token that is specified in the grammar as a String over a token specified as a RegExp." So then it runs off down that path and then fails when it doesn't find the foo. But I would have thought it should recover back and try the without_foo path, but I guess it doesn't somehow.

So, that's one thing to do, but I actually don't want that, because in my real grammar the with_foo should only match a single :, while without_foo should match :, ::, or :::

[sogaiu]

So then it runs off down that path and then fails when it doesn't find the foo. But I would have thought it should recover back and try the without_foo path, but I guess it doesn't somehow.

May be you have already -- but have you tried observing the output of the parse subcommand using the --debug and/or --debug-graph flags?

Those should give some details [1] about what actually happened, though interpreting the results takes getting used to (still not very good at that).

---

[1] For --debug-graph, a log.html file is produced (I've usually found it in the root of the grammar directory) that contains svg. I open it in a web browser to have a look.

[sogaiu]

I also tried the following:

module.exports = grammar({
  name: 'buglang',

  conflicts: $ => [
      [$.hsep, $.with_foo],
      [$.with_foo, $.with_foo]
  ],

  rules: {
    source_file: $ => $.expr,

    expr: $ =>
      choice($.txt,
             $.without_foo,
             $.with_foo),

    txt: $ => "txt",

    hsep: $ =>
      choice(":",
             "::",
             ":::"),

    without_foo: $ =>
      seq($.expr,
          $.hsep,
          $.txt),

    with_foo: $ =>
      seq(optional(seq($.bar, ",")),
          $.expr,
          ":",
          $.txt,
          $.foo),

    foo: $ => "foo",

    bar: $ => "bar",

  }
});

The results with parse were:

$ echo "txt: txt" | tree-sitter.ahlinc parse -
(source_file [0, 0] - [1, 0]
  (expr [0, 0] - [0, 8]
    (without_foo [0, 0] - [0, 8]
      (expr [0, 0] - [0, 3]
        (txt [0, 0] - [0, 3]))
      (hsep [0, 3] - [0, 4])
      (txt [0, 5] - [0, 8]))))

$ echo "txt: txt foo" | tree-sitter.ahlinc parse -
(source_file [0, 0] - [1, 0]
  (expr [0, 0] - [0, 12]
    (with_foo [0, 0] - [0, 12]
      (expr [0, 0] - [0, 3]
        (txt [0, 0] - [0, 3]))
      (txt [0, 5] - [0, 8])
      (foo [0, 9] - [0, 12]))))

I wonder if it's possible there's some issue with the regular expression support. I wrote up some details about tree-sitter's regular expression support here. I've tried to avoid certain regular expression constructs in tree-sitter as what exactly is suported is a bit unclear to me.

[nicklan]

Ohh wow yeah, switching from regex to choice totally fixes things. Seems like that would be a bug (or maybe a strange but intended consequence of using a regex).

I don't think that it's a regex feature issue. even just making it hsep => /:/ means that the grammar won't parse the without_foo version.

Thanks so much for the help! I'm going to make this more complex to match my real grammar and see if I can totally fix things :)

[ahlinc]

@sogaiu nice fix!

As I remember I saw here in repo issues or discussions a similar case where it was needed to include the same token into two different rules. In this case the ":" token is the same token for Tree-sitter even if it's mentioned in a literal form in multiple places so it doesn't conflict with itself and the choice(":", "::", ":::") just tells to TS to lookup more tokens on the same position to switch to that rule finally. While the /:{1,3}/ form defines totally different token from TS perspective and it may conflict with the ":" string literal token.

[ahlinc]

@nicklan don't forget please to mark the answer.

[nicklan]

@ahlinc makes sense that it's a different token, but why wouldn't tree-sitter try and recover back and use the other token? is it just that recovery points are only at the place where there was the same token for two possible paths? seems like that makes reasoning about grammars with regexs really tricky.

not knowing the code or cost at all, it seems it would be "more" correct to generate the list of possible rules that could apply, and then recover to points where there is more than one. that's I think how a person intuitively thinks about writing the grammar. I could imagine that's prohibitively expensive or not feasible for some other reason I haven't thought of though :)