antlr / antlr/antlr4

Left recursive rules that do not conform to a pattern ANTLR can handle

Open
#4,599 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

`VarsDecl.g4` describes the syntax of variable declarations, such as `int a, b, c`.

```
grammar VarsDecl;

decl : type vars ;
type : 'int' # IntType
| 'float' # FloatType
;
vars : left = vars ',' ID # VarsList
| ID # VarsID
;

ID : [a-z]+ ;
WS : [ \t\r\n]+ -> skip ;
```

`VarsDeclAG.g4` is the version of `VarsDeclAG.g4` with parameters of rules and and embedded actions.

```
grammar VarsDeclAG;

decl : type vars[$type.text] ;
type : 'int'
| 'float'
;
vars[String typeStr]
: left = vars[$typeStr] ',' ID { System.out.println($ID.text + " : " + $typeStr); }
| ID { System.out.println($ID.text + " : " + $typeStr); }
;

ID : [a-z]+ ;
WS : [ \t\r\n]+ -> skip ;
```

However, ANTLR 4 (version [antlr 'org.antlr:antlr4:4.13.1'](https://mvnrepository.com/artifact/org.antlr/antlr4)) reports that

`in VarsDeclAG.g4: rule vars is left recursive but doesn't conform to a pattern ANTLR can handle` (no errors in `VarsDecl.g4`).

The comments on [StackOverflow](https://stackoverflow.com/q/76062088/1833118) (thanks to [Bart Kiers](https://stackoverflow.com/users/50476/bart-kiers)) suggest that it may be a bug in [translateLeftRecursiveRule](https://github.com/antlr/antlr4/blob/8dcc6526cfb154d688497f31cf1e0904801c6df2/tool/src/org/antlr/v4/analysis/LeftRecursiveRuleTransformer.java#L94).

Contributor guide

Open the contributing guide

Research direction

Start with the VarsDecl.g4 and VarsDeclAG.g4 reproductions using ANTLR 4.13.1, comparing the accepted left-recursive rule with the parameterized version that fails. Read tool/src/org/antlr/v4/analysis/LeftRecursiveRuleTransformer.java, especially translateLeftRecursiveRule, and trace why the embedded action and rule parameter prevent recognition. Done means the parameterized grammar is handled without the reported error while preserving its demonstrated output.

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
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.