Make Script-level Annotation friendlier to EBNF grammar.

[TemporalCatcher]

I wanted to see if I could tackle updating the GDScript Grammar page; however, there are some very strange behaviors with the parser at the beginning of the file that will make translating to EBNF much more complicated than anticipated.

In trying to understand the way GDScript is parsed I discovered the following code makes a valid and full file without any error:

@abstract
@tool 
@static_unload 
@icon("res://icon.svg")

Note: There is a warning because there is no static variable to unload, but EBNF only cares about syntax, so its fine.

All 4 lines can be moved around to your hearts content and compressed to a single line separated by spaces with no issue.

Before we continue I have a definition.
Script-level annotation: an annotation that must come before the class definition and have at most 1 instance of itself in a file.

Complexity

Before I get to the real problem, the current design of script-level annotation is not built to be extensible in EBNF.
Limiting the number of occurrences while allowing freedom of order actually makes the context-free grammar (EBNF is a context-free grammar) more complex, even though it seems trivial to a Turing machine.
Below, I will show you two languages that have alphabet {a, b} and show that the smaller language L(a) is actually is more complicated to fully represent all instances

{* can only print each letter at most once *)
a = ["a"], ["b"] | "ba" ;
(* can print each letter any number of times *)
b = {["a"], ["b"]}; 

L(a) = {"", "a", "b", "ab", "ba"}
L(b) = {"", "a", "b", "ab", "ba", "aa", "bb", "aab", ...}

You might think a is not that much more complex than b, but that's because the number of characters in the alphabet is 2.
I mapped the number of options a will have to have written with the formula:

f(n) = sum(C(n, k) * (k!)) for 0<=k<=n

n represents the number of script-level annotations that can be arranged in any order.
you are choosing k items from n annotations and you're permuting the items you chose for every choice k to represent all possible ordering of script-level annotation. The following are how much individual options one must represent for different number of annotations:
f(0) = 1
f(1) = 2
F(2) = 5
f(3) = 16
f(4) = 65
f(5) = 326

The nice thing is the option sequence (denoted by [ ]) can optimize your result, but optimizing 65 options is a big task and is not extensible when you add more script-level annotations. Meanwhile b's increases linearly, making it highly extensible.

Current issue in complexity

Everything above assumes script-level annotations are equal. However the following file has an error:

@tool 
@static_unload 
@icon("res://icon.svg")
@abstract

var some_var := 3

because whereas before, the @abstract is read as the script being an abstract class, now the annotation is trying to make the variable abstract.

This makes the formalization even more complicated because you will have to split the possibilities

program = [[scriptAnnWAbs] [classDef] | [scriptAnnWoAbs] "@abstract" classDef] {topLevelDecl};

scriptAnnWAbs = (* Some complex sequence where @abstract cannot be last *);
scriptAnnWoABs = (* Less complex sequence without @abstract *);
classDef = (* Class Definition *);
topLevelDecl = (* Rest of the program *);

So, Solutions?

I already showed one way, which is to allow more than one of each individual annotation, but I feel that would cause a lot of headaches for the little payoff of making the EBNF easier to write.

Another way is to add more restrictions by enforcing order of the annotation (eg. have @tool->@icon->static_unload), This will allow the EBNF to grow linearly when creating new script-level annotation. The problem is this would break compatibility.

The next one is my favorite solution. Separate @abstract from the rest of the script-level annotations, and put it in the class definition logic. Although technically breaks compatibility, I noticed nowhere in the documentation does it imply the following is a valid file:

@abstract

It creates an empty, nameless, abstract RefCounted. This is a completely useless file, but being a valid file actually makes the EBNF more complex than it should be due to it being intermixed with the other script-level annotations. You can't even add anything to it without class definition because

@abstract
@abstract func foo()

is invalid, even though

@abstract
@tool # or @static_unload or @icon("res://icon.svg")
@abstract func foo()

is valid.
Overall, @abstract is too inconsistent with it's behavior to be treated as a standard script-level annotation, so I suggest putting it into the class definition instead.

Each solution only addresses one of my issues. The first two addresses the extensibility problem when adding more script-level annotations, while the last specifically targets the issue I get from @abstract. The last tangentially helps with formalizing by reducing script-level annotations from 4 to 3. I feel like separating @abstract is the most actionable one and is good enough unless there are plans for more script-level annotations.

The only other suggestion I have is when drafting the new EBNF, add a comment that explains how it actually works, while having a simplified version of the grammar relating to script-level annotations. I don't really like this solution, but is a good compromise.

[dalexeev]

I understand what you mean, but I think this discussion is mostly theoretical, not a real issue. The GDScript implementation doesn't use a formal grammar, even the outdated documentation page states that EBNF is provided as a reference and may be incorrect.

