[C] Interprete che riconosce le parentesi (Yacc/Bison)

**Matthew82** · 03-06-2008, 19:44

Mi potete postare, per favore, una parte di codice dove si capisce come creare un parser (scritto con yacc) che rispetti le varie parentesi (tonde, quadre, graffe) rispettando le priorità? Ad esempio vorrei fare in modo che l'interprete riconosca correttamente una sequenza scritta in questa maniera: {[(qx + qy)*(qx-qy)]+(qx+qy)]}.
Grazie.

**810106** · 04-06-2008, 00:08

Che piattaforma usi per lo sviluppo?

**Vincenzo1968** · 04-06-2008, 00:39

Ciao Matthew,

L'esempio che segue effettua il parsing di un'espressione matematica che può essere formata da parentesi tonde, costanti numeriche, variabili e gli operatori +, -(unario e binario), *, /.
Per gestire la precedenza utilizzo le regole della grammatica e per l'associatività le regole di bison( p. es. %left '-' '+' significa che gli operatori + e - associano da sinistra). Dunque, le parentesi quadre e graffe non servono(puoi comunque gestirle con una piccola modifica alla grammatica nel file expression.y).

Ho utilizzato Flex e Bison al posto di Lex e Yacc(ma i file .y e .l sono compatibili con entrambe le versioni).

Questo è il file "Expression.y", per Bison(Yacc) :

codice:

%{
#include "symtab.h"
#include <string.h>
#include <stdio.h>
#include "errors.h"  

void yyerror(char *s)
{
    Error(Current_Line,"%s\n",s);  
}
%}

%union {
	double dval;
	struct symtab *symp;
}
%token <symp> NAME
%token <dval> NUMBER
%left '-' '+'
%left '*' '/'
%nonassoc UMINUS

%type <dval> expression
%%
statement_list:	statement '\n'
	|	statement_list statement '\n'
	;

statement:	NAME '=' expression	{ $1->Value = $3; }
	|	expression		{ printf("= %g\n", $1); }
	;

expression:	expression '+' expression { $$ = $1 + $3; }
	|	expression '-' expression { $$ = $1 - $3; }
	|	expression '*' expression { $$ = $1 * $3; }
	|	expression '/' expression
				{	if($3 == 0.0)
						yyerror("divisione per zero");
					else
						$$ = $1 / $3;
				}
	|	'-' expression %prec UMINUS	{ $$ = -$2; }
	|	'(' expression ')'	{ $$ = $2; }
	|	NUMBER
	|	NAME			{ $$ = $1->Value; }
	;
%%

struct symtab * symlook(char *s)
{
	char *p;
	struct symtab *sp;
	
	for(sp = symtab; sp < &symtab[MAX_SYMBOLS]; sp++)
	{
		if(sp->VariableName && !strcmp(sp->VariableName, s))
			return sp;
		
		if(!sp->VariableName)
		{
			sp->VariableName = strdup(s);
			return sp;
		}
	}
	yyerror("Troppi simboli");
	exit(1);
}

Bison crea i file "Expression.tab.c" e "Ecpression.tab.h"

Questo è il file "Expression.l", per Flex(Lex):

codice:

%{
#include "Expression.tab.h"
#include "symtab.h"
#include <math.h>
%}

%%
([0-9]+|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?) {
		yylval.dval = atof(yytext);
		return NUMBER;
	}

[ \t]	;		 /* ignoriamo gli spazi bianchi */

[A-Za-z][A-Za-z0-9]*	{	/* ritorna un puntatore al simbolo */
		yylval.symp = symlook(yytext);
		return NAME;
	}

"$"	{ return 0; }

\n	|
.	return yytext[0];

Flex crea il file "lex.yy.c".

I seguenti file vanno creati a mano:

"symtab.h" contiene le definizioni per la tabella dei simboli:

codice:

#define MAX_SYMBOLS 21	/* Numero massimo di simboli */

struct symtab
{
	char  *VariableName;
	double Value;
} symtab[MAX_SYMBOLS];

struct symtab *symlook();

i file "errors.h" e "errors.c" servono per la gestione degli errori:
errors.h:

codice:

extern int Number_Of_Errors;
extern int Current_Line;


void Error(int position, char * message,...);
int numErrors();
int anyErrors();

errors.c:

codice:

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include "errors.h"

int Number_Of_Errors = 0;

int Current_Line = 1;

