dunque andiamo per gradi: io provo a eseguire questo comando da console: java -Xss100m Main e ottengo nuovamente uno stack overflow, il che mi pare abbastanza impossibile se ho un input di 12 righe (e con 11, risposta istantanea senza problemi) e uno stack di 100 mega, come dovrei averlo settato. quindi probabilmente sbaglio qualcosa.
dal lato proprio algoritmico, proviamo a postare qualcosa e a commentare quello che diavolo ho combinato. il programma dovrebbe eseguire essere un parser universale per grammatiche di tipo 1. premettiamo un po' di oggetti che io ho definito ad-hoc:
Production, fatto di una coppia di stringhe (leftSide, rightSide)
Grammar, fatto di un vector di production (productionSet) e una stringa (startSymbol)
Ancestor, fatto di una coppia stringa (sententialForm) e intero (productionIndexUsedToUnfold)
poi ho definito un sententialFormStack, che e' uno Stack<Ancestor>, che e' lo stack delle sentential forms che devo controllare per verificare se una data stringa (stringToCheck) appartiene o no alla grammatica.
il metodo check prende in unput un int (scanIndex), che e' il puntatore al productionSet che mi dice da dove devo cominciare a trovare a trovare delle produzioni "buone" per unfoldare.
io faccio questo se lo stack e' vuoto cerco nel productionSet
una produzione del tipostartSymbol => sententialForm, where |sententialForm| <= |stringToCheck| (perche' sappiamo che le grammatiche di tipo uno "non si accorciano"). appena trovo una produzione "buona"
pusho nello stack l'Ancestor(startSymbol, i),
dove i ie' l'indice usato per unfoldare l'assioma della grammatica (cioe' startSymbol). poi parte una chiamata ricorsiva di check
se lo stack non e' vuoto, sono "in mezzo" al mio unfolding tree:
guardo l'elemento al top of the stack, e cerco nel productionSet delle parti sinistre (leftSide) che sono nella sententialForm corrente, cioe' quella dove sono arrivato unfoldando fino ad adesso. appena ne ho trovata una continuo ad unfoldare, controllando ogni volta se stringToCheck matcha la currentSententialForm e la pusho nello stack con l'indice della produzione che ho usato. se non riesco a trovare ulteriori produzioni per la currentStringToCheck, allora rimuovo l'elemento al top of the stack e continuo a parsare dall'indice dealla produzione che ho usato per andare nella vecchia sententialForm che ho eliminato. l'algoritmo funziona, da quello che ho potuto testare con stringhe da checkare di una decina di caratteri. il problema e' che con input piu' grossi incorro il 90% delle volte in stack overflow. ora ho qualche possibilita', apparte quella di cambiare completamente algoritmo?
public boolean check(int scanIndex)
{
productionSet = givenGrammar.getProductionSet();
startSymbol = givenGrammar.getStartSymbol();
if(sententialFormStack.isEmpty())
{
for (i = scanIndex; i < productionSet.size(); i++)
{
currentLeftSide = productionSet.elementAt(i).getLeftSide();
currentRightSide = productionSet.elementAt(i).getRightSide();
if (currentLeftSide.equals(startSymbol) && currentRightSide.length() <= stringToCheck.length())
{
if(currentLeftSide.equals(stringToCheck))
{
return true;
}
sententialFormStack.push(new Ancestor(startSymbol, i));
return check(0);
}
}
return false;
}
else
{
currentSententialForm = sententialFormStack.peek().getSententialForm();
currentScanIndex = sententialFormStack.peek().getProductionIndexUsedToUnfold();
for(i = scanIndex; i < productionSet.size(); i++)
{
currentLeftSide = productionSet.elementAt(i).getLeftSide();
currentRightSide = productionSet.elementAt(i).getRightSide();
totalLength = currentSententialForm.length() + currentRightSide.length() - currentLeftSide.length();
if(currentSententialForm.contains(currentLeftSide) && totalLength <= stringToCheck.length())
{
newSententialForm = currentSententialForm.replaceFirst(currentLeftSide, currentRightSide);
if(newSententialForm.equals(stringToCheck))
{
return true;
}
sententialFormStack.peek().setProductionIndexUsedToUnfold(i);
sententialFormStack.push(new Ancestor(newSententialForm, -1));
return check(0);
}
}
if(currentSententialForm.equals(startSymbol))
{
return false;
}
sententialFormStack.removeElementAt(sententialFormStack.size()-1);
currentScanIndex = sententialFormStack.peek().getProductionIndexUsedToUnfold();
sententialFormStack.peek().setProductionIndexUsedToUnfold(-1);
return check(currentScanIndex+1);
}
}