yacc-how to write yacc code for checking balanced parentheses

Question

It should give valid for
()
()()()()
(()()()(()))

And Invalid for
(
(((
()())

YACC CODE:

%{
#include<stdio.h>
int yylex();
int yyerror(char* err);
extern FILE* yyin;
%}

%token OPENING CLOSING

%%
stmt : S {printf("Valid \n"); return 0;}
S    : OPENING S CLOSING S
|  ;
%%

int main(){
yyin=fopen("input.c","r");
yyparse();
return 1;
}
int yyerror(char* err){
printf("Invalid\n");
return 1;
}

LEX CODE:

%{
#include<stdio.h>
#include "y.tab.h"

%}

%%
'\('  {return OPENING;}
'\)'  {return CLOSING;}
.     {return yytext[0];}
%%

int yywrap(){
return 1;
}

It's printing valid for every input even for strings like
(
()(
And also please mention about some good resources to start with

Answer 1

The first problem you have is that ' characters don't mean anything to lex, so having them in your match patterns will look for a literal ' in the input. Since you have none, your rules won't match and you'll be giving undefined tokens to your parser.

The second problem is that putting return 0; in an action causes the parser to immediately return success when it occurs. Since an action can be reduced whenever it is in a context when it can appear regardless of lookahead (due to default reductions), this causes your parser to print Valid and exit if the first token seen is anything other than OPENING.

In order to determine the success of a parser (or not), you need to check the return value of yyparse() -- it returns 0 on success and non-zero for failures (1 for invalid input and 2 for running out of memory). So your parser should be:

%%
stmt : S
S    : OPENING S CLOSING S
|  ;
%%

int main(){
    if (!(yyin=fopen("input.c","r")) {
        /* ALWAYS check the return value of fopen */
        printf("can't open input.c\n");
        return 1; }
    if (yyparse() == 0) {
        printf("Valid\n");
        return 0;
    } else {
        return 1;
    }
}

Combine that with fixed lexer patterns:

"("    {return OPENING;}
")"    {return CLOSING;}
[\n ]  ;  /* ignore newlines and spaces */
.      {return yytext[0];}

and things should work more like you expect