Lex 和 yacc 程序查找回文串
Lex and yacc program to find palindrome string
这是我的 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
用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 冲突。
在@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 文件,用于识别回文字符串,但它为有效字符串和无效字符串提供了 "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
用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 冲突。
在@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" 情况。