Parsing a statement and Adding Paranthesis to them

Question

I am trying to parse logical BNF statements , and trying to apply paranthesis to them.

For example: I am trying to parse a statement a=>b<=>c&d as ((a)=>(b))<=>((c)&(d)), and similar statements as well.

Problem Facing: Some of the statements are working fine, and while some are not. The example provided above is not working and the solution is printing as ((c)&(d))<=>((c)&(d)) The second expr seems to be overriding the first one.

Conditions that are working: While other simple examples like a<=>b , a|(b&c) are working fine.

I think I have made some basic error in my code, which I cannot figure out.

Here is my code

lex file

letters [a-zA-Z]
identifier {letters}+
operator (?:<=>|=>|\||&|!)
separator [\(\)]    

%%
{identifier} {
    yylval.s = strdup(yytext);
    return IDENTIFIER; }
{operator} { return *yytext; }
{separator} { return *yytext; }
[\n] { return *yytext; }
%%

yacc file

%start program
%union  {char* s;}
%type <s> program expr IDENTIFIER
%token IDENTIFIER
%left '<=>'
%left '=>'
%left '|' 
%left '&'
%right '!'
%left '(' ')'

%%
program : expr '\n'     
          { 
            cout<<$$;
            exit(0);
          }
     ;
    
expr : IDENTIFIER  {  
        cout<<" Atom ";
        cout<<$1<<endl;
        string s1 = string($1);
        cout<<$$<<endl;
        
    }
     | expr '<=>' expr   {
        cout<<"Inside <=>\n";
        string s1 = string($1); 
        string s2 = string($3); 
        string s3 = "(" + s1 +")" +"<=>"+"(" + s2 +")";
        $$ = (char *    )s3.c_str();
        cout<<s3<<endl;
     }
     | expr '=>' expr   {
        cout<<"Inside =>\n";
        string s1 = string($1);
        string s2 = string($3); 
        string s3 = "(" + s1 +")" +"=>"+"(" + s2 +")";
        $$ = (char *)s3.c_str();
        cout<<$$<<endl;
     }
     | expr '|' expr    { 
 
        cout<<"Inside |\n";
        string s1 = string($1);
        string s2 = string($3); 
        string s3 = "(" + s1 +")" +"|"+"(" + s2 +")";
        $$ = (char *)s3.c_str();
        cout<<$$<<endl;
     }
     | expr '&' expr    {

        cout<<"Inside &\n";
        string s1 = string($1);
        string s2 = string($3); 
        string s3 = "(" + s1 +")" +"&"+"(" + s2 +")";
        $$ = (char *)s3.c_str();
        cout<<$$<<endl;
     }
     | '!' expr {      

        cout<<"Inside !\n"; 
        string s1 = string($2);
        cout<<s1<<endl;
        string s2 = "!" + s1;
        $$ = (char *)s2.c_str();
        cout<<$$<<endl;
     }
     | '(' expr ')'         {  $$ = $2; cout<<"INSIDE BRACKETS"; }
     ;
%%

Please let me know the mistake I have made.

Thank you

Answer 1

The basic problem you have is that you save the pointer returned by string::c_str() on the yacc value stack, but after the action finishes and the string object is destroyed, that pointer is no longer valid.

To fix this you need to either not use std::string at all, or change your %union to be { std::string *s; } (instead of char *). In either case you have issues with memory leaks. If you are using Linux, the former is pretty easy. Your actions would become something like:

     | expr '<=>' expr   {
        cout<<"Inside <=>\n";
        asprintf(&$$, "(%s)<=>(%s)", $1, $3);
        cout<<$$<<endl;
        free($1);
        free($3);
     }

for the latter, the action would look like:

     | expr '<=>' expr   {
        cout<<"Inside <=>\n";
        $$ = new string("(" + *$1 +")" +"<=>"+"(" + *$2 +")");
        cout<<$$<<endl;
        delete $1;
        delete $3;
     }