parsing - 如何从语法中删除间接左递归

Question

我有一些相互左递归的 ANTLR 代码：

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 ;

有想法该怎么解决这个吗？

Answer 1

ANTLR 4 只能处理直接左递归，但您的语法包含来自规则expr→ array_elem→的间接左递归expr。在您的特定语法中解决此问题的最简单方法是将规则内联array_elem到expr规则中，并使用标记的外部替代项为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
  ;

请注意以下关于使用标记的外部替代方案的限制：

1. 没有两个外部备选方案可以共享一个标签，并且标签不能匹配任何规则名称；标签在整个语法中必须是唯一的。
2. 如果标记了规则的一个外部替代项（例如array_elem替代项），则必须标记该规则的所有外部替代项。