[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

lex & yacc question



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



Reply to: