antlr / antlr/antlr4

Semantic predicates does not work as expected with left recursion

Open
#1,968 13 comments 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 the following grammar:

```antlr
start: rule EOF;
rule: rule suffix | value;
suffix: {!isParentRule(ContextualRuleContext.class)}? 'bar' contextualRule;
contextualRule: rule;
value: 'foo';
```
Where `isParentRule` checks if the current context has a parent context which extends from a given class.

The problem is that an input like `foobarfoobarfoo` always results in "no viable alternative". I expected that whenever the semantic predicate returns false, the immediate parent suffix would match.

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the supplied grammar with the input `foobarfoobarfoo`, focusing on the left-recursive `rule`, `suffix`, and `contextualRule` productions and the `isParentRule` predicate. Trace how the semantic predicate is evaluated during left-recursion handling; done means the input parses as expected when the predicate returns false for the immediate parent suffix.

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.