[antlr-interest] LL(*) conjectures

Loring Craymer lgcraymer at yahoo.com
Wed Aug 8 13:48:05 PDT 2007


I have reworked the java grammar for processing
without the backtracking options.  At the moment, I
have 12 synpreds but some of those should go away with
a bit more refactoring.  As I had expected from other
postings, the percentage of generated code devoted to
DFAs was larger than for the smaller grammars I had
been working with.  That makes sense:  the larger the
grammar, the harder it is to express in LL(1) form. 
Thinking along those lines led me to

1.)  DFA growth is non-linear in the number of
tokens/rules that comprise grammars.
2.)  Automated backtracking generates synpreds
non-linearly with grammar size.
3.)  This growth can be countered by refactoring
grammars towards an LL(1) form.

Assuming that these conjectures are correct, then the
proper way of keeping generated files to a manageable
size is to generate DFA code into separate files from
the main body of code.  Effort should be invested to
provide better analysis/reporting for identifying
decision points that might benefit from refactoring,
and in the codification of useful refactorings for
incorporation into ANTLRWorks and similar tools.

--Loring


      ____________________________________________________________________________________
Park yourself in front of a world of choices in alternative vehicles. Visit the Yahoo! Auto Green Center.
http://autos.yahoo.com/green_center/ 


More information about the antlr-interest mailing list