编译原理实验报告
实验4：验证Yacc的使用
实验e4：从语言SUM到栈式计算机STACK的机器语言的翻译
中国海洋大学编译原理实验2023春
仅供同学参考思路 请勿直接抄袭 否则可能喜提0分
目录
文章目录
- 编译原理实验报告
- 目录
- 一.实验目的
- 二.实验内容
- 实验4
- 实验e4
- 三.实验要求
- 实验4
- 实验e4
- 四.实验过程及重点内容
- 实验4:
- 二义性文法:
- 非二义性文法:
- 实验e4:
- compile函数
- print函数
- 修改语法树为1+(2+3)
- 五.实验结果
- 实验4
- 实验e4:
一.实验目的
实验4:
熟悉语法分析器生成工具Yacc的使用，并学会在实验环境下使用bison工具编译Yacc文法说明文件。学习如何使用lex和yacc合作进行语法分析。
实验e4:
熟悉语言SUM 到栈式计算机STACK的机器语言的翻译过程，理解编译的一般步骤。
二.实验内容
实验4
根据给出的calculator例子（calculator0,calculator1,calculator2,calculator3）
完成下面题目：用lex和yacc写一个计算布尔表达式真值的计算器。
实验e4
sum.c是用c语言写的从sum语言到栈式计算机STACK的机器语言的编译器（省略了词法语法分析部分）。
该程序的基本功能是先构造SUM语言的某句子的抽象语法树，然后将该语法树翻译成STACK的机器语言程序，并按顺序打印出该机器语言程序的指令。
程序中有两段内容不完整（在程序中用TODO表示），请读懂并编译通过该程序，再将TODO的部分补充完整，并编译通过。
三.实验要求
实验4
输入为一个布尔表达式，以换行结束。输出为这个布尔表达式的真值（true或false）。
尝试二义文法和非二义文法两种不同的实现方式。布尔表达式二义文法为：
S –> S or S |
S and S |
not S |
(S) |
true |
false，其中优先级or < and < not，or 和 and 左结合，not 右结合。
非二义文法请参照表达式非二义文法自己写出来。
在实验环境下用flex，bison和gcc工具将实验调试通过，并写出测试例测试正确性。
实验e4
-
读懂程序sum.c并编译通过。（该程序可以使用gcc编译通过，其他编译环境请自行调试）
-
用你自己写的程序段替换程序中的TODO部分，使程序功能与实验内容的描述一致。
-
（此要求为额外要求，供学有余力的同学自行选择。）将程序的输入改为句子1+(2+3)的抽象语法树，尝试程序能否输出正确的结果。
四.实验过程及重点内容
实验4:
本实验需要编写两个文件 一个是词法分析器的lex文件 一个是语法分析的yacc文件
二义性文法:
lex需要用到的记号
yacc:
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CC1jnclr-1687580593336)(null)]
token定义了所有终结符
left和right定义了左右结合性 从上至下代表着优先级从低到高
定义文法boool
$$代表左侧记号属性值 %i代表右侧第i个记号的属性值
根据布尔运算的定义 右侧用C语言计算属性值
阅读yacc使用指南 对.y和.l文件进行编译链接
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9WVwLPzH-1687580524132)(null)]
在ERYI.l中加入头文件引用
最后使用gcc编译器 生成e4.exe
测试结果如下:
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UD5RRAlg-1687580524861)(null)]
与预期结果相等 括号也可正常识别
非二义性文法:
主要修改yacc文件中的文法
优先级从低到高
S->S or T | T
T->T and F | F
F->not F | (S) | false | true
编译运行生成的exe文件 测试用例为:
true or not true and false
false or (not true and true)
false or not (true and false)
false or not true and false
结果符合预期输出:
实验e4:
首先读懂main函数:
由Exp_sum_new和exp_int_new构成了一棵加法的二叉树
Exp_print函数则是分析语法树,输出语法树对应的表达式是什么
接下来由compile函数对二叉树进行后续遍历,如果是INT结点直接入栈
如果是SUM结点则继续遍历,并把ADD入栈
最后由List_reverse_print函数输出链表的结果
compile函数
INT结点直接将值入栈
SUM结点继续递归后序遍历 并把ADD入栈
print函数
先对list_new函数进行分析 由分析可知链表采用的是头插法
例如1+2 链表中储存的顺序由头节点开始应为 ADD->2->1
但实验要求翻转输出 函数名也对应为reverse_print
接下来对list链表进行逆序输出:
我采取的做法是将list再次使用头插法重新插入到一个新链表中 再次输出链表则为逆序
定义新结点类型:
使用头插法把结点插入新链表中
直接顺序遍历新链表:
结果如下:
修改语法树为1+(2+3)
结果正常输出:
五.实验结果
实验4
二义性文法:
非二义性文法:
实验e4:
