Newsgroup: it.comp.lang.c++
Titolo: Costruzione, distruzione e ricorsione

Ciao,
per i miei loschi scopi sto architettando (quando avrò finito di 
architettarlo passerò a scrivere il codice) un analizzatore sintattico 
della lingua italiana. L'idea sarebbe di creare una classe base 
"costituente", che poi viene specializzata nelle varie classi 
"SintagmaVerbale", "SintagmaNominale", "Verbo", "Nome" ecc. ecc. ecc.
L'idea è di agire ricorsivamente: la classe costituente è questa, per ora:
// classe base astratta da cui discendono tutti gli altri elementi
class costituente
{
private:
bool terminale;
list <costituente*> Parti;
list <costituente*>::iterator CurrParte;
costituente* CPadre;
public:
costituente(costituente *P);  // CPadre = P
costituente(costituente *P, char *Testo);
costituente* GetPrimaParte(void);
costituente* GetAltraParte(void);
inline costituente* GetPadre() {return CPadre;};
virtual char* analizza(char *T);
virtual ~costituente();
};
la funzione analizza(char *T) è poi diversa per ogni sottoclasse e 
analizza il frammento di frase dato spezzandolo nelle varie Parti 
costituenti, creando in questo modo una rappresentazione ad albero della 
frase che verrà poi sottoposta a trasformazioni e yada yada...
Come detto, la procedura è ricorsiva e ogni nuovo costituente viene 
creato con new, provato e poi, se non va bene, distrutto per provarne 
(creandolo) un altro. Il problema che mi pongo ora è: così facendo avrò 
MOOOLTE new e delete di oggetti... che impatto avrà sull'efficienza? E 
sulla gestione della memoria??
In alternativa ho pensato di creare sullo stack, per ogni versione di 
analizza(), un esemplare di tutte le sottoclassi potenzialmente utili in 
quel passo e poi creare e copiare nell'albero sintattico solo quelli 
effettivamente individuati nell'analisi, ma così rischio invece di 
finirmi lo stack.
Consigli? Come la risolvereste voi? Oppure va bene così e non mi devo 
preoccupare?

 sulla gestione della memoria??
Questo e' un problema generale dei parser, indipendentemente dal fatto
di allocare deallocare memoria: la necessita' di "guardare avanti" ed
eventualmente provare altre strade (back tracking) ammazza le
prestazioni perche' introduce una potenziale esplosione combinatoria
dei tentativi di riconoscere la frase.
Idealmente dovresti cercare di limitarti il piu' possibile al look
ahead di un singolo elemento e magari cercare di ordinare i tentativi
in base alla frequenza con la quale ricorrono i diversi tentativi.
L'approccio generale a me piace perche' tende a risultare sistematico e
ordinato, ma puo' effettivamente essere poco efficiente.
Ciao,
Nicola

 preoccupare?
Dato che lo schema è ricorsivo, ti consiglio di usare un allocatore a 
stack. Ho letto molto in fretta, ma mi pare che l'oggetto deallocato sia 
sempre l'ultimo ancora allocato, quindi puoi benissimo usare un 
allocatore a stack, cioè che non necessità di ricerca pur incorrendo in 
frammentazione nulla.
Kiuhnm

 frammentazione nulla.
Idea buona ma inapplicabile: gli oggetti sono tutti diversi. Le varie 
sottoclassi NON sono identiche fra loro come impronta in memoria, quindi 
questa strada non funzionerebbe. Hm hm, però potrei implementare N stack 
di allocazione diversi, uno per ogni tipo di oggetto che uso. Forse è 
applicabile lo stesso, dopotutto.

 in base alla frequenza con la quale ricorrono i diversi tentativi.
Una seconda possibile strada che sto indagando č quella di limitare il 
parsing a una sola frase per volta, in modo da avere al massimo un 
venti-trenta termini "concreti" da organizzare in albero, sfruttando la 
spezzatura dei punti fermi. Solo che molto spesso in italiano il 
soggetto č sottinteso e il verbo anche, perfino. E questo č un problema 
quando poi devo ricostruire la rete semantica.
Vabbč, per adesso lascerň il sistema ricorsivo cosě come l'ho pensato, 
se mi rompo la testa me la fascerň :-)

 Idea buona ma inapplicabile: gli oggetti sono tutti diversi. Le varie 
La CPU usa vari stack per allocare vari oggetti?
Kiuhnm

 applicabile lo stesso, dopotutto.
La necessita' di allocare oggetti diversi complica l'implementazione
perche' rende indispensabile gestire l'allineamento, ma cio' non vuol
dire che questo approccio sia inapplicabile, anche con uno stack unico.
Ciao,
Nicola

 dire che questo approccio sia inapplicabile, anche con uno stack unico.
...in cui si allocano blocchi di memoria pari all'oggetto più grande da 
costruire. Sì, si spreca un pò di memoria ma funziona.

 dire che questo approccio sia inapplicabile, anche con uno stack unico.
Si potrebbe definire una union delle strutture "incriminate".
Se le strutture sono di dimensioni simili, il risultato potrebbe essere 
soddisfacente.
Kiuhnm


Non necessariamente. Il problema e' piuttosto conoscere i vincoli di
allineamento della piattaforma con la quale lavori, dal momento che non
esiste una funzione alignment_of standard. Non dovrebbe essere pero'
difficile calcolare a partire dalla cima dello stack la posizione del
prossimo oggetto T che vuoi allocare. Assumendo che lo stack sia
allineato per qualsiasi oggetto (e lo e' per definizione se e' allocato
dinamicamente) il prossimo indirizzo "buono" e' qualcosa del tipo
( ( top - base ) / align(T) + 1) * align(T)
Cosi' non dovresti sprecare di piu' dell'allocatore standard.
Ciao,
Nicola