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.SymbolSet;
014:
015: import org.apache.commons.logging.Log;
016:
017: import java.util.ArrayList;
018:
019: /**
020: * This class contains a automaton of states.
021: *
022: * @author <a href="mailto:stephan@apache.org">Stephan Michels</a>
023: * @version CVS $Id: Automaton.java,v 1.8 2003/12/09 19:55:53 benedikta Exp $
024: */
025: public class Automaton {
026: private ArrayList states = new ArrayList();
027: private Grammar grammar;
028: private SymbolSet tsymbols;
029: private SymbolSet ntsymbols;
030: private Log log;
031:
032: /**
033: * Create a new automaton of states, calculated with the aid of the grammar. The constructor
034: * calculates all state and transitions and combine all states with the same core.
035: *
036: * @param grammar Grammar.
037: */
038: public Automaton(Grammar grammar) {
039: this (grammar, null);
040: }
041:
042: /**
043: * Create a new automaton of states, calculated with the aid of the grammar. The constructor
044: * calculates all state and transitions and combine all states with the same core.
045: *
046: * @param grammar Grammar
047: * @param firstsets First sets.
048: * @param log Log, which should be used.
049: */
050: public Automaton(Grammar grammar, Log log) {
051: this .grammar = grammar;
052: this .log = log;
053:
054: SymbolSet symbols = grammar.getSymbols();
055:
056: tsymbols = symbols.getTerminals();
057: ntsymbols = symbols.getNonterminals();
058:
059: // C = closure( [S'=^S] )
060: addState(getStartState());
061:
062: State I;
063: State J;
064: int index;
065: SymbolSet nextterminals;
066: SymbolSet nextnonterminals;
067:
068: for (int i = 0; i < getStateCount(); i++) {
069: I = getState(i);
070:
071: // J = goto(I,X) add to C, for all nonterminal and terminal symbols X
072: // for the non terminal symbols
073: nextnonterminals = I.getNextNonterminals();
074: for (int j = 0; j < nextnonterminals.getSymbolCount(); j++) {
075: J = I.jump(nextnonterminals.getSymbol(j));
076:
077: if (!J.isEmpty()) {
078: index = indexOf(J);
079: if (index < 0) // if C doesn't contain J
080: {
081: index = addState(J);
082:
083: // stores the transition for this symbol
084: I.addShiftAction(nextnonterminals.getSymbol(j),
085: J);
086: } else
087: I.addShiftAction(nextnonterminals.getSymbol(j),
088: getState(index));
089: }
090: }
091:
092: // and for the terminal symbls
093: nextterminals = I.getNextTerminals();
094: for (int j = 0; j < nextterminals.getSymbolCount(); j++) {
095: J = I.jump(nextterminals.getSymbol(j));
096:
097: if (!J.isEmpty()) {
098: index = indexOf(J);
099: if (index < 0) // if C doesn't contain J
100: {
101: index = addState(J);
102:
103: // stores the transition for this symbol
104: I.addShiftAction(nextterminals.getSymbol(j), J);
105: } else
106: I.addShiftAction(nextterminals.getSymbol(j),
107: getState(index));
108: }
109: }
110: }
111: }
112:
113: /**
114: * Return the state as start point for the calculation.
115: *
116: * @return Start point for the calculation.
117: */
118: private State getStartState() {
119: if (grammar.getStartSymbol() == null)
120: throw new IllegalArgumentException(
121: "Start symbol is not defined");
122:
123: State I = new State(grammar);
124: Production[] productions = grammar.getProductions(grammar
125: .getStartSymbol());
126:
127: for (int i = 0; i < productions.length; i++)
128: I.addItem(productions[i], 0);
129:
130: return I;
131: }
132:
133: public Grammar getGrammar() {
134: return grammar;
135: }
136:
137: /**
138: * Add a state to this automaton.
139: *
140: * @param state State.
141: *
142: * @return Index of the state in the automaton.
143: */
144: public int addState(State state) {
145: int index = indexOf(state);
146:
147: if (index == -1) {
148: states.add(state);
149: index = states.size() - 1;
150: }
151:
152: return index;
153: }
154:
155: /**
156: * Return an state given by an index.
157: *
158: * @param index Index of the state.
159: *
160: * @return State.
161: */
162: public State getState(int index) {
163: return (State) states.get(index);
164: }
165:
166: /**
167: * Return the count of states in this automaton
168: *
169: * @return Count of states.
170: */
171: public int getStateCount() {
172: return states.size();
173: }
174:
175: /**
176: * Return the index of an state. If the automaton does not contain the state, then return this
177: * method will return -1.
178: *
179: * @param state State, which should be found.
180: *
181: * @return Index of the state.
182: */
183: public int indexOf(State state) {
184: for (int i = 0; i < states.size(); i++)
185: if (((State) states.get(i)).equals(state))
186: return i;
187:
188: return -1;
189: }
190:
191: /**
192: * If this automaton contains the state.
193: *
194: * @param state State, which should be found.
195: *
196: * @return True, if the automaton contains the state.
197: */
198: public boolean contains(State state) {
199: for (int i = 0; i < states.size(); i++)
200: if (((State) states.get(i)).equals(state))
201: return true;
202:
203: return false;
204: }
205:
206: /**
207: * Return a string representation of the automaton.
208: *
209: * @return String representation of the automaton.
210: */
211: public String toString() {
212: StringBuffer buffer = new StringBuffer();
213:
214: for (int i = 0; i < getStateCount(); i++) {
215: buffer.append("State ");
216: buffer.append(String.valueOf(i));
217: buffer.append(":\n");
218: buffer.append(getState(i).toString());
219:
220: ShiftAction[] shiftactions = getState(i).getShiftActions();
221: for (int index = 0; index < shiftactions.length; index++) {
222: buffer.append("Shift ");
223: buffer.append(shiftactions[index].symbol);
224: buffer.append(" -> State ");
225: buffer.append(indexOf(shiftactions[index].state));
226: buffer.append("\n");
227: }
228:
229: ReduceAction[] reduceactions = getState(i)
230: .getReduceActions();
231: for (int index = 0; index < reduceactions.length; index++) {
232: buffer.append("Reduce ");
233: buffer.append(reduceactions[index].production
234: .getSymbol());
235: buffer.append(" <- ");
236: buffer.append(reduceactions[index].production
237: .getDefinition());
238: buffer.append("\n");
239: }
240:
241: buffer.append("\n");
242: }
243:
244: return buffer.toString();
245: }
246: }
|