Hi folks!
Although I know this list is intended to be only about Linux, I would
like to make a question about some troubles I've had programming in lex and
yacc. In reality I don't know whether that I want to do using lex and yacc(yacc
more precisely) is possible to be made in it, so I'd like to ask someone more
experienced with yacc if he(she) can give me some sugestions.
I'm trying to implement a parser for a propositional logic language, so
I get some sentence as input and I look at it to evaluate it or not. This is
working very fine. The problem is that I would like to build the "structural
tree" that represents the formula at the time of parsing. For example: If I get
the sentence ~(A&B)&(C&~D) I would like to evaluate it and after that get the
following tree:
&
|
/ \
/ \
~ &
| |
/ \ / \
A B C ~
|
D
With the lexer I get the tokens as usual and return VARIABLE, which
contains the variable A, B,etc., to the parser.
So in the yacc grammar I've put the following:
..
formula: formula '&' formula {
/* Here I would like to create a node
of the tree and link it with the two
(supposed) nodes represented by each
of the "formula"'s .
e.g.(in a pseudo-code):
new_node.symbol="&";
new_node.left=$1;
new_node.right=$3;*/
}
| '~' formula %prec UNEG { ; }
| '(' formula ')' { ; }
| VARIABLE { /* Here I intend to create a node and make it
a leaf, linking it as a son of formula, which is
represented by $$ */
}
;
In order to make "formula" have the meaning of the struct that I've
defined, I've put the declarations:
%union {
struct node *nodo;
}
and
%type <nodo> formula
before the code fragment above. Node is a symple struct I've defined containing
just a identification field and the pointers needed:
typedef struct node{
char *symbol;
node *left;
node *right;
};
So the problem is that during the parser I always lose the contents of
the left and right pointers, and at the end there's no more tree.
I send below the complete files I'm using for testing. I'm really so
sorry for bothering you with this kind of question, but I hope someone could
help me. Any sugestions will be very appreciated.
Thanks in advance!
--- start of file lex.l ---
%{
#include<string.h>
#include "y.tab.h"
#include "node.h"
/*extern int yylval;*/
extern char *variable;
%}
%%
[A-Z]+ { variable=(char*)malloc(sizeof(char)*(strlen(yytext)+1));
strcpy(variable, yytext); return VARIABLE;
}
[ \t] ;
\n return 0;
return yytext[0];
%%
--- end of lex.l ---
--- start of file yacc.y ---
%{
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "node.h"
int yyerror(char *errmsg);
int yylex();
char *variable;
%}
%union {
struct node *nodo;
}
%token VARIABLE
%left '&'
%nonassoc BOX
%nonassoc UNEG
%type <nodo> formula
%%
formula: formula '&' formula { node leaf; /* only for testing: */
strcpy(leaf.symbol,"&");
leaf.left=$1;
leaf.right=$3;
if((leaf.left)!=NULL){
printf("%s\n",leaf.symbol);
printf("%s\n",leaf.left->symbol);
}
if((leaf.right)!=NULL){
printf("%s\n",leaf.symbol);
printf("%s\n",leaf.right->symbol);
}
}
| '[' ']' formula %prec BOX { ; }
| '~' formula %prec UNEG { ; }
| '(' formula ')' { ; }
| VARIABLE { node leaf; /* only for testing: */
strcpy(leaf.symbol,variable);
leaf.left=NULL;
leaf.right=NULL;
printf("%s\n",leaf.symbol);
$$=(node*)malloc(sizeof(node));
$$->left=&leaf;
printf("%s\n",$$->left->symbol);
}
;
%%
int main()
{
yyparse();
return 0;
}
int yyerror(char *errmsg)
{
fprintf(stderr, "%s\n", errmsg);
}
--- end of yacc.y ---
--- start of node.h ---
typedef struct node{
char *symbol;
node *left;
node *right;
};
--- end of node.h ---
--
Ivan J. Varzinczak - http://www.inf.ufpr.br/~ivan
Scholarship holder - Boursier - (PET/CAPES)
Informatics Department - Département d'Informatique
Federal University of Paraná - Université Fédérale du Paraná
Curitiba - Paraná - Brazil/Brésil
05-VI-2000
