/*******************************************************************************
 * GenRGenS v.1.0, Generation of Random Genomic Sequences                      *
 * Copyright (C) 2001  Alain Denise/Yann Ponty                                 *
 *                                                                             *
 * This program is free software; you can redistribute it and/or               *
 * modify it under the terms of the GNU General Public License                 *
 * as published by the Free Software Foundation; either version 2              *
 * of the License, or (at your option) any later version.                      *
 *                                                                             *
 * This program is distributed in the hope that it will be useful,             *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of              *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               *
 * GNU General Public License for more details.                                *
 *                                                                             *
 * You should have received a copy of the GNU General Public License           *
 * along with this program; if not, write to the Free Software                 *
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA. *
 *******************************************************************************/

package GenRGenS.grammar;

import java.io.*;
import java.util.*;
import java.math.BigDecimal;
import GenRGenS.utility.*;
import GenRGenS.*;

/**
 * Classe ContextFreeGrammar
 * 
 * Tout symbole est en relation bijective avec son indexe Les symboles
 * non-terminaux(auxiliaires) sont les entiers >=0 Les symboles terminaux sont
 * les entiers <0 Le symbole de depart est initialement l'entier 0
 * 
 * Terminologie : - LHS (Left Hand Side) représente le partie gauche d'une règle
 * c-?d le non-terminal a dévelloper. - RHS (Right Hand Side) est la liste des
 * symboles en concaténation, développement du LHS.
 * 
 * A class for the context-free grammar (CFG)
 * 
 * @author Fr&eacute;d&eacute;ric Sarron
 * @version 1.0
 */
public class ContextFreeGrammar {
	public static final BigDecimal bigOne = new BigDecimal(1);

	private static final String newSymbolNamePrefix = "_New";
	/** numero utilisé pour l'ajout de nouveaux auxiliaires */
	private int numeroNouvelAuxiliaire = 1;

	/** index du symbol start */
	private int symbolStart = 0;

	/** representation textuelle des symboles non-terminaux */
	private String[] nonTerminaux;

	/** representation textuelle des symboles terminaux */
	private String[] terminaux;

	/**
	 * representation des productions de la grammaire - une ligne par regle - le
	 * premier entier du tableau est le symbole productif (LHS) - les suivants
	 * sont les symboles produits (RHS)
	 */
	private ContextFreeGrammarProduction[] productions;

	/**
	 * true ssi les symboles sont des chaines de caracteres false : un symbole
	 * <-> une lettre -> pas d'espaces de separation
	 */
	private boolean words = true;

	/** ponderation des terminaux */
	private BigDecimal[] terminalsMasses;

	/*
	 * ==================================================================
	 * CONSTRUCTEURS
	 * ================================================================
	 */

	/**
	 * Create a CFG with minimal informations. <br>
	 * for initialisation purpose
	 */

	public ContextFreeGrammar() {
		super();
	};

	/**
	 * Create a CFG using the given string.<BR>
	 * Try to parse it on the language whose specification follows :<BR>
	 * <UL>
	 * <LI>terminals and non_terminal name are alphanumeric idents<BR>
	 * it follows the regular expression <I>letter(letter|digit)*</I>
	 * <LI>a rule is given by :
	 * <UL>
	 * <LI>an ident for the left hand side (LHS)
	 * <LI>the symbol "->" (literally MINUS GREATER THAN) or the symbol "::="
	 * <LI>a sequence of idents for the right hand side (RHS)
	 * <LI>the rule ends by the symbole ";"
	 * </UL>
	 * <LI>an epsilon production is simply coded by an empty list as RHS
	 * <LI>comments are C-like
	 * </UL>
	 * The first LHS is assumed to be the start symbol.<BR>
	 * Any non-productive symbol (which doesn't appear as LHS) is considered as
	 * a terminal symbol.
	 * <P>
	 * an exemple :<BR>
	 * 
	 * <PRE>
	 * // this my grammar
	 * S -> A b thisisalong S;
	 * S -> ;                             // epsilon production
	 * thisisalong -> short thisisalong;
	 * </PRE>
	 */

	public ContextFreeGrammar(String s) throws IOException, BadGrammarException {
		this(new StringReader(s));
	};

	public ContextFreeGrammar(File fd) throws IOException, BadGrammarException {
		this(new FileReader(fd));
	};

