antlr3 - Performance of compiler decreases drastically when using backtrack option -

i've implemented transpiler c-like language using c# version of antlr3 on windows7.

to parse if/else statements use following rule:

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

to translate tree generated rule own language c# use following grammar snippet:

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 } ; 

this works fine in cases, example translates following code without problems:

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

but when have more 20 "else if" clauses, compiler needs several minutes work. time needed compilation not increase linearly, compiler returns 17 or 18 "else if" clauses.

update:

i have fixed issue. i've replaced

     ^(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 } 

with

     ^(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}         ) 

that i've merged last 2 alternatives single one.

now transpiler blazingly fast , still returns correct results.

i'd know why change makes such big difference.

welcome backtracking.

if force parser choose between (for example) 3 choices (as have in grammar), , has backtrack, , choices nest [as if-then-else does], nested set of n constructs can require 3^n units of work parse. 3^20 27 times long 3^17.

lesson: backtracking useful sometimes, should avoid it.

for grammar, why not treat if construct every other statement? doesn't show special case, , can avoid backtracking altogether. you'll standard "else attaches closest if" rule standard in programming langauges.