编译原理实验 之 语法分析程序自动生成工具Yacc实验

什么是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 expr3. expr MUL expr4. expr DIV expr   (最高)

显而易见！！！

• 既然老师让我们写出对应的无二义性文法，所以上面的那个肯定是有二义性的，那么具体怎么改，直接GPT
• 但是我们要写出测试用例证明这个是错的，在这里，我稍微给一点提示(a-b-c和a/b/c)就是连续的减和连续的除法可以验证上面的文法是错误的，上面的a,b,c大家可以替换为具体的数字进行测试，但是为了让老师看出我们确实是思考的，可以把对应的a,b,c数字不要简单弄个1,2,3之类的

任务2：自行设计无二义性文法

• 这个大家就自行设计啦！！！