Need help with creating linker script parser

[mtoohey31]

Hello! So I have an almost-complete grammar for linker scripts (repo here: https://github.com/mtoohey31/tree-sitter-ld). I've translated things pretty carefully from the upstream yacc grammar (ld/ldgram.y in the binutils repository) so it should be pretty accurate.

I'm struggling with an issue though, where syntactically valid assignment statements inside sections result in errors (here's a test which demonstrates the bug). I've spent a while trying to figure it out on my own but haven't made any progress really. Assignment statements inside sections are correctly accepted without errors if I remove the input_section_spec case from the statement rule (and delete all the input sections from within the test case). The initial identifier of the assignment statement in the test case in question would initially be ambiguous as to whether it's a NAME or a wildcard_name. I would expect backtracking to occur after the input_section_spec case fails, but this evidently isn't happening. Is this the sort of case where a grammar should include a conflict for the two rules? If so, tree-sitter doesn't appear to be recognizing this.

Does anyone have any suggestions about what I might be doing wrong here?

[amaanq]

Well, I haven't looked deeply into your problem but I've made a linkerscript grammar here 😁 https://github.com/tree-sitter-grammars/tree-sitter-linkerscript

N.B: it was quite annoying that there was no official spec/ebnf grammar for linkerscript, and I didn't feel like deeply understanding ldgram.y in the binutils repo to be 100% accurate, so there might be some edge cases in my grammar. If you would like to collaborate, I'm all ears

[mtoohey31]

Hi, thanks for the super quick reply! I did notice your grammar while I was considering whether to write mine, but I'm hoping to support as much of the strange syntax allowed by the binutils grammar as possible, so I decided to try translating things directly from that grammar. Taking that approach basically required rewriting things from the start though, so it didn't really occur to me to file the changes as a pull request against your repo.

I just noticed while looking at the tree-sitter-grammars organization that we also have some overlap in terms of:

• https://github.com/tree-sitter-grammars/tree-sitter-pem and https://github.com/mtoohey31/tree-sitter-pem
• https://github.com/tree-sitter-grammars/tree-sitter-gitattributes and https://github.com/mtoohey31/tree-sitter-gitattributes

I created both of those for use in helix, but I don't really see any reason to have two different grammars for each as they're both pretty simple. If I have time at some point, is it fine if I create PRs for anything that my grammars might happen to handle better, then swap helix to use the tree-sitter-grammars versions?

[mingodad]

I've been looking at it and found that changing the order of wildcard_name seems to fix the problem (see bellow).

Looking the original lexer here https://github.com/bminor/binutils-gdb/blob/0fd455766e7f1bd7df328e104281b49a5268677f/ld/ldlex.l#L95 we can see that the character set for each type of NAME is shown form the more general to less general, to reproduce it in tree-sitter we should order then in less general to more general (shortest match first, longest match last).

Probably you should review the order of the other NAMEs too.

---------------------------------- grammar.js ----------------------------------
index b192b3d..4e2dc01 100644
@@ -57,7 +57,6 @@ module.exports = grammar({
         seq($.assignment, $.separator),
         seq("ASSERT", "(", $.exp, ",", $.NAME, ")"),
       ),
-    wildcard_name: (_) => /[_a-zA-Z0-9/.\\$~\-+:\[\],=?*^!]+/,
     section_name_spec: ($) =>
       choice(
         $.wildcard_maybe_reverse,
@@ -420,6 +419,7 @@ module.exports = grammar({
     NAME: (_) =>
       /=?[_a-zA-Z/.\\$~][_a-zA-Z0-9/.\\$~\-+:\[\],=]*|[_a-zA-Z.\\$][_a-zA-Z0-9/.\\$~]*|\/DISCARD\/|"[^"]*"/,
     LNAME: (_) => /-l[_a-zA-Z0-9/.\\$~\-+:\[\],=]+/,
+    wildcard_name: (_) => /[_a-zA-Z0-9/.\\$~\-+:\[\],=?*^!]+/,
     INT: (_) =>
       choice(
         /\$[0-9A-Fa-f]+/,

[mtoohey31]

Thanks, yes this did fix it!! I didn't even realize this was relevant, but now that I've checked the docs I see that tree-sitter does apparently consider this as the last criteria (link in case others are reading this). I'll be sure to take a look at how I've ordered other things too. Thanks!

[mingodad]

The link provided by @amaanq to his tree-sitter parser/grammar doesn't parse the problematic example https://github.com/mtoohey31/tree-sitter-ld/blob/52ce5060f5fa6d75c6b4cc6c0510f86e34747d8a/test/corpus/corpus.txt .

[amaanq]

This patch would fix it, but I'm not 100% sure if it's valid (not a linkerscript expert)

diff --git a/grammar.js b/grammar.js
index 06b9417..974e9ed 100644
--- a/grammar.js
+++ b/grammar.js
@@ -82,2 +82,3 @@ module.exports = grammar({
       $.assert_command,
+      $.provide_command,
     ),

[mingodad]

The original grammar have a lot of lexer states to help filter which/how tokens are valid in a specific context.
I'm not aware of tree-sitter having a way to create lexer states, does someone knows how to have user controlled lexer states ?

[amaanq]

The usage of an external scanner can control the lexing/statefulness of certain tokens that might need to be context-aware, it's how indentation is handled in python, heredocs in bash/ruby, etc

[amaanq]

Oh I sorta see what you mean, if you mean having certain tokens/keywords be allowed in certain rules/states then the reserved word api (still a WIP) is what you'd be interested in, #1635

[mtoohey31]

Part of the use of lexer states is to handle different filetypes. The MRI, VERS_START, VERS_SCRIPT, and VERS_NODE are all for other filetypes that aren't plain linker scripts, so I'm just ignoring those, which simplifies things somewhat. But yeah some of the lexer states do make things challenging... so that might be part of the problem.

[mingodad]

Hello @amaanq, thanks for reply !
There is any place that describe it (other than read the code) ?

[amaanq]

https://tree-sitter.github.io/tree-sitter/creating-parsers#external-scanners

It is a pretty difficult topic that needs a lot more docs around tricks/stuff authors can use to validate/invalidate certain states based on others, or based on if we're in error recovery or not.