Newsgroup: it.comp.lang.c
Titolo: Riconoscitore di linguaggi

Salve a tutti,
dovrei implementare un algoritmo che permetta al programma di decidere 
de le righe di un file di testo sono o meno conformi ad una data grammatica.
Ho scritto una piccola routine che memorizza la riga in analisi in un 
array di char del tipo "char buffer[dimensioneriga]" a questo punto mi 
chiedo come implementare il riconoscitore vero e proprio.
Non sono molto pratico di programmazione quindi basandomi sulle mie 
rudimentali conoscenze avevo pensato ad una serie di condizioni 
*if-then* legate a dei comandi *goto* che rimandino alla condizione più 
opportuna.
Tipo "se buffer[0] è una parentesi aperta allora procedi -> se buffer[1] 
è una lettera "s" oppure "l" allora procedi... altrimenti esci dal ciclo 
e restituisci una variabile di stato che mi permetta di sapere che la 
stringa non è conforme".
Le regole da seguire sono le seguenti ovvero il testo deve essere del tipo:
(comando "caratteri") tra gli apici è ammessa anche l'assenza di caratteri
oppure
(comando numero)  ci deve essere almeno un numero (i numeri da soli 
vanno senza apici)
oppure
(comando (comando...))   ovvero le espressioni come sopra possono essere 
annidate
comando= "set","setq","lambda"
caratteri= lettere maiuscole e minuscole e cifre da 0 a 9
numero= cifre da 0 a 9
Mi rendo perfettamente conto dell'inefficienza del mio algoritmo. 
Qualcuno avrebbe suggerimenti su come procedere o magari su matreriale 
da consultare a riguardo.
Grazie per l'attenzione
Dan
PS: naturalmente non posso usare strumenti tipo Lex o cose del genere.


Cosě ti stai inoltrando in una branca particolare dell'informatica. Con un
motore di ricerca prova con:
"lex"
"yacc"
"lex&yacc"
"compilatore di compilatori"
+scanner +parser
...e auguri per il lavoro.
Un saluto.

 wrote