	public ContextFreeGrammar(Reader r) throws IOException, BadGrammarException {
		ParseGrammar p = null;
		GenRGenSScanner s = new GenRGenSScanner(r);
		if (GenRGenS.verbose) {
			GenRGenS.err.println("Parsing description file ...");
		}
		p = new ParseGrammar(s);
		try {
			p.parse();
		} catch (Exception e) {
			throw (new BadGrammarException("Invalid description file !"));
		}

		if (p.isParseError()) {
			if (GenRGenS.verbose) {
				GenRGenS.err.println("Parsing failed !");
			}
			throw (new BadGrammarException(
					"Fatal semantic error(s), can't proceed to generation !"));
		} else {
			if (GenRGenS.verbose) {
				GenRGenS.err.println("Parsing Successfull !");
			}
		}
		symbolStart = p.getSymbolStart();
		nonTerminaux = p.getNonTerminaux();
		terminaux = p.getTerminaux();
		productions = p.getProductions();
		words = p.isWord();
		terminalsMasses = p.getTerminalsMasses();
	};

	/**
	 * Return a String object describing the grammar<BR>
	 * for the exemple below it will be something like this :
	 * 
	 * <PRE>
	 * Start : S
	 * Aux : S thisisalong
	 * Term : A b short
	 * Prod :
	 * S -> A b thisisalong S
	 * S -> -epsilon-
	 * thisisalong -> short thisisalong
	 * </PRE>
	 */
	public String toString() {
		int numLettre;
		String temp = "Start : " + nonTerminaux[symbolStart] + "\nAux : ";
		for (int i = 0; i < nonTerminaux.length; i++)
			temp += nonTerminaux[i] + " ";
		temp += "\nTerm : ";
		for (int i = 0; i < terminaux.length; i++)
			temp += terminaux[i] + " ";
		temp += "\nSequence spacing : " + (words ? "WORDS" : "LETTERS");
		temp += "\nWeights :";
		for (int i = 0; i < terminalsMasses.length; i++)
			temp += "\n\t" + terminaux[i] + " = "
					+ terminalsMasses[i].toString();
		temp += "\nProd :";
		for (int i = 0; i < productions.length; i++) {
			temp += "\n\t" + symbolName(productions[i].getLHS()) + " -> ";
			if (productions[i].isEpsilonProduction())
				temp += "-epsilon-";
			else
				for (int j = 1; j < productions[i].size(); j++)
					temp += symbolName(productions[i].get(j)) + " ";
		}
		;
		return (temp);
	};

	/**
	 * Trie les regles des productions selon l'ordre des indices des
	 * non-terminaux des LHS
	 */
	private void sortRules() {
		Arrays.sort(productions, new ContextFreeGrammarProductionComparator());
	};

	/*
	 * ==================================================================
	 * METHODES D'ACCES
	 * ==================================================================
	 */

	/**
	 * Renvoie le nombre de non-terminaux dans la grammaire initiale.
	 * 
	 * @return Le nombre de non-terminaux dans la grammaire initiale.
	 */
	public int numberOfNonTerminals() {
		return (nonTerminaux.length);
	};

	/**
	 * Renvoie un tableau de chaînes représentations des non-terminaux dans la
	 * grammaire initiale.
	 * 
	 * @return Un tableau de chaînes représentations des non-terminaux dans la
	 *         grammaire initiale.
	 */
	public String[] nonTerminalsNames() {
		return (nonTerminaux);
	};

	/**
	 * Renvoie le nombre de terminaux dans la grammaire initiale.
	 * 
	 * @return Le nombre de terminaux dans la grammaire initiale.
	 */
	public int numberOfTerminals() {
		return (terminaux.length);
	};

	/**
	 * Renvoie un tableau de chaînes représentations des terminaux dans la
	 * grammaire initiale.
	 * 
	 * @return Un tableau de chaînes représentations des terminaux dans la
	 *         grammaire initiale.
	 */
	public String[] terminalsNames() {
		return (terminaux);
	};

	/**
	 * Renvoie une représentation d'un symbole de la grammaire initiale.
	 * 
	 * @param index
	 *            L'index du symbole
	 * @return Une représentation d'un symbole de la grammaire initiale.
	 */
	public String symbolName(int index) {
		if (index < 0)
			return (terminaux[-1 - index]);
		else
			return (nonTerminaux[index]);
	}

	/**
	 * Affecte à un symbole une représentation.
	 * 
	 * @param index
	 *            L'index du symbole
	 * @param name
	 *            La nouvelle représentation pour le symbole
	 * @throws IllegalArgumentException
	 *             Si il n'existe pas de symbole d'index spécifié.
	 */
	public void setName(int index, String name) throws IllegalArgumentException {
		int indexTableau;
		if (index < 0) {
			indexTableau = -1 - index;
			if (indexTableau < terminaux.length)
				terminaux[-1 - index] = name;
			else
				throw (new IllegalArgumentException());
		} else if (index < nonTerminaux.length)
			nonTerminaux[index] = name;
		else
			throw (new IllegalArgumentException());
	}

	/**
	 * Renvoie le nombre de règles dans la grammaire initiale.
	 * 
	 * @return Le nombre de règles dans la grammaire initiale.
	 */
	public int numberOfProductions() {
		return (productions.length);
	};

