Programma LexYacc Help

di
Marco8914
il
16 risposte
M
Marco8914
Pochi posts
Iscritto da
apr, 2015
Messaggi:
7

Programma LexYacc Help

Buonasera mi chiamo Marco. Avrei bisogno di un piccolo aiuto per realizzare un programma con Lex&Yacc.
Nello specifico quello che dovrei fare è:
Realizzare un interprete che esegue un ciclo while in cui sono utilizzate
un paio di variabili predefinite. Es.

i = <valore iniziale>;
x = <valore iniziale>;
while (<condizione su i>) {
x = <operazione su x, i, costanti>;
i = <operazione che calcola il nuovo i>;
}

Il problema è che non capisco proprio da dove iniziare nonostante abbia letto svariati argomenti di teoria su Lex &Yacc.
Qualcuno può essermi di aiuto??
Grazie mille in anticipo.

16 Risposte

  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6011

    Re: Programma LexYacc Help

    Comincia con qualcosa di piu' semplice:

    leggi un numero e stampalo.

    Inizia con un numero intero.


    Ad esempio:

    lex.l: 
    
%{
%}
digit  [0-9]
%%
{digit}+  {yylval.d = atof(yytext); return tFLOAT;}
%%

    yacc.y:
    
%{
%}
%union {
    float  d;
}
%token <d> tFLOAT

%%
Numbers : /* empty */
             | Numbers Number
             ;

