Newsgroup: it.comp.lang.c++
Titolo: Dubbi su push, pop e stack

Salve,
tempo fa ho scritto un programma (un interprete per il linguaggio brainfuck) 
il quale in alcuni casi mostrava dei malfunzionamenti. Per la gestione dei 
cicli, salvavo in un vettore tramite push, la posizione in cui iniziava il 
ciclo e alla fine del ciclo stesso, vedevo se la condizione era ancora vera 
ed in caso positivo estraevo la posizione precedentemente salvata nel 
vettore tramite pop(). Mi era stato fatto notare che l'interprete non doveva 
fare uso di stack e che quindi il problema probabilmente era legato a tale 
meccanismo.
Così ho cambiato implementazione e invece di salvare la posizione e poi 
estrarla, facevo scorrere il vettore all'indietro fino all'inizio del ciclo, 
ed in effetti ho risolto il problema. Ma vorrei capire come mai si sia 
verificato tutto ciò.
A me sembra che il meccanismo sia uguale perché tenevo traccia dei vari 
cicli annidati, ma evidentemente succede qualcosa che lo rende diverso.
Ecco lo stralcio di codice relativo all'uso di push e pop. La quadra aperta 
indica l'inizio del ciclo e la quadra chiusa la fine:
La variabile "i" è l'indice usato per il ciclo for dentro il quale avviene 
lo scorrimento del vettore delle istruzioni mentre "indice" è l'indice per 
scorrere il vettore "Vettore" che rappresenta in puntatore usato dal 
linguaggio per simulare le varie istruzioni.
case '[' :
    if (!Vettore[indice]) {
        int quadre = 0;
        while (i < Istruzioni.size()) {
            if (Istruzioni[i] == '[')
                quadre++;
            else
            if (Istruzioni[i] == ']')
                quadre--;
            i++;
            if (quadre == 0)
                break;
         };
     }
     else
         Loop.push_back(i);
     break;
case ']' :
    if (Loop.size() > 0)
        if (Vettore[indice])
            i = Loop.back();
        else
            Loop.pop_back();
        break;
Questo invece è il codice corretto:
case '[' :
    if (!Vettore[indice]) {
        int quadre = 0;
        while (i < Istruzioni.size()) {
            if (Istruzioni[i] == '[')
                quadre++;
            else
            if (Istruzioni[i] == ']')
                quadre--;
            i++;
            if (quadre == 0) {
                i--;
                break;
            };
         };
     };
     break;
case ']' :
    if (Vettore[indice]) {
        int quadre = 0;
        while (i >= 0) {
            if (Istruzioni[i] == '[')
                quadre++;
            else
            if (Istruzioni[i] == ']')
                quadre--;
            i--;
            if (quadre == 0) {
                i++;
                break;
            };
        };
     };
     break;
Saluti 

 while (i < Istruzioni.size()) {
scusa ma dove inizializzi il contatore "i" ?
E' la stessa variabile di controllo del loop esterno ? Non 
credo ... Volevo capire da che valore iniziale cominci la 
scansione, dalla cella successiva a quella del select case ?
Anche la condizione del test mi è oscura : procedi solo se 
vettore indice è == 0.
Boh ... non capisco

eh ... quella "i" dove viene inizializzata non è chiaro, a 
parte il resto.
Ciao
Soviet

 scusa ma dove inizializzi il contatore "i" ?
Dicevo che la i è la variabile di un ciclo for.
Comunque in effetti è meglio se incollo tutto il codice (in fondo non è 
molto lungo):
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;
vector<char> Istruzioni, Vettore;
int main (int argc, char* argv[]) {
    ifstream input (argv[1], ios_base::in);
    string str;
    int indice = 0;
    do {
        getline(input, str, '\n');
        for (int i = 0; i < str.size(); i++)
            Istruzioni.push_back(str[i]);
    }
    while (!input.eof());
    input.close();
    Vettore.resize(Istruzioni.size());
    for (int i = 0; i < Istruzioni.size(); i++) {
        switch (Istruzioni[i]) {
            case '>' :
                if (indice < Vettore.size() - 1)
                    indice++;
                break;
            case '<' :
                if (indice > 0)
                    indice--;
                break;
            case '+' :
                Vettore[indice]++;
                break;
            case '-' :
                if (Vettore[indice] > 0)
                    Vettore[indice]--;
                break;
            case '.' :
                putchar(Vettore[indice]);
                break;
            case ',' :
                Vettore[indice] = getchar();
                break;
           /* Il codice dei due case seguenti è quello postato in precedenza 
in due versioni (con e senza uso di push e pop) */
           case '[' :
            case ']' :
    };
    return 0;
}
 

 informazioni date fossero sufficienti.
magari è soggettivo che non lo sembrassero ...
Cmq, riguardandolo ho notato solo una differenza : che 
compensi l'incremento dell'indice qualora incontri una 
chiusura delle nested in sospeso
non sono sicuro cmq di capire bene il senso del ciclo while 
interno. Vengono gestite solo le parentesi, ma l'indice 
incrementato sempre (skippando ogni cosa diversa dalle 
parentesi, che non viene gestita ... e tuttavia l'incremento 
dell'indice i permane all'uscita del while, ergo le 
istruzioni interne dove vengono gestite ?).
Forse la mia confusione nasce dal fatto che in effetti pochi 
linguaggi sono tolleranti come il C/C++ sulla modifica 
diretta delle variabili contatori all'interno del ciclo come 
tutte le altre.
Sorry ma non riesco a dare nessun contributo
ciao
Soviet


 Soviet
Grazie lo stesso.
Saluti 

 un estremo di un ciclo all'altro.
Da l'estremo di un ciclo all'altro. Ad esempio usando la sintassi C++ da 
"while (condizione) {" a "}" e viceversa. 


faccio finta di avere capito :-)
In realtà mi sarei aspettato che, ogni volta che trovavi la 
prima parentesi chiusa, cercassi a ritroso il matching più 
recente di parentesi aperta, ed ergo invocassi 
ricorsivamente l'interprete per eseguire i comandi contenuti 
tra le due. Invece mi pare che questo scorrere e ricercare 
la prima e l'ultima parentesi, non comporti la scansione dei 
token contenuti da nessuna parte. Ma te lo dissi, non ho 
capito bene l'intera logica. Never mind
ciao
Soviet

 comandi contenuti tra le due.
Forse questo ti può aiutare: Brainfuck 
(
http://it.wikipedia.org/wiki/Brainfuck
) è un linguaggio in cui sono ammessi 
solo pochi caratteri.
Se il flusso del programma incontra una quadra aperta vuol dire che si trova 
di fronte ad un ciclo. A quel punto i casi sono 2:
1. Se la condizione è vera, continua la normale esecuzione delle istruzioni 
che vengono gestite dai vari case.
2. Se la condizione è falsa, ignora tutte le istruzioni finché non raggiunge 
la quadra chiusa corrispondente.
Se invece incontra una quadra chiusa deve semplicemente ritornare all'inizio 
del ciclo scorrendo le istruzioni a ritroso ma *senza* eseguirle.
Dopo aver raggiunto la quadra aperta corrispondente, si ritorna al caso 
precedente esposto gestito dal case relativo alla quadra aperta.
L'interpretazione vera e propria è gestita dagli altri case. I due relativi 
ai cicli gestiscono solo lo "spostamento" del flusso di codice, proprio per 
simulare l'iterazione.