Application of precedence in multi alternative rule having common prefix

[n-dragon]

hi,

I'm using :
antlr : 4.7.1
antlr intellij plugin: 1.23

I have the following lexer/grammar:

lexer grammar Test;


LSQUARE       : '[';
LT            : '<';

MINUS         : '-';

RSQUARE       : ']';


fragment LETTER    : [a-zA-Z_];
fragment DIGIT     : [0-9];


IDENTIFIER: LETTER (LETTER|DIGIT)*;

 parser grammar Test;



parseExpression
	:	exp EOF
	;
exp:
    identifier  
    |
    collectionCreation
    |
    MINUS exp
    |
    exp LT MINUS parameters
    |
    exp LT exp
   ;





identifier
    :    IDENTIFIER
    ;




parameters
	:	LSQUARE (identifier) RSQUARE
	;


  collectionCreation
  	:	LSQUARE collectionEntry RSQUARE
  	;

  collectionEntry
      :   exp
      ;

I have the following expression:

a<-[test]

I expect antlr to parse it with rule "exp LT MINUS parameters" but it goes with "exp LT exp"
IntellijPlugin tells me that there is an ambiguity but changing rule alternative orders doesn't change anything.

issue seems to come from different rules starting with same token, it has higher precedence but order of check stays the same:
extract from antlr4 -Xlog Test.g4

  2 2024-08-28 16:49:00:313 left-recursion LogManager.java:25 exp
  3     :   ( {} identifier<tokenIndex=39>
  4         | collectionCreation<tokenIndex=43>
  5         | MINUS<tokenIndex=47> exp<tokenIndex=49,p=3>
  6         )
  7         (
  8           {precpred(_ctx, 1)}?<p=1> LT<tokenIndex=65> exp<tokenIndex=67,p=2>
  9                   | {precpred(_ctx, 2)}?<p=2> LT<tokenIndex=55> MINUS<tokenIndex=57> parameters<tokenIndex=59>
 10         )*
 11     ;

what would be the solution to force antlr to match longest token sequence ?

Update:

Antlr4 seems to always take combination of several rules instead a one.
in this case I have rules:

• MINUS exp
• LT exp
• exp LT MINUS parameters

=> ANTLR seems to always take combination of rules having same combination of token instead of one having all

[kaby76]

Is there a reason why you don't define a lexer rule for the operator <-?

[n-dragon]

I thought about it but lexer is greedy and so I would have a new token LTMINUS that blocks parsing of 1<-2.
as it would tokenize as IDENTIFIER LTMINUS IDENTIFIER which does not match exp LT MINUS parameters

[jimidle]

Your MINUS exp unary rule has the highest precedence so it takes that, which it should. Make <- a single token. On Aug 28, 2024, at 15:37, Ken Domino ***@***.***> wrote: Is there a reason why you don't define a lexer rule for the operator <-? —Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[n-dragon]

that's the funny part,
my rules are:

• 5.identifier
• 4.collectionCreation
• 3.MINUS exp
• 2.exp LT MINUS parameters
• 1.exp LT exp

when doing a<-[test] it goes into :

• identifier (5)
• exp LT exp (1)
• MINUS exp (3)

when it should do:

• identifier (5)
• exp LT MINUS parameters (2) // here 2 >1 of rule exp LT exp

[n-dragon]

Is there a reason why you don't define a lexer rule for the operator <-?

as mentioned above, tokenizer is greedy and so I won't be able to recognize rule : 1<-2 as it would be parsed as exp LTMINUS exp

[kaby76]

as mentioned above, tokenizer is greedy and so I won't be able to recognize rule : 1<-2 as it would be parsed as exp LTMINUS exp

Then try something like the following grammar.

Your grammar contains a number of unnecessary single-use productions. Simplify.

lexer grammar TestLexer;
LTMINUS : '<-' { this.InputStream.LA(1) == '[' }?;
LSQUARE       : '[';
LT            : '<';
MINUS         : '-';
RSQUARE       : ']';
fragment LETTER    : [a-zA-Z_];
fragment DIGIT     : [0-9];
IDENTIFIER: LETTER (LETTER|DIGIT)*;

parser grammar TestParser;
options { tokenVocab = TestLexer; }
parser grammar TestParser;
options { tokenVocab = TestLexer; }
parseExpression: exp EOF ;
exp
    : MINUS exp
    | exp LTMINUS exp
    | exp LT exp
    | IDENTIFIER
    | LSQUARE exp RSQUARE
    ;

$ ./bin/Debug/net8.0/Test.exe -tree -input 'a<-b'
(parseExpression (exp (exp a) < (exp - (exp b))) <EOF>)
CSharp 0 string0 success 0.0228248
Total Time: 0.1413432
08/29-04:10:17 ~/issues/a4-4686/Generated-CSharp
$ ./bin/Debug/net8.0/Test.exe -tree -input 'a<-[test]'
(parseExpression (exp (exp a) <- (exp [ (exp test) ])) <EOF>)
CSharp 0 string0 success 0.0224625
Total Time: 0.0663042
08/29-04:10:24 ~/issues/a4-4686/Generated-CSharp
$ ./bin/Debug/net8.0/Test.exe -tree -input 'a<--b'
(parseExpression (exp (exp a) < (exp - (exp - (exp b)))) <EOF>)
CSharp 0 string0 success 0.0224419
Total Time: 0.0669603
08/29-04:14:07 ~/issues/a4-4686/Generated-CSharp

Note, actions are target specific. This is in C#, but you can port it to whatever of the eight targets supported. Also, a grammar with actions cannot be "interpreted". You cannot use lab.antlr.org or "test this rule" in Intellij, but you can use "grun" or write your own driver.

If you don't like any of this, then you'll need to just implement operator precedence yourself using an operator precedence grammar (i.e., the change of parser rules you see in grammars like the Java Language Spec for expressions, "and_expr", "or_expr", "rel_op_expr", "mult_expr", "add_expr", etc).

[n-dragon]

hi,
thanks for the quick answer.
I thought about that but the issue is I have other kind of possibilities after LT MINUS,(example is a simple version of my real grammar)
but I will try to see if I can tokenize more to avoid ambiguity.
however the real question , is why antlr precedence application chose shortest matching tokens for a rule and does not apply precedence.

I will wait a bit but I think I will create an issue out of this behavior.
I looked into documentation and nothing mentioned this.

for your second point,
this is what I saw in antlr grammar repository, this should allow me to control more easily precedence but the negative side is code generated code where I need to pass through rules, number of created objects as my child rule are nested in parent rule and I don't know well performance impact of this kind of grammar.

[n-dragon]

here is the atn:

issue seems to come from here:

I don't understand why rule declared in 5th seems to be tested first ?

I don't mind pushing a merge request for the bug but I might need some guidance to start.

[MisterErwin]

(Just some educated guesses & pointers)

I see that you've inlined your collectionCreation rule, as indirect left recursive rules do not work (cough #4480 :) ).

The first adaptive prediction decision (whether < or <= should be used) appears to be ambiguous.

The PredictionMode#resolvesToJustOneViableAlt / #getSingleViableAlt simply returns the first alt(1 in your example) if all alt-subsets ( (1,2) in your case) from a configuration set (#getConflictingAltSubsets) have this one alt as their first one.

The precedence appears to only be respected in the discarding of left-recursive alts, not when resolving ambiguity.

Right now, I'm not sure if there should even be an ambiguity, as I would have to refresh my memory on precedence climbing 1 2.

When changing the predictedAlt to 2, as in the alt with the higher precedence in the PrecedencePredicate of its D.config, your input parses as expected, although it's a bit too late to run the testsuite to see what else breaks :)