void Error(int position, char *message, ...)
{
	va_list ap;
	Number_Of_Errors++;
	fprintf(stderr, "Errore linea n. %d: ", position);
	va_start(ap, message);
	vfprintf(stderr, message, ap);
	va_end(ap);
	fprintf(stderr, "\n");
}

int numErrors()
{
	return Number_Of_Errors;
}

int anyErrors()
{
	return Number_Of_Errors;
}

infine, il file che contiene la funzione main:
expr.c

codice:

#include <stdio.h>

extern int yyparse(void);
extern FILE *yyin;

#ifdef yywrap
#	undef yywrap
#endif
int yywrap(void)
{
	return 0;
}

void parse(char *filename)
{
	yyin = fopen(filename, "r");
	if (yyin == NULL)
	{
		fprintf(stderr,"Impossibile aprire il file: %s\n", filename);
	}
	else
	{
		if (yyparse() == 0)
			fprintf(stderr,"Parsing eseguito con successo!\n");
		else
			fprintf(stderr,"Parsing fallito.\n");
	}
}

int main(int argc, char **argv)
{
	if (argc!=2)
	{
		fprintf(stderr,"uso: %s filename\n", argv[0]);
		return -1;
	}
	
	parse(argv[1]);
	return 0;
}

la funzione main si aspetta, come argomento dalla linea di comando, un file di testo. Un esempio di programma valido:

VarA = 21.34
VarB = 8
((5 + VarA) / (VarB + 5.8)) * 34.55
$

L'output è il seguente:
= 65.9454
Parsing eseguito con successo!

Se hai qualche dubbio, chiedi pure.

Ciao

**alka** · 04-06-2008, 01:08

Originariamente inviato da Matthew82
Mi potete postare, per favore, una parte di codice dove si capisce come creare un parser (scritto con yacc) che rispetti le varie parentesi (tonde, quadre, graffe) rispettando le priorità? Ad esempio vorrei fare in modo che l'interprete riconosca correttamente una sequenza scritta in questa maniera: {[(qx + qy)*(qx-qy)]+(qx+qy)]}.

Manca il linguaggio.

**Vincenzo1968** · 04-06-2008, 07:27

Originariamente inviato da alka
Manca il linguaggio.

Il linguaggio è [C][Yacc/Bison] e, se non diventa troppo lungo, [Generatori di parser].

**Matthew82** · 04-06-2008, 12:34

Tu hai scritto che:
"Per gestire la precedenza utilizzo le regole della grammatica e per l'associatività le regole di bison( p. es. %left '-' '+' significa che gli operatori + e - associano da sinistra). Dunque, le parentesi quadre e graffe non servono."

Posso gestire le precedenze utilizzando le regole della grammatica e per l'associatività le regole di bison, anche per degli operatori creati da me stesso che svolgono delle particolari funzioni? Invece di utilizzarli escusivamente per gli operatori aritimetici?
Ad esempio posso scrivere una cosa del tipo:

%left operazione1
%left operazione2

così dando la precedenza a operazione2 rispetto a operazione1 quando si incontra una espressione del tipo:
(ax operazione1 bx operazione2 cx) ???
Grazie.

**Vincenzo1968** · 04-06-2008, 14:56

Originariamente inviato da Matthew82
Posso gestire le precedenze utilizzando le regole della grammatica e per l'associatività le regole di bison, anche per degli operatori creati da me stesso che svolgono delle particolari funzioni? Invece di utilizzarli escusivamente per gli operatori aritimetici?
Ad esempio posso scrivere una cosa del tipo:

%left operazione1
%left operazione2

così dando la precedenza a operazione2 rispetto a operazione1 quando si incontra una espressione del tipo:
(ax operazione1 bx operazione2 cx) ???
Grazie.

con %left e %right gestisci l'associatività sinistra e destra, rispettivamente. Per esempio, per l'operatore di elevamento a potenza( indichiamolo con ^), che associa da destra, scriviamo:

%right '^'

La precedenza tra gli operatori è, invece, gestita dall'ordine con il quale sono elencati nella grammatica: i primi hanno precedenza minore, gli ultimi maggiore.
Quindi, per esempio, scrivendo

codice:

expression:	expression '+' expression { $$ = $1 + $3; }
	|	expression '-' expression { $$ = $1 - $3; }
	|	expression '*' expression { $$ = $1 * $3; }
	|	expression '/' expression { $$ = $1 / $3; }

+ e - hanno una precedenza minore rispetto a * e /.
Nel tuo caso, se vuoi che operazione2 abbia una precedenza maggiore, devi scrivere:

codice:

