Pagina 2 di 2

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 14/12/2018, 01:04
da nick_10
Come ultima cosa ho scritto questo
Codice:
bool checkone(int v[],int dim){
    if(dim<=0) return false;
    else if(dim==1){
        if(v[0]==1) return true;
        else return false;
    }
    else return checkone(v+1,dim-1);
}
bool check(int v[],int dim,int from){
    if(dim<=2) return false;
    if(from>=dim) return true;
    else if(dim==3){
        if((v[0]==0) && (v[1]==1) && (v[2]==0)) return true;
        else return false;
    }
    else if((v[from]!=v[dim-1])&&(v[0]!=0)) return false;
    else if(v[from]==0) {
        return check(v+1,dim-2,from+1);
    }
    else if(v[from]==1) return checkone(v+1,dim-2);
    else return false;
}

Però ci sono dei problemi...ad esempio legge anche stringhe con tutti 1 oppure non legge stringhe del tipo 0110
Per stasera la chiudo qui che non ragiono più. Riproverò sicuramente domani

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 14/12/2018, 01:46
da apatriarca
Qual'è il significato di from?

Un modo per implementare le funzione ricorsive per una qualche grammatica consiste nell'avere una funzione per ogni simbolo non terminale. Dalle produzione che hai scritto è chiaro che qualsiasi stringa prodotta da \(S\) deve essere compresa tra zeri. Puoi quindi iniziare a scriverla come condizione iniziale:
Codice:
bool checkS(int v[], int n)
{
    if (n < 2 || (v[0] != 0 && v[1] != 0)) { return false; }
    // resto della funzione
}

A questo punto devi stabilire quale delle due regole usare per continuare con il test. Il modo più semplice seguendo le regole di produzione è quella di provare entrambe le strade come segue:
Codice:
bool checkS(int v[], int n)
{
    if (n < 2 || (v[0] != 0 && v[1] != 0)) { return false; }
   
    return checkS(v+1, n-2) || checkA(v+1, n-2);
}

Tuttavia una delle due strade verrà subito esclusa e converrebbe quindi verificare la condizione immediatamente. Un modo sarebbe quello di modificare la grammatica in questo modo:
\[ \begin{align*} S &\to 0\,S\,0\;\mid\;0\,1\,A\,0 \\ A &\to \epsilon\;\mid\;1\,A \end{align*} \]
dove \(\epsilon\) indica la stringa vuota. A questo punto le due produzioni sono facilmente distinguibili senza dover andare a "tentativi". Ti lascio il compito di implementare questa ultima idea..

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 14/12/2018, 10:54
da nick_10
Scusa la versione di prima era molto incasinata...con quel from volevo verificare se il primo elemento di ogni pezzo di array (ad ogni passo della ricorsione) fosse 0 o 1 e così dividere i due casi

Comunque ho provato a seguire i tuoi consigli seguendo le produzioni della grammatica(in particolare quelle modificate con l'epsilon) e ho scritto questo:
Codice:
bool checkA(int v[],int dim){
    if(dim==0) return true;
    if(v[0]!=1) return false;
    else return checkA(v+1,dim-1);
}
bool checkS(int v[],int dim){
    if((dim<2)||(v[0]!=0)||(v[0]!=v[dim-1])) return false;
    else if(v[1]==0) return checkS(v+1,dim-2);
    else if(v[1]==1) return checkA(v+1,dim-2);
    else return false;
}

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 14/12/2018, 11:28
da apatriarca
Devi cambiare anche il test sulla dimensione. Hai bisogno di almeno 3 valori a questo punto.

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 14/12/2018, 14:40
da nick_10
Mmm...dov'è che può andare male il mio frammento di codice?

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 14/12/2018, 14:42
da apatriarca
Hai ragione, dovrebbe funzionare lo stesso.

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 14/12/2018, 17:58
da nick_10
Grazie mille per l'aiuto!! :)