Number : tFLOAT { printf("%f\n", $1); }
%%
    Non e' detto che funzioni, l'ho scritto senza controllare, ma dovrebbe essere molto vicino al formato corretto.
  • M
    Marco8914
    Pochi posts
    Iscritto da
    apr, 2015
    Messaggi:
    7

    Re: Programma LexYacc Help

    Anzitutto ti ringrazio. Ho letto e cercato di capire il tuo esempio e mi sembra che torni quasi tutto (forse manca solo la dichiarazione della libreria "stdio.h" nella parte di codice per il Yacc).
    Tuttavia se qualcuno può potesse indicarmi una strada ancora più vicina al mio problema originario gli sarei estremamente grato.
  • D
    Della
    Molto attivo
    Iscritto da
    nov, 2010
    Messaggi:
    1305

    Re: Programma LexYacc Help

    A livello concettuale il codice che vuoi parsare è abbastanza semplice, perché è costituito da 2 soli tipi di istruzioni (simbolo non terminale): assegnamenti e istruzioni di controllo (in particolare il solo ciclo while).

    A loro volta gli assegnamenti sono abbastanza facili, perché sono composti da un identificatore (la variabile), l'operatore di assegnamento, un'espressione e il punto e virgola.

    Anche il while è facile: è composto da una keyword, una parentesi aperta, un'espressione, una parentesi chiusa e un blocco di codice. Il blocco di codice può essere una singola istruzione oppure può essere una graffa aperta, una lista di istruzioni (anche vuota), una graffa chiusa. Nota che ho parlato di istruzioni (quindi c'è una ricorsione sul non terminale "istruzioni").

    La parte più difficile secondo me è la definizione di un'espressione: infatti un'espressione può essere una costante numerica, una variabile, una somma di 2 espressioni, una differenza di 2 espressioni, ecc. Inoltre può essere utile sovrascrivere le priorità, per cui un'espressione può anche essere la struttura "aperta parentesi tonda, espressione, chiusa tonda" (es: l'espressione "(2+3)*5").
    Inoltre dovrai definire associatività e precedenze (es: se avessi "2+x-4*25" in che ordine andrebbero fatte le varie operazioni?)
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6011

    Re: Programma LexYacc Help

    Della ha scritto:

    A livello concettuale il codice che vuoi parsare è abbastanza semplice, perché è costituito da 2 soli tipi di istruzioni (simbolo non terminale): assegnamenti e istruzioni di controllo (in particolare il solo ciclo while).

    A loro volta gli assegnamenti sono abbastanza facili, perché sono composti da un identificatore (la variabile), l'operatore di assegnamento, un'espressione e il punto e virgola.

    Anche il while è facile: è composto da una keyword, una parentesi aperta, un'espressione, una parentesi chiusa e un blocco di codice. Il blocco di codice può essere una singola istruzione oppure può essere una graffa aperta, una lista di istruzioni (anche vuota), una graffa chiusa. Nota che ho parlato di istruzioni (quindi c'è una ricorsione sul non terminale "istruzioni").

    La parte più difficile secondo me è la definizione di un'espressione: infatti un'espressione può essere una costante numerica, una variabile, una somma di 2 espressioni, una differenza di 2 espressioni, ecc. Inoltre può essere utile sovrascrivere le priorità, per cui un'espressione può anche essere la struttura "aperta parentesi tonda, espressione, chiusa tonda" (es: l'espressione "(2+3)*5").
    Inoltre dovrai definire associatività e precedenze (es: se avessi "2+x-4*25" in che ordine andrebbero fatte le varie operazioni?)
    E' troppo complicato!
    Ricorda che chi ha iniziato il post non si trova nemmeno con la definizione della RE di un intero!

    Inoltre, anche la tua descrizione e' sovvradefinita.
    Ad esempio, non ti serve introdurre le parentesi nella definizione del WHILE:

    WHILE ::= 'while' EXPR BODY

    le parentesi le metti nella definizione di EXPR e BODY, se necessario
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6011

    Re: Programma LexYacc Help

    Marco8914 ha scritto:

    Anzitutto ti ringrazio. Ho letto e cercato di capire il tuo esempio e mi sembra che torni quasi tutto (forse manca solo la dichiarazione della libreria "stdio.h" nella parte di codice per il Yacc).
    Tuttavia se qualcuno può potesse indicarmi una strada ancora più vicina al mio problema originario gli sarei estremamente grato.
    Ascolta, ha gia' ricevuto moooolto.

    Prova a metterci un po' del tuo.

    Inizia con definire sintassi e grammatica, senza necessariamente utilizare LEX/YACC, ma semplicemente in termini di espressioni regolari e sintassi BNF ().

    Una volta che questa e' a posto, passare a LEX/YACC e' immediato.
  • D
    Della
    Molto attivo
    Iscritto da
    nov, 2010
    Messaggi:
    1305

    Re: Programma LexYacc Help

    migliorabile ha scritto:

    E' troppo complicato!
    Ricorda che chi ha iniziato il post non si trova nemmeno con la definizione della RE di un intero!
    Si, sicuramente non è una cosa che si fa in poco tempo, è necessario avere un po' di dimestichezza ed iniziare da qualcosa di semplice.

    migliorabile ha scritto:

    Inoltre, anche la tua descrizione e' sovvradefinita.
    Ad esempio, non ti serve introdurre le parentesi nella definizione del WHILE:

    WHILE ::= 'while' EXPR BODY

    le parentesi le metti nella definizione di EXPR e BODY, se necessario
    Su questo non sono pienamente d'accordo, dipende dallo stile che vuoi imporre. Ad esempio io pensavo ad un while in cui la condizione deve essere per forza messa fra parentesi tonde (stile java). Se le parentesi le metti dentro ad EXPR potrebbero diventare opzionali, in base a come definisci EXPR. Per quanto riguarda il body invece siamo d'accordo, equivale a quello che ho chiamato " blocco di codice "
  • vbextreme
    vbextreme
    Molto attivo
    Iscritto da
    feb, 2012
    Messaggi:
    1143

    Re: Programma LexYacc Help

    Simpatico
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6011

    Re: Programma LexYacc Help

    vbextreme ha scritto:

    Simpatico
    termine alternativo per dire CROSSPOST?

    @Marco: cosa decisamente antipatica !
  • vbextreme
    vbextreme
    Molto attivo
    Iscritto da
    feb, 2012
    Messaggi:
    1143

    Re: Programma LexYacc Help

    Hahaha mi avevano anche censurato nell altro forum....
    Per di più è vietato anche li, solo che mi ero scordato che li è vietato anche il sarcasmo regola che viene prima del crosspost.
  • M
    Marco8914
    Pochi posts
    Iscritto da
    apr, 2015
    Messaggi:
    7

    Re: Programma LexYacc Help

    migliorabile ha scritto:

    vbextreme ha scritto:

    Simpatico
    termine alternativo per dire CROSSPOST?

    @Marco: cosa decisamente antipatica !
    Chiedo scusa, ma fino a 2 minuti fa non ero nemmeno a conoscenza dell' esistenza della parola "CROSSPOST" ne tanto meno del suo significato. Ovviamente colpa mia che non ho letto il regolamento, ho solo cercato di fare quello che faccio sempre ogniqualvolta ho bisogno di un informazione, cioè attingere da 4/5 fonti in modo da avere le idee più chiare possibili. Non era mia intenzione mancare di rispetto a nessuno se ciò fosse avvenuto gli porgo nuovamente le mie scuse. Ci tengo a sottolineare che ho agito in totale buona fede inquanto ho utilizzato anche lo stesso titolo per entrambi i post.
  • M
    Marco8914
    Pochi posts
    Iscritto da
    apr, 2015
    Messaggi:
    7

    Re: Programma LexYacc Help

    Ad ogni modo ho provato a scrivere una grammatica {G=(T,N,P,S)} per un possibile programma generico con un ciclo WHILE.
    La Grammatica è la seguente:
    
