编译技术课程设计
班 级 计算机1201
学 号
姓 名
指导老师
20##年 6 月
目 录
一、目的.......................................................................................................................... 2
二﹑题目.......................................................................................................................... 2
三、要求.......................................................................................................................... 2
四、实验环境................................................................................................................... 2
五、系统实现................................................................................................................... 3
1.词法分析................................................................................................................ 3
2.语法分析................................................................................................................ 7
3.中间代码................................................................................................................ 8
4.错误处理.............................................................................................................. 13
六、程序运行结果.......................................................................................................... 14
1.成功用例.............................................................................................................. 14
2.出错处理用例....................................................................................................... 15
七、总结........................................................................................................................ 18
一、目的
<<编译技术>>是理论与实践并重的课程,而其课程设计要综合运用一、二年级所学的多门课程的内容,用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解;培养学生对完整系统的独立分析和设计的能力,进一步培养学生的独立编程能力。
二﹑题目
表达式的小型编译器
三、要求
表达式的小型编译器:
1. 词法分析 产生语言的单词序列
2. 语法分析 能识别由加+ 乘* 括号()操作数(变量或常数)所组成的算术表达式,其文法如下:
E→E+T|T
T→T*F|F
F→(E)|i
使用的分析方法可以是:递归下降分析法或LR分析法。
3. 中间代码生成 产生上述算术表达式的中间代码
4. 错误处理 给出错误信息
输入:算术表达式
输出:符号表,常数表。
递归下降分析法:递归调用过程/ LR分析法:语义栈和符号栈
四元式序列
四、实验环境
操作系统:Win8.1
实验软件:Visual Studio 2013
五、系统实现
1.词法分析
(1)单词符号表
(2)状态转换图
(只画出算数表达式需要部分)
(3)数据结构
单词二元式:(单词种别,单词自身的值)
符号表:(表序号,符号表自身的值)
常数表:(表序号,常数表自身的值)
(4)函数说明
//判断是否为字母
bool letter(){
if ((('a' <= character) && (character <= 'z')) || (('A' <= character) && (character <= 'Z')))
return true;
else
return false;
}
//判断是否为数字
bool digit(){
if (('0' <= character) && (character <= '9'))
return true;
else
return false;
}
//将token中的字符串与character的字符连接
void concatenation(){
token[a] = character;
a++;
p++;
character = in[p];
}
//扫描指针回退一个字符
void retract() {
p- -;
}
//将token中的字符串与关键字比较
int reserve() {
string To = token;
for (int j = 0; j < 5; j++){
if (To == keyword[j]){
return j + 1;
break;
}
}
return 0;
}
//变量表去重
int varilist(string token){
int i;
for (i = 0; i < a1; i++)
{
if (token == blmb[i])
{
break;
}
}
if (i == a1)
{
blmb[a1] = token;
a1++;
}
return 0;
}
//常数表去重
int conslist(){
int i;
for (i = 0; i < b; i++)
{
if (token == csb[i])
{
break;
}
}
if (i == b)
{
csb[b] = token;
b++;
}
return 0;
}
//显示变量名表
void showVari()
{
cout << endl;
cout << "-------变量名表--------" << endl;
for (int i = 0; i < a1; i++)
{
cout << i << " " << blmb[i] << endl;
}
}
//显示常量名表
void showCons()
{
cout << endl;
cout << "-------常数表-------" << endl;
for (int i = 0; i < b; i++)
{
cout << i << " " << csb[i] << endl;
}
}
2.语法分析
(1)分析方法说明
LR分析法指从左至右扫描和自底向上的语法分析,且在分析的每一步,只须根据分析栈当前已移进和归约出的全部文法符号,并至多再向前查看K个输入符号,就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成,从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。
每一项ACTION[s, a]所规定的动作是以下四种情况之一:
(1) 移进:使(s, a)的下一状态s'=ACTION[s, a]和输入符号a进栈(注:对终结符a来说,下一状态s'=GOTO[s, a]的值实际上是放在ACTION[s, a]中的),下一输入符号变成现行输入符号。
(2) 归约:指用某一产生式A→β进行归约。假若β的长度为γ,则归约的动作是去掉栈顶的γ个项,即使状态sm-γ变成栈顶状态,然后使(sm-γ,A)的下一状态s'=GOTO[sm-γ,A] 和文法符号(非终结符)A进栈。归约的动作不改变现行输入符号,执行归约的动作意味着呈现于栈顶的符号串Xm-γ+1…Xm是一个相对于A的句柄。
(3) 接受:宣布分析成功,停止分析器的工作。
(4) 报错:报告发现源程序含有错误,调用出错处理程序。
LR分析器的总控程序本身的工作十分简单,它的任何一步只需按分析栈的栈顶状态s和现行输入符号a执行ACTION[s,a]所规定的动作即可。
(2)文法
LR分析表如下:
状态转换图如下:
(3)数据结构
stack<int> status; //状态栈
stack<char> sign; //符号栈
(4)函数说明
void showLR()//栈遍历
3.中间代码
(1)属性文法
产生式 语义规则
(1) ?S→E print (E.val)
(2) ?E→E(1)+T E.val=E(1).val+T.val
(3) ?E→T E.val=T.val
(4) ?T→T(1)*F T.val=T(1).val*F.val
(5) ?T→T(1) T.val=T(1).val
(6) ?F→(E) F.val=E.val
(7) ?F→i F.val=i.lexval
(2)数据结构
stack<string> yuyi; //语义栈
yuyi.push(); //入栈
yuyi.pop(); //出栈
string v1, v2, v3, v4; //四元式
v1 = "+"/"*" //四元式第一位显示操作符
v2 = tempYuyiPush.top(); //四元式第二位显示操作数
v3 = tempYuyiPush.top(); //四元式第三位显示操作数
v4 = intToStr(strToInt(v2) + strToInt(v3)); //四元式第四位显示结果
(3)函数说明
void yffxSolve() //规约和移进处理,以及四元式的输出
{
stack<string> tempYuyiPush;
showLR();
int i = -1;
if (cifa[m][0] == "6" || cifa[m][0] == "7"){//标识符或数字
i = 0;
}
if (cifa[m][0] == "8"){//+
i = 1;
}
if (cifa[m][0] == "10"){//*
i = 2;
}
if (cifa[m][0] == "14"){//(
i = 3;
}
if (cifa[m][0] == "15"){//)
i = 4;
}
if (cifa[m][0] == "16"){//#
i = 5;
}
if (i == -1) {
cout << "输入了错误的种别编码" << endl;
m++;
return;
}
if (action[status.top() - 48][i] > 0)
{
if (action[status.top() - 48][i] > 100)
{
if (action[status.top() - 48][i] == 1000)
{
cout << "acc" << endl;
system("pause");
exit(0);
}
//规约
int s = action[status.top() - 48][i] - 100;
for (int j = 0; j < gyLen[s - 1]; j++)
{
if (s != 4)
{
tempYuyiPush.push(yuyi.top());
yuyi.pop();
}
status.pop();
sign.pop();
}
int current = status.top();
status.push(action[current - 48][6] + 48);
sign.push('E');
if (s == 4)
{
}
else {
v2 = tempYuyiPush.top();
tempYuyiPush.pop();
string v2plus5 = tempYuyiPush.top();
tempYuyiPush.pop();
v3 = tempYuyiPush.top();
tempYuyiPush.pop();
if (isdigit(v2) && isdigit(v3))
{
if (s == 1)
{
v4 = intToStr(strToInt(v2) + strToInt(v3));
}
if (s == 2)
{
v4 = intToStr(strToInt(v2) * strToInt(v3));
}
yuyi.push(v4);
}
else {
if (v2 == "_" && isdigit(v2plus5) && v3 == "_")
{
v4 = v2plus5;
yuyi.push(v4);
}
else {
string tempNum = intToStr(yuyiNum);
string tempS = "T" + tempNum;
yuyiNum++;
yuyi.push(tempS);
v4 = tempS;
}
}
if (s == 1)
{
v1 = "+";
}
if (s == 2)
{
v1 = "*";
}
}
}
else
{
//移进
status.push(action[status.top() - 48][i] + 48);
sign.push(inputSign[i]);
if (cifa[m][0] == "6" || cifa[m][0] == "7")
{
if (cifa[m][0] == "6")
{
yuyi.push(cifa[m][1]);
}
else {
stringstream s1;
s1 << cifa[m][1];
string tempVal;
s1 >> tempVal;
yuyi.push(tempVal);
}
}
else {
yuyi.push("_");
}
m++;
}
}
else
{
int err = action[status.top() - 48][i];
cout << "第"<<m+1<<"个单词错误:"<<"\t"<<showErr[err + 12] << endl;
system("pause");
m++;
}
lrNum++;
}
(4)流程图
4.错误处理
(1)数据结构
在分析表的空格中分别确定各种不同的错误类型
string showErr[12] =
{
" +前缺少变量或常量",
" *前缺少变量或常量",
" )前缺少对应(",
" 连续的变量或常量,缺少+/*",
" (前缺少+/*",
" (后缺少常量或变量",
" ()内无表达式",
" +后缺少变量或常量",
" *后缺少变量或常量",
" 算数表达式为空",
" 缺少对应)",
" 语法分析错误" };
(2)函数说明
static int action[10][7] = { //在分析表的数组中插入出错的序列
{ 3, -12, -11, 2, -10, -3, 1 },
{ -9, 4, 5, -8, -10, 1000, -1 },
{ 3, -7, -7, 2, -6, -2, 6 },
{ -9, 104, 104, -8, 104, 104, -1 },
{ 3, -5, -5, 2, -10, -5, 7 },
{ 3, -4, -4, 2, -10, -4, 8 },
{ -9, 4, 5, -9, 9, -2, -1 },
{ -9, 101, 5, -9, 101, 101, -1 },
{ -9, 102, 102, -9, 102, 102, -1 },
{ -9, 103, 103, -9, 103, 103, -1 }
};
Else //该段代码位于函数void yffxSolve()中,当不是移进或规约是就进行出错处理
{
int err = action[status.top() ][i];
cout << "第"<<m+1<<"个单词错误:"<<"\t"<<showErr[err + 12] << endl;
system("pause");
m++;
}
六、程序运行结果
1.成功用例
加和乘和括号,标识符和数字混合运算
词法分析显示如下:
语法分析及中间代码显示如下:
显示acc,分析成功
2.出错处理用例
(1)缺少变量或常量
(2)缺少对应的括号
缺右括号
缺左括号
(3)算数表达式为空
(4)括号内没有表达式
(5)括号前缺少+/*
七、总结
通过这次编译原理的课程设计,我对自底向上的LR分析法有了更加深入的认识与了解,对简单的表达式的识别过程也有了更加深入的了解,知道了编译器编写过程的繁复,以及要考虑到各种问题。
在实验过程中,从刚开始的一知半解到后来的深入理解,其中的过程可谓是曲折的。尤其是在实现语义栈和四元式时,由于情况比较多,出现了各种错误。然后是在出错处理这方面也费了不少工夫,在各种Debug过程中最终总算是完成了。
这次课设,我发现了自己的很多不足。在以后的学习中,一定更加努力,不断提高自己的学习能,知识水平以及动手能力。