使用backtrack选项时，编译器的性能急剧下降

Maik Schmidt 发表于 Dev

迈克·施密特（Maik Schmidt）

我已经在Windows7上使用ANTLR3的C＃版本为类C语言实现了Transpiler。

为了解析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}
        )

那就是我已经将最后两个选择合并为一个。

现在，Transpiler的运行速度非常快，并且仍然可以返回正确的结果。

我真的很想知道为什么这种变化会带来如此大的变化。

艾拉·巴克斯特（Ira Baxter）

欢迎回溯。

如果强制解析器在（例如）三个选项之间进行选择（如您在语法中一样），并且必须回溯，并且这些选项嵌套（如if-then-else一样），则嵌套的N集构造可能需要3 ^ N个工作单元来解析。3 ^ 20是3 ^ 17的27倍。

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

对于您的语法，为什么不像对待其他所有语句一样对待if构造？这样就不会出现特殊情况，您可以完全避免回溯。您甚至可以获得标准的“否则，则附加到最接近的if”规则，这是大多数编程语言中的标准规则。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。