/*******************************************************************************
 * 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>

		 */
		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 */};
														};
										};
								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;
														// greater index will now replace lesser
														reassignement[indexDescendant--]=indexMontant++;
												};
								// operating last deleted
								for (;indexMontant<nonTerminaux.length;indexMontant++)
										if (Arrays.binarySearch(silly,indexMontant)>=0)
												reassignement[indexMontant]=-1;
								replaceIndexes(reassignement,silly);
								// but removing some sillies may have create 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());
		};
}
