Does Antlr4 support multiple token types in type()? If not, why not?

[matthew-dean]

The documentation is surprisingly thin for Antlr4, so I'm not sure if this is possible or not, but I've, in the past, used Chevrotain, which allows you to map tokens to other categories. The idea is that for the parsing phase, you can reference a "category" as a token. It looks like Antlr's equivalent of this is -> type( x ) but it looks like you can only map to one type. Is it possible to do more such that input can be mapped to multiple token types?

[kaby76]

In Antlr, there is no notion of multiple types for a token. A token type is an integer, and it is generally immutable when set.

In an Antlr grammar, the name of the lexer rule represents the token type, which you can use in a parser rule, e.g., PACKAGE in packageDeclaration : annotation* PACKAGE qualifiedName ';' ;. However, sometimes one might want to use a different name of the token than from the rule name. That's where -> type() might come in handy. All this is consistent with what we've all been taught about formal languages, compiler construction, and lexical analysis--for generations.

The Chevrotain documentation does not contain a single discussion of the "categories" field of a token (under lexing), and there are only a few closed issues that make reference to the feature. Chevrotain/chevrotain#962 Chevrotain/chevrotain#1055 Chevrotain/chevrotain#564 (comment). So we can only guess as to how it is supposed to work from one of the eight example grammars.

In the calculator example, a category is set for Mult and for Div. Where is the field actually used?

• In a call to CONSUME(). This method is an implementation detail of the recognizer. Antlr grammars are specifications, not implementations.
• In retrieving a token value.

It isn't clear what value a category brings.

[matthew-dean]

Categories in Chevrotain are like virtual tokens.

Say you have a lexer spec like:

AttributeFlag : [is];
PlainIdent : [a-zA-Z]+;

There are places in your parser where you want to accept any identifier, so you might want something like:

rule1 : '(' AttributeFlag | PlainIdent ')';

However, there may be many places in the parser where you want to accept any identifier, in which case, in Antlr, it looks like you may do something like:

AttributeFlag : [is] -> type(Ident);
PlainIdent : [a-zA-Z]+ -> type(Ident);

This simplifies the parser:

rule1 : '(' Ident ')';

...except now we come to a rule where we can only accept "i" or "s"

attributeRule: '[' Ident (ws AttributeFlag)? ']'

In Chevrotain, you can essentially "alias" tokens to other virtual tokens using categories, and reference them in the parser where any of that token is acceptable, as in:

// lexer (using Antlr-like syntax for readability)
Tilde : '~' -> type(Combinator);
Plus : '+' -> type(AdditionOp, Combinator);
Minus : '-' -> type(AdditionOp);

// parser
selector : SelectorToken Combinator SelectorToken;
addition : Number AdditionOp Number;

// or even
language : 'C' Plus Plus; // "Plus" is still a valid token identifier

So it allows you to preserve the token type, or use another token type in your parser grammar, which can simplify the parser a lot.

As to this:

Where is the field actually used? In a call to CONSUME(). This method is an implementation detail of the recognizer.

No, it isn't. It is the specification and the implementation, as in, it is how the specification is written, and can be statically analyzed, generate railroad diagrams, etc. I'm not saying combining the two is the best way to do it (as it limits you to one implementation language), which is one reason why I'm experimenting with Antlr, but each "method" call is also, effectively, a lexer or parser rule definition the same as a .g4 file.

[matthew-dean]

Maybe there's a fundamental piece of Antlr that I'm misunderstanding. If I'm looking at something like the Java 9 lexer, it has a list of keywords, but those keywords aren't referenced in the parser. Is it identifying those those keywords as the keyword but also Identifier based on this such that this rule matches all keywords?

[KvanTTT]

Yes, identifier parse rule handles all identifiers including contextual keywords. There is a feature request Token value comparison operator for keywords handling simplifying, but it's not implemented.

[kaby76]

AttributeFlag : [is];
PlainIdent : [a-zA-Z]+;
rule1 : '(' AttributeFlag | PlainIdent ')';
AttributeFlag : [is] -> type(Ident);
PlainIdent : [a-zA-Z]+ -> type(Ident);
rule1 : '(' Ident ')';
attributeRule: '[' Ident (ws AttributeFlag)? ']'

Referencing AttributeFlag cannot work in Antlr. I checked using both split and combined grammar, and using a tokens declared token type (see below example) and a rule that would never match.

Here are the .g4's for a split grammar.

lexer grammar TestLexer;
tokens { Ident }
AttributeFlag : [is] -> type(Ident);
PlainIdent : [a-zA-Z]+ -> type(Ident);
WS : [ \t\n\r]+ -> skip;
LP: '(';
RP: ')';
LB: '[';
RB: ']';
S: ';';

parser grammar TestParser;
options { tokenVocab=TestLexer; }
start : r (';' r)* EOF;
r : rule1 | attributeRule;
rule1 : '(' Ident ')';
attributeRule: '[' Ident AttributeFlag? ']';

-> type(Ident) means that the token type is Ident. The command antlr4 TestLexer.g4 generates a lexer .tokens file has a mapping of Ident=1, and there is no token type AttributeFlag. Following the first call, the command antlr4 TestParser.g4 generates the warning implicit definition of token AttributeFlag. While it also generates .tokens file with AttrbiuteFlag, this cannot be returned by any rule in the lexer. The parser fails for input [abc i].

$ ./bin/Debug/net7.0/Test.exe -input '( abc ); [ abc]; [abc i]'
line 1:22 extraneous input 'i' expecting {']', AttributeFlag}

In other words, a token type is just an integer, not a set of integers.

If I'm looking at something like the Java 9 lexer, it has a list of keywords, but those keywords aren't referenced in the parser.

This can be confusing, but most keywords are referenced in the parser grammar for java/java9. Antlr creates a table of aliases between lexer symbol name and the string literal it represents. To actually see what lexer rules that are not referenced, the string literals have to be unfolded, which is how Antlr works. Using Trash, clone the grammars-v4 repo, cd to java/java9, and execute the command rm -rf xxxx; mkdir xxxx; trparse *.g4 | trfoldlit | trsponge -o xxxx; trparse xxxx/*.g4 | trxgrep 'for $i in (//lexerRuleSpec[not(FRAGMENT)]/TOKEN_REF) return concat($i/text(), " ", count(doc("*")//parserRuleSpec/ruleBlock//TOKEN_REF[text() = $i/text()]))' | grep " 0". This command parses the two grammar files, folds the string literals out of the RHS of all parser rules, then counts all occurrences of the lexer symbol on the RHS of a parser rule. The only rules not referenced are GOTO, CONST, and UNDER_SCORE but these are bugs in the grammar. The rests of the rules are referenced. Rules that are skip or hidden should never be referenced in a parser rule.

Yes, identifier : Identifier | 'to' | 'module' | 'open' | 'with' | 'provides' | 'uses' | 'opens' | 'requires' | 'exports'; is how https://docs.oracle.com/javase/specs/jls/se20/html/jls-3.html#jls-ContextualKeyword is implemented. (Looks like the grammar should be updated for Java 20.)