Direi che ti devi studiare un pochino di teoria.... la puoi trovare sul
dragon book o anche su altri libri.
Per il problema seplice che devi fare basta un qualsiasi libro che abbia un
esempio di parser banale.
Inoltre la tua grammatica non e' completamente specificata....
Se ti hanno dato questo esercizio e ti hanno detto di non usare tools
significa che ti hanno spiegato come scrivere un parser, almeno credo. Hai
frequentato le lezioni?
Tommy

 
In effetti le lezioni non le ho seguite, si tratta di un esame che avrei 
dovuto dare al secondo anno e che ho lasciato indietro. Questo spiega 
anche la ruggine sul mio C...
La questione del riconoscimento l'ho risolta con un automa a stati 
finiti e ina serie di condizioni if e switch con salti condizionati ai 
relativi stati. Ora sto combattendo con un po' di sintassi quindi provo 
ad abusare della vostra gentilezza proponendovi il codice che ho scritto.
/***********************************************************************
*                         Funzione LEGGI_FILE                          *
legge una riga e la memorizza nell'array buffer, chiama conformita
***********************************************************************
int leggi_file()
   {
   int conriga=0,locale=0,end=0;     // variabili di controllo
   char ch, buffer[dim];           // variabile per la lettura dell'input
                                    // e lo storage dell'input
leggiriga:
       while (ch=fgetc(filein)!= "\r")// ciclo che legge e inserisce 
//nella lista
                                      // 'buffer' le sequenze di stringhe
       {                              //alfanumeriche.
acquisisci:      ch=fgetc(filein);           //lettura carattere
       if(!isspace(ch))                       //ignora gli spazi
          {
          buffer[locale]=ch;
          locale=locale+1;
          }
       else goto acquisisci;}
buffer[locale]="\0";
conformita(buffer[dim]);
locale=0;
if (ch=fgetc(filein)!= EOF)
goto leggiriga;
end=1; //...allora termina
return end;
}
*/
/***********************************************************************
*                         Funzione CONFORMITA
mediante l'automa a stati finiti verifica che il linguaggio sia conforme:
                           *
***********************************************************************/
int conformita(char lista[dim])
{ int fine=0,i=0;
        if (lista[i]=="(")
        {
        i=i+1;
        goto 10;}
        else
        goto fineconf;
10:    if (lista[i]=="s")or(lista[i]=="l")
        {
        i=i+1;
        goto 20;}
        else
        goto fineconf;
20:    if (lista[i]=="e")or(lista[i]=="a")
        {
        i=i+1;
        goto 30;}
        else
        goto fineconf;
30:    if (lista[i]=="t")or(lista[i]=="m")
        {
        i=i+1;
        goto 40;}
        else
        goto fineconf;
40:    switch (lista[i])
        {
        i=i+1;
        case "q": case "b": goto 90; break;
        case "'": goto 50; break;
        case "(": goto 10; break;
        case isdigit(lista[i-1]): goto 80; break;
        default:
        goto fineconf;}
50:    if (isalpha(lista[i])
        {
        i=i+1;
        goto 60;}
        else
        goto fineconf;
60:    switch (lista[i])
        {
        i=i+1;
        case "'": goto 70; break;
        case isalpha(lista[i-1]: goto 60; break;
        default:
        goto fineconf;}
70:    if (lista[i]==")")
        {
        i=i+1;
        goto successo;}
        else
        goto fineconf;
80:    switch (lista[i])
        {
        i=i+1;
        case isdigit(lista[i-1]): goto 80; break;
        case ")": goto successo; break;
        default:
        goto fineconf;}
90:   switch (lista[i])
        {
        i=i+1;
        case "d": goto 100; break;
        case isdigit(lista[i-1]): goto 80; break;
        case "'": goto 50; break;
        case "(": goto 10; break;
        default:
        goto fineconf;}
100:   if (lista[i]=="a")
        {
        i=i+1;
        goto 110;}
        else
        goto fineconf;
110:   switch (lista[i])
        {
        i=i+1;
        case "'": goto 50; break;
        case isdigit(lista[i-1]): goto 80; break;
        case "(": goto 10; break;
        default:
        goto fineconf;}
successo:
if (lista[i]=="\0")
fine=1;
fineconf:  return fine;
}
Quando l'ho fatto vedere al compilatore mi ha riso in faccia... eheh
Scherzi a parte vi pare che possa andare come "approccio"?
Ciao e grazie
Dan

Se ho capito bene la grammatica che devi riconoscere è questa:
exp    ::= '(' fun arg ')'
arg    ::= string | num | exp
string ::= '"' { char } '"'
num    ::= digit {digit}
digit  ::= '0' | ... | '9'
char   ::= 'A' | ... | 'Z' | 'a' | ... | 'z' | digit
fun    ::= 'set' | 'setq' | 'lambda'
(scusate i "..." , mi sembrava eccessivo scrivere tutto l'alfabeto).
Se non puoi utilizzare tool (lex&yacc,RDP,  ... ce ne sono un sacco) e devi
fare tutto a mano, ricordati che hai il problema di gestire il bilanciamento
delle parentesi. Dal tuo codice non mi sembra che tu ne tenga conto.
Perdonami se te lo dico mi cio' che hai scritto è assolutamente illegibile
(e dubito che funzioni). Se proprio vuoi usare i goto per una macchina a
stati finiti (cosa che in genere non disapprovo) almeno metti delle label
significative invece di 10, 20 etc.
Disegna prima la macchina a stati su un pezzo di carta e poi prova a
codificarla in C, cercare di fare tutte e due le cose insieme mi sembra un
attimino complicato! :)
Questo è solo uno scheletro per darti un'idea di come potresti strutturare
il codice. Immagina che c sia un puntatore al carattere corrente (se devi
per forza leggere un carattere per volta da file, si complica un po' la
verifica di "set" etc ma il concetto è lo stesso).
Ciao,
                            R.D.
----8<---- cut here -----8<---- cut here -----8<---- cut here ---
START:
    if (isspace(*c)) {
        c++;
        goto START:
    }
    else if ( *c == '(' ) {
        parentesi ++;
        c++;
        goto INFUNC;
    }
    else goto FAIL;
INFUNC:
    if (isspace(*c)) {
        c++;
        goto INFUNC:
    }
    if (strncmp(c,"setq",4) == 0) {
        c++;
        goto INARG;
    }
    else if (strncmp(c,"set",3) == 0) {
    }
    else if (strncmp(c,"lambda",6) == 0) {
    }
    else goto FAIL;
INARG:
    if (isspace(*c)) {
        c++;
        goto INARG:
    }
    else if (isdigit(*c)) {        /* riconosciamo gli argomenti "numerici"
*/
        while (isdigit(*c)) c++;
        goto ENDARG;
    }
   .....

 
Sei stato gentilissimo! Grazie ancora!
Ciao
Dan