antlr / antlr/antlr4

Ambiguity bug

Open
#2,575 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Java
Stars
19k
Forks
3.5k
PR merge metrics
No merged PRs in 30d

Description

I have an issue described [here](https://github.com/antlr/intellij-plugin-v4/issues/361).
Reproducing it here for convenience

I have a simple parser
```antlr4
prog: rawStatement;

rawStatement
: expression
;

chain
: VarName memberAccess*
;

memberAccess
: Dot VarName arguments?
;

expression
: constant #ScalarExpression
| chain #ChainExpression
| expression op=('+' | '-') expression #ArithmeticExpression
| chain '=' expression #AssignmentExpression
;

constant
: Decimal
;

arguments
: '(' actualArgument? ')'
| actualArgument
;

actualArgument
: expression
| chain
;
```
where lexer rules are
```antlr4
VarName: [a-zA-Z_][a-zA-Z_0-9]*;
Decimal: Digit+;
fragment Digit: [0-9];
Dot: '.';
```
and the input `abc = 1+2`. The output should be obvious, but profiler produces
![image](https://user-images.githubusercontent.com/33381180/59608323-c5325500-911d-11e9-831f-8855b102d477.png)
The issue here that I don't have any dots in the input but antlr goes to `arguments` rule. It can be spotted because after adding something to the end of memberAccess like
```antlr4
memberAccess
: Dot VarName arguments? Dot
;
```
the ambiguity disappears.
Looks like antlr is looking from right to left too, going to `arguments:2` rule, then `actualArgument`, then to `expression` and finally recognizes `(abc = 1)+2` expression.

I also saw [this](https://github.com/antlr/antlr4/issues/1209), but it doesn't seem to be my particular case.

Contributor guide

Open the contributing guide

Research direction

Start with the reproduced grammar, especially memberAccess, arguments, actualArgument, and expression, and run the abc = 1+2 example through the profiler. Trace why arguments is explored despite no dot in the input, then verify that the ambiguity is resolved without the added trailing Dot rule.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.