什么是Yacc
Yacc(Yet Another Compiler Compiler)是一个语法分析程序自动生成工具，Yacc实验通常是在编译原理相关课程中进行的实践项目，旨在让学生深入理解编译器的语法分析阶段以及掌握Yacc工具的使用
实验环境准备
- 安装
Yacc，（安装包可通过解压学习通下载的压缩包得到）
- 全称一股脑下载即可，注意的是下载的路径
和先前下载的MinGW的路径一致，我下载bison的时候默认的路径就是我下载MinGW的路径了，所以直接默认即可
- 对于安装
MinGW和Flex以及配置环境变量，在Flex工具实验中以及配置完成，这里就不需要重复配置 ，如果还没配置完成，可以查看我先前的博客 编译原理 实验二 词法分析程序自动生成工具实验
复现实验例子
- 实验名称：
实验名称：结合flex工具实现简单表达式求值
Step 1:使用文本编辑器输入构词规则序列，文件名为token.l，格式见LEX工具实验。
%{
#include "expr.tab.h"
%}
%%
"q" return STOP;
"(" return LP;
")" return RP;
"\+" return PLUS;
"\-" return MINUS;
"\*" return MUL;
"\/" return DIV;
[0-9]+ {yylval=atoi(yytext); return DIGIT;}
%%
运行命令：
flex token.l
- 得到文件
lex.yy.c
Step 2：使用文本编辑器输入上下文无关文法，文件名为expr.y。
expr.y文件
%{
#include <stdio.h>
%}
%token DIGIT STOP LP RP PLUS MINUS MUL DIV
%%
start : expr STOP {printf("expr=%d\n", $1); exit(1);}
;
expr:expr PLUS expr {$$=$1+$3;}
|expr MINUS expr {$$=$1-$3;}
|expr MUL expr {$$=$1*$3;}
|expr DIV expr {$$=$1/$3;}
|LP expr RP {$$=$2; }
|DIGIT {$$=$1; }
;
%%
main(){
printf("Type something followed by Return. Type 'q' to end.\n");
printf("\n");
return(yyparse()); /* Start the parser */
}
yyerror(s)
char *s; {
printf("yacc error: %s\n", s);
}
yywrap(){
return(0);
}
运行命令
bison -d expr.y
- 得到文件
expr.tab.c。如果调用bison(YACC)时使用『-d』选项，那么它们会输出到expr.tab.h中。
Step 3: 得到语法分析程序
运行命令
gcc lex.yy.c expr.tab.c -o expr
- 得到可执行文件
expr.exe，即语法分析程序
Step 4：使用语法分析程序分析输入文件
运行命令(下面的命令是
CMD命令)
expr <b.c> a.txt
给出对应的
PowerShell的等价运行指令
Get-Content b.c | expr > a.tx
当然，也可以通过命令行接收输入,直接运行
expr程序即可
expr
- 得到输出文件
a.txt
分析总的文件架构
token.l：Flex词法分析文件，定义词法规则，用于识别输入的token，每一个规则对应一个动作，返回相应的token类型lex.yy.c：Flex生成的C源文件，包含词法分析器的具体实现、输入缓冲区管理、模式匹配代码expr.y：Yacc/Bison语法文件，定义语法规则和语义动作expr.tab.h：Bison生成的头文件，供词法分析器使用的接口文件expr.tab.c：Bison生成的C源文件expr.exe：最终得到的语法分析程序b.c：测试文件a.txt：最终结果输出文件
文件之间的关系
1. token.l -(flex)-> lex.yy.c
2. expr.y -(bison)-> expr.tab.c + expr.tab.h
3. token.l 包含 expr.tab.h 以使用token定义
4. 最终所有.c文件被编译链接成可执行文件
工作流程
1. 词法分析器(lex.yy.c)读取输入，识别token
2. 语法分析器(expr.tab.c)根据语法规则构建语法树
3. 在归约过程中执行语义动作，计算表达式值
4. 最终输出计算结果
实验任务
任务1：根据expr.y所定义的文法，写出对应的无二义性的文法，设计输入验证这个原本的二义性文法的错误，以及你的无二义性文法的正确性
- 原始的
expr.y所定义的文法
%%
start : expr STOP {printf("expr=%d\n", $1); exit(1);}
;
expr:expr PLUS expr {$$=$1+$3;}
|expr MINUS expr {$$=$1-$3;}
|expr MUL expr {$$=$1*$3;}
|expr DIV expr {$$=$1/$3;}
|LP expr RP {$$=$2; }
|DIGIT {$$=$1; }
;
%%
- 在
Yacc/Bison中，运算符的优先级和结合性遵循以下规则
- 在同一层级的产生式中，先出现的规则优先级较低
- 所以在当前文法中从上到下优先级依次增加：
1. expr PLUS expr (最低)
2. expr MINUS expr
3. expr MUL expr
4. expr DIV expr (最高)
显而易见！！！
- 既然老师让我们写出对应的无二义性文法，所以上面的那个肯定是有二义性的，那么具体怎么改，直接
GPT - 但是我们要写出测试用例证明这个是错的，在这里，我稍微给一点提示(
a-b-c和a/b/c)就是连续的减和连续的除法可以验证上面的文法是错误的，上面的a,b,c大家可以替换为具体的数字进行测试，但是为了让老师看出我们确实是思考的，可以把对应的a,b,c数字不要简单弄个1,2,3之类的
任务2：自行设计无二义性文法
- 这个大家就自行设计啦！！！