	/**
	 * Renvoie une règle de la grammaire initiale.
	 * 
	 * @param index
	 *            L'index de la règle.
	 * @return Une règle de la grammaire initiale.
	 */
	public ContextFreeGrammarProduction getProduction(int index) {
		return (productions[index]);
	};

	/**
	 * Renvoie le non-terminal initial.
	 * 
	 * @return L'index du non-terminal initial.
	 */
	public int startSymbol() {
		return (symbolStart);
	};

	/**
	 * Renvoie le numéro d'index à attribuer au prochain non-terminal.
	 * 
	 * @return L'index à attribuer au prochain non-terminal.
	 */
	public int newNTid() {
		return (numeroNouvelAuxiliaire);
	};

	/*
	 * ==================================================================
	 * Utilitaires
	 * ==================================================================
	 */

	/**
	 * Renvoie le type de génération souhaitée.
	 * 
	 * @return true si génération en mode "mot", false sinon.
	 */
	public boolean getWords() {
		return words;
	};

	/**
	 * Renvoie les poids associé aux non-terminaux.
	 * 
	 * @return Un tableau d'instances de <code>BigDecimal</code> où le poids
	 *         d'un Terminal d'index <code>i</code> est obtenu en prenant la
	 *         <code>i-ème</code> case du tableau.
	 */
	public BigDecimal[] getWeights() {
		return terminalsMasses;
	};

	/**
	 * Transforme la grammaire en celle qui decrit le language contenant
	 * uniquement le mot vide. Le symbol start et sa représentation restent
	 * inchangés.
	 */
	private void makeEpsilonLanguage() {
		String start = nonTerminaux[symbolStart];
		nonTerminaux = new String[1];
		nonTerminaux[0] = start;
		terminaux = new String[0];
		ContextFreeGrammarProduction theOnlyProd = new ContextFreeGrammarProduction(
				1);
		theOnlyProd.put(0, 0);
		productions = new ContextFreeGrammarProduction[1];
		productions[0] = theOnlyProd;
	};

	/**
	 * This method will throw a <I>BadGrammarException</I> if this grammar
	 * contains non-terminals symbols which can't be reached. It will not try to
	 * remove them, just warning.
	 */

	public void testNonTerminalsAccessibility() throws BadGrammarException {
		boolean[] accessible = accessibleSymbols();
		for (int index = 0; index < accessible.length; index++)
			if (!accessible[index]) {
				String message = "Existing inaccessible symbol(s) : ";
				for (; index < accessible.length; index++) {
					if (!accessible[index])
						message += nonTerminaux[index];
				}
				message += "\nCan't proceed to generation ! ";
				throw (new BadGrammarException(message));
			}
	};

	/**
	 * This method will remove both unreachable non-terminals and their
	 * associate productions.
	 */
	public void removeUnreachableNonTerminals() {
		boolean[] accessible = accessibleSymbols();
		// deleting obsolete productions
		Vector newProductions = new Vector();
		for (int numProd = 0; numProd < productions.length; numProd++) {
			ContextFreeGrammarProduction prod = productions[numProd];
			int lhs = prod.getLHS();
			if (accessible[lhs])
				newProductions.add(productions[numProd]);
		}
		;
		productions = new ContextFreeGrammarProduction[newProductions.size()];
		for (int numProd = 0; numProd < newProductions.size(); numProd++)
			productions[numProd] = (ContextFreeGrammarProduction) newProductions
					.get(numProd);
		// since some non-terminals disappeared,
		// we have to update arrays, reassigning indexes
		int[] reassignement = new int[nonTerminaux.length];
		int indexMontant = 0;
		for (int indexCourant = 0; indexCourant < reassignement.length; indexCourant++)
			if (accessible[indexCourant])
				reassignement[indexCourant] = indexMontant++;
			else
				reassignement[indexCourant] = -1;
		int longueur = 0;
		for (int nt = 0; nt < accessible.length; nt++)
			if (!accessible[nt])
				longueur++;
		int[] compactInaccessible = new int[longueur];
		longueur = 0;
		for (int index = 0; index < accessible.length; index++)
			if (!accessible[index])
				compactInaccessible[longueur++] = index;
		replaceIndexes(reassignement, compactInaccessible);
	};

