Clarified imports/includes

[ericvergnaud]

Grammars can range from self contained "combined" grammars, "lexer" grammars, "parser" grammars (that require a "lexer" grammar, and more complex grammars that import other grammars. The latter are extremely useful for high level languages: linq in C#, jsx in js, js and css in html...

The current mechanism for wiring grammars together relies on the import statement. Its behavior is not well documented.
Experience shows the following:

1. • in case of rule collision, imported rules are overridden by rules of the importing grammar
2. • imported rules are appended after the rules of the importing grammar

Behavior 1 is highly desirable. It operates in an intuitive way. However the tool could raise a warning in case of collision, and not raise it if the overriding rule is annotated (for example using a @override decorator)

Behavior 2 is fine for parser grammars, but severely problematic for lexer ones. This is because top-level parser rules to not have precedence, whereas the precedence of lexer rules is determines by their sequence in the grammar.

This makes it very difficult to re-use grammar fragments across lexers, because a well-formed lexer grammar typically ends with a whitespace rule followed by a catch-all one. Hence, imported lexer rules often end up never being matched.

To avoid this, we could adopt the following:

• importing any grammar into a combined grammar is a recipe for problems and should be forbidden
• importing a lexer grammar into a parser grammar is a recipe for problems and should be forbidden (use tokenVocab instead)
• importing a parser grammar into a lexer grammar makes no sense and should be forbidden
• importing a parser grammar into a parser grammar is fine and can be kept as-is
• importing any grammar into a lexer grammar should be forbidden, instead provide an include statement that can be placed anywhere in the grammar, thus imperatively specifying where the lexer rules should be placed

[ftomassetti]

In general I think that rules for combining grammars are very useful and improvements in this area would be very valuable. For example, we would like to write different grammars for ANSI SQL, and different SQL dialects and have some form of inheritance among them, however it seems hard to do with ANTLR 4.

I think that importing/combining grammars would be a very advanced feature, of interest for advanced users, so I would err on the side of making it more powerful even at the cost of being a little harder to learn.

Reading this, one consideration that comes to mind is: would things be simpler if we did not have combined grammars?

For lexers, the only thing that comes to mind is that, if I understand correctly, we are considering the to inject all the imported lexer rules, all consecutively, in a certain point of the importing lexer. I think that would be appropriate for lexer rules which were designed to be imported, but it could not always work for lexer rules that were intended to be used on their own and they are now reused.

Example of grammar conceived to be reused: a grammar defining common mathematical symbols
Example of grammar conceived to be used on its own, and then also reused: a grammar for ANSI SQL. I want to parse ANSI SQL using that grammar as-is, but then I also want to extend it to build a parser for Teradata SQL or PL/SQL.

In the latter case I may want to intertwine the imported rules with the rules in the importing grammars. To support that we could perhaps allow the user to define blocks of rules or sections of rules and import them as a block. Something like:

#punctuation {
   DOT = '.'
   COMMA=';'
}

One could then specify in the importing grammar where to import a block of lexer rules. This could be optional, so that it is relevant only for advanced users and the others can safely ignore it.

Also, what about lexer modes?

[ericvergnaud]

Things would definitely be simpler for antlr developers if we didn't support combined grammars, but not for beginners...

My proposal is as follows:

• don't support import/include in combined grammars
• only support import in parser grammars (because parser rules placement does not affect precedence)
• only support include in lexer grammars (because lexer rules placement affects precedence)

A parser grammar could start like this:

parser grammar HTMLParser;

// insert imported rules anywhere (currently at the very end)
import CSSParser, JSParser;

tag: LT ID GT;

...

whereas a lexer grammar would not allow the above, but would support the following:

lexer grammar HTMLLexer;

HTML_COMMENT: '<!--' .*? '-->';

.../...

// explicitly insert imported rules here
include DoubleQuotedStringLexer;
include SingleQuotedStringLexer;
include IntegerLiteralLexer;

.../...

ATTRIBUTE: DOUBLE_QUOTED_STRING | SINGLE_QUOTED_STRING | INTEGER_LITERAL;

.../...

The above indeed doesn't cater for reuse of grammars not designed for reuse.
Do we want to support that ? I suspect that could become extremely complex ?
I'd rather encourage developers to split their original grammar into reusable segments, that are then simpler to include ?

[kaby76]

These rules seem fine, but I'm not an expert on import because I could never get import to solve any significant problems. (For example, how does one take html, css3, and javascript, and combine these with the html as top-level grammar? It is a hard problem, and I suggest everyone in this group try as an exercise. You will "discover" all sorts of problems.)

