yacc-如何编写检查平衡括号的yacc代码

Question

它应该有效
()
()()()()
(()()()(()))

且无效
(
(((
()())

YACC 代码：

%{
#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 代码：

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

%}

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

int yywrap(){
return 1;
}

它对每个输入都打印有效，甚至对于像这样的字符串也有效 (
()(
另外请提及一些好的资源来开始

Answer 1

您遇到的第一个问题是

'

 字符对 lex 没有任何意义，因此将它们放在匹配模式中将在输入中查找文字 

'

。由于您没有，您的规则将不匹配，并且您将向解析器提供未定义的标记。

第二个问题是，将

return 0;

 放入操作中会导致解析器在发生时立即返回成功。由于无论何时出现在上下文中，无论是否先行（由于默认减少），操作都可以减少，这会导致解析器打印 

Valid

 并在看到的第一个标记不是 

OPENING

 之外的任何内容时退出。

为了确定解析器是否成功，您需要检查

yyparse

 的返回值——成功时返回 0，失败时返回非零（1 表示无效输入，2 表示耗尽）记忆）。所以你的解析器应该是：

%%
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;
    }
}

将其与固定的词法分析器模式相结合：

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

事情应该会更像你期望的那样