	/**
	 * Retourne un tableau de booléen disant pour chaque auxiliaire s'il est
	 * accessible depuis le symbole départ.
	 */
	private boolean[] accessibleSymbols() {
		boolean[] accessible = new boolean[nonTerminaux.length];
		accessible[symbolStart] = true;
		boolean accessibleHasChanged = true;
		ContextFreeGrammarProduction currentProd;
		int nt;
		while (accessibleHasChanged) {
			accessibleHasChanged = false;
			for (int numProd = 0; numProd < productions.length; numProd++)
				if (accessible[(currentProd = productions[numProd]).getLHS()])
					for (int index = 1; index < currentProd.size(); index++) {
						nt = currentProd.get(index);
						if (nt >= 0 && !accessible[nt])
							accessibleHasChanged = accessible[nt] = true;
					}
			;
		}
		;
		return (accessible);
	}

	/**
	 * return <i>true</i> iff this CFG grm <b>does not</b> describe the empty
	 * language :<br>
	 * {words generated by grm} != empty set
	 */
	public boolean describeNonEmptyLanguage() {
		// j'appelle auxiliaire generant un non-terminal
		// qui peut se deriver en un mot sur l'alphabet terminal
		boolean[] auxiliairesGenerant;
		int aux;
		auxiliairesGenerant = new boolean[nonTerminaux.length];
		// auxiliaireAjoute : true ssi un auxiliaire a ete
		// amene au statut de generant pendant un iteration du while
		boolean auxiliaireAjoute = true;
		// regleGeneratrice : true ssi la regle examinee peut produire
		// un mot sur l'alphabet terminal
		boolean regleGeneratrice;
		while (auxiliaireAjoute) {
			auxiliaireAjoute = false;
			for (int numProd = 0; numProd < productions.length; numProd++) {
				if (productions[numProd].size() == 1
						&& !auxiliairesGenerant[aux = productions[numProd]
								.getLHS()]) {
					auxiliaireAjoute = auxiliairesGenerant[aux] = true;
				} else {
					regleGeneratrice = true;
					for (int indexRHS = 1; indexRHS < productions[numProd]
							.size(); indexRHS++) {
						if ((aux = productions[numProd].get(indexRHS)) >= 0
								&& !auxiliairesGenerant[aux]) {
							regleGeneratrice = false;
							break;
						}
					}
					if (regleGeneratrice
							&& (!auxiliairesGenerant[aux = productions[numProd]
									.getLHS()]))
						auxiliaireAjoute = auxiliairesGenerant[aux] = true;
				}
			}
		}
		// la grammaire ne decrit pas le language vide
		// ssi le symbole de debut est generant
		return (auxiliairesGenerant[symbolStart]);
	}

	/**
	 * Calling this method cause the CFG to drop his "silly components" :<br>
	 * A "silly" non-terminal is a non-terminal whose all productions are
	 * epsilon-production. With this method the CFG loose both silly
	 * non-terminals and their corresponding productions.<br>
	 * Therefore RHS containing silly non-terminals are accordingly modified.<BR>
	 * <b>an exemple </b>:
	 * 
	 * <pre>
	 * 			 S -> a T b S;
	 * 			 S -> ;         // epsilon-production
	 * 			 T -> ;
	 * </pre>
	 * 
	 * becomes :
	 * 
	 * <pre>
	 * 			 S -> a b S;
	 * 			 S -> ;
	 * </pre>
	 * Note: Thanks to Alois Dreyfus for a bug report/fix on this function, 
	 * previously leading to some non-terminals being erroneously overwritten.
	 */
	public void removeSillyComponents() {
		int[] silly = sillyNonTerminals();
		if (Arrays.binarySearch(silly, symbolStart) >= 0) {
			// if the start symbol is silly
			// then the grammar simply describe the language
			// containing only the empty word
			makeEpsilonLanguage();
			return;
		}
		;
		if (silly.length != 0) {
			Vector newProductions = new Vector();
			for (int numProd = 0; numProd < productions.length; numProd++) {
				ContextFreeGrammarProduction prod = productions[numProd];
				int lhs = prod.getLHS();
				if (Arrays.binarySearch(silly, lhs) < 0) {
					Vector newRule = new Vector();
					// This rule dosn't "extend"
					// a silly non-terminal.
					// we transform the rule (if necessary),
					// removing all sillies from RHS
					newRule.add(new Integer(lhs));
					for (int index = 1; index < prod.size(); index++) {
						int nt;
						if (Arrays.binarySearch(silly, nt = prod.get(index)) < 0)
							// element of RHS is not silly
							newRule.add(new Integer(nt));
					}
					;
					try {
						newProductions.add(new ContextFreeGrammarProduction(
								newRule));
					} catch (BadGrammarException e) {/* levée si vecteur nul */
						e.printStackTrace();
					}
					;
				}
				;
			}
			;
			productions = new ContextFreeGrammarProduction[newProductions
					.size()];
			for (int numProd = 0; numProd < newProductions.size(); numProd++)
				productions[numProd] = (ContextFreeGrammarProduction) newProductions
						.get(numProd);
			// since some non-termials disappeared,
			// we have to update arrays, reassigning indexes
			int[] reassignement = new int[nonTerminaux.length];
			int indexMontant = 0, indexDescendant = nonTerminaux.length - 1;
			while (indexMontant <= indexDescendant)
				if (Arrays.binarySearch(silly, indexMontant) < 0)
					reassignement[indexMontant] = indexMontant++;
				else {
					// the non-terminals "indexMontant" is marked
					// to be disappeared
					reassignement[indexMontant] = -1;

					while (indexDescendant > indexMontant
							&& Arrays.binarySearch(silly, indexDescendant) >= 0) {
						// the non-terminals "indexDescendant" is marked
						// to be disappeared
						reassignement[indexDescendant--] = -1;
					}

					if (indexDescendant > indexMontant) { // if indexDescendant
															// >= indexMontant,
															// then the case has
															// already been
															// treated with
															// indexMontant
						// greater index will now replace lesser
						reassignement[indexDescendant--] = indexMontant++;
					}
				}
			;
			replaceIndexes(reassignement, silly);
			// but removing some sillies may have created others
			removeSillyComponents();
		}
		;
	}

