Styjun

Is the Amazon rainforest the "world's lungs"?

Stolen MacBook: should I worry about my data?

What is the sound/audio equivalent of "unsightly"?

Should I judge the efficacy of Samadhi based on the ethical qualities of the meditator?

If I said I had $100 when asked, but I actually had $200, would I be lying by omission?

What is the name of this plot that has rows with two connected dots?

In Endgame, wouldn't Stark have remembered Hulk busting out of the stairwell?

How could a self contained organic body propel itself in space

Employing a contractor proving difficult

Did the Apollo Guidance Computer really use 60% of the world's ICs in 1963?

What does GDPR mean to myself regarding my own data?

Was the six engine Boeing-747 ever seriously considered by Boeing?

Printing a list as "a, b, c." using Python

Term used to describe a person who predicts future outcomes

What to do about my 1-month-old boy peeing through diapers?

Why did the population of Bhutan drop by 70% between 2007 and 2008?

Why does `buck` mean `step-down`?

Did ancient peoples ever hide their treasure behind puzzles?

Don't look at what I did there

Why is 3/4 a simple meter while 6/8 is a compound meter?

Why is there no Disney logo in MCU movies?

Is there an in-universe explanation given to the senior Imperial Navy Officers as to why Darth Vader serves Emperor Palpatine?

How to reply to people who accuse me of putting people out of work?

Why does the weaker C–H bond have a higher wavenumber than the C=O bond?

How is parser rule precedence chosen with left recursion and a greedy '?' operator?

NodeVisitor class for PEG parser in PythonIs “Implicit token definition in parser rule” something to worry about?Overlapping Tokens in ANTLR 4How Lexer lookahead works with greedy and non-greedy matching in ANTLR3 and ANTLR4?ANTLR4 lexer not resolving ambiguity in grammar orderGrammar for ANLTR 4Antlr4 ignores tokensBind ANTLR4 subrules of a ruleANTLR4 grun rig doesn't appear to report tokens properly… do I understand this?Does -> skip change the behavior of the lexer rule precedence?How does ANTLR decide which lexer rule to apply? The longest matching lexer rule wins?

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

3

Taking an (almost) textbook example, where we expect multiplication to have precedence over addition, but also include an optional part to match.

expr : expr '*' expr ('ALSO')?
 | expr '+' expr
 | INT
 ;

INT: [0-9]+;

WS : [ trn]+ -> skip ;

When trying out the grammar with 3 * 4 + 2 we get an unexpected tree that looks like

 expr:1
 / | 
 expr:1 * expr:2
 | / | 
 3 expr:1 + expr:1
 | |
 4 2

However, when use 3 + 4 * 2 we get what I might expect

 expr:1
 / | 
 expr:1 + expr:2
 | / | 
 3 expr:1 * expr:1
 | |
 4 2

Also, if you switch the optional token to the second line, we get the expected tree every time.

expr : expr '*' expr
 | expr '+' expr ('ALSO')?
 | INT
 ;

I also tried this using the non-greedy operator ??, and defining lexer tokens so we don't have to worry about oddities around ordering due to implicit tokens.

What would explain this ordering?

antlr4

share|improve this question

asked Mar 27 at 20:45

CodyTCodyT

1833 bronze badges

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  For those reading this Q&A, the issue is reported here: github.com/antlr/antlr4/issues/2525
  
  – Bart Kiers
  Apr 1 at 10:49
  

  
  
  
  

add a comment | 

3

Taking an (almost) textbook example, where we expect multiplication to have precedence over addition, but also include an optional part to match.

expr : expr '*' expr ('ALSO')?
 | expr '+' expr
 | INT
 ;

INT: [0-9]+;

WS : [ trn]+ -> skip ;

When trying out the grammar with 3 * 4 + 2 we get an unexpected tree that looks like

 expr:1
 / | 
 expr:1 * expr:2
 | / | 
 3 expr:1 + expr:1
 | |
 4 2

However, when use 3 + 4 * 2 we get what I might expect

 expr:1
 / | 
 expr:1 + expr:2
 | / | 
 3 expr:1 * expr:1
 | |
 4 2

Also, if you switch the optional token to the second line, we get the expected tree every time.

expr : expr '*' expr
 | expr '+' expr ('ALSO')?
 | INT
 ;

I also tried this using the non-greedy operator ??, and defining lexer tokens so we don't have to worry about oddities around ordering due to implicit tokens.

What would explain this ordering?

antlr4

share|improve this question

asked Mar 27 at 20:45

CodyTCodyT

1833 bronze badges

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  For those reading this Q&A, the issue is reported here: github.com/antlr/antlr4/issues/2525
  
  – Bart Kiers
  Apr 1 at 10:49
  

  
  
  
  

add a comment | 

Taking an (almost) textbook example, where we expect multiplication to have precedence over addition, but also include an optional part to match.

expr : expr '*' expr ('ALSO')?
 | expr '+' expr
 | INT
 ;

INT: [0-9]+;

WS : [ trn]+ -> skip ;

