[antlr-interest] LL(1), LL(k), LL(*), predicated decisions

[Terence Parr]

On Jun 5, 2006, at 3:15 PM, Loring Craymer wrote:

> Ter--
>
> Out of curiosity, what's the distribution of k values in  
> representative
> grammars?

Here is what I get running -report when running antlr on java.g (all  
but 3 decisions are fixed LL(k) out of 90):

ANTLR Grammar Report; Stats Version 2
Grammar: JavaParser
Type: combined
Target language: Java
Rules: 67
Productions: 108
Decisions: 87
Cyclic DFA decisions: 3
Min fixed k: 1
Max fixed k: 2
Average fixed k: 1.130952380952381
Standard deviation of fixed k: 0.33937440336141017
Min acyclic DFA states: 3
Max acyclic DFA states: 11
Average acyclic DFA states: 3.392857142857143
Standard deviation of acyclic DFA states: 1.1721451567543082
Total acyclic DFA states: 285
Min cyclic DFA states: 12
Max cyclic DFA states: 29
Average cyclic DFA states: 19.0
Standard deviation of cyclic DFA states: 8.888194417315589
Total cyclic DFA states: 57
Vocabulary size: 153
DFA creation time in ms: 447
Number of semantic predicates found: 0
Number of manual fixed lookahead k=value options: 2
Number of nondeterministic decisions: 4
Number of nondeterministic decisions resolved with predicates: 0
Number of DFA conversions terminated early: 0
Number of errors: 0
Number of warnings: 6
Number of infos: 1
Number of syntactic predicates found: 0
Decisions with syntactic predicates: 0
Decision DFAs using syntactic predicates: 0
Decisions with semantic predicates: 0
Decision DFAs using semantic predicates: 0

>   It might be useful to be able to gather that statistic when
> trying to optimize a grammar; in fact, it might be useful to get  
> that on a
> per-rule basis (eventually) and feed that to ANTLRWorks.  Also, we  
> know from
> experience that tree grammars have predominantly LL(1) decisions-- 
> especially
> since up until ANTLR 3 tree grammars have been predicated-LL(1) of
> necessity--and the same is probably true of most parser grammars.

Yup.  Running ANTLR -report on my symbol phase of mantra, I get  
following.  Note that there are no cyclic DFA states and max k=2:

ANTLR Grammar Report; Stats Version 2
Grammar: ResolvePhase
Type: tree
Target language: Java
Rules: 36
Productions: 82
Decisions: 47
Cyclic DFA decisions: 0
Min fixed k: 1
Max fixed k: 2
Average fixed k: 1.0425531914893618
Standard deviation of fixed k: 0.2040297088885788
Min acyclic DFA states: 3
Max acyclic DFA states: 15
Average acyclic DFA states: 3.8297872340425534
Standard deviation of acyclic DFA states: 2.6401510903418934
Total acyclic DFA states: 180
Min cyclic DFA states: 0
Max cyclic DFA states: 0
Average cyclic DFA states: 0.0
Standard deviation of cyclic DFA states: 0.0
Total cyclic DFA states: 0
Vocabulary size: 119
DFA creation time in ms: 134
Number of semantic predicates found: 0
Number of manual fixed lookahead k=value options: 0
Number of nondeterministic decisions: 0
Number of nondeterministic decisions resolved with predicates: 0
Number of DFA conversions terminated early: 0
Number of errors: 0
Number of warnings: 0
Number of infos: 1
Number of syntactic predicates found: 0
Decisions with syntactic predicates: 0
Decision DFAs using syntactic predicates: 0
Decisions with semantic predicates: 0
Decision DFAs using semantic predicates: 0

> Given the code bloat resulting from excessive DFAs, I rather think  
> that not
> only was the investigation worthwhile, but it also merits follow-up  
> when
> time is available.

Yup.  Note that .class file size with inline DFA and then with table- 
driven DFA including set up code:

-rw-r--r--   1 parrt  wheel  70289 Jun  5 13:59 JavaParser.class
-rw-r--r--   1 parrt  wheel  95637 Jun  5 14:26 JavaParser.class

C could kick java's ass on this probably--it just gives the encoded  
DFA, no set up time nor code needed.  Code size in loc is

     5412 JavaParser.java inline
     8042 JavaParser.java table-base DFA

Ter