[antlr-interest] target language independent action code

[Loring Craymer]

Mark--

Thanks for the info!  The explanation of "lots of sempreds" is also helpful--hoisting will contribute to the code size, and could be the reason that DFA defs are "only" 1/3 of the total.

--Loring

----- Original Message ----
> From: Mark Wright <markwright at internode.on.net>
> To: antlr-interest at antlr.org
> Sent: Sunday, January 20, 2008 9:34:17 PM
> Subject: Re: [antlr-interest] target language independent action code
> 
> On Sun, 20 Jan 2008 19:42:38 -0800 (PST)
> Loring Craymer  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/a
> ntlr/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-2
> 8.10/lib/stringtemplate-3.1b1.jar:/h/goanna/2/ts/antlr/antlr-2007-12-28.10/lib/a
> ntlr-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
> 
> -- 
> 




      ____________________________________________________________________________________
Looking for last minute shopping deals?  
Find them fast with Yahoo! Search.  http://tools.search.yahoo.com/newsearch/category.php?category=shopping