CODEWITHSUNDEEP
antlr4
Matthew Gilliard
Matthew Gilliard

Reputation: 9498

Making a recursive antlr4 rule greedy

I'd like to have a grammar where a filter can be either an operation or any number of filters joined by |. My grammar is like this:

filter
  : filter ('|' filter)+  #pipedFilter
  | OPERATION             #operation
  ;


OPERATION
  : [a-z]+
  ;

(This is a simplified example, there will be other ways of grouping filters which have different precedence than piping)

On input like xxx|yyy this works fine, we get:

FILTER: [
  OPERATION: xxx,
  OPERATION: yyy
]

But for input of xxx|yyy|zzz we get:

FILTER: [
  OPERATION: xxx,
  FILTER: [
    OPERATION: yyy,
    OPERATION: zzz
  ]
]

and I would like

FILTER: [
  OPERATION: xxx,
  OPERATION: yyy,
  OPERATION: zzz
]

Both interpretations seem valid, but I would like the second. It seems to me that the problem is that the #pipedFilter rule isn't being applied as greedily as it could be. Is my understanding correct here? What can be the fix?

Upvotes: 1

Views: 95

Answers (1)

Mike Lischke
Mike Lischke

Reputation: 53407

It hasn't to do with greedyness. The default in ANTLR4 is to match as much as possible in one rule.

The output structure you get is dictated by your grammar. Don't make filter a recursive rule if you don't want a tree. What speaks against writing filter like so:

filter:
    OPERATION (PIPE OPERATION)?

If you absolutely need filters containing filters then, I'm afraid, there's no way around a tree like result.

Upvotes: 2

Related Questions