	/**
	 * replaceIndexes(int[] newAssignement, int[] deleted) : modifie les
	 * attributs de la classe (noms et règles) de sorte que les indexes de
	 * non-terminaux soit réarrangés comme précis? exemple :
	 * newAssignement=[0;1;-1;3;2] toute référence à l'index 4 sera remplacée
	 * par une référence à l'index 2.
	 * 
	 * note : "deleted" contient tout les indexes dont la valeur par
	 * "newAssignement" est -1;
	 */
	private void replaceIndexes(int[] newAssignement, int[] deleted) {
		// cas du symbole de départ :
		symbolStart = newAssignement[symbolStart];
		// traitement des noms des non-terminaux
		String[] nonTerminauxSave = nonTerminaux;
		nonTerminaux = new String[nonTerminauxSave.length - deleted.length];
		int correspondance;
		for (int index = 0; index < nonTerminauxSave.length; index++)
			if ((correspondance = newAssignement[index]) >= 0)
				nonTerminaux[correspondance] = nonTerminauxSave[index];
		// on passe aux productions
		int symbol;
		for (int numProd = 0; numProd < productions.length; numProd++) {
			ContextFreeGrammarProduction prod = productions[numProd];
			for (int index = 0; index < prod.size(); index++)
				if ((symbol = prod.get(index)) >= 0)
					prod.put(index, newAssignement[symbol]);
		}
		;
	};

	/**
	 * sillyNonTerminals() : renvoie l'ensemble trié des non-terminaux idiots
	 * (voir removeSillyComponents)
	 */
	private int[] sillyNonTerminals() {
		boolean[] hasOnlyEpsilonProductions = new boolean[nonTerminaux.length];
		int[] retour;
		int combien = 0;
		Arrays.fill(hasOnlyEpsilonProductions, true);
		for (int numProd = 0; numProd < productions.length; numProd++)
			hasOnlyEpsilonProductions[productions[numProd].getLHS()] &= productions[numProd]
					.isEpsilonProduction();
		for (int nt = 0; nt < nonTerminaux.length; nt++)
			if (hasOnlyEpsilonProductions[nt])
				combien++;
		retour = new int[combien];
		combien = 0;
		for (int nt = 0; nt < nonTerminaux.length; nt++)
			if (hasOnlyEpsilonProductions[nt])
				retour[combien++] = nt;
		return (retour);
	}

