KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > net > sourceforge > chaperon > build > Automaton


1 /*
2  * Copyright (C) Chaperon. All rights reserved.
3  * -------------------------------------------------------------------------
4  * This software is published under the terms of the Apache Software License
5  * version 1.1, a copy of which has been included with this distribution in
6  * the LICENSE file.
7  */
8
9 package net.sourceforge.chaperon.build;
10
11 import net.sourceforge.chaperon.model.grammar.Grammar;
12 import net.sourceforge.chaperon.model.grammar.Production;
13 import net.sourceforge.chaperon.model.symbol.SymbolSet;
14
15 import org.apache.commons.logging.Log;
16
17 import java.util.ArrayList JavaDoc;
18
19 /**
20  * This class contains a automaton of states.
21  *
22  * @author <a HREF="mailto:stephan@apache.org">Stephan Michels</a>
23  * @version CVS $Id: Automaton.java,v 1.8 2003/12/09 19:55:53 benedikta Exp $
24  */
25 public class Automaton
26 {
27   private ArrayList JavaDoc states = new ArrayList JavaDoc();
28   private Grammar grammar;
29   private SymbolSet tsymbols;
30   private SymbolSet ntsymbols;
31   private Log log;
32
33   /**
34    * Create a new automaton of states, calculated with the aid of the grammar. The constructor
35    * calculates all state and transitions and combine all states with the same core.
36    *
37    * @param grammar Grammar.
38    */
39   public Automaton(Grammar grammar)
40   {
41     this(grammar, null);
42   }
43
44   /**
45    * Create a new automaton of states, calculated with the aid of the grammar. The constructor
46    * calculates all state and transitions and combine all states with the same core.
47    *
48    * @param grammar Grammar
49    * @param firstsets First sets.
50    * @param log Log, which should be used.
51    */
52   public Automaton(Grammar grammar, Log log)
53   {
54     this.grammar = grammar;
55     this.log = log;
56
57     SymbolSet symbols = grammar.getSymbols();
58
59     tsymbols = symbols.getTerminals();
60     ntsymbols = symbols.getNonterminals();
61
62     // C = closure( [S'=^S] )
63 addState(getStartState());
64
65     State I;
66     State J;
67     int index;
68     SymbolSet nextterminals;
69     SymbolSet nextnonterminals;
70
71     for (int i = 0; i<getStateCount(); i++)
72     {
73       I = getState(i);
74
75       // J = goto(I,X) add to C, for all nonterminal and terminal symbols X
76 // for the non terminal symbols
77 nextnonterminals = I.getNextNonterminals();
78       for (int j = 0; j<nextnonterminals.getSymbolCount(); j++)
79       {
80         J = I.jump(nextnonterminals.getSymbol(j));
81
82         if (!J.isEmpty())
83         {
84           index = indexOf(J);
85           if (index<0) // if C doesn't contain J
86 {
87             index = addState(J);
88
89             // stores the transition for this symbol
90 I.addShiftAction(nextnonterminals.getSymbol(j), J);
91           }
92           else
93             I.addShiftAction(nextnonterminals.getSymbol(j), getState(index));
94         }
95       }
96
97       // and for the terminal symbls
98 nextterminals = I.getNextTerminals();
99       for (int j = 0; j<nextterminals.getSymbolCount(); j++)
100       {
101         J = I.jump(nextterminals.getSymbol(j));
102
103         if (!J.isEmpty())
104         {
105           index = indexOf(J);
106           if (index<0) // if C doesn't contain J
107 {
108             index = addState(J);
109
110             // stores the transition for this symbol
111 I.addShiftAction(nextterminals.getSymbol(j), J);
112           }
113           else
114             I.addShiftAction(nextterminals.getSymbol(j), getState(index));
115         }
116       }
117     }
118   }
119
120   /**
121    * Return the state as start point for the calculation.
122    *
123    * @return Start point for the calculation.
124    */
125   private State getStartState()
126   {
127     if (grammar.getStartSymbol()==null)
128       throw new IllegalArgumentException JavaDoc("Start symbol is not defined");
129
130     State I = new State(grammar);
131     Production[] productions = grammar.getProductions(grammar.getStartSymbol());
132
133     for (int i = 0; i<productions.length; i++)
134       I.addItem(productions[i], 0);
135
136     return I;
137   }
138
139   public Grammar getGrammar()
140   {
141     return grammar;
142   }
143
144   /**
145    * Add a state to this automaton.
146    *
147    * @param state State.
148    *
149    * @return Index of the state in the automaton.
150    */
151   public int addState(State state)
152   {
153     int index = indexOf(state);
154
155     if (index==-1)
156     {
157       states.add(state);
158       index = states.size()-1;
159     }
160
161     return index;
162   }
163
164   /**
165    * Return an state given by an index.
166    *
167    * @param index Index of the state.
168    *
169    * @return State.
170    */
171   public State getState(int index)
172   {
173     return (State)states.get(index);
174   }
175
176   /**
177    * Return the count of states in this automaton
178    *
179    * @return Count of states.
180    */
181   public int getStateCount()
182   {
183     return states.size();
184   }
185
186   /**
187    * Return the index of an state. If the automaton does not contain the state, then return this
188    * method will return -1.
189    *
190    * @param state State, which should be found.
191    *
192    * @return Index of the state.
193    */
194   public int indexOf(State state)
195   {
196     for (int i = 0; i<states.size(); i++)
197       if (((State)states.get(i)).equals(state))
198         return i;
199
200     return -1;
201   }
202
203   /**
204    * If this automaton contains the state.
205    *
206    * @param state State, which should be found.
207    *
208    * @return True, if the automaton contains the state.
209    */
210   public boolean contains(State state)
211   {
212     for (int i = 0; i<states.size(); i++)
213       if (((State)states.get(i)).equals(state))
214         return true;
215
216     return false;
217   }
218
219   /**
220    * Return a string representation of the automaton.
221    *
222    * @return String representation of the automaton.
223    */
224   public String JavaDoc toString()
225   {
226     StringBuffer JavaDoc buffer = new StringBuffer JavaDoc();
227
228     for (int i = 0; i<getStateCount(); i++)
229     {
230       buffer.append("State ");
231       buffer.append(String.valueOf(i));
232       buffer.append(":\n");
233       buffer.append(getState(i).toString());
234
235       ShiftAction[] shiftactions = getState(i).getShiftActions();
236       for (int index = 0; index<shiftactions.length; index++)
237       {
238         buffer.append("Shift ");
239         buffer.append(shiftactions[index].symbol);
240         buffer.append(" -> State ");
241         buffer.append(indexOf(shiftactions[index].state));
242         buffer.append("\n");
243       }
244
245       ReduceAction[] reduceactions = getState(i).getReduceActions();
246       for (int index = 0; index<reduceactions.length; index++)
247       {
248         buffer.append("Reduce ");
249         buffer.append(reduceactions[index].production.getSymbol());
250         buffer.append(" <- ");
251         buffer.append(reduceactions[index].production.getDefinition());
252         buffer.append("\n");
253       }
254
255       buffer.append("\n");
256     }
257
258     return buffer.toString();
259   }
260 }
261
Popular Tags