Lex 和 yacc 程序查找回文串

Question

这是我的 lex 和 yacc 文件，用于识别回文字符串，但它为有效字符串和无效字符串提供了 "INVALID "。请帮我找出问题所在，我是 lex 和 yacc 的新手。提前致谢

LEX 文件

%{
#include "y.tab.h"
%}

%%
a return A;
b return B;
. return *yytext;
%%

YACC 文件

%{
#include<stdio.h>
#include "lex.yy.c"
int i=0;
%}
%token A B
%%
S: pal '\n' {i=1;}
pal:
   | A pal A {printf("my3");i=1;}
   | B pal B {printf("my4");i=1;}       
   | A {printf("my1");i=1;}
   | B {printf("my2");i=1;}         
   ;
%%
int main()
{
    printf("Enter Valid string\n");
    yyparse();
    if(i==1)
    printf("Valid");
    return 0;
}
int yyerror(char* s)
{
    printf("Invalid\n");
    return 0;
}

示例：输入的字符串是：aba 预期输出应该是 VALID 但它给出 INVALID

Answer 1

用Yacc无法解决这个问题

Yacc 是一个 LALR(1) 解析器生成器。 LALR 指的是 class 文法。语法是一种推理解析的数学工具。括号中的一个指的是先行——这是我们在明确决定要遵循哪个替代产品（或"rules"）之前考虑的最大令牌数。请记住，解析算法是一次通过，它不能像某些正则表达式引擎那样回溯并尝试另一种选择。

关于你的回文问题，当解析器遇到'a'时，它必须以某种方式选择正确的选择

pal: A - 'a'本身就是一个有效的回文，我们称它为内核
pal: [A] pal A - 外层，增加嵌套层数
pal：朋友[A] - 外层，嵌套层数递减

没有无限前瞻就不可能做出正确的选择，但是Yacc只有一个前瞻标记。

Yacc 处理这种语法的方式也很有趣。

如果语法有歧义或不是 LR(1)，则生成的堆栈自动机是不确定的。有一些内置工具可以修复它。

第一个工具是优先级和关联性，用于处理编程语言中的运算符（此处不相关）。

另一个是怪癖 - 默认情况下 Yacc 更喜欢 "shift" 而不是 "reduce"。这两个是涉及解析算法内部操作的技术细节。基本上令牌是 "shift" 到堆栈中。一旦顶部的一组标记匹配规则，就可以 "reduce" 它们，用规则左侧的单个非终结符替换整个组。

因此，一旦我们在顶部有 'a'，我们可以将其缩减为朋友，或者我们可以转移另一个令牌，假设嵌套的朋友最终会出现。 Yacc更喜欢后者。

这种偏好的原因是什么？大多数语言中的 if-then-else 语句中都会出现同样的歧义。考虑两个嵌套的 if 语句但只有一个 else 子句。 Yacc 将 else 附加到最里面的 if 语句，这似乎是正确的做法。

此外，Yacc 还可以生成一份报告，突出显示语法中的问题，例如上面提到的 shift-reduce 冲突。

Answer 2

在@ChrisDod 和@NickZavaritsky 评论的延续中，我添加了 glr (bison) 解析器的工作版本。

%option noyywrap

%%
a    return A;
b    return B;
\n   return '\n';
.    {fprintf(stderr, "Error\n"); exit(1);}
%%

和 Yacc/bison

%{
#include <stdio.h>
int i=0;
%}

%token A B
%glr-parser

%%
S  : pal   '\n'   {i=1; return 1 ;}
   | error '\n'   {i=0; return 1 ;}

pal: A pal A
   | B pal B
   | A
   | B
   |
   ;
%%
#include "lex.yy.c"

int main() {
    yyparse();
    if(i==1) printf("Valid\n");
    else     printf("inValid\n");
    return 0;
}
int yyerror(char* s) { return 0; }

词法分析器中引入了一些更改：(1) \n 缺失； (2) 未知字符现在是致命错误；

错误恢复 error 用于获取 "invalid palindrome" 情况。

Lex 和 yacc 程序查找回文串

Lex and yacc program to find palindrome string

yacc

lex