expression:	expression operazione1 expression { $$ = ... }
	|	expression operazione2 expression { $$ = ... }

così, invece:

codice:

expression:	expression operazione2 expression { $$ = ... }
	|	expression operazione1 expression { $$ = ... }

diamo la precedenza maggiore all'operatore operazione1.

**Vincenzo1968** · 04-06-2008, 16:12

mi sono sbagliato

Ho dato un'occhiata al manuale utente ed effettivamente l'ordine con il quale sono dichiarati gli operatori stabilisce la precedenza. Ma la cosa va fatta nella sezione delle dichiarazioni e quindi hai ragione tu: per dare precedenza maggiore a operazione2 dobbiamo scrivere:

%left operazione1
%left operazione2

Per assegnare la stessa precedenza gli operatori vanno scritti nella stessa riga. Per esempio:

%left operazione1
%left operazione2 operazione 3

operazione2 e operazione3 hanno la stessa precedenza(che è maggiore rispetto a quella di operatore1)

**Matthew82** · 04-06-2008, 16:48

Avevo provato così:
%left operazione1
%left operazione2
ma non funzionava....
Adesso scrivendo così:
expression: expression operazione1 expression { $$ = ... }
| expression operazione2 expression { $$ = ... }

sembra funzionare. Quindi forse avevi ragione tu. Quale è la giusta risposta???

**Vincenzo1968** · 04-06-2008, 19:51

Originariamente inviato da Matthew82
Avevo provato così:
%left operazione1
%left operazione2
ma non funzionava....
Adesso scrivendo così:
expression: expression operazione1 expression { $$ = ... }
| expression operazione2 expression { $$ = ... }

sembra funzionare. Quindi forse avevi ragione tu. Quale è la giusta risposta???

La risposta giusta è sicuramente quella del manuale.
Scrivendo

expression: expression operazione1 expression { $$ = ... }
| expression operazione2 expression { $$ = ... }

senza specificare la precedenza nella sezione delle dichiarazioni, funziona perchè Yacc/Bison produce un parser di tipo LALR(1) in cui le derivazioni sono di tipo Right-Most.
Quindi viene valutata prima l'espressione più a destra (expression operazione2 expression).
Devi comunque scrivere sia la dichiarazione (precedenza + associatività ) sia la regola grammaticale.
Nell'esempio seguente ho definito due operatori: ~ esegue la sottrazione e # esegue la moltiplicazione. Scrivendo l'espressione 8 ~ 5 # 3, il parser fornisce il risultato corretto, -7.

codice:

%{
#include "symtab.h"
#include <string.h>
#include <stdio.h>
#include "errors.h"  

void yyerror(char *s)
{
    Error(Current_Line,"%s\n",s);  
}
%}

%union {
	double dval;
	struct symtab *symp;
}
%token <symp> NAME
%token <dval> NUMBER
%left '~'
%left '#'
%nonassoc UMINUS

%type <dval> expression
%%
statement_list:	statement '\n'
	|	statement_list statement '\n'
	;

statement:	NAME '=' expression	{ $1->Value = $3; }
	|	expression		{ printf("= %g\n", $1); }
	;

expression:	expression '~' expression { $$ = $1 - $3; }
	|	expression '#' expression { $$ = $1 * $3; }
	|	'-' expression %prec UMINUS	{ $$ = -$2; }
	|	'(' expression ')'	{ $$ = $2; }
	|	NUMBER
	|	NAME			{ $$ = $1->Value; }
	;
%%

struct symtab * symlook(char *s)
{
	char *p;
	struct symtab *sp;
	
	for(sp = symtab; sp < &symtab[MAX_SYMBOLS]; sp++)
	{
		if(sp->VariableName && !strcmp(sp->VariableName, s))
			return sp;
		
		if(!sp->VariableName)
		{
			sp->VariableName = strdup(s);
			return sp;
		}
	}
	yyerror("Troppi simboli");
	exit(1);
}

Come vedi ho dichiarato precedenza e associatività:

%left '~'
%left '#'

e ho definito le regole grammaticali:

expression: expression '~' expression { $$ = $1 - $3; }
| expression '#' expression { $$ = $1 * $3; }

Fammi sapere e, se hai ancora problemi, posta il codice per intero.
Ciao

Discussione: [C] Interprete che riconosce le parentesi (Yacc/Bison)

Strumenti discussione

Ricerca discussione

Visualizza

interprete che riconosce le parentesi

Moderazione

Re: Moderazione

Permessi di invio