001: /*
002: * Copyright (C) Chaperon. All rights reserved.
003: * -------------------------------------------------------------------------
004: * This software is published under the terms of the Apache Software License
005: * version 1.1, a copy of which has been included with this distribution in
006: * the LICENSE file.
007: */
008:
009: package net.sourceforge.chaperon.build;
010:
011: import net.sourceforge.chaperon.model.grammar.Grammar;
012: import net.sourceforge.chaperon.model.grammar.Production;
013: import net.sourceforge.chaperon.model.symbol.Nonterminal;
014: import net.sourceforge.chaperon.model.symbol.Symbol;
015: import net.sourceforge.chaperon.model.symbol.SymbolList;
016: import net.sourceforge.chaperon.model.symbol.SymbolSet;
017: import net.sourceforge.chaperon.model.symbol.Terminal;
018:
019: /**
020: * This class represents a set of items, which means positions of production, in production. These
021: * states were used to decribes states.
022: *
023: * @author <a href="mailto:stephan@apache.org">Stephan Michels</a>
024: * @version CVS $Id: State.java,v 1.8 2003/12/09 19:55:53 benedikta Exp $
025: */
026: public class State {
027: private Production[] productions = new Production[0];
028: private int[] positions = new int[0];
029:
030: // The symbols, which translate the states into other states
031: private ShiftAction[] shiftactions = new ShiftAction[0];
032: private ReduceAction[] reduceactions = new ReduceAction[0];
033: private Grammar grammar;
034: private static final EmptyList EMPTYLIST = new EmptyList();
035:
036: /**
037: * Create an empty set of items.
038: *
039: * @param grammar Grammar.
040: */
041: public State(Grammar grammar) {
042: this .grammar = grammar;
043: }
044:
045: /**
046: * Add a item to this set.
047: *
048: * @param production Production.
049: * @param position Position in this production.
050: *
051: * @return True, if this item was added
052: */
053: public boolean addItem(Production production, int position) {
054: for (int i = 0; i < productions.length; i++)
055: if ((productions[i] == production)
056: && (positions[i] == position))
057: return false;
058:
059: Production[] newProductions = new Production[productions.length + 1];
060: int[] newPositions = new int[positions.length + 1];
061:
062: System.arraycopy(productions, 0, newProductions, 0,
063: productions.length);
064: System.arraycopy(positions, 0, newPositions, 0,
065: positions.length);
066:
067: newProductions[productions.length] = production;
068: newPositions[positions.length] = position;
069:
070: productions = newProductions;
071: positions = newPositions;
072:
073: // buildind closure for every item in state I
074: SymbolList productiondefinition = production.getDefinition();
075:
076: // and not A=uv^w and w ist not empty
077: if (position < productiondefinition.getSymbolCount()) {
078: Symbol symbol = productiondefinition.getSymbol(position); // A=u ^symbol w
079:
080: // for every item [A=u^Bv,a] in J and production B=w in G
081: if (symbol instanceof Nonterminal) {
082: // list of all productions B
083: Production[] nestedproductions = grammar
084: .getProductions(symbol);
085:
086: // for alle productions B
087: for (int i = 0; i < nestedproductions.length; i++)
088:
089: // if J doesn't contain [B=^w] , should it added
090: addItem(nestedproductions[i], 0);
091: }
092: } else
093: addReduceAction(production);
094:
095: return true;
096: }
097:
098: /**
099: * Test, if all items from a other state exists in this state
100: *
101: * @param state Other state.
102: *
103: * @return True, if the state contains all items.
104: */
105: public boolean contains(State state) {
106: int i;
107: int j;
108: int position;
109: Production production;
110: boolean found;
111:
112: for (i = 0; i < state.productions.length; i++) {
113: production = state.productions[i];
114: position = state.positions[i];
115:
116: found = false;
117: for (j = 0; (j < productions.length) && !found; j++)
118: found = ((productions[j] == production) && (positions[j] == position));
119:
120: if (!found)
121: return false;
122: }
123:
124: return true;
125: }
126:
127: /**
128: * Returns the count of items in this set.
129: *
130: * @return Count of items of the core.
131: */
132: public int getItemCount() {
133: return productions.length;
134: }
135:
136: /**
137: * Returns true, if this set is empty.
138: *
139: * @return True, if this set is empty.
140: */
141: public boolean isEmpty() {
142: return (productions.length == 0);
143: }
144:
145: /**
146: * Compares two states.
147: *
148: * @param o Other state.
149: *
150: * @return True, if the states are equal.
151: */
152: public boolean equals(Object o) {
153: if (o instanceof State) {
154: State state = (State) o;
155:
156: if (state.getItemCount() != getItemCount())
157: return false;
158:
159: // The state must contain all item from this set.
160: if (!contains(state))
161: return false;
162:
163: // And this set must contain all item from the state
164: if (!state.contains(this ))
165: return false;
166:
167: return true;
168: }
169:
170: return false;
171: }
172:
173: /**
174: * Return the next Symbol, which follow the item.
175: *
176: * @param index Index the item.
177: *
178: * @return Symbol of the next position, otherwise the symbol for an empty list.
179: */
180: private Symbol getNextSymbol(int index) {
181: SymbolList productiondefinition;
182:
183: if (positions[index] < ((productiondefinition = productions[index]
184: .getDefinition()).getSymbolCount()))
185: return productiondefinition.getSymbol(positions[index]);
186:
187: return EMPTYLIST;
188: }
189:
190: public SymbolSet getNextTerminals() {
191: SymbolSet set = new SymbolSet();
192:
193: SymbolList productiondefinition;
194: for (int item = 0; item < productions.length; item++)
195: if ((positions[item] < ((productiondefinition = productions[item]
196: .getDefinition()).getSymbolCount()))
197: && (productiondefinition.getSymbol(positions[item]) instanceof Terminal))
198: set.addSymbol(productiondefinition
199: .getSymbol(positions[item]));
200:
201: return set;
202: }
203:
204: public SymbolSet getNextNonterminals() {
205: SymbolSet set = new SymbolSet();
206:
207: SymbolList productiondefinition;
208: for (int item = 0; item < productions.length; item++)
209: if ((positions[item] < ((productiondefinition = productions[item]
210: .getDefinition()).getSymbolCount()))
211: && (productiondefinition.getSymbol(positions[item]) instanceof Nonterminal))
212: set.addSymbol(productiondefinition
213: .getSymbol(positions[item]));
214:
215: return set;
216: }
217:
218: /**
219: * Calculates the next state by a transition through the symbol X.
220: *
221: * @param symbol A Symbol, which can be a terminal or a nonterminal symbol.
222: *
223: * @return The next state, represented by an state.
224: */
225: public State jump(Symbol symbol) {
226: State J = new State(grammar);
227:
228: // For every item [A=u^Xv,a] in I
229: for (int i = 0; i < productions.length; i++) {
230: if (getNextSymbol(i).equals(symbol))
231:
232: // add [A=uX^v,a] to J
233: J.addItem(productions[i], positions[i] + 1);
234: }
235:
236: // jump(I,X) = closure(J)
237: return J;
238: }
239:
240: /**
241: * Add a transition to this state.
242: *
243: * @param symbol Symbol, which forces a transition into another state.
244: * @param state Destination state.
245: */
246: public boolean addShiftAction(Symbol symbol, State state) {
247: for (int i = 0; i < shiftactions.length; i++)
248: if (shiftactions[i].symbol.equals(symbol))
249: return false;
250:
251: ShiftAction[] newshiftactions = new ShiftAction[shiftactions.length + 1];
252: System.arraycopy(shiftactions, 0, newshiftactions, 0,
253: shiftactions.length);
254: newshiftactions[shiftactions.length] = new ShiftAction(symbol,
255: state);
256: shiftactions = newshiftactions;
257: return true;
258: }
259:
260: /**
261: * Returns the destination state of a transition.
262: *
263: * @param symbol Symbol, which force the transition.
264: *
265: * @return Destination state.
266: */
267: public ShiftAction getShiftAction(Symbol symbol) {
268: for (int i = 0; i < shiftactions.length; i++)
269: if (shiftactions[i].symbol.equals(symbol))
270: return shiftactions[i];
271:
272: return null;
273: }
274:
275: public ShiftAction[] getShiftActions() {
276: return shiftactions;
277: }
278:
279: public void addReduceAction(Production production) {
280: for (int i = 0; i < reduceactions.length; i++)
281: if (reduceactions[i].production == production)
282: return;
283:
284: ReduceAction[] newreduceactions = new ReduceAction[reduceactions.length + 1];
285: for (int i = 0; i < reduceactions.length; i++)
286: newreduceactions[i] = reduceactions[i];
287:
288: newreduceactions[reduceactions.length] = new ReduceAction(
289: production);
290: reduceactions = newreduceactions;
291: }
292:
293: public ReduceAction[] getReduceActions() {
294: int count = 0;
295: for (int i = 0; i < productions.length; i++)
296: if (getNextSymbol(i).equals(EMPTYLIST)) // for all A=u^ and all symbols in FOLLOW(A)
297:
298: count++;
299:
300: ReduceAction[] reduceactions = new ReduceAction[count];
301:
302: for (int i = 0; i < productions.length; i++)
303: if (getNextSymbol(i).equals(EMPTYLIST)) // for all A=u^ and all symbols in FOLLOW(A)
304:
305: reduceactions[--count] = new ReduceAction(
306: productions[i]);
307:
308: return reduceactions;
309: }
310:
311: /**
312: * Return a string representation of this state.
313: *
314: * @return String representation of this state.
315: */
316: public String toString() {
317: StringBuffer buffer = new StringBuffer();
318:
319: SymbolList list;
320:
321: for (int productionindex = 0; productionindex < grammar
322: .getProductionCount(); productionindex++) {
323: list = grammar.getProduction(productionindex)
324: .getDefinition();
325:
326: for (int position = 0; position <= list.getSymbolCount(); position++) {
327: for (int item = 0; item < productions.length; item++)
328: if ((productions[item] == grammar
329: .getProduction(productionindex))
330: && (positions[item] == position)) {
331: buffer.append(productions[item].getSymbol());
332: buffer.append(" := ");
333:
334: for (int i = 0; i < list.getSymbolCount(); i++) {
335: if (i == position)
336: buffer.append(".");
337:
338: buffer.append(list.getSymbol(i) + " ");
339: }
340:
341: if (position == list.getSymbolCount())
342: buffer.append(".");
343:
344: buffer.append("\n");
345: break;
346: }
347: }
348: }
349:
350: return buffer.toString();
351: }
352: }
|