	/**
	 * Return an array containing all the indexes of the non-terminals A such as
	 * A ->* epsilon.<BR>
	 * (for each of these non-terminals there is a derivation path leading to
	 * epsilon).<BR>
	 * This array is sorted so you can launch a binary search on it.<br>
	 * <b>prerequisite </b>: the CFG in input describe a non-empty language.
	 */
	public int[] epsilonDerivableNonTerminals() throws BadGrammarException {
		if (!describeNonEmptyLanguage())
			throw (new BadGrammarException(
					"This grammar describes an empty langage !\n"
							+ "Can't proceed to generation."));
		// j'appelle epsilon-auxiliaire un non-terminal
		// qui peut se deriver en le mot vide
		boolean[] epsilonAuxiliaires;
		int aux;
		epsilonAuxiliaires = new boolean[nonTerminaux.length];
		// auxiliaireAjoute : true ssi un auxiliaire a ete
		// amene au statut d'epsilon-auxiliaire pendant un iteration du while
		boolean auxiliaireAjoute = true;
		// regleEpsilonable : true ssi la regle examinee peut produire
		// le mot vide
		boolean regleEpsilonable;
		while (auxiliaireAjoute) {
			auxiliaireAjoute = false;
			for (int numProd = 0; numProd < productions.length; numProd++) {
				if (productions[numProd].size() == 1
						&& !epsilonAuxiliaires[aux = productions[numProd]
								.getLHS()]) {
					auxiliaireAjoute = epsilonAuxiliaires[aux] = true;
				} else {
					regleEpsilonable = true;
					for (int indexRHS = 1; indexRHS < productions[numProd]
							.size(); indexRHS++) {
						// ce symbol est terminal
						if ((aux = productions[numProd].get(indexRHS)) < 0) {
							regleEpsilonable = false;
							break;
						}
						;
						// ce symbole est non-terminal
						// mais il n'est pas certifie
						// comme derivant le mot vide
						if (!epsilonAuxiliaires[aux]) {
							regleEpsilonable = false;
							break;
						}
					}

					if (regleEpsilonable
							&& (!epsilonAuxiliaires[aux = productions[numProd]
									.getLHS()]))
						// si on a rencontr?que des non-terminaux
						// certifiés derivant le mot vide
						// alors partie gauche dérive le mot vide
						auxiliaireAjoute = epsilonAuxiliaires[aux] = true;
				}
			}
		}
		// on renvoit la liste triée des auxiliaires
		// pouvant engendrer le mot vide
		int longueur = 0;
		for (int i = 0; i < nonTerminaux.length; i++)
			if (epsilonAuxiliaires[i])
				longueur++;
		int[] resultat = new int[longueur];
		int index = 0;
		for (int i = 0; i < nonTerminaux.length; i++)
			if (epsilonAuxiliaires[i])
				resultat[index++] = i;
		return (resultat);
	}

	/**
	 * Transform this CFG to an equivalent e-free CFG. <b>prerequisite </b>:
	 * input CFG must describe a non_empty language.<br>
	 * This could create twin rules if your CFG is ambiguous.
	 */
	public void removeEpsilonProductions() throws BadGrammarException {
		removeSillyComponents();
		/*
		 * construction de l'ensemble ordonn?Ne qui regroupe tous les
		 * non-terminaux qui se derivent en epsilon Ne={A in NT / A->* e}
		 */
		int[] epsilonDerivables = epsilonDerivableNonTerminals();
		Vector newProductions = new Vector();
		for (int numProd = 0; numProd < productions.length; numProd++)
			removeEpsilonOneProduction(newProductions, productions[numProd],
					epsilonDerivables);
		productions = new ContextFreeGrammarProduction[newProductions.size()];
		for (int i = 0; i < newProductions.size(); i++)
			productions[i] = (ContextFreeGrammarProduction) newProductions
					.get(i);

		if (productions.length == 0)
			// the language conatin only epsilon,
			// but the production has been removed
			makeEpsilonLanguage();
		else if (Arrays.binarySearch(epsilonDerivables, symbolStart) >= 0)
		// si le symbole de départ peut se dériver en epsilon
		{
			int longueur = nonTerminaux.length;
			String[] nonTerminauxCopie = nonTerminaux;
			ContextFreeGrammarProduction[] productionsCopie = new ContextFreeGrammarProduction[productions.length + 2];

			// ajout d'un nouvel auxiliaire
			// en tant que symbole de départ
			nonTerminaux = new String[longueur + 1];
			for (int i = 0; i < longueur; i++)
				nonTerminaux[i] = nonTerminauxCopie[i];
			// calcul du nom
			nonTerminaux[longueur] = newSymbolNamePrefix
					+ String.valueOf(numeroNouvelAuxiliaire++);
			// création des nouvelles productions S'->S (prod1)
			// et S'->epsilon (prod2)
			ContextFreeGrammarProduction prod1 = new ContextFreeGrammarProduction(
					2);
			ContextFreeGrammarProduction prod2 = new ContextFreeGrammarProduction(
					1);
			prod1.put(0, longueur);
			prod1.put(1, symbolStart);
			prod2.put(0, longueur);
			// assignation du symbol start
			symbolStart = longueur;
			// ajout des nouvelles règles
			longueur = productions.length;
			for (int i = 0; i < longueur; i++)
				productionsCopie[i] = productions[i];
			productionsCopie[longueur] = prod1;
			productionsCopie[longueur + 1] = prod2;
			productions = productionsCopie;
		}
		;
		sortRules();
	}

	/**
	 * removeEpsilonOneProduction (Vector newProdutions,
	 * ContextFreeGrammarProduction prod, int[] epsilonDerivables) : transforme
	 * la liste des productions en substituant les non-terminaux dérivant
	 * epsilon dans la règle donnée
	 */
	private void removeEpsilonOneProduction(Vector newProdutions,
			ContextFreeGrammarProduction prod, int[] epsilonDerivables) {
		// si prod est une epsilon-production on peut l'oublier :
		// son influence est prise en compte dans l'algorithme
		// (sa LHS est elemnt de l'ensemble des auxiliaires
		// dérivant epsilon
		if (!prod.isEpsilonProduction()) {
			Vector partieRegleEnConstruction = new Vector();
			partieRegleEnConstruction.add(new Integer(prod.getLHS()));
			removeEpsilonOneProductionSlave(epsilonDerivables, newProdutions,
					partieRegleEnConstruction, prod, 1);
		}
	}

