FAFactory


1   /*
2   
3   [The "BSD licence"]
4   Copyright (c) 2005 Jean Bovet
5   All rights reserved.
6   
7   Redistribution and use in source and binary forms, with or without
8   modification, are permitted provided that the following conditions
9   are met:
10  
11  1. Redistributions of source code must retain the above copyright
12  notice, this list of conditions and the following disclaimer.
13  2. Redistributions in binary form must reproduce the above copyright
14  notice, this list of conditions and the following disclaimer in the
15  documentation and/or other materials provided with the distribution.
16  3. The name of the author may not be used to endorse or promote products
17  derived from this software without specific prior written permission.
18  
19  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  
30  */
31  
32  package org.antlr.works.visualization.fa;
33  
34  import org.antlr.analysis.NFAState;
35  import org.antlr.analysis.RuleClosureTransition;
36  import org.antlr.analysis.State;
37  import org.antlr.analysis.Transition;
38  import org.antlr.tool.Grammar;
39  
40  import java.util.*;
41  
42  /** This class builds an "GUI" NFA from an "ANTLR" NFA by removing redundant epsilon transition(s).
43   *
44   */
45  
46  public class FAFactory {
47  
48      protected Grammar g;
49      protected boolean optimize;
50      protected FAAnalysis analysis = new FAAnalysis();
51      protected Map<NFAState,FAState> processedStates = new HashMap<NFAState, FAState>();
52      protected Map<Integer  ,FAState> skippedStatesMap = new HashMap<Integer  , FAState>();
53  
54      protected int newStateNumber = State.INVALID_STATE_NUMBER-1;
55  
56      public FAFactory(Grammar g) {
57          this.g = g;
58      }
59  
60      public FAState buildNFA(NFAState state, boolean optimize) {
61          this.optimize = optimize;
62          return build(state);
63      }
64  
65      public Map<Integer  ,FAState> getSkippedStatesMap() {
66          return skippedStatesMap;
67      }
68  
69      public FAState build(NFAState state) {
70          processedStates.clear();
71  
72          // First compute the incoming transition for each state. This will be used later to
73          // know if a state can be simplified or not.
74          analysis.analyze(state);
75          return buildRecursiveState(state, new HashSet<NFAState>());
76      }
77  
78      public FAState buildRecursiveState(NFAState state, Set<NFAState> currentPath) {
79          if(processedStates.get(state) != null) {
80              FAState js = processedStates.get(state);
81              if(currentPath.contains(state)) {
82                  // Set this temporary flag to indicate to the parent method that
83                  // the transition to be created has to be flagged as "loop".
84                  js.loop = true;
85              }
86              return js;
87          }
88  
89          FAState js = new FAState(state);
90          processedStates.put(state, js);
91          currentPath.add(state);
92  
93          if(state.isAcceptState()) {
94              // Stop as soon as we reach an accepted state
95              return js;
96          }
97  
98          for(int t=0; t<state.getNumberOfTransitions(); t++) {
99              FAState parentState = js;
100 
101             Transition transition = state.transition(t);
102             NFAState target = (NFAState)transition.target;
103             if(targetStateIsInAnotherRule(transition)) {
104                 target = targetStateOfTransition(transition);
105                 parentState = createRuleReferenceState(parentState, transition, null);
106             }
107 
108             if(transition.isEpsilon()) {
109                 buildRecursiveSkipState(parentState, target, new HashSet<NFAState>(currentPath), new ArrayList<Integer  >());
110             } else {
111                 FAState targetState = buildRecursiveState(target, new HashSet<NFAState>(currentPath));
112                 if(targetState.loop) {
113                     // Handle "loop" transition by creating a "normal" transition and assigning a flag
114                     // to this transition so when drawing it, we can draw the arrow at the right place
115                     // (in the reverse direction)
116                     targetState.addTransition(new FATransition(transition.label.toString(g), parentState), true);
117                     targetState.loop = false;
118                 } else
119                     parentState.addTransition(new FATransition(transition.label.toString(g), targetState));
120             }
121         }
122         return js;
123     }
124 
125     /** This method is used to skip redundant state following epsilon transition.
126      *
127      */
128 
129     public void buildRecursiveSkipState(FAState parentState, NFAState state, Set<NFAState> currentPath, List<Integer  > skippedStates) {
130         if(canBeSkipped(state)) {
131             // If the state can be skipped, apply recursively the same method for each transition(s)
132             // providing the parent state.
133 
134             // Record each skipped state. They will be added later to the transition that replace them
135             Integer   skippedState = state.stateNumber;
136             skippedStates.add(skippedState);
137             skippedStatesMap.put(skippedState, parentState);
138 
139             for(int t=0; t<state.getNumberOfTransitions(); t++) {
140                 Transition transition = state.transition(t);
141                 if(targetStateIsInAnotherRule(transition)) {
142                     NFAState target = targetStateOfTransition(transition);
143                     FAState ruleRefState = createRuleReferenceState(parentState, transition, skippedStates);
144                     buildRecursiveSkipState(ruleRefState, target, currentPath, new ArrayList<Integer  >(skippedStates));
145                 } else
146                     buildRecursiveSkipState(parentState, (NFAState)transition.target, currentPath, new ArrayList<Integer  >(skippedStates));
147             }
148         } else {
149             // The state cannot be skipped. Build the remaining of the NFA...
150             FAState targetState = buildRecursiveState(state, currentPath);
151             // and then create the transition from the parentState to this current state
152             // (this is the simplification ;-))
153             if(targetState.loop) {
154                 // See comment above (in the previous method)
155                 targetState.addTransition(new FATransition(parentState, skippedStates), true);
156                 targetState.loop = false;
157             } else
158                 parentState.addTransition(new FATransition(targetState, skippedStates));
159         }
160     }
161 
162     public boolean targetStateIsInAnotherRule(Transition transition) {
163         return transition instanceof RuleClosureTransition;
164     }
165 
166     public String   nameOfExternalReferencedRule(Transition transition) {
167         if(transition instanceof RuleClosureTransition) {
168             RuleClosureTransition rct = (RuleClosureTransition)transition;
169             // @todo to finish
170             String   tokenName = g.getRuleName(rct.getRuleIndex());
171             //System.out.println(tokenName);
172             //System.err.println(g.getTokenDisplayName(g.getTokenType(tokenName)));
173             return tokenName;
174         } else
175             return null;
176     }
177 
178     public FAState createRuleReferenceState(FAState parentState, Transition transition, List<Integer  > skippedStates) {
179         // Create epsilon transition before the external reference transition
180         FAState dummyState = new FAState(newStateNumber--);
181         dummyState.enclosingRuleName = parentState.enclosingRuleName;
182         FATransition epsilon = new FATransition(dummyState, skippedStates);
183         parentState.addTransition(epsilon);
184 
185         FAState ruleRefState = new FAState(newStateNumber--);
186         ruleRefState.enclosingRuleName = parentState.enclosingRuleName;
187         FATransition tr = new FATransition(nameOfExternalReferencedRule(transition), ruleRefState);
188         tr.setExternalRuleRef(true);
189         dummyState.addTransition(tr);
190 
191         return ruleRefState;
192     }
193 
194     public NFAState targetStateOfTransition(Transition transition) {
195         NFAState target;
196         if(transition instanceof RuleClosureTransition) {
197             RuleClosureTransition rct = (RuleClosureTransition)transition;
198             target = rct.getFollowState();
199         } else {
200             target = (NFAState)transition.target;
201         }
202         return target;
203     }
204 
205     /** This method returns true if the state can be skipped, using several criteria.
206      *
207      */
208 
209     public boolean canBeSkipped(NFAState state) {
210         if(!optimize)
211             return false;
212 
213         // Cannot skip first state
214         if(state.stateNumber == 0)
215             return false;
216 
217         // Cannot skip accepted state
218         if(state.isAcceptState())
219             return false;
220 
221         // Cannot skip alternative state
222         if(state.getDecisionNumber() > 0)
223             return false;
224 
225         // Cannot skip start of block state
226         if(state.endOfBlockStateNumber != State.INVALID_STATE_NUMBER)
227             return false;
228 
229         // Cannot skip state with more than one incoming transition (often an end-of-alternative state)
230         if(analysis.numberOfIncomingTransition(state)>1)
231             return false;
232 
233         return hasOneOrMoreEpsilonTransitionOnly(state);
234     }
235 
236     public boolean hasOneEpsilonTransitionOnly(NFAState state) {
237         return state.getNumberOfTransitions() == 1 && state.transition(0).isEpsilon();
238     }
239 
240     public boolean hasOneOrMoreEpsilonTransitionOnly(NFAState state) {
241         for(int t=0; t<state.getNumberOfTransitions(); t++) {
242             Transition transition = state.transition(t);
243             if(!transition.isEpsilon())
244                 return false;
245         }
246         return state.getNumberOfTransitions()>0;
247     }
248 
249     public boolean hasMoreThanOneEpsilonTransitionOnly(NFAState state) {
250         for(int t=0; t<state.getNumberOfTransitions(); t++) {
251             Transition transition = state.transition(t);
252             if(!transition.isEpsilon())
253                 return false;
254         }
255         return state.getNumberOfTransitions()>1;
256     }
257 
258     public boolean isAlternativeTransitionEndingAtSameState(NFAState state) {
259         NFAState endState = endStateOfAlternative((NFAState)state.transition(0).target);
260 
261         for(int t=1; t<state.getNumberOfTransitions(); t++) {
262             Transition transition = state.transition(t);
263             NFAState newEndState = endStateOfAlternative((NFAState)transition.target);
264             if(!endState.equals(newEndState))
265                 return false;
266         }
267         return true;
268     }
269 
270     public NFAState endStateOfAlternative(NFAState alt) {
271         int endOfBlockStateNumber = alt.endOfBlockStateNumber;
272 
273         NFAState state = alt;
274         while(state.stateNumber != endOfBlockStateNumber) {
275             state = (NFAState)state.transition(0).target;
276         }
277         return state;
278     }
279 }
280
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags