[C] Creare parser per analisi breve testo naturale

[phantom85]

Ciao a tutti,

vorrei creare un parser in C che mi permetta, dato in ingresso un testo abbastanza breve, di poter estrarre determinati termini in base a delle regole che stabilirò io.

Le regole vorrei implementarle nel programma in modo che poi faccia tutto in automatico.


Secondo voi da dove dovrei partire??


Ho scelto come linguaggio il C perchè è quello che conosco decentemente....

[Jecko]

potresti utilizzare la funzione strtok() (la trovi nell'header string.h). La funzione riceve due parametri: il primo è l'indirizzo del vettore contente la stringa, il secondo un delimitatore (o una serie di delimitatori) racchiuso tra apici. Ogni volta che la funzione individua un carattere delimitatore inizia la scansione alla ricerca del delimitatore successivo. Arrivato al delimitatore successivo crea il cosìdetto "token" inserendo un tappo dopo il delimitatore. Questa funzione modifica la stringa che stai manipolando quindi ti consiglio di copiarla in un vettore provvisorio prima di applicarla. Quando richiami la strtok devi sempre distinguere la prima chiamata inserendo il nome della stringa --> strtok(stringa,"delimitatore/i") dalle successive chiamate dove il primo parametro deve essere un valore NULL --> strtok(NULL,"delimitatore/i"). Non ti preoccupare perchè comunque la funzione dalla chiamate successive ricomincerà a tokenizzare da dove aveva interrotto. restituisce il valore NULL se no ha trovato delimitatori o se ha finito di tokenizzare la stringa. Ciao spero di esserti stato utile e non di averti confuso le idee

[Y3PP4]

Guarda, se cerchi indietro nei threads trovi il contest 16 dedicato proprio alla implementazione di parser. Ci sono varie risorse ed esempi, potresti prenderne spunto per capire come funziona il tutto -un parser con la P maiuscola-

Poi dipende da quello che devi analizzare, dalla complessità delle regole e da come queste si applicano al testo.

Saluti.

[wingman87]

Ma non avevi già aperto un thread sullo stesso argomento? Potresti continuare lì, stava venendo una bella discussione.

[maulattu]

Originariamente inviato da Jecko

potresti utilizzare la funzione strtok()
cut...

meglio ancora la strtok_r (piattaforme *nix) oppure strtok_s (piattaforma win), sono thread safe rispetto alla strtok. ok, magari non sta facendo un'applicazione multithread, però male non fa

[phantom85]

Originariamente inviato da wingman87

Ma non avevi già aperto un thread sullo stesso argomento? Potresti continuare lì, stava venendo una bella discussione.

Veramente il discorso era leggermente diverso e poi quel thread era proprio per capire come realizzare il programma, o meglio cosa realizzare!

Ora sono quasi sicuro che mi serve un parser o meglio forse un tokenizzatore.


Ho dato un occhio al contest 16, proprio dove si parla di interpreti.

Da quel che ricordo io il parser fa un'analisi di un linguaggio strutturato, ma a pensarci bene non è il mio caso. Io ho un linguaggio naturale, scritto così come viene in italiano...quindi non ho nulla di strutturato.

Credo proprio che si tratti di un tokenizzatore e l'idea di Jecko e maulattu penso siano quelle corrette. Ovviamente ora cercherò della documentazione su queste funzioni!

Chi avesse altre dritte posti pureee!

[phantom85]

Ho dato un occhio alla funzione strtok, ma mi sorge un dubbio.

Se non ho capito male questa funzione serve per spezzare una stringa in base a dei caratteri di separazione...appunto in base a dei caratteri, e non delle stringhe.


Mi spiego:

char s[]="1abch8dejdkj37390ms";
char c[]="0123456789";
char *p;

alla prima chiamata di funzione, questa dovrebbe analizzare la stringa s e se incontra caratteri in s che appartengono a c, isola gli altri...e quindi:

p=strtok(s,c);      */p="abch"/*

successivamente

p=strtok(NULL,c);      */p="dejdkj"/*

p=strtok(NULL,c);      */p="ms"/*

Ma se volessi isolare dei termini tra delle parole, ad esempio:


"devo trovare un gatto rosso"

mi interessa isolare "gatto" e "rosso", del resto non mi interessa.

Cioè voglio isolare l'oggetto centrale della frase e la sua caratteristica


La funzione strtok mi potrebbe aiutare??!

[phantom85]

Piccola parentesi...


...se volessi fare un programma in C che dato in input un testo scritto da tastiera, lo divida in token in base allo spazio, come dovrei fare?

#include <stdio.h>

#include <string.h>


#define MAX 100



int main() {
	char input[MAX];
	int i=0;
	printf ("Inserisci testo e premi invio:\n");
	while (input[i]!='\n') {
		for (i=0;i<MAX;i++) {

        		scanf("%c", &input[i]);
		}
	}
	int x;	

        char *str1;

 	str1 = strtok(input, " ");
	printf("%i: %s\n", x, str1);

 

        while (1) {

                str1 = strtok(NULL, " ");

 

                if (str1 == NULL) {

                        printf("Tokenizing complete\n");

                        exit(0);

                }

 

                printf("%i: %s\n", x, str1);

                x++;

        }

 

        return 0;

 

}

Ho riscontrato nell'esecuzione che quando inserisco il testo, il programma non termina mai...e non esegue la tokenizzazione...

Devo aver cannato qualcosa nel codice

[wingman87]

Un problema è sicuramente nel while, il resto non l'ho guardato, comunque questo è il tuo codice:

while (input[i]!='\n') {
   for (i=0;i<MAX;i++) {
      scanf("%c", &input[i]);
   }
}

l'esecuzione entra nel ciclo, scopre che input[i] è diverso da zero (presumibilmente) e entra nel ciclo for, che legge MAX caratteri senza mai fermarsi. Al termine del ciclo for i vale 100 e quindi viene fatto il controllo del while:
input[100]!='\n'
strano che a sto punto non ti dia errore, perché sei andato oltre il limite del tuo array, probabilmente ora stai puntando a qualche altra variabile che hai dichiarato, magari i stessa... Comunque ancora una volta presumibilmente questo valore è diverso da '\n' e quindi rientra nel ciclo.
Quello che volevi fare tu molto probabilmente era questo:

i=0;
scanf("%c", &input[i]);
while (i<MAX && input[i]!='\n') {
   i++;
   scanf("%c", &input[i]);
}

[phantom85]

Grazie,appena avrò modo modificherò il codice e farò il test. Si la mia idea era proprio quella, solo che sono leggermente arrugginito

Grazie!

[cionci]

Il problema era probabilmente nella lettura tramite scanf. Infatti la lettura non terminava fino a MAX caratteri.
Usa fgets per leggere l'input !!!

char str[MAX];
fgets(str, MAX, stdin);

[phantom85]

Originariamente inviato da cionci

Il problema era probabilmente nella lettura tramite scanf. Infatti la lettura non terminava fino a MAX caratteri.
Usa fgets per leggere l'input !!!

char str[MAX];
fgets(str, MAX, stdin);

Grazie! Alla fine ho usato quella funzione ed è corretto. Effettivamente mi ricordavo di una funzione per leggere stringhe ma mi veniva in mente getstring


Ora ho realizzato un semplicissimo tokenizzatore che divide in token secondo gli spazi bianchi. Ma se volessi che il mio tokenizzatore (che brutto termine ) dividesse i token oltre che per spazi bianchi, anche per segni di punteggiatura?!

Come dovrei modificare strtok?


edit
ho dichiarato un array con i caratteri che devono dividere le varie parole e ho passato il puntatore nell'argomento della strtok.
Unico problema è che non posso inserire come separatore le virgolette " (all'interno dell'array tk)

char tk[]=".,;:-_'*+ ";

[phantom85]

Al di là del problema del separatore, mi chiedevo come posso fare un confronto all'interno del ciclo, cioè confrontare un token con una determinata parola.

ES: se un token è uguale alla parola "con" vorrei che l'output sia "ingrediente: con cioccolato" (dove "cioccolato" è la parola/token successiva a "con").


Esempio:

Input: voglio fare una torta con cioccolato

Output

1: voglio
2: fare
3: una
4: torta
5: Ingrediente: con cioccolato


E' possibile farlo??

[wingman87]

Puoi usare la strcmp: LINK

Ah, e poi la strcat per concatenare i token: LINK

[phantom85]

grazie, ora mi sto dedicando alla strcmp.

Secondo voi è possibile creare una sorta di struttura che contenga tutte le parole che confrontate con il token porti poi alla stampa di "ingrediente"?

Mi spiego:

prima ho detto che se il tokenizer trova "con" allora deve stampare "ingrediente: con..."

Ma se volessi estendere questa cosa ad altre parole, oltre a "con"?

Potrei creare un if con una serie di OR

if ( (strcmp(str,"con")==0) || (strcmp (str,"al") ==0) )
               printf ("Ingrediente: ");

Non è possibile creare una struttura che contenga tutte le parole (in questo caso "con" e "al") in modo da inserire nella strcmp solo str e una variabile con cui confrontare?

[wingman87]

Puoi creare un array di stringhe in cui mettere "con" "al" e tutto quello che vuoi e poi usare un ciclo per fare i vari confronti e se almeno uno dei confronti va a buon fine stampare "ingrediente: ..."
Stai cercando di individuare delle parole chiave per definire una grammatica giusto?

[cionci]

Originariamente inviato da phantom85

grazie, ora mi sto dedicando alla strcmp.

Secondo voi è possibile creare una sorta di struttura che contenga tutte le parole che confrontate con il token porti poi alla stampa di "ingrediente"?

Mi spiego:

prima ho detto che se il tokenizer trova "con" allora deve stampare "ingrediente: con..."

Ma se volessi estendere questa cosa ad altre parole, oltre a "con"?

Potrei creare un if con una serie di OR

if ( (strcmp(str,"con")==0) || (strcmp (str,"al") ==0) )
               printf ("Ingrediente: ");

Non è possibile creare una struttura che contenga tutte le parole (in questo caso "con" e "al") in modo da inserire nella strcmp solo str e una variabile con cui confrontare?

Puoi generalizzare l'or con un ciclo:

for(i = 0; i < N; ++i)
{
   if(strcmp(str, strings[i]) == 0)
   {
      printf ("Ingrediente: ");   
      break;
   }
}

[Ibrahimovic]

Originariamente inviato da phantom85

grazie, ora mi sto dedicando alla strcmp.

Secondo voi è possibile creare una sorta di struttura che contenga tutte le parole che confrontate con il token porti poi alla stampa di "ingrediente"?

Mi spiego:

prima ho detto che se il tokenizer trova "con" allora deve stampare "ingrediente: con..."

Ma se volessi estendere questa cosa ad altre parole, oltre a "con"?

Potrei creare un if con una serie di OR

if ( (strcmp(str,"con")==0) || (strcmp (str,"al") ==0) )
               printf ("Ingrediente: ");

Non è possibile creare una struttura che contenga tutte le parole (in questo caso "con" e "al") in modo da inserire nella strcmp solo str e una variabile con cui confrontare?

Potresti creare un vettore bidimensionale in cui a ogni indice inserisci una stringa tra quelle "speciali" che richiederann la scritta "Ingrediente".

A questo punto al posto di usare la strcmp per verificare se il tuo token è uguale alla parola "con" usi , ad esempio, una funzione is_present( parola, matr[][] ) booleana che restituisce TRUE se il token è una parola speciale contenuta nel tuo vettore bidimensionale e FALSE se non lo è.

A questo punto se ti è stato restituito il valore TRUE stampi "Ingrediente bla bla bla" mentre stampi semplicemnete la parola se hai ricevuto FALSE

[phantom85]

Ho seguito la dritta di cionci realizzando l'or con un ciclo for e devo dire che tutta funzia bene


Ora se volessi che la parola "ingrediente" venisse stampata DOPO le parola "con" o "al" ?

Adesso il programma esegue questo, se rileva "al" o "con"
...
token
Ingrediente: con cioccolato
token
...

...
token
Ingrediente: al curry
token
...

Vorrei che l'output invece fosse

...
token
con
Ingrediente: cioccolato
token
...

Come potrei fare?

vi ringrazio ancora tutti


PS: @wingman: si più o meno è quello che vorrei fare, diciamo che dato un testo vorrei fare una prima "scrematura" o meglio "raffinarlo" e strutturalo


EDIT: sono riuscito a fare quello che volevo, nell'if che verificava la presenza di una parola ho semplicemente richiamato un'altra volta la printf del token e nuovamente la funzione strtok

Sicuramente posterò ancora per porre nuove modifiche o nuove feature del programmino!

[phantom85]

Ho un problema con il programma, un bug.

Ho notato che se verifico la presenza delle parole con o al che indicano la presenza di un ingrediente (token successivo) tutto funziona,
ma se impongo un if in cui verifico che nel caso un token sia uguale ad una determinata parola, il programma deve stampare una parola (lasciamo sempre ingrediente), se la parola compare alla fine del testo non stampa nulla (ovvero se la parola è l'ultimo token), altrimenti se la parola non è alla fine tutto gira!


Cioè

...
char *strings[]= {"con","al"};
char *str;

str = strtok(input, tk);

...

while (1) {

str = strtok(NULL, tk);



if (str == NULL) {

printf("Analisi completata\n");

exit(0);

}


for (i=0;i<2;i++) {
if ( (strcmp (str,strings[i]) == 0) ) {
printf ("Ingrediente ");
}
}

if ( strcmp (str,"farina") == 0)
printf ("Ingrediente: ");




printf("%s\n", str);

}