Compliance with the grammar doesn't guarantee that the source file is valid. It may still contain semantic errors. Annotation resolution is primarily performed by the static analyzer, although some annotations have special processing in the parser.

You're right that it's difficult to describe a grammar that would even allow for correct AST construction (identifying which node an annotation belongs to). However, the problems begin even earlier: the tokenizer is interactive (its modes are controlled by the parser), while the current outdated grammar omits whitespace tokens altogether.

The problem with determining whether an annotation applies to the script/root class or to the first member of the root class is caused by the fact that in GDScript, files are classes, and both extends and class_name are optional. We could simplify the logic for determining script-level annotations by requiring at least one of the keywords to be present (otherwise, the annotations would be treated as applying to the first member of the root class). Or we could even make extends mandatory. But that would break compatibility, so it's not possible until 5.0.

I would advise you not to put script-level annotations into a separate category in EBNF. Just use the general "annotation" category, even though different annotations apply at different levels.

[TemporalCatcher]

Okay, and following the current outdated documentations, if I am to use the general annotation category, would it be better to put ANNOTATION as it's done by the tokenizer, or do you think defining annotations is good?

By extension,, how much of the tokenizer should I use? I noticed that the outdated documentation did not use tokens such as IF and instead went with "if".

Also, the comment says that INDENT and DEDENT are not generated by the tokenizer, but since it is outdated, I take it that it's different now? I'm looking at the parser code and I don't know enough about it to know for certain, but it looks like that is no longer true. as I see GDScriptTokenizer::Token::INDENT throughout the parser code.

[dalexeev]

if I am to use the general annotation category, would it be better to put ANNOTATION as it's done by the tokenizer, or do you think defining annotations is good?

AnnotationNode is more than Token::ANNOTATION. In the grammar, it could be:

annotation = ANNOTATION [ "(" argList ")" ] ;
argList = [ expression { "," expression } [ "," ] ] ;

By extension,, how much of the tokenizer should I use? I noticed that the outdated documentation did not use tokens such as IF and instead went with "if".

By convention, terminals are UPPERCASE. In simple cases, it's better to provide terminals as is ("if"). In complex cases, terminals are mentioned without a definition (IDENTIFIER, STRING, NUMBER, etc.). Note that the latter are terminals only from the perspective of the parser, which processes tokens, not characters. But potentially we could further define STRING and NUMBER as non-terminals.

I'm looking at the parser code and I don't know enough about it to know for certain, but it looks like that is no longer true. as I see GDScriptTokenizer::Token::INDENT throughout the parser code.

The problem is that whitespace tokens aren't always generated, but depend on the multiline mode and expression-indented block stack, which are interactively controlled by the parser (whitespace tokens aren't generated inside parentheses, etc., but they are generated inside lambdas). This makes the grammar even less rigorous and potentially applicable in practice for third-party tools.

In my opinion, perhaps we should remove this outdated documentation page altogether and not provide any grammar.

[TemporalCatcher]

But potentially we could further define STRING and NUMBER as non-terminals.

True, but I desire accuracy in the end result (like in the editor) over formality. I find myself trying to formalize it too much because I want it to be accurate. However, I'm fine with implying STRING and NUMBER because those who would use the page should know what strings and numbers are and how they're represented.

The problem is that whitespace tokens aren't always generated, but depend on the multiline mode and expression-indented block stack, which are interactively controlled by the parser (whitespace tokens aren't generated inside parentheses, etc., but they are generated inside lambdas).

Oh so that's why I don't have to end a line with a backslash when I'm doing multilines inside parentheses. I was only asking the question because I wanted to know if updating the comment was necessary. However, I feel like it may be possible to represent the whitespace specification in a CFG (and therefore in EBNF) as long as you can represent the areas that requires it (and not) with an open/close form (eg. parentheses).

This makes the grammar even less rigorous and potentially applicable in practice for third-party tools.

In my opinion, perhaps we should remove this outdated documentation page altogether and not provide any grammar.

You do make a good point. I forgot I found the page when looking at the GDScript Reference, and I clicked the grammar page linked there without reading that it was for helping with third-party tools for the language. By now, anyone who is making such tool is definitely not getting the grammar from that page. The grammar also seems to not be high in priority nor demand to the point that it has been outdated for years.

[Calinou]

In my opinion, perhaps we should remove this outdated documentation page altogether and not provide any grammar.

I'm inclined to agree as well. Pull request opened:

• Remove outdated GDScript grammar page godot-docs#11889

[TemporalCatcher]

I'm closing this discussion because even though I like one of the solutions I proposed. With the removal of the grammar page, I don't feel like any of the proposed solutions are necessary anymore.