antlr3 - 使用回溯选项时编译器的性能急剧下降

Question

我在 Windows7 上使用 C# 版本的 ANTLR3 实现了类似 C 语言的转译器。

为了解析 if/else 语句，我使用以下规则:

ifStatement
: 'if' '(' expression ')' b1=block
   (
       'else' b2=block      -> ^('if' expression $b1 $b2 'else')
   |   'else' ifStatement   -> ^('if' expression $b1 ^(ELSIF ifStatement))
   |                        -> ^('if' expression $b1)
   )
;

为了将此规则生成的树从我自己的语言翻译成 C#，我使用以下语法片段:

ifStatement
options { backtrack = true; }
: 
     ^(n='if' expression b1=block)
     -> if(
          node={$n},
          cond={$expression.st},
          block1={$b1.st},
          block2={null},
          isElsif={($n.Parent.Text == "ELSIF") ? "true" : null},
          node2={null}
        )
|
     ^(n='if' expression b1=block b2=block n2='else')
     -> if(
          node={$n},
          cond={$expression.st},
          block1={$b1.st},
          block2={$b2.st},
          isElsif={($n.Parent.Text == "ELSIF") ? "true" : null},
          node2={$n2}
        )
|
     ^(n='if' expression b1=block b2=ifStatement)
     -> elsif(
          node={$n},
          cond={$expression.st},
          block1={$b1.st},
          block2={$b2.st},
          isElsif={($n.Parent.Text == "ELSIF") ? "true" : null}
        )
|
     ^(ELSIF i=ifStatement) -> { $i.st }
;

这在大多数情况下都可以正常工作，例如，它可以毫无问题地翻译以下代码:

if (x == "1") {
}
else if (x == "2") {
}
else if (x == "3") {
}

但是当我有超过 20 个“else if”子句时，编译器需要几分钟才能完成工作。编译所需的时间不会线性增加，即编译器立即返回 17 或 18 个“else if”子句。

更新:

我已经解决了这个问题。我已经更换了

     ^(n='if' expression b1=block b2=ifStatement)
     -> elsif(
          node={$n},
          cond={$expression.st},
          block1={$b1.st},
          block2={$b2.st},
          isElsif={($n.Parent.Text == "ELSIF") ? "true" : null}
        )
|
     ^(ELSIF i=ifStatement) -> { $i.st }

与

     ^(n='if' expression b1=block ^(ELSIF b2=ifStatement))
     -> elsif(
          node={$n},
          cond={$expression.st},
          block1={$b1.st},
          block2={$b2.st},
          isElsif={($n.Parent.Text == "ELSIF") ? "true" : null}
        )

也就是说，我已将最后两个替代方案合并为一个。

现在转译器速度非常快，并且仍然返回正确的结果。

我真的很想知道为什么这一变化会产生如此大的差异。

Answer 1

欢迎回溯。

如果你强制解析器在(例如)三个选择之间进行选择(就像你在语法中所做的那样)，它必须回溯，并且选择嵌套 [作为你的 if-then- else 确实如此]，那么 N 个构造的嵌套集合可能需要 3^N 个工作单元来解析。 3^20 是 3^17 的 27 倍。

教训:回溯有时很有用，但通常应该避免它。

对于您的语法，为什么不像其他语句一样对待 if 结构呢？那么它就不会显示为特殊情况，并且您可以完全避免回溯。您甚至可以获得标准的“else 附加到最接近的 if”规则，这是大多数编程语言的标准。