CODEWITHSUNDEEP
parsingrecursionantlrgrammarleft-recursion
user2640331
user2640331

Reputation: 51

How to remove indirect left-recursion from grammar

I have some mutually left-recursive ANTLR code:

expr: int_liter
| bool_liter
| char_liter
| str_liter
| pair_liter
| ident
| array_elem
| unary_oper expr
| expr binary_oper expr
| OPEN_PARENTHESES expr CLOSE_PARENTHESES
;

array_elem:  expr  OPEN_BRACKET expr CLOSE_BRACKET ;

Any ideas on how to fix this?

Upvotes: 1

Views: 571

Answers (1)

Sam Harwell
Sam Harwell

Reputation: 99989

ANTLR 4 can handle direct left-recursion only, but your grammar contains indirect left recursion from the rules expr → array_elem → expr. The easiest way to resolve this problem in your particular grammar is to inline the array_elem rule into the expr rule, and use labeled outer alternatives to assign meaningful names to each of the alternatives in expr.

expr
  : int_liter                                # someLabel
  | bool_liter                               # someLabel               
  | char_liter                               # someLabel
  | str_liter                                # someLabel
  | pair_liter                               # someLabel
  | ident                                    # someLabel
  | expr OPEN_BRACKET expr CLOSE_BRACKET     # array_elem
  | unary_oper expr                          # someLabel
  | expr binary_oper expr                    # someLabel
  | OPEN_PARENTHESES expr CLOSE_PARENTHESES  # someLabel
  ;

Note the following constraints around using labeled outer alternatives:

  1. No two outer alternatives can share a label, and labels cannot match any rule name; labels must be unique throughout the grammar.
  2. If one outer alternative of a rule is labeled (e.g. the array_elem alternative), then all outer alternatives for that rule must be labeled.

Upvotes: 1

Related Questions