Token match clarification

[anderay]

Can someone explain why:

grammar HelloWorld
entry Model:
    (persons+=Person | greetings+=Greeting)*;
Person:
    'person' name=ID;
Greeting:
    'Hello' problem=PROBLEM person=[Person:ID] '!';
hidden terminal WS: /\s+/;
terminal PROBLEM: 'Problem';
terminal ID: /[_a-zA-Z][\w_]*/;
terminal INT returns number: /[0-9]+/;
terminal STRING: /"(\\.|[^"\\])*"|'(\\.|[^'\\])*'/;
hidden terminal ML_COMMENT: /\/\*[\s\S]*?\*\//;
hidden terminal SL_COMMENT: /\/\/[^\n\r]*/;

introduces problem e.g. for following input:

person ProblemPerson

whereas grammar with terminal as inline token gives no problem:

grammar HelloWorld
entry Model:
    (persons+=Person | greetings+=Greeting)*;
Person:
    'person' name=ID;
Greeting:
    'Hello' 'Problem' person=[Person:ID] '!';
hidden terminal WS: /\s+/;
terminal ID: /[_a-zA-Z][\w_]*/;
terminal INT returns number: /[0-9]+/;
terminal STRING: /"(\\.|[^"\\])*"|'(\\.|[^'\\])*'/;
hidden terminal ML_COMMENT: /\/\*[\s\S]*?\*\//;
hidden terminal SL_COMMENT: /\/\/[^\n\r]*/;

note that also data-type-rule works fine:

grammar HelloWorld
entry Model:
    (persons+=Person | greetings+=Greeting)*;
Person:
    'person' name=ID;
Greeting:
    'Hello' problem=PROBLEM person=[Person:ID] '!';
hidden terminal WS: /\s+/;
PROBLEM returns string: 'Problem';
terminal ID: /[_a-zA-Z][\w_]*/;
terminal INT returns number: /[0-9]+/;
terminal STRING: /"(\\.|[^"\\])*"|'(\\.|[^'\\])*'/;
hidden terminal ML_COMMENT: /\/\*[\s\S]*?\*\//;
hidden terminal SL_COMMENT: /\/\/[^\n\r]*/;

[msujew]

Hey @anderay

our underlying parser/lexer library (Chevrotain) performs first-fit lexing. I.e. it returns the terminal type that first matches the input at a given position. To match longer token sequences, Chevrotain requires to declare a longer_alt. Langium tries to identify these longer alternatives algorithmically, but can only do so for keywords.

The problem is pretty difficult, as identifying whether a regex is a longer alt of another regex isn't as simple compared to the keyword case (and this problem/property might be symmetrical, making it potentially ambiguous).

As for why it works in a datatype rule: A datatype rule isn't evaluated during the lexing phase, so it is handled by the algorithm mentioned above.

[anderay]

Could you elaborate more on longer_alt?
Also how this behaviour compares to Xtext (where no such problem observed)?

[msujew]

There is a lot of documentation on it over at the chevrotain docs.

The difference to xtext is due to the mentioned first-fit matching. Xtext uses Antlr, which performs longest-fit. It has no need for the longer_alt, but takes a performance hit in return.

Note that Langiums behavior can be overriden by overriding the TokenBuilder service in Langium.

[szarnekow]

Can you elaborate on the aforementioned performance hit?
As far as I can tell, Chevrotain uses linear probing for the tokens whereas Antlr doesn't. So my best guess would be that Chevrotain scales linearly with the number of keywords and Antlr searches a single tree that is built from the terminal definitions. Can you help me understand what you were referring to?