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.model.extended;
010:
011: import net.sourceforge.chaperon.model.Violations;
012:
013: import java.io.Serializable;
014:
015: /**
016: * This class represents a model for a grammar. The content of the grammar includes the
017: * definitions, start symbol, associativities and priorities.
018: *
019: * @author <a href="mailto:stephan@apache.org">Stephan Michels </a>
020: * @version CVS $Id: ExtendedGrammar.java,v 1.19 2004/01/08 11:30:52 benedikta Exp $
021: */
022: public class ExtendedGrammar implements Serializable, Cloneable {
023: // Start symbol
024: private String startSymbol = null;
025:
026: // Definitions
027: private Definition[] definitions = new Definition[0];
028: private String location = null;
029: private BeginOfText BOT = new BeginOfText();
030: private EndOfText EOT = new EndOfText();
031:
032: /**
033: * Creates an empty grammar.
034: */
035: public ExtendedGrammar() {
036: }
037:
038: /**
039: * Add a definition to this grammar.
040: *
041: * @param definition Definition, which should be added.
042: *
043: * @return Index of the definition in this grammar.
044: */
045: public void addDefinition(Definition definition) {
046: if (definition == null)
047: throw new NullPointerException();
048:
049: for (PatternIterator i = definition.getAllPattern()
050: .getPattern(); i.hasNext();) {
051: Pattern pattern = i.next();
052: pattern.setDefinition(definition);
053: }
054:
055: Definition[] newDefinitions = new Definition[definitions.length + 1];
056: System.arraycopy(definitions, 0, newDefinitions, 0,
057: definitions.length);
058: newDefinitions[definitions.length] = definition;
059: definitions = newDefinitions;
060: }
061:
062: /**
063: * Return a definition giving by an index.
064: *
065: * @param index Index of the Definition.
066: *
067: * @return The definition.
068: */
069: public Definition getDefinition(int index) {
070: return definitions[index];
071: }
072:
073: /**
074: * Returns all definition for given nonterminal symbol as a list of indices.
075: *
076: * @param ntsymbol Nonterminal symbol
077: *
078: * @return List of indices from the definitions
079: */
080: public Definition getDefinition(String symbol) {
081: for (int i = 0; i < definitions.length; i++)
082: if (definitions[i].getSymbol().equals(symbol))
083: return definitions[i];
084:
085: return null;
086: }
087:
088: public Definition[] getDefinitions() {
089: return definitions;
090: }
091:
092: /**
093: * Returns the count of definitions in this grammar.
094: *
095: * @return Count of definitions.
096: */
097: public int getDefinitionCount() {
098: return definitions.length;
099: }
100:
101: public PatternSet getAllPattern() {
102: PatternSet set = new PatternSet();
103:
104: for (int i = 0; i < definitions.length; i++)
105: set.addPattern(definitions[i].getAllPattern());
106:
107: set.addPattern(BOT);
108: set.addPattern(EOT);
109:
110: return set;
111: }
112:
113: public void update() {
114: for (int i = 0; i < definitions.length; i++)
115: definitions[i].update();
116:
117: updateAscendingSuccessors();
118: updateDescendingSuccessors();
119: }
120:
121: public void updateAscendingSuccessors() {
122: for (PatternIterator successors = getFirstSet(getStartSymbol())
123: .getPattern(); successors.hasNext();) {
124: Pattern succesor = successors.next();
125: BOT.addAscendingSuccessor(succesor);
126: }
127:
128: boolean modified;
129: do {
130: modified = false;
131: for (PatternIterator successors = getAllPattern()
132: .getPattern(); successors.hasNext();) {
133: Pattern successor = successors.next();
134:
135: if (successor.getSymbol() != null) {
136: PatternSet firstSet = getFirstSet(successor
137: .getSymbol());
138:
139: for (PatternIterator ancestors = successor
140: .getAncestors(); ancestors.hasNext();) {
141: Pattern ancestor = ancestors.next();
142:
143: for (PatternIterator i = firstSet.getPattern(); i
144: .hasNext();) {
145: Pattern firstPattern = i.next();
146: modified |= ancestor
147: .addAscendingSuccessor(firstPattern);
148: }
149: }
150:
151: for (PatternIterator ancestors = successor
152: .getAscendingAncestors(); ancestors
153: .hasNext();) {
154: Pattern ancestor = ancestors.next();
155:
156: for (PatternIterator i = firstSet.getPattern(); i
157: .hasNext();) {
158: Pattern firstPattern = i.next();
159: modified |= ancestor
160: .addAscendingSuccessor(firstPattern);
161: }
162: }
163: }
164: }
165: } while (modified);
166: }
167:
168: public boolean isNullable(String symbol) {
169: for (int i = 0; i < definitions.length; i++)
170: if (definitions[i].getSymbol().equals(symbol))
171: return definitions[i].isNullable();
172:
173: return true;
174: }
175:
176: public PatternSet getFirstSet(String symbol) {
177: PatternSet firstSet = new PatternSet();
178:
179: for (int i = 0; i < definitions.length; i++)
180: if (definitions[i].getSymbol().equals(symbol))
181: firstSet.addPattern(definitions[i].getFirstSet());
182:
183: return firstSet;
184: }
185:
186: public PatternSet getFirstSet() {
187: return getFirstSet(getStartSymbol());
188: }
189:
190: public PatternSet getLastSet(String symbol) {
191: PatternSet lastSet = new PatternSet();
192:
193: for (int i = 0; i < definitions.length; i++)
194: if (definitions[i].getSymbol().equals(symbol))
195: lastSet.addPattern(definitions[i].getLastSet());
196:
197: return lastSet;
198: }
199:
200: public PatternSet getLastSet() {
201: return getLastSet(getStartSymbol());
202: }
203:
204: public void updateDescendingSuccessors() {
205: for (PatternIterator ancestors = getLastSet(getStartSymbol())
206: .getPattern(); ancestors.hasNext();) {
207: Pattern ancestor = ancestors.next();
208: ancestor.addDescendingSuccessor(EOT);
209: }
210:
211: boolean modified;
212: do {
213: modified = false;
214:
215: for (PatternIterator ancestors = getAllPattern()
216: .getPattern(); ancestors.hasNext();) {
217: Pattern ancestor = ancestors.next();
218:
219: if (ancestor.getSymbol() != null) {
220: for (PatternIterator pattern = getLastSet(
221: ancestor.getSymbol()).getPattern(); pattern
222: .hasNext();) {
223: Pattern lastPattern = pattern.next();
224:
225: for (PatternIterator successors = ancestor
226: .getSuccessors(); successors.hasNext();) {
227: Pattern successor = successors.next();
228:
229: if ((lastPattern != successor)
230: || (!lastPattern
231: .hasSuccessor(successor)))
232: modified |= lastPattern
233: .addDescendingSuccessor(successor);
234: }
235:
236: for (PatternIterator successors = ancestor
237: .getAscendingSuccessors(); successors
238: .hasNext();) {
239: Pattern successor = successors.next();
240:
241: if ((lastPattern != successor)
242: || (!lastPattern
243: .hasDescendingSuccessor(successor)))
244: modified |= lastPattern
245: .addDescendingSuccessor(successor);
246: }
247:
248: for (PatternIterator successors = ancestor
249: .getDescendingSuccessors(); successors
250: .hasNext();) {
251: Pattern successor = successors.next();
252:
253: if ((lastPattern != successor)
254: || (!lastPattern
255: .hasDescendingSuccessor(successor)))
256: modified |= lastPattern
257: .addDescendingSuccessor(successor);
258: }
259: }
260: }
261:
262: for (PatternIterator successors = ancestor
263: .getDescendingSuccessors(); successors
264: .hasNext();) {
265: Pattern successor = successors.next();
266:
267: if ((successor.getSymbol() != null)
268: && (isNullable(successor.getSymbol()))) {
269: for (PatternIterator i = successor
270: .getSuccessors(); i.hasNext();) {
271: Pattern follow = i.next();
272: modified |= ancestor
273: .addDescendingSuccessor(follow);
274: }
275:
276: for (PatternIterator i = successor
277: .getAscendingSuccessors(); i.hasNext();) {
278: Pattern follow = i.next();
279: modified |= ancestor
280: .addDescendingSuccessor(follow);
281: }
282:
283: for (PatternIterator i = successor
284: .getDescendingSuccessors(); i.hasNext();) {
285: Pattern follow = i.next();
286: modified |= ancestor
287: .addDescendingSuccessor(follow);
288: }
289: }
290: }
291: }
292: } while (modified);
293: }
294:
295: /**
296: * Set the start symbol for this grammar.
297: *
298: * @param startSymbol Start symbol.
299: */
300: public void setStartSymbol(String symbol) {
301: this .startSymbol = symbol;
302: }
303:
304: /**
305: * Return the start symbol.
306: *
307: * @return Start symbol.
308: */
309: public String getStartSymbol() {
310: return startSymbol;
311: }
312:
313: public Pattern getStartPattern() {
314: return BOT;
315: }
316:
317: public Pattern getEndPattern() {
318: return EOT;
319: }
320:
321: /**
322: * Set the location from the input source.
323: *
324: * @param location Location in the input source.
325: */
326: public void setLocation(String location) {
327: this .location = location;
328: }
329:
330: /**
331: * Returns the location from the input source.
332: *
333: * @return Location in the input source.
334: */
335: public String getLocation() {
336: return location;
337: }
338:
339: /**
340: * Validated the grammar.
341: *
342: * @return Return a list of violations, if this object isn't valid.
343: */
344: public Violations validate() {
345: Violations violations = new Violations();
346:
347: if (startSymbol == null)
348: violations.addViolation("Start symbol is not defined",
349: location);
350:
351: /*for (int i = 0; i<definitions.length; i++)
352: for (int j = 0; j<definitions.length; j++)
353: if ((i!=j) && (definitions[i].getSymbol().equals(definitions[j].getSymbol())))
354: violations.addViolation("Element '"+definitions[i].getSymbol()+"' is already defined",
355: definitions[i].getLocation());*/
356: if (getDefinition(startSymbol) == null)
357: violations.addViolation("Start symbol \"" + startSymbol
358: + "\"" + "is not defined through a definition",
359: location);
360:
361: if (getDefinitionCount() <= 0)
362: violations.addViolation("No definitions are defined",
363: location);
364:
365: for (int i = 0; i < definitions.length; i++)
366: violations.addViolations(definitions[i].validate());
367:
368: /*SymbolSet ntdefinitions = getSymbols().getNonterminals();
369:
370: for (int i = 0; i<ntdefinitions.getSymbolCount(); i++)
371: if ( !contains(ntdefinitions.getSymbol(i)))
372: violations.addViolation("Nonterminal symbol \""+
373: ntdefinitions.getSymbol(i)+"\""+
374: "is not defined through a definition", location);*/
375: return violations;
376: }
377:
378: /**
379: * Return a string representation of the grammar.
380: *
381: * @return String representation.
382: */
383: public String toString() {
384: StringBuffer buffer = new StringBuffer();
385:
386: buffer.append("Definitions:\n");
387: for (int i = 0; i < getDefinitionCount(); i++) {
388: buffer.append(String.valueOf(i));
389: buffer.append(".Definition: ");
390:
391: buffer.append(definitions[i]);
392: buffer.append(" ");
393:
394: buffer.append("\n");
395: }
396:
397: buffer.append("\n");
398:
399: return buffer.toString();
400: }
401:
402: public String toString(PatternSet previous, PatternSet next) {
403: boolean first = true;
404: StringBuffer buffer = new StringBuffer();
405: for (int i = 0; i < getDefinitionCount(); i++) {
406: PatternSet pattern = definitions[i].getAllPattern();
407: boolean found = false;
408: for (PatternIterator previousPattern = previous
409: .getPattern(); previousPattern.hasNext() && !found;)
410: found |= pattern.contains(previousPattern.next());
411:
412: for (PatternIterator nextPattern = next.getPattern(); nextPattern
413: .hasNext()
414: && !found;)
415: found |= pattern.contains(nextPattern.next());
416:
417: if (found) {
418: if (!first)
419: buffer.append("\n");
420:
421: buffer.append(definitions[i].toString(previous, next));
422: first = false;
423: }
424: }
425:
426: return buffer.toString();
427: }
428:
429: /**
430: * Creates a clone of this grammar.
431: *
432: * @return Clone of this grammar.
433: *
434: * @throws CloneNotSupportedException If an exception occurs during the cloning.
435: */
436: public Object clone() throws CloneNotSupportedException {
437: ExtendedGrammar clone = new ExtendedGrammar();
438:
439: clone.startSymbol = startSymbol;
440: for (int i = 0; i < definitions.length; i++)
441: clone.addDefinition((Definition) definitions[i].clone());
442:
443: clone.location = location;
444:
445: return clone;
446: }
447: }
|