T=simboli teminali={digit,N,M,I,WHILE,AND,OR,LT,GT,EQ,LE,GE,NE,INC.DEC,FINE}
N=simboli non terminali={S,STMT,COND,ISTR,A,B,C,OPL,OP}
S->S
P=produzioni {
S->STMT
STMT->WHILE(COND) ISTR
ISTR->C
COND->B OPL B
COND->B
OPL->AND
OPL->OR
B->C OP C
B->C
C->M
C->N
C->I
C->C+C
C->C-C
C->C*C
C->C/C
C->C^C
C->(C)
C->digit
OP-> >=
OP-> <=
OP-> >
OP-> <
OP-> ==
OP-> !=
}
    Tuttavia ho qualche perplessità su alcune produzioni, in particolari per le seguenti:

    STMT->WHILE(COND) ISTR
    OP-> >=
    OP-> <=
    OP-> >
    OP-> <
    OP-> ==
    OP-> !=

    Qualcuno può dirmi se potrebbe essere corretta come grammatica?
    Grazie mille.
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6011

    Re: Programma LexYacc Help

    Ma quale accipicchia di sintassi hai utilizzato?

    Non e' BNF,
    Non e' Lex/Yacc

    Ci sono degli standard per la scrittura delle grammatiche!

    E se hai usato quella matematica, non segue le regole solite!!!!

  • M
    Marco8914
    Pochi posts
    Iscritto da
    apr, 2015
    Messaggi:
    7

    Re: Programma LexYacc Help

    Ho utilizzato una grammatica context free. L'unica che mi hanno spiegato.
    Inserisco anche il file in Yacc per illustrarti meglio quello che ho fatto:
    
%{
#include<stdio.h>
#include<stdlib.h>
#include"lex.yy.c"
%}
%token digit N M I LT GT EQ LE GE NE AND OR INC DEC FINE
%left '+''-'
%left '*''/'
%right '^'
%right '='
%nonassoc UMINUS 
%nonassoc WHILE
%left GE NE LT GT LE EQ
%left AND OR
%%
S:STMT FINE{printf("\nCorretto\n");return(0);}
STMT:WHILE'('COND')''{'ISTR'}'
ISTR:C
COND:B OPL B
 |B
OPL:AND
 |OR
B:C OP C
 |C
C:N'='C
 |M'='C
 |I'='C
 |C'+'C
 |C'-'C
 |C'*'C
 |C'/'C
 |C'^'C
 |'('C')'
 |'-'C %prec UMINUS
 |M
 |N
 |I
 |digit
 |M INC
 |N INC
 |I INC
 |M DEC
 |N DEC
 |I DEC
OP:LT
 |GT
 |EQ
 |LE
 |GE
 |NE
 ;
%%
int main()
{
yyparse();
yylex();
return FINE;
}
yyerror(char *s)
{
printf("\nError");
}
    NB: I,M,N sono delle ipotetiche variabili. Ovviamente il file funziona solo se si usano queste variabili (so che è limitativo ma per quello che dovrei fare è sufficiente).
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6011

    Re: Programma LexYacc Help

    Marco8914 ha scritto:

    Ho utilizzato una grammatica context free. L'unica che mi hanno spiegato.
    Ti e' chiara la differenza tra sintassi usata per descrivere una grammatica e che cosa e' una grammatica context free?

    Comunque la grammatica che hai descritto e' molto approssimativa.
    Hai inserito troppe funzionalita' senza una logica decente.

    a AND b OR c

    come la interpreti?

    (a AND b) OR c

    oppure

    a AND (b OR c)

    ???

    Altra cosa: non ti serve risparmiare sul nome degli oggetti usati nella grammatica!
    Assegna NOMI COMPRENSIBILI!!!

    E non devi nemmeno risparmiare sugli spazi: SCRIVI IL CODICE IN MODO LEGGIBILE, correttamente identato e correttamente spaziato.

    Ed usa i tag [ code ] e [/ code ].
Devi accedere o registrarti per scrivere nel forum
16 risposte