Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda nick_10 » 14/12/2018, 00:04

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
nick_10
Average Member
Average Member
 
Messaggio: 365 di 754
Iscritto il: 17/11/2016, 16:21

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda apatriarca » 14/12/2018, 00:46

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..
apatriarca
Moderatore
Moderatore
 
Messaggio: 5171 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda nick_10 » 14/12/2018, 09:54

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;
}
nick_10
Average Member
Average Member
 
Messaggio: 366 di 754
Iscritto il: 17/11/2016, 16:21

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda apatriarca » 14/12/2018, 10:28

Devi cambiare anche il test sulla dimensione. Hai bisogno di almeno 3 valori a questo punto.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5172 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda nick_10 » 14/12/2018, 13:40

Mmm...dov'è che può andare male il mio frammento di codice?
nick_10
Average Member
Average Member
 
Messaggio: 367 di 754
Iscritto il: 17/11/2016, 16:21

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda apatriarca » 14/12/2018, 13:42

Hai ragione, dovrebbe funzionare lo stesso.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5173 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda nick_10 » 14/12/2018, 16:58

Grazie mille per l'aiuto!! :)
nick_10
Average Member
Average Member
 
Messaggio: 368 di 754
Iscritto il: 17/11/2016, 16:21

Precedente

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite