1 实验目的和内容
1.1 实验目的
(1)通过上机实习,加深对语法制导翻译原理的理解,掌握将语法分析 所识别的语法范畴变换为某种中间代码的语义翻译方法。
(2)掌握目前普遍采用的语义分析方法──语法制导翻译技术。
(3)给出 PL/0 文法规范,要求在语法分析程序中添加语义处理,对于语法正确的表达式,输出其中间代码;对于语法正确的算术表达式,输出其计算值。
1.2 实验内容
已给 PL/0 语言文法,在实验二或实验三的表达式语法分析程序里,添加语义处理部分,输出表达式的中间代码,用四元式序列表示。
1.3 实验要求
(1)语义分析对象重点考虑经过语法分析后已是正确的语法范畴,本实 验重点是语义子程序。
(2)在实验二或实验三“语法分析器”的里面添加 PL/0 语言“表达式”部分的语义处理,输出表达式的中间代码,计算表达式的语义值。
(3)中间代码用四元式序列表示。
2 设计思想
2.1 语义规则
属性计算的过程即是语义处理的过程对于文法的每一个产生式配备一组属性的计算规则,则称为语义规则。
(1)终结符只有综合属性,它由词法分析器提供。
(2)非终结符既可以有综合属性也可以有继承属性,文法开始符号的所有继承属性作为属性计算前的初始值。
(3)产生式右边符号的继承属性和产生式左边符号的综合属性都必须提供一个计算规则。
(4)产生式左边符号的继承属性和产生式右边符号的综合属性由其它产生式的属性规则计算。
2.2 递归下降翻译器
递归下降分析法的原理是利用函数之间的递归调用来模拟语法树自上而下的构建过程。从根节点出发,自顶向下为输入串中寻找一个最左匹配序列,建立一棵语法树。对于每个非终结符的继承属性当作形式参数,函数的返回值当作非终结符的继承属性;对于终结符要初始化所有的继承属性。再进行分析过程中,非终结符根据当前的输入符号决定使用哪个产生式候选。
2.3 递归下降子程序伪代码
(1)表达式
function表达式:string;
string s1, s2, s3, result;
BEGIN
IF SYM=’+’ OR SYM=’-’ THEN
ADVANCE;
ELSE IF SYM =FIRST(项)
ELSE ERROR;
BEGIN s1:=项;
END;
WHILE SYM=’+’ OR SYM=’-’ THEN
BEGIN
ADVANCE;
S2:=项;
result := newtemp();
emit(SYM,s1,s2,result);
s1:= result;
END;
Return result;
END;
(2)项
function 项:string;
string s1, s2, s3, result;
BEGIN
IF SYM =FIRST(因子) THEN
BEGIN
s1:=因子;
END;
ELSE ERROR;
WHILE SYM =’*’OR SYM=’/’ THEN
IF SYM =FIRST(因子) THEN
BEGIN
ADVANCE;
S2:=因子;
result := newtemp();
emit(SYM,s1,s2,result);
s1:= result;
END;
Return result;
END;
ELSE ERROR;
(3)因子
function 因子:string;
string s;
BEGIN
IF SYM =’(’ THEN
ADVANCE;
s:=表达式;
ADVANCE;
IF SYM=’)’ THEN
ADVANCE;
Return s;
ELSE ERROR;
ELSE IF SYM =FIRST(因子) THEN
ADVANCE;
ELSE ERROR;
END;
3 算法流程
算法流程图如下所示,首先输入表达式,然后进行词法分析,把词法分析的结果存在结构体中,之后调用递归下降分析器中的表达式子程序进行分析,最后得到四元组并存在相应的结构体中,下一步进行判断,如果是算术表达式,就计算该算术表达式的值并输出,如果不是算术表达式,就不做处理,直接输出四元组,最后判断程序的输入是否结束,如果没有结束,就再次输入表达式,重复上述步骤,如果结束,则程序退出。
图1 算法流程图
4 源程序
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
using namespace std;
struct cf_tv
{
string t;
string v;
};
struct qua
{
string symbal;
string op_a;
string op_b;
string result;
};
string input;
int cnt;
int k=0;
int ljw=0;
cf_tv result[200];
qua output[200];
int x=0;
int ans=0;
bool error=true;
int is_letter=0;
int t[1001];
string item();
string factor();
string new_temp()
{
char *pq;
char mm[18];
pq=(char*)malloc(18);
ljw++;
snprintf(mm,sizeof(mm),"%d",ljw);
strcpy(pq+1,mm);
pq[0]='t';
string s;
s=pq;
return s;
}
bool judge (string input, string s)
{
if (input.length()!=s.length()) return false;
else
{
for(unsigned int i=0;i<s.length();i++)
{
if(input[i]!=s[i]) return false;
}
return true;
}
}
bool judge1 (string input, string s)
{
if(input[0]==s[0]) return true;
else return false;
}
void not_fh(string p)
{
if(judge (p,"begin"))
{
result[k].t="beginsym";
result[k].v=p;
k++;
}
else if(judge (p,"call"))
{
result[k].t="callsym";
result[k].v=p;
k++;
}
else if(judge (p,"const"))
{
result[k].t="constsym";
result[k].v=p;
k++;
}
else if(judge (p,"do"))
{
result[k].t="dosym";
result[k].v=p;
k++;
}
else if(judge (p,"end"))
{
result[k].t="endsym";
result[k].v=p;
k++;
}
else if(judge (p,"if"))
{
result[k].t="ifsym";
result[k].v=p;
k++;
}
else if(judge (p,"odd"))
{
result[k].t="oddsym";
result[k].v=p;
k++;
}
else if(judge (p,"procedure"))
{
result[k].t="proceduresym";
result[k].v=p;
k++;
}
else if(judge (p,"read"))
{
result[k].t="readsym";
result[k].v=p;
k++;
}
else if(judge (p,"var"))
{
result[k].t="varsym";
result[k].v=p;
k++;
}
else if(judge (p,"then"))
{
result[k].t="thensym";
result[k].v=p;
k++;
}
else if(judge (p,"write"))
{
result[k].t="writesym";
result[k].v=p;
k++;
}
else if(judge (p,"while"))
{
result[k].t="whilesym";
result[k].v=p;
k++;
}
else
{
int flag = 0;
for(unsigned int i=0;i<p.length();i++)
{
if(!isdigit(p[i]))
{
flag = 1;
result[k].t="ident";
result[k].v=p;
k++;
break;
}
}
if(!flag)
{
result[k].t="number";
result[k].v=p;
k++;
}
}
}
int change(string str,int cnt)
{
int y=0;
char fh[15]={'+','-','*','/','=','<','>',':','(',')',',',';','.'};
for(int i=0;i<13;i++)
{
if(str[cnt]==fh[i])
{
y=i;
}
}
if(y==5)
{
if(str[cnt+1]=='>')
{
cnt=cnt+1;
return cnt;
}
else if(str[cnt+1]=='=')
{
cnt=cnt+1;
return cnt;
}
}
if(y==7)
{
cnt=cnt+1;
return cnt;
}
return cnt;
}
void fh_1(string str,int cnt)
{
int y=0;
char fh[15]={'+','-','*','/','=','<','>',':','(',')',',',';','.'};
for(int i=0;i<13;i++)
{
if(str[cnt]==fh[i]) y=i;
}
if(y==0)
{
result[k].t="plus";
result[k].v=fh[y];
k++;
}
if(y==1)
{
result[k].t="minus";
result[k].v=fh[y];
k++;
}
if(y==2)
{
result[k].t="times";
result[k].v=fh[y];
k++;
}
if(y==3)
{
result[k].t="slash";
result[k].v=fh[y];
k++;
}
if(y==4)
{
result[k].t="eql";
result[k].v=fh[y];
k++;
}
if(y==5)
{
if(str[cnt+1]=='>')
{
cnt=cnt+1;
result[k].t="neq";
result[k].v="<>";
k++;
}
else if(str[cnt+1]=='=')
{
result[k].t="leq";
result[k].v="<=";
k++;
}
else
{
result[k].t="lss";
result[k].v="<";
k++;
}
}
if(y==6)
{
if(str[cnt+1]=='=')
{
result[k].t="geq";
result[k].v=">=";
k++;
}
else
{
result[k].t="gtr";
result[k].v=">";
k++;
}
}
if(y==7)
{
result[k].t="becomes";
result[k].v=":=";
k++;
}
if(y==8)
{
result[k].t="lparen";
result[k].v="(";
k++;
}
if(y==9)
{
result[k].t="rparen";
result[k].v=")";
k++;
}
if(y==10)
{
result[k].t="comma";
result[k].v=",";
k++;
}
if(y==11)
{
result[k].t="semicolon";
result[k].v=";";
k++;
}
if(y==12)
{
result[k].t="period";
result[k].v=".";
k++;
}
}
void cifa()
{
string str;
while(cin>>str)
{
cnt=0;
const char *d = " +-*/=<>:(),;.";
char *p;
char buf[1001] ;
strcpy(buf , str.c_str());
p = strtok(buf,d);
while(p)
{
if(str[cnt]==p[0])
{
not_fh(p);
cnt=cnt+strlen(p);
}
else
{
while(str[cnt]!=p[0])
{
fh_1(str,cnt);
cnt=change(str,cnt);
cnt=cnt+1;
}
not_fh(p);
cnt=cnt+strlen(p);
}
p=strtok(NULL,d);
}
for(unsigned int i=cnt;i<str.length();i++)
{
fh_1(str,i);
}
}
}
void judge_type()
{
for(int i=0;i<k;i++)
{
if(judge(result[i].t,"ident"))
{
is_letter=1;
break;
}
}
}
string bds()
{
string s;
string s1,s2,s3;
if(ans>k) return NULL;
if(judge(result[ans].v,"+") || judge(result[ans].v,"-"))
{
ans++;
if(ans>k)
{
cout<<1<<endl;
error=false;
}
s1=item();
}
else if( judge(result[ans].v,"(") ||judge(result[ans].t,"ident") ||judge(result[ans].t,"number"))
{
s1=item();
}
else
{
cout<<2<<endl;
error=false;
}
while(judge(result[ans].v,"+") || judge(result[ans].v,"-"))
{
int ans_temp=ans;
ans++;
if(ans>k)
{
cout<<3<<endl;
error=false;
}
s2=item();
output[x].symbal=result[ans_temp].v;
output[x].op_a=s1;
output[x].op_b=s2;
output[x].result=new_temp();
s=output[x].result;
s1=s;
x++;
}
return s;
}
string item()
{
string s;
string s1,s2,s3;
if(ans>k) return NULL;
s1=factor();
while(judge(result[ans].v,"*") || judge(result[ans].v,"/"))
{
int ans_temp=ans;
ans++;
if(ans>k)
{
cout<<4<<endl;
error=false;
}
s2=factor();
output[x].op_a=s1;
output[x].symbal=result[ans_temp].v;
output[x].op_b=s2;
output[x].result=new_temp();
s=output[x].result;
s1=s;
x++;
}
return s1;
}
string factor()
{
string s;
if(ans>=k) return NULL;
if(judge(result[ans].t,"ident") ||judge(result[ans].t,"number"))
{
s=result[ans].v;
ans++;
if(ans>k)
{
cout<<5<<endl;
error=false;
}
}
else if(judge(result[ans].v,"("))
{
ans++;
s = bds();
if(judge(result[ans].v,")"))
{
ans++;
if(ans>k)
{
cout<<6<<endl;
error=false;
}
}
}
else
{
cout<<7<<endl;
error=false;
}
return s;
}
string del(string s)
{
char c[101];
for(unsigned int i=0;i<s.length()-1;i++)
{
c[i]=s[i+1];
}
return c;
}
void js(int i)
{
char* end;
if(judge(output[i].symbal,"*"))
{
if(!judge1(output[i].op_a,"t"))
{
if(!judge1(output[i].op_b,"t"))
{
t[i+1]=static_cast<int>(strtol(output[i].op_a.c_str(),&end,10))*static_cast<int>(strtol(output[i].op_b.c_str(),&end,10));
}
}
}
else
{
if(!judge1(output[i].op_b,"t"))
{
string ss;
ss=del(output[i].op_a);
int z=static_cast<int>(strtol(ss.c_str(),&end,10));
t[i+1]=t[z]*static_cast<int>(strtol(output[i].op_b.c_str(),&end,10));
}
else
{
string s;
s=del(output[i].op_a);
int yy=static_cast<int>(strtol(s.c_str(),&end,10));
string ss;
ss=del(output[i].op_b);
int zz=static_cast<int>(strtol(ss.c_str(),&end,10));
t[i+1]=t[yy]*t[zz];
}
if(judge(output[i].symbal,"+"))
{
if(!judge1(output[i].op_a,"t"))
{
if(!judge1(output[i].op_b,"t"))
{
t[i+1]=static_cast<int>(strtol(output[i].op_a.c_str(),&end,10))+static_cast<int>(strtol(output[i].op_b.c_str(),&end,10));
}
else
{
string ss;
ss=del(output[i].op_b);
int yy=static_cast<int>(strtol(output[i].op_a.c_str(),&end,10));
int zz=static_cast<int>(strtol(ss.c_str(),&end,10));
t[i+1]=yy+t[zz];
}
}
else
{
if(!judge1(output[i].op_b,"t"))
{
string ss;
ss=del(output[i].op_a);
int zz=static_cast<int>(strtol(ss.c_str(),&end,10));
t[i+1]=t[zz]+static_cast<int>(strtol(output[i].op_b.c_str(),&end,10));
}
else
{
string s;
s=del(output[i].op_a);
int yy=static_cast<int>(strtol(s.c_str(),&end,10));
string ss;
ss=del(output[i].op_b);
int zz=static_cast<int>(strtol(ss.c_str(),&end,10));
t[i+1]=t[yy]+t[zz];
}
}
}
}
}
int main()
{
cifa();
judge_type();
bds();
if(is_letter==1)
{
for(int i=0;i<x;i++)
{
cout<<"("<<output[i].symbal<<","<<output[i].op_a<<","<<output[i].op_b<<","<<output[i].result<<")"<<endl;
}
}
else
{
for(int i=0;i<x;i++)
{
js(i);
}
cout<<t[x]<<endl;
}
return 0;
}
5 调试数据
5.1 测试样例一
【样例输入】
2+3*5
【样例输出】
17
样例一结果如下所示
图2 样例一测试结果
5.2 测试样例二
【样例输入】
2+3*5+7
【样例输出】
24
样例二结果如下所示
图3 样例二测试结果
5.3 测试样例三
【样例输入】
a*(b+c)
【样例输出】
(+,b,c,t1)
(*,a,t1,t2)
样例三结果如下所示
图4 样例三测试结果
5.4 测试样例四
【样例输入】
a*(b+c)+d
【样例输出】
(+,b,c,t1)
(*,a,t1,t2)
(+,t2,d,t3)
样例四结果如下所示
图5 样例四测试结果
6 实验调试情况及体会
6.1 实验调试情况
由上一步中的四个测试样例可以得到,所有的测试样例均得到了相应的输出结果,说明代码编写成功,并且在代码中设置了出错处理,以便解决其他情况。
6.2 实验体会
这次实验在上课之前及时的进行了预习,在编写代码之前需要写出递归下降翻译器的伪代码,重点就是要找到对于每个非终结符的属性哪些是继承属性,哪些是综合属性。然后将继承属性作为参数,综合属性作为返回值,进行计算。
编写代码的时候,需要用到实验一和实验二的代码,写实验一代码的时候没考虑到后面会用到,直接将结果输出并没有保存中间结果,以至于自己在编码的时候需要先将实验一的结果存放在一个自定义的结构体中,里面包含词法分析的两个因素:值和类型。而分析器分析的时候,直接调取这个结构体的内容,四元式的结果也会放在一个特殊的结构体,里面记录了四元式的四个值,方便输出。如果是数字运算式,可以模拟计算器对于这四个值进行计算,并且需要数组和判定运算符函数来判断是数字还是辅助变量,根据对应符号进行运算。
通过这次实验,从词法分析到语法分析到语义分析的知识点有了大致的回顾,并且重点回顾了每个阶段输入什么,输出什么,这些信息怎么存储,用什么算法来计算。还需要进一步优化自己的代码,比如在这次的实验代码过程中,需要改进的是将词法分析和语法分析合并,降低时间复杂度,提高执行效率。
通过这四次的实验过程,让我对于编译原理这门课有了比较清晰的认识,可能理论课当时听懂了,过一会可能就会遗忘。通过学习编译原理,感觉用到了数据结构,算法等思维理解,又需要对于许多概念的理解记忆。这也是这门课的难点所在。通过这次学习,懂得更要注重对于基础科目的掌握,不断加强和拓展自己的计算机思维。
最后感谢刘善梅老师对我一学期的悉心指导,不胜感激,我会继续努力学好接下来的每一门专业课程,不负老师厚望!
|