When trying out the grammar with 3 * 4 + 2 we get an unexpected tree that looks like

 expr:1
 / | 
 expr:1 * expr:2
 | / | 
 3 expr:1 + expr:1
 | |
 4 2

However, when use 3 + 4 * 2 we get what I might expect

 expr:1
 / | 
 expr:1 + expr:2
 | / | 
 3 expr:1 * expr:1
 | |
 4 2

Also, if you switch the optional token to the second line, we get the expected tree every time.

expr : expr '*' expr
 | expr '+' expr ('ALSO')?
 | INT
 ;

I also tried this using the non-greedy operator ??, and defining lexer tokens so we don't have to worry about oddities around ordering due to implicit tokens.

What would explain this ordering?

antlr4

share|improve this question

asked Mar 27 at 20:45

CodyTCodyT

1833 bronze badges

expr : expr '*' expr ('ALSO')?
 | expr '+' expr
 | INT
 ;

INT: [0-9]+;

WS : [ trn]+ -> skip ;

 expr:1
 / | 
 expr:1 * expr:2
 | / | 
 3 expr:1 + expr:1
 | |
 4 2

 expr:1
 / | 
 expr:1 + expr:2
 | / | 
 3 expr:1 * expr:1
 | |
 4 2

expr : expr '*' expr
 | expr '+' expr ('ALSO')?
 | INT
 ;

share|improve this question

asked Mar 27 at 20:45

CodyTCodyT

1833 bronze badges

share|improve this question

asked Mar 27 at 20:45

CodyTCodyT

1833 bronze badges

asked Mar 27 at 20:45

CodyTCodyT

1833 bronze badges

asked Mar 27 at 20:45

CodyTCodyT

1833 bronze badges

1 Answer
1

active

oldest

votes

2

That looks like a bug. You can report it here: https://github.com/antlr/antlr4/issues (if it's not already reported... I did not check)

It seems a workaround would be to include an extra alternative that does not contain the ALSO token:

expr : expr '*' expr 'ALSO'
 | expr '*' expr
 | expr '+' expr
 | INT
 ;

which produces the expected parse trees for both 3 * 4 + 2 and 3 + 4 * 2.

share|improve this answer

answered Mar 29 at 16:06

Bart KiersBart Kiers

137k2929 gold badges255255 silver badges255255 bronze badges

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Bart, I was crawling through the golden parsing badge holders - could you have a look at my question with an open bounty ?
  
  – Jan
  Apr 1 at 9:33
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55386152%2fhow-is-parser-rule-precedence-chosen-with-left-recursion-and-a-greedy-operat%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

That looks like a bug. You can report it here: https://github.com/antlr/antlr4/issues (if it's not already reported... I did not check)

It seems a workaround would be to include an extra alternative that does not contain the ALSO token:

expr : expr '*' expr 'ALSO'
 | expr '*' expr
 | expr '+' expr
 | INT
 ;

which produces the expected parse trees for both 3 * 4 + 2 and 3 + 4 * 2.

share|improve this answer

answered Mar 29 at 16:06

Bart KiersBart Kiers

137k2929 gold badges255255 silver badges255255 bronze badges

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Bart, I was crawling through the golden parsing badge holders - could you have a look at my question with an open bounty ?
  
  – Jan
  Apr 1 at 9:33
  

  
  
  
  

add a comment | 

2

That looks like a bug. You can report it here: https://github.com/antlr/antlr4/issues (if it's not already reported... I did not check)

It seems a workaround would be to include an extra alternative that does not contain the ALSO token:

expr : expr '*' expr 'ALSO'
 | expr '*' expr
 | expr '+' expr
 | INT
 ;

which produces the expected parse trees for both 3 * 4 + 2 and 3 + 4 * 2.

share|improve this answer

answered Mar 29 at 16:06

Bart KiersBart Kiers

137k2929 gold badges255255 silver badges255255 bronze badges

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Bart, I was crawling through the golden parsing badge holders - could you have a look at my question with an open bounty ?
  
  – Jan
  Apr 1 at 9:33
  

  
  
  
  

add a comment | 

That looks like a bug. You can report it here: https://github.com/antlr/antlr4/issues (if it's not already reported... I did not check)

It seems a workaround would be to include an extra alternative that does not contain the ALSO token:

expr : expr '*' expr 'ALSO'
 | expr '*' expr
 | expr '+' expr
 | INT
 ;

which produces the expected parse trees for both 3 * 4 + 2 and 3 + 4 * 2.

share|improve this answer

answered Mar 29 at 16:06

Bart KiersBart Kiers

137k2929 gold badges255255 silver badges255255 bronze badges

expr : expr '*' expr 'ALSO'
 | expr '*' expr
 | expr '+' expr
 | INT
 ;

share|improve this answer

answered Mar 29 at 16:06

Bart KiersBart Kiers

137k2929 gold badges255255 silver badges255255 bronze badges

answered Mar 29 at 16:06

Bart KiersBart Kiers

137k2929 gold badges255255 silver badges255255 bronze badges

answered Mar 29 at 16:06

Bart KiersBart Kiers

137k2929 gold badges255255 silver badges255255 bronze badges