[antlr-interest] Decision DFA w/ 51 Nodes & 133 Arcs — Should I Be Worried?
Randall R Schulz
rschulz at sonic.net
Wed Jun 27 09:15:35 PDT 2007
Hi,
I'm concerned about what appears to me to be an outsized DFA for a
particular production in a grammar I'm working on.
As the subject says, this DFA has 51 nodes and 133 arcs (and two accept
states).
Is this a sign of a potential problem? Or do I just have an invalid
intuition about typical complexity and efficiency for LL(k) grammar
DFAs with backtracking?
Should I be looking at elaborating the grammar to reduce the complexity
of the DFA generated by this production?
Conversely, if I were to turn off backtracking and manually address the
ambiguity, would I just end up producing a lot of rules of comparable
complexity to this DFA?
I went systematically through the grammar viewing the decision DFA for
each production, and all the others are miniscule by comparison.
Thanks.
Randall Schulz
More information about the antlr-interest
mailing list