[antlr-interest] target language independent action code

Mark Wright markwright at internode.on.net
Sun Jan 20 21:34:17 PST 2008


On Sun, 20 Jan 2008 19:42:38 -0800 (PST)
Loring Craymer <lgcraymer at yahoo.com> wrote:

> Mark--
> 
> Oh good--someone with a very large parser.  How much of the generated
> code is DFA definitions?  That is, if you split the file where the
> DFA classes start appearing, how big are the two pieces?  From the
> cases I have seen, DFA classes grow non-linearly with the size of the
> grammar.  For a generated file to be this large, my guess is that
> most of the code is DFA definitions that could be generated in
> separate files in a dfa directory to end up with manageable file
> sizes.
> 
> --Loring

Hello Loring,

Thanks for you interest, some stats are below.

The stats say there is no backtracking, and no syntactic predicates.
Instead there is thousands of lines (in separate Java files) of
dis-ambiguating semantic predicates that do things like:

* scan backwards one or two symbols to retrieve a
pointer from a token (that was set in an earlier action)
to a symbol table entry necessary (if it is present)
to understand what comes next.

* scan forwards looking for dis-ambiguating tokens.

* look up stuff in symbol tables.

* scan forwards with little hand coded recursive descent compilers
looking up stuff in symbols tables and looking for dis-ambiguating
tokens.

There is a reason for this madness:

p. 256 ANTLR book:
"When building grammars for really difficult languages such as C++,
engineers often leave the grammar in a natural condition and then
add semantic predicates ... to manually scan ahead looking for
the distinguishing symbol."

Thanks, Mark

goanna% wc TntdboParser.java                
   41973  104845 2507347 TntdboParser.java
goanna% grep -n "extends DFA" TntdboParser.java
27312:    class DFA6 extends DFA {
28163:    class DFA14 extends DFA {
28641:    class DFA22 extends DFA {
28801:    class DFA28 extends DFA {
28941:    class DFA33 extends DFA {
29051:    class DFA34 extends DFA {
29165:    class DFA35 extends DFA {
29366:    class DFA41 extends DFA {
29462:    class DFA51 extends DFA {
29596:    class DFA59 extends DFA {
30451:    class DFA60 extends DFA {
31328:    class DFA62 extends DFA {
31825:    class DFA68 extends DFA {
32323:    class DFA72 extends DFA {
32809:    class DFA76 extends DFA {
33455:    class DFA77 extends DFA {
33534:    class DFA81 extends DFA {
33663:    class DFA94 extends DFA {
33837:    class DFA123 extends DFA {
33976:    class DFA133 extends DFA {
34482:    class DFA135 extends DFA {
34727:    class DFA138 extends DFA {
34912:    class DFA139 extends DFA {
35082:    class DFA141 extends DFA {
35252:    class DFA142 extends DFA {
35340:    class DFA151 extends DFA {
35550:    class DFA159 extends DFA {
35685:    class DFA168 extends DFA {
35830:    class DFA174 extends DFA {
36409:    class DFA175 extends DFA {
36558:    class DFA178 extends DFA {
37286:    class DFA195 extends DFA {
37797:    class DFA199 extends DFA {
38441:    class DFA212 extends DFA {
38945:    class DFA231 extends DFA {
39061:    class DFA236 extends DFA {
39976:    class DFA237 extends DFA {
40484:    class DFA243 extends DFA {
goanna% ls -al TntdboParser.java 
-rw-rw-r--   1 mwright  eng      2507347 Jan 21 01:31 TntdboParser.java
goanna% 

java -Xmx256m
-classpath /h/goanna/2/eng/dev/tntdbo/java_src:/h/goanna/2/eng/dev/tntdbo:/h/goanna/2/ts/antlr/antlr-2007-12-28.10/lib/antlr-2007-12-28.10.jar:/h/goanna/2/ts/antlr/antlr-2007-12-28.10/lib/runtime-2007-12-28.10.jar:/h/goanna/2/ts/antlr/antlr-2007-12-28.10/lib/stringtemplate-3.1b1.jar:/h/goanna/2/ts/antlr/antlr-2007-12-28.10/lib/antlr-2.7.7.jar
org.antlr.Tool -Xconversiontimeout 60000 -report Tntdbo.g ANTLR Parser
Generator  Version 3.1b1 (??)  1989-2007 ANTLR Grammar Report; Stats
Version 4 Grammar: Tntdbo Type: combined
Target language: Java
Output: AST
Grammar option k: none
Grammar option backtrack: false
Rules: 181
Productions: 450
Decisions: 252
Cyclic DFA decisions: 0
LL(1) decisions: 155
Min fixed k: -1
Max fixed k: 5
Average fixed k: 0.4722222222222222
Standard deviation of fixed k: 1.0763771972404776
Min acyclic DFA states: 0
Max acyclic DFA states: 95
Average acyclic DFA states: 8.738095238095237
Standard deviation of acyclic DFA states: 17.405489160926603
Total acyclic DFA states: 2202
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: 269
DFA creation time in ms: 28142
Number of semantic predicates found: 111
Number of manual fixed lookahead k=value options: 56
Number of nondeterministic decisions: 97
Number of nondeterministic decisions resolved with predicates: 97
Number of DFA conversions terminated early: 0
Number of errors: 0
Number of warnings: 0
Number of infos: 0
Number of syntactic predicates found: 0
Decisions with syntactic predicates: 0
Decision DFAs using syntactic predicates: 0
Decisions with semantic predicates: 56
Decision DFAs using semantic predicates: 97

Backtracking report:
Number of decisions that backtrack: 0

NFA conversion early termination report:
Number of NFA conversions that terminated early: 0


Compilation finished at Mon Jan 21 01:31:10

-- 


More information about the antlr-interest mailing list