I'm writing some "lint"-type scripts for these rules and will check it against grammars-v4. Already I see that https://github.com/antlr/grammars-v4/tree/master/oncrpc violates your first rule ("don't support import/include in combined grammars"), but the grammar does seem to "work." (The grammar is tested with only one test input, and checks only 62% of the parser rules in the grammar.) For Antlr5, the grammar would have to be split.

Split grammars are required to write "target agnostic grammars", but otherwise not necessary. Note, we don't have any "official" tools to split and combine grammars but Trash does this easily preserving off-channel content.

If there are new import/include rules on grammars, Antlr4 grammars that did work would involve a change when coverted to Antlr5. For example, the "import LexBasic;" would need to be changed to "include LexBasic;".

[ericvergnaud]

I think we might need to accept that in order to better support grammar inclusions (via imports or includes) we might have to slightly break backwards compatibility.
I also think that combining grammars not designed to be combined might be over ambitious ?
Combining html, css and js grammars is a great goal, but maybe that requires tuning css and js grammars a bit ?
How about using that example to iteratively reach a valid spec ? We want a spec that solves real problems, not one that just makes logical sense. I am fine with the idea of evolving the spec to make this example work.

[kaby76]

This example is from the ISO Spec on HTML. But, it is not unique. For example, combined grammars occur with the ISO spec for XQuery (which uses XPath); the "spec" (aka manual) for SQL Plus (which uses SQL). Many of the ANSI/ISO specs cross reference other specs. Sub-grammars are written without consideration of whether it is used in another grammar--and it shouldn't.

While the css3, javascript, and html grammars are not designed to be combined, the solution is hard to construct. Antlr does not work well to support these.

There are two reasons for why it is hard to combine grammars with Antlr.

The main reason is that combining disparate grammars create collisions in lexer rules (both by name and by the string it recognizes). Antlr pools all lexer rules into one gigantic default mode and applies the usual "two rules for Antlr lexer recognition". The ANSI/ISO specs are not written this way. I can work around this problem by renaming (to avoid name collisions), declaring all lexer rules in a unique mode, using unbuffered token streams, and having parser rule actions to switch modes (to avoid lexer rule recognition collisions).

When people write a grammar, they don't consider how the lexer rules overlap. Detangling overlapping lexer rules is a hard problem because you can't compare the overlap at code generation time usually. (Antlr does check overlap when the RHS of a rule is a string literal.) The burden is then shifted to testing, which is a terrible price to pay, likely leading to many unchecked errors.

The other reason for why this is hard is because the support code for sub-grammars requires constants that are generated in the "root" grammar. Consequently, the support code for each sub-grammar can't compile in the combined (via import) grammar. It would have been better if these constants were associated with the sub-grammars. I can work past that by refactoring the support code, which I can do with Trash and each of the target-specific grammars (like csharp)--but most people don't have automated means to do this. I don't know how actions are going to be written yet, so this may not be a problem for Antlr5.

But, there is no "turn key" solution here with Antlr. I'm not sure what the solution would be. But, it is something that should be addressed because it happens over and over.

On the checks for the 500 grammars in grammars-v4, I found only a few violations for the 'import of non-parser grammar into parser grammar' rule (antlr/antlr4, kotlin/kotlin-formal, sql/hive/v2, sql/hive/v3, stringtemlate), and only one of the 'importing any grammar into a combined grammar is a recipe for problems and should be forbidden' (oncrpc).

[ericvergnaud]

What if, following the lexer mode pattern, entire sections of the main document were delegated to sub-grammars ? Something like: ``` .../... javascript: SCRIPT_TAG_OPEN delegate JavaScriptParser sourceElements SCRIPT_TAG_CLOSE; .../... ``` In the above, the HTMLParser would consume SCRIPT_TAG_OPEN, accumulate all input up to SCRIPT_TAG_CLOSE, and delegate the lexing and parsing of the accumulated input to a JavaScriptParser, invoking the sourceElements rule. This would involve introducing a new node type i.e. DelegateNode, that would hold a reference to the autonomous javascript parse tree... (just thinking out loud here...)

[kaby76]

Yes, I was thinking of something like this! I will mull on this a bit.

[ericvergnaud]

TBH doing this would simply be automating a standard practice that is relatively easy to implement post-parsing by extracting the text content and parsing it using whatever means. People do that with CDATA. JS and CSS can be considered as explicitly typed CDATA. Which raises 2 questions:

• how much value does it create to automate this vs manual implementation ?
• should it be part of our MVP ? (I don't see its implementation leaking to other areas)