	/**
	 * removeEpsilonOneProductionSlave(int[] epsilonDerivables, Vector
	 * newProdutions, Vector partieRegle, ContextFreeGrammarProduction prod, int
	 * indexRHS) : induction du procéd?de construction des règles de
	 * substitution dans l'élimination des production dérivant epsilon.
	 * partieRegle est la regle en construction sous forme de vecteur d'entiers
	 * (symboles).
	 */
	private void removeEpsilonOneProductionSlave(int[] epsilonDerivables,
			Vector newProductions, Vector partieRegle,
			ContextFreeGrammarProduction prod, int indexRHS) {
		while (indexRHS < prod.size()) {
			int symbole;
			if ((symbole = prod.get(indexRHS)) < 0
					|| Arrays.binarySearch(epsilonDerivables, symbole) < 0)
				// les terminaux et les non-terminaux
				// ne dérivant pas epsilon restent
				partieRegle.add(new Integer(symbole));
			else
			// dédoublement de la règle partielle :
			{
				Vector partieRegleCopie = (Vector) partieRegle.clone();
				partieRegleCopie.add(new Integer(symbole));
				// soit le symbole donne le mot vide
				removeEpsilonOneProductionSlave(epsilonDerivables,
						newProductions, partieRegle, prod, indexRHS + 1);

				// soit il est reproduit pour ses derivations non vide
				removeEpsilonOneProductionSlave(epsilonDerivables,
						newProductions, partieRegleCopie, prod, indexRHS + 1);
				break;
			}
			;
			indexRHS++;
		}
		;
		if (indexRHS >= prod.size())
		// bouclage : ajout de la nouvelle règle
		// a condition qu'elle ne soit pas une epsilon-production
		{
			if (partieRegle.size() > 1) {
				try {
					ContextFreeGrammarProduction newProd = new ContextFreeGrammarProduction(
							partieRegle);
					newProductions.add(newProd);
				} catch (BadGrammarException e) {/* cela n'arrive pas */
				}

			}
		}
		;
	}

	/**
	 * retourne true ssi la production donnée en argument n'a que des
	 * non-terminaux dans sa RHS et chacun de ces auxiliaires peut dériver
	 * epsilon
	 */
	private boolean allEpsilonDerivableRHS(ContextFreeGrammarProduction prod,
			int[] epsilonDerivables) {
		if (prod.isEpsilonProduction())
			return (true);
		else {
			boolean aedRHS = true;
			int indexSymbol;
			for (int i = 1; i < prod.size(); i++) {
				if ((indexSymbol = prod.get(i)) < 0
						|| Arrays.binarySearch(epsilonDerivables, indexSymbol) < 0) {
					aedRHS = false;
					break;
				}
				;
			}
			return (aedRHS);
		}
	}

