[antlr-interest] slowdown

Justin Murray jmurray at aerotech.com
Thu Dec 16 08:56:37 PST 2010


Hello,

 

I have started adding {actions} to my grammar, and have noticed that the
code generation started taking much longer than before. I used the
-Xwatchconversion flag to try to get an idea of what is happening. What
I found is that the generation gets to the following point:

 

attempting LL(1) DFA (d=627) for ()* loopback of 1409:3: (o= OR e2=
exprAND )*

--------------------

attempting LL(1) DFA (d=628) for ()* loopback of 1417:3: (o= AND e2=
exprBOR )*

--------------------

attempting LL(1) DFA (d=629) for ()* loopback of 1425:3: (o= BOR e2=
exprBXOR | o= BNOR e2= exprBXOR )*

--------------------

attempting LL(1) DFA (d=630) for ()* loopback of 1434:3: (o= BXOR e2=
exprBAND )*

--------------------

attempting LL(1) DFA (d=631) for ()* loopback of 1442:3: (o= BAND e2=
exprEqual | o= BNAND e2= exprEqual )*

--------------------

attempting LL(1) DFA (d=632) for ()* loopback of 1451:3: (o= ( EQ | '='
) e2= exprComp | o= NE e2= exprComp )*

--------------------

attempting LL(1) DFA (d=633) for ()* loopback of 1460:3: (o= LT_ e2=
exprShift | o= LE e2= exprShift | o= GT e2= exprShift | o= GE e2=
exprShift )*

--------------------

attempting LL(1) DFA (d=634) for ()* loopback of 1471:3: (o= '<<' e2=
exprAdd | o= '>>' e2= exprAdd )*

--------------------

attempting LL(1) DFA (d=635) for ()* loopback of 1481:3: (o= '+' e2=
exprMult | o= '-' e2= exprMult )*

decision 635 not suitable for LL(1)-optimized DFA analysis

--------------------

building lookahead DFA (d=635) for ()* loopback of 1481:3: (o= '+' e2=
exprMult | o= '-' e2= exprMult )*

convert DFA state 0 (174414 nfa states)

convert DFA state 29 (106645 nfa states)

 

It then hangs on this last line for several minutes (3 or 4), before
proceeding on with this output:

 

trying decision 635 again with k=1; reason: non-LL(*) && predicate
visible

convert DFA state 0 (174414 nfa states)

convert DFA state 29 (106645 nfa states)

convert DFA state 30 (106645 nfa states)

cost: 173 states, 160260 ms

--------------------

attempting LL(1) DFA (d=636) for ()* loopback of 1490:3: (o= '*' e2=
exprPow | o= '/' e2= exprPow | o= '%' e2= exprPow )*

 

While it is possible that I may have inadvertently changed the syntax,
for the most part I was just adding in my action code. The first
question is, should adding action code have any effect on the time it
takes to generate the code? That aside, what would cause the lengthy
hangup on that one decision? The rest of the decisions go by very
quickly.

 

Thanks,

Justin Murray 
Software Engineer 
jmurray at aerotech.com

Aerotech, Inc. 
101 Zeta Drive 
Pittsburgh, PA 15238 
412-963-7470

 



More information about the antlr-interest mailing list