Incorrect Parser rule order
- Dominant language
- Java
- Stars
- 19k
- Forks
- 3.5k
- PR merge metrics
- No merged PRs in 30d
Description
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 : [ \t\r\n]+ -> 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
;
https://stackoverflow.com/questions/55386152/how-is-parser-rule-precedence-chosen-with-left-recursion-and-a-greedy-operat/55421390#55421390
Contributor guide
Research direction
Start with the minimal grammar in the issue and reproduce parse trees for 3 * 4 + 2 and 3 + 4 * 2. Compare those results with the grammar variant that moves the optional ALSO clause; a useful resolution would explain or correct the inconsistent precedence behavior.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100