/*
* Copyright (C) Chaperon. All rights reserved.
* -------------------------------------------------------------------------
* This software is published under the terms of the Apache Software License
* version 1.1, a copy of which has been included with this distribution in
* the LICENSE file.
*/
package net.sourceforge.chaperon.model.extended;
import net.sourceforge.chaperon.model.Violations;
import java.io.Serializable;
/**
* This class represents a model for a grammar. The content of the grammar includes the
* definitions, start symbol, associativities and priorities.
*
* @author <a href="mailto:stephan@apache.org">Stephan Michels </a>
* @version CVS $Id: ExtendedGrammar.java,v 1.19 2004/01/08 11:30:52 benedikta Exp $
*/
public class ExtendedGrammar implements Serializable, Cloneable
{
// Start symbol
private String startSymbol = null;
// Definitions
private Definition[] definitions = new Definition[0];
private String location = null;
private BeginOfText BOT = new BeginOfText();
private EndOfText EOT = new EndOfText();
/**
* Creates an empty grammar.
*/
public ExtendedGrammar() {}
/**
* Add a definition to this grammar.
*
* @param definition Definition, which should be added.
*
* @return Index of the definition in this grammar.
*/
public void addDefinition(Definition definition)
{
if (definition==null)
throw new NullPointerException();
for (PatternIterator i = definition.getAllPattern().getPattern(); i.hasNext();)
{
Pattern pattern = i.next();
pattern.setDefinition(definition);
}
Definition[] newDefinitions = new Definition[definitions.length+1];
System.arraycopy(definitions, 0, newDefinitions, 0, definitions.length);
newDefinitions[definitions.length] = definition;
definitions = newDefinitions;
}
/**
* Return a definition giving by an index.
*
* @param index Index of the Definition.
*
* @return The definition.
*/
public Definition getDefinition(int index)
{
return definitions[index];
}
/**
* Returns all definition for given nonterminal symbol as a list of indices.
*
* @param ntsymbol Nonterminal symbol
*
* @return List of indices from the definitions
*/
public Definition getDefinition(String symbol)
{
for (int i = 0; i<definitions.length; i++)
if (definitions[i].getSymbol().equals(symbol))
return definitions[i];
return null;
}
public Definition[] getDefinitions()
{
return definitions;
}
/**
* Returns the count of definitions in this grammar.
*
* @return Count of definitions.
*/
public int getDefinitionCount()
{
return definitions.length;
}
public PatternSet getAllPattern()
{
PatternSet set = new PatternSet();
for (int i = 0; i<definitions.length; i++)
set.addPattern(definitions[i].getAllPattern());
set.addPattern(BOT);
set.addPattern(EOT);
return set;
}
public void update()
{
for (int i = 0; i<definitions.length; i++)
definitions[i].update();
updateAscendingSuccessors();
updateDescendingSuccessors();
}
public void updateAscendingSuccessors()
{
for (PatternIterator successors = getFirstSet(getStartSymbol()).getPattern();
successors.hasNext();)
{
Pattern succesor = successors.next();
BOT.addAscendingSuccessor(succesor);
}
boolean modified;
do
{
modified = false;
for (PatternIterator successors = getAllPattern().getPattern(); successors.hasNext();)
{
Pattern successor = successors.next();
if (successor.getSymbol()!=null)
{
PatternSet firstSet = getFirstSet(successor.getSymbol());
for (PatternIterator ancestors = successor.getAncestors(); ancestors.hasNext();)
{
Pattern ancestor = ancestors.next();
for (PatternIterator i = firstSet.getPattern(); i.hasNext();)
{
Pattern firstPattern = i.next();
modified |= ancestor.addAscendingSuccessor(firstPattern);
}
}
for (PatternIterator ancestors = successor.getAscendingAncestors(); ancestors.hasNext();)
{
Pattern ancestor = ancestors.next();
for (PatternIterator i = firstSet.getPattern(); i.hasNext();)
{
Pattern firstPattern = i.next();
modified |= ancestor.addAscendingSuccessor(firstPattern);
}
}
}
}
}
while (modified);
}
public boolean isNullable(String symbol)
{
for (int i = 0; i<definitions.length; i++)
if (definitions[i].getSymbol().equals(symbol))
return definitions[i].isNullable();
return true;
}
public PatternSet getFirstSet(String symbol)
{
PatternSet firstSet = new PatternSet();
for (int i = 0; i<definitions.length; i++)
if (definitions[i].getSymbol().equals(symbol))
firstSet.addPattern(definitions[i].getFirstSet());
return firstSet;
}
public PatternSet getFirstSet()
{
return getFirstSet(getStartSymbol());
}
public PatternSet getLastSet(String symbol)
{
PatternSet lastSet = new PatternSet();
for (int i = 0; i<definitions.length; i++)
if (definitions[i].getSymbol().equals(symbol))
lastSet.addPattern(definitions[i].getLastSet());
return lastSet;
}
public PatternSet getLastSet()
{
return getLastSet(getStartSymbol());
}
public void updateDescendingSuccessors()
{
for (PatternIterator ancestors = getLastSet(getStartSymbol()).getPattern();
ancestors.hasNext();)
{
Pattern ancestor = ancestors.next();
ancestor.addDescendingSuccessor(EOT);
}
boolean modified;
do
{
modified = false;
for (PatternIterator ancestors = getAllPattern().getPattern(); ancestors.hasNext();)
{
Pattern ancestor = ancestors.next();
if (ancestor.getSymbol()!=null)
{
for (PatternIterator pattern = getLastSet(ancestor.getSymbol()).getPattern();
pattern.hasNext();)
{
Pattern lastPattern = pattern.next();
for (PatternIterator successors = ancestor.getSuccessors(); successors.hasNext();)
{
Pattern successor = successors.next();
if ((lastPattern!=successor) || (!lastPattern.hasSuccessor(successor)))
modified |= lastPattern.addDescendingSuccessor(successor);
}
for (PatternIterator successors = ancestor.getAscendingSuccessors();
successors.hasNext();)
{
Pattern successor = successors.next();
if ((lastPattern!=successor) || (!lastPattern.hasDescendingSuccessor(successor)))
modified |= lastPattern.addDescendingSuccessor(successor);
}
for (PatternIterator successors = ancestor.getDescendingSuccessors();
successors.hasNext();)
{
Pattern successor = successors.next();
if ((lastPattern!=successor) || (!lastPattern.hasDescendingSuccessor(successor)))
modified |= lastPattern.addDescendingSuccessor(successor);
}
}
}
for (PatternIterator successors = ancestor.getDescendingSuccessors(); successors.hasNext();)
{
Pattern successor = successors.next();
if ((successor.getSymbol()!=null) && (isNullable(successor.getSymbol())))
{
for (PatternIterator i = successor.getSuccessors(); i.hasNext();)
{
Pattern follow = i.next();
modified |= ancestor.addDescendingSuccessor(follow);
}
for (PatternIterator i = successor.getAscendingSuccessors(); i.hasNext();)
{
Pattern follow = i.next();
modified |= ancestor.addDescendingSuccessor(follow);
}
for (PatternIterator i = successor.getDescendingSuccessors(); i.hasNext();)
{
Pattern follow = i.next();
modified |= ancestor.addDescendingSuccessor(follow);
}
}
}
}
}
while (modified);
}
/**
* Set the start symbol for this grammar.
*
* @param startSymbol Start symbol.
*/
public void setStartSymbol(String symbol)
{
this.startSymbol = symbol;
}
/**
* Return the start symbol.
*
* @return Start symbol.
*/
public String getStartSymbol()
{
return startSymbol;
}
public Pattern getStartPattern()
{
return BOT;
}
public Pattern getEndPattern()
{
return EOT;
}
/**
* Set the location from the input source.
*
* @param location Location in the input source.
*/
public void setLocation(String location)
{
this.location = location;
}
/**
* Returns the location from the input source.
*
* @return Location in the input source.
*/
public String getLocation()
{
return location;
}
/**
* Validated the grammar.
*
* @return Return a list of violations, if this object isn't valid.
*/
public Violations validate()
{
Violations violations = new Violations();
if (startSymbol==null)
violations.addViolation("Start symbol is not defined", location);
/*for (int i = 0; i<definitions.length; i++)
for (int j = 0; j<definitions.length; j++)
if ((i!=j) && (definitions[i].getSymbol().equals(definitions[j].getSymbol())))
violations.addViolation("Element '"+definitions[i].getSymbol()+"' is already defined",
definitions[i].getLocation());*/
if (getDefinition(startSymbol)==null)
violations.addViolation("Start symbol \""+startSymbol+"\""+
"is not defined through a definition", location);
if (getDefinitionCount()<=0)
violations.addViolation("No definitions are defined", location);
for (int i = 0; i<definitions.length; i++)
violations.addViolations(definitions[i].validate());
/*SymbolSet ntdefinitions = getSymbols().getNonterminals();
for (int i = 0; i<ntdefinitions.getSymbolCount(); i++)
if ( !contains(ntdefinitions.getSymbol(i)))
violations.addViolation("Nonterminal symbol \""+
ntdefinitions.getSymbol(i)+"\""+
"is not defined through a definition", location);*/
return violations;
}
/**
* Return a string representation of the grammar.
*
* @return String representation.
*/
public String toString()
{
StringBuffer buffer = new StringBuffer();
buffer.append("Definitions:\n");
for (int i = 0; i<getDefinitionCount(); i++)
{
buffer.append(String.valueOf(i));
buffer.append(".Definition: ");
buffer.append(definitions[i]);
buffer.append(" ");
buffer.append("\n");
}
buffer.append("\n");
return buffer.toString();
}
public String toString(PatternSet previous, PatternSet next)
{
boolean first = true;
StringBuffer buffer = new StringBuffer();
for (int i = 0; i<getDefinitionCount(); i++)
{
PatternSet pattern = definitions[i].getAllPattern();
boolean found = false;
for (PatternIterator previousPattern = previous.getPattern();
previousPattern.hasNext() && !found;)
found |= pattern.contains(previousPattern.next());
for (PatternIterator nextPattern = next.getPattern(); nextPattern.hasNext() && !found;)
found |= pattern.contains(nextPattern.next());
if (found)
{
if (!first)
buffer.append("\n");
buffer.append(definitions[i].toString(previous, next));
first = false;
}
}
return buffer.toString();
}
/**
* Creates a clone of this grammar.
*
* @return Clone of this grammar.
*
* @throws CloneNotSupportedException If an exception occurs during the cloning.
*/
public Object clone() throws CloneNotSupportedException
{
ExtendedGrammar clone = new ExtendedGrammar();
clone.startSymbol = startSymbol;
for (int i = 0; i<definitions.length; i++)
clone.addDefinition((Definition)definitions[i].clone());
clone.location = location;
return clone;
}
}