Java Doc for DFAOptimizer.java in  » Parser » antlr-3.0.1 » org » antlr » analysis » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Parser » antlr 3.0.1 » org.antlr.analysis 
Source Cross Reference  Class Diagram Java Document (Java Doc) 


java.lang.Object
   org.antlr.analysis.DFAOptimizer

DFAOptimizer
public class DFAOptimizer (Code)
A module to perform optimizations on DFAs. I could more easily (and more quickly) do some optimizations (such as PRUNE_EBNF_EXIT_BRANCHES) during DFA construction, but then it messes up the determinism checking. For example, it looks like loop exit branches are unreachable if you prune exit branches during DFA construction and before determinism checks. In general, ANTLR's NFA->DFA->codegen pipeline seems very robust to me which I attribute to a uniform and consistent set of data structures. Regardless of what I want to "say"/implement, I do so within the confines of, for example, a DFA. The code generator can then just generate code--it doesn't have to do much thinking. Putting optimizations in the code gen code really starts to make it a spagetti factory (uh oh, now I'm hungry!). The pipeline is very testable; each stage has well defined input/output pairs. ### Optimization: PRUNE_EBNF_EXIT_BRANCHES There is no need to test EBNF block exit branches. Not only is it an unneeded computation, but counter-intuitively, you actually get better errors. You can report an error at the missing or extra token rather than as soon as you've figured out you will fail. Imagine optional block "( DOT CLASS )? SEMI". ANTLR generates: int alt=0; if ( input.LA(1)==DOT ) { alt=1; } else if ( input.LA(1)==SEMI ) { alt=2; } Clearly, since Parser.match() will ultimately find the error, we do not want to report an error nor do we want to bother testing lookahead against what follows the (...)? We want to generate simply "should I enter the subrule?": int alt=2; if ( input.LA(1)==DOT ) { alt=1; } NOTE 1. Greedy loops cannot be optimized in this way. For example, "(greedy=false:'x'|.)* '\n'". You specifically need the exit branch to tell you when to terminate the loop as the same input actually predicts one of the alts (i.e., staying in the loop). NOTE 2. I do not optimize cyclic DFAs at the moment as it doesn't seem to work. ;) I'll have to investigate later to see what work I can do on cyclic DFAs to make them have fewer edges. Might have something to do with the EOT token. ### PRUNE_SUPERFLUOUS_EOT_EDGES When a token is a subset of another such as the following rules, ANTLR quietly assumes the first token to resolve the ambiguity. EQ : '=' ; ASSIGNOP : '=' | '+=' ; It can yield states that have only a single edge on EOT to an accept state. This is a waste and messes up my code generation. ;) If Tokens rule DFA goes s0 -'='-> s3 -EOT-> s5 (accept) then s5 should be pruned and s3 should be made an accept. Do NOT do this for keyword versus ID as the state with EOT edge emanating from it will also have another edge. ### Optimization: COLLAPSE_ALL_INCIDENT_EDGES Done during DFA construction. See method addTransition() in NFAToDFAConverter. ### Optimization: MERGE_STOP_STATES Done during DFA construction. See addDFAState() in NFAToDFAConverter.


Field Summary
public static  booleanCOLLAPSE_ALL_PARALLEL_EDGES
    
public static  booleanMERGE_STOP_STATES
    
public static  booleanPRUNE_EBNF_EXIT_BRANCHES
    
public static  booleanPRUNE_TOKENS_RULE_SUPERFLUOUS_EOT_EDGES
    
protected  Grammargrammar
    
protected  Setvisited
     Used by DFA state machine generator to avoid infinite recursion resulting from cycles int the DFA.

Constructor Summary
public  DFAOptimizer(Grammar grammar)
    

Method Summary
public  voidoptimize()
    
protected  voidoptimize(DFA dfa)
    
protected  voidoptimizeEOTBranches(DFAState d)
    
protected  voidoptimizeExitBranches(DFAState d)
    

Field Detail
COLLAPSE_ALL_PARALLEL_EDGES
public static boolean COLLAPSE_ALL_PARALLEL_EDGES(Code)



MERGE_STOP_STATES
public static boolean MERGE_STOP_STATES(Code)



PRUNE_EBNF_EXIT_BRANCHES
public static boolean PRUNE_EBNF_EXIT_BRANCHES(Code)



PRUNE_TOKENS_RULE_SUPERFLUOUS_EOT_EDGES
public static boolean PRUNE_TOKENS_RULE_SUPERFLUOUS_EOT_EDGES(Code)



grammar
protected Grammar grammar(Code)



visited
protected Set visited(Code)
Used by DFA state machine generator to avoid infinite recursion resulting from cycles int the DFA. This is a set of int state #s.




Constructor Detail
DFAOptimizer
public DFAOptimizer(Grammar grammar)(Code)




Method Detail
optimize
public void optimize()(Code)



optimize
protected void optimize(DFA dfa)(Code)



optimizeEOTBranches
protected void optimizeEOTBranches(DFAState d)(Code)



optimizeExitBranches
protected void optimizeExitBranches(DFAState d)(Code)



Methods inherited from java.lang.Object
native protected Object clone() throws CloneNotSupportedException(Code)(Java Doc)
public boolean equals(Object obj)(Code)(Java Doc)
protected void finalize() throws Throwable(Code)(Java Doc)
final native public Class getClass()(Code)(Java Doc)
native public int hashCode()(Code)(Java Doc)
final native public void notify()(Code)(Java Doc)
final native public void notifyAll()(Code)(Java Doc)
public String toString()(Code)(Java Doc)
final native public void wait(long timeout) throws InterruptedException(Code)(Java Doc)
final public void wait(long timeout, int nanos) throws InterruptedException(Code)(Java Doc)
final public void wait() throws InterruptedException(Code)(Java Doc)

www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.