	/**
	 * Transform this CFG to an equivalent CFG without single productions.<BR>
	 * <B>prerequisite</B> : this CFG must be e-free.
	 */
	public void removeSingleProductions() {
		// singleProducted[nt1][nt2] is true
		// iff there is a chain of single productions such as nt1 ->* nt2
		int combienNT = nonTerminaux.length, destination, lhs;
		boolean[][] singleProducted = new boolean[combienNT][combienNT];
		boolean singleProductedHasChanged;
		ContextFreeGrammarProduction currentProd;
		for (int origine = 0; origine < combienNT; origine++) {
			// A ->* A
			singleProducted[origine][origine] = singleProductedHasChanged = true;
			while (singleProductedHasChanged) {
				singleProductedHasChanged = false;
				for (int numProd = 0; numProd < productions.length; numProd++)
					if (
					// si la LHS L est telle que origine ->* L
					singleProducted[origine][lhs = (currentProd = productions[numProd])
							.getLHS()] &&
					// et nous observons une production simple
							currentProd.isSingleProduction() &&
							// et cette RHS n'est pas encore incluse
							!singleProducted[origine][destination = currentProd
									.get(1)])
						// alors
						singleProductedHasChanged = singleProducted[origine][destination] = true;
			}
			;
		}
		;
		/*
		 * construisons de nouvelles regles ou toutes les productions simples
		 * sont éliminées. Ajout donc de nouvelles règles qui reprennent les
		 * relations de chaînage découvertes précédemment
		 */
		Vector newProductions = new Vector();
		Vector RHSprod;
		for (int numProd = 0; numProd < productions.length; numProd++) {
			if ((currentProd = productions[numProd]).isEpsilonProduction())
				// c'est l'unique epsilon-production
				// (d'apres les prerequis : la grammaire est e-free
				newProductions.add(currentProd);
			else if (!currentProd.isSingleProduction()) {
				destination = currentProd.get(0);
				RHSprod = new Vector();
				// construction de la RHS
				for (int index = 0; index < currentProd.size(); index++)
					RHSprod.add(new Integer(currentProd.get(index)));
				// ajout de la RHS pour tout les NT simplement chaînés
				// ?"origine"
				for (int origine = 0; origine < combienNT; origine++)
					if (singleProducted[origine][destination]) {
						try {
							RHSprod.set(0, new Integer(origine));
							newProductions
									.add(new ContextFreeGrammarProduction(
											RHSprod));
						} catch (BadGrammarException e) {
							/*
							 * pas possible : on ajoute au moins la prod.
							 * originale
							 */
						}
						;
					}
				;
			}
			;
		}
		;
		// on fixe les nouvelles productions
		productions = new ContextFreeGrammarProduction[newProductions.size()];
		for (int numProd = 0; numProd < newProductions.size(); numProd++)
			productions[numProd] = (ContextFreeGrammarProduction) newProductions
					.get(numProd);
		/*
		 * des auxiliaires ont pu devenir inaccessibles exemple : A -> B;
		 * (start) B -> b; devient A -> b par court-circuit du chaînage B -> b
		 * reste, est devenu inaccessible
		 */
		removeUnreachableNonTerminals();
		sortRules();
	};

	// pour test de la classe
	private static void main(String[] arg) {
		ContextFreeGrammar cfg;
		File[] directoryListing = (new File("../testfiles/ContextFreeGrammar/")
				.listFiles(new FileExtensionFilter("ggd")));
		PrintStream testResult;

		for (int numFichier = 0; numFichier < directoryListing.length; numFichier++) {
			cfg = new ContextFreeGrammar();
			// = null : seule solution trouvée au prb du
			// try/catch et "may not have been init."
			testResult = null;
			try {
				testResult = new PrintStream(new FileOutputStream(
						directoryListing[numFichier].toString() + ".result"));
			} catch (IOException e) {
				GenRGenS.out.println("Damned ! " + e.toString());
			}
			if (testResult != null) {
				try {
					testResult.println("=*=*= Result for file "
							+ directoryListing[numFichier] + " =*=*=");
					cfg = new ContextFreeGrammar((new File(
							directoryListing[numFichier].getAbsolutePath())));
					testResult.println("Stored CFG :\n" + cfg.toString());
					testResult.println("\nDescribe non-empty language : "
							+ cfg.describeNonEmptyLanguage());
					cfg.testNonTerminalsAccessibility();
					int[] silly = cfg.sillyNonTerminals();
					testResult.print("\nSilly non-terminals : ");
					if (silly.length == 0)
						testResult.println("(none)");
					else
						for (int i = 0; i < silly.length; i++)
							testResult.print(cfg.symbolName(silly[i]) + " ");
					int[] auxMotVide = cfg.epsilonDerivableNonTerminals();
					testResult.print("\nEpsilon derivating non-terminals : ");
					if (auxMotVide.length == 0)
						testResult.println("(none)");
					else
						for (int i = 0; i < auxMotVide.length; i++)
							testResult.print(cfg.symbolName(auxMotVide[i])
									+ " ");
					testResult.println("\n\ne-free equivalent grammar :");
					cfg.removeEpsilonProductions();
					testResult.println(cfg.toString());
					testResult.println("\nsingle-free equivalent grammar :");
					cfg.removeSingleProductions();
					testResult.println(cfg.toString());
				} catch (IOException e) {
					testResult.println("Damned ! " + e.toString());
				} catch (BadGrammarException e) {
					testResult.println(e.toString());
				}
				;
				testResult.println("\n\n\n\n");
				testResult.close();
				GenRGenS.out.println("wrote "
						+ directoryListing[numFichier].toString() + ".result");
			}
			;
		}
		;
		GenRGenS.out.println("All done !");
		System.exit(0);

	};
}

/*****************************************************************/
/* classe ContextFreeGrammarProductionComparator */
/* compare les productions des grammaires context-free */
/* (A ::= X1 ... Xn) < (B ::= Y1 ... Yn) */
/* ssi index(A)<index(B) */
/*****************************************************************/
class ContextFreeGrammarProductionComparator implements Comparator {
	public int compare(Object o1, Object o2) {
		return (((ContextFreeGrammarProduction) o1).getLHS() - ((ContextFreeGrammarProduction) o2)
				.getLHS());
	};
}
