如何处理无限递归

Question

让我们以下面的示例语法为例：

Model:
    m+=Main*
;

Main:
    "bla" r=Rule1
    | Rule3
    | Rule2
;

    Rule1:
        i=INT
        | "key" r=Rule2
    ;

    Rule2:
        "b" r=Rule3
    ;

    Rule3:
        "b" (r=Rule1 | r=Rule2)
    ;

当我编译这个时，我收到错误消息：

error(211): ../org.xtext.example.test/src-gen/org/xtext/example/test/parser/antlr/internal/InternalTest.g:119:1: [fatal] rule ruleMain has non-LL(*) decision due to recursive rule invocations reachable from alts 2,3.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.

据我了解，这个问题是因为 Rule3 的 ruleCall 可以无限长（因为 Rule3 可以调用 Rule2，然后可以再次调用 Rule3，依此类推......）以及 Rule2 的 ruleCall。
因此，解析器无法为这些无限规则调用创建前瞻，在规则 Main 中，我们要求解析器在这些无限替代方案之间做出决定，但缺少前瞻会导致此错误消息...
（如果我错了请纠正我）

我的问题是如何解决这个问题？
必须有一种方法来重构这个语法，以便解析器可以处理它。

乌鸦问候

Answer 1

如果我查看您的语法，我发现您有一个 Rule2 和 Rule3，它们只能在一个规则中进行重构。因为您的规则 2 和 3 以 "b" 开头。所以如果你有 'Rule2 : "b" r=(Rule1 | Rule2) ;' 也是一样的。在我看来，规则 3 是不必要的。我会像这样重构你的语法：

Model:
    m+=Main*
;

Main:
    "bla" r=Rule1
    | Rule2
;

Rule1:
    i=INT
    | "key" r=Rule2
;

Rule2:
    "b" r=(Rule1 | Rule2)
;

如何处理无限递归

How to deal with endless recursion

parsing

antlr

grammar

antlr3

xtext