语义计算的递归下降（预测）翻译程序

语义计算的递归下降（预测）翻译程序

一、实验内容

实现属性文法的递归下降翻译程序
Ｇ［Ｎ］：
N-> . . .S {S.f:=1;print(S.v)}
S->BS1 {S1.f:=S.f+1;B.f:=S.f;S.v:=B.v+S.v}
S->ε {S.v:=0}
B->0 {B.v:=0}
B->1 {B.v:=2^(-B.f)}

二、内容分析

1. 首先我们由文法可知是L属性文法，因此需将其改写为L属性的翻译模式:G［Ｎ］
   N-> . . .{S.f:=1}S{print(S.v)}
   S->{B.f:=S.f}B{S1.f:=S.f+1}S1{S.v:=B.v+S.v}
   S->ε {S.v:=0}
   B->0 {B.v:=0}
   B->1 {B.v:=2^(-B.f)}
2. 然后我们根据文法左部非终结符进行划分，分成N、S、B三部分，需计算出三个非终结符的first集进行递归子程序的判断
   first(N)={.}
   first(S)={0,1,ε}
   first(B)={0,1}
3. 准备工作已完成，然后我们便可以设计

三、算法设计

1. 从键盘输入字符串，跳转至左部非终结符为初始符N调用函数，进行判断：
   若当前字符为．，则执行文法N－＞．Ｓ的翻译语句（Sf=1、S() 、printf(S.val) ）
   反之，则输出错误
2. 当跳转至左部为S的调用函数时，进行判断：
   若当前字符为０或１，则执行S－＞ＢＳ１的翻译语句（Bf=Sf、B()、S1f=Sf+1、S()、Sv=Bv+S1v ）
   若当前字符为ε，则执行S－＞ε的翻译语句（Sv=0）
   反之，则输出错误
3. 当跳转至左部为Ｂ的调用函数时，进行判断：
   若当前字符为０，则执行Ｂ－＞０的翻译语句
   （Match(0)、Bv=0）
   若当前字符为１，则执行Ｂ－＞１的翻译语句
   （Match(1）、Bv=2^(-Bf)）
   反之，则输出错误
4. 字符判断Match(ａ）：
   若当前字符和输入串匹配，则继续进行下一个字符比较，反之则输出错误

四、模块分析

1. 输入：
   显示属性文法并输入字符串

//初始化，输入属性文法和待判断表达式 
void Init(){
	int i;
	cout<<"属性文法为："<<endl;//该文法用于将二进制无符号定点小数转化为十进制小数 
	cout<<"N->.S     {S.f=1;print(S.v)}"<<endl;
	cout<<"S->BS1    {S1.f=S.f+1;B.f=S.f;S.v=B.v+S1.v}"<<endl;
	cout<<"S->ε     {S.v=0}"<<endl;
	cout<<"B->0      {B.v=0}"<<endl;
	cout<<"B->1      {B.v=2^(-B.f)}"<<endl;
	cout<<"输入字符串："<<endl;
	for(i=0;;i++){//输入内容以#结尾 
		cin>>str[i];
		if(str[i]=='#')
		break;
	}
	N();//转入判断 
}

2. N：
   执行左部为非终结符N的语句

//左侧为N的产生式 
void N(){//if的判断语句来源于N的first集 
	float Sf,Sv;
	if(str[temp]=='.'){
		Match('.');
		Sf=1;
		Sv=S(Sf);
		cout<<"S.val="<<Sv<<endl;
	}
	else
	cout<<"syntax error!"<<endl;
}

3. S：
   执行左部为非终结符S的语句

//左侧为S的产生式 
float S(float f){//if的判断语句来源于S的first集 
	float Bf,Bv,S1f,S1v,Sv;
	if(str[temp]=='0'|str[temp]=='1'){
		Bf=f;
		Bv=B(Bf);
		S1f=f+1;
		S1v=S(S1f);
		Sv=Bv+S1v; 
	}
	else if(str[temp]=='#')
	Sv=0;
	else{
		cout<<"syntax error!"<<endl;
		exit(0);
	}
	return Sv;
}

4. B:
   执行左部为非终结符B的语句

//左侧为B的产生式 
float B(float f){//if判断语句来源于B的first集 
	float Bv; 
	if(str[temp]=='0'){
		Match('0');
		Bv=0;
	}
	else if(str[temp]=='1'){
		Match('1');
		Bv=pow(2,-f);
	}
	else{
		cout<<"syntax error!"<<endl;
		exit(0);
	}
	return Bv;
}

5. 字符判断：
   逐个进行字符判断

//进行字符串匹配的判断 
void Match(char ss){//终结符的匹配 
	if(str[temp]!=ss){//若当前字符不匹配 
    	cout<<"syntax error"<<endl;
    }
	else//若当前字符匹配，进行下一字符 
	temp++;
}

五、结果展示

注：由文法属性可知，输入内容必须是二进制小数，第一位是小数点才可以，否则输出错误
正确案例：



错误案例：

六、源代码

代码已经过编译，可直接使用

#include<iostream>
#include<math.h>
using namespace std;
 
//全局变量 
char str[10];//存储待判断表达式 
int temp=0;//当前匹配字符 

void N();//左侧非终结符N 
float S(float);//左侧非终结符S 
float B(float);//左侧非终结符B 
void Match(char);//判断字符的匹配 

//初始化，输入属性文法和待判断表达式 
void Init(){
	int i;
	cout<<"属性文法为："<<endl;//该文法用于将二进制无符号定点小数转化为十进制小数 
	cout<<"N->.S     {S.f=1;print(S.v)}"<<endl;
	cout<<"S->BS1    {S1.f=S.f+1;B.f=S.f;S.v=B.v+S1.v}"<<endl;
	cout<<"S->ε     {S.v=0}"<<endl;
	cout<<"B->0      {B.v=0}"<<endl;
	cout<<"B->1      {B.v=2^(-B.f)}"<<endl;
	cout<<"输入字符串："<<endl;
	for(i=0;;i++){//输入内容以#结尾 
		cin>>str[i];
		if(str[i]=='#')
		break;
	}
	N();//转入判断 
}

//左侧为N的产生式 
void N(){//if的判断语句来源于N的first集 
	float Sf,Sv;
	if(str[temp]=='.'){
		Match('.');
		Sf=1;
		Sv=S(Sf);
		cout<<"S.val="<<Sv<<endl;
	}
	else
	cout<<"syntax error!"<<endl;
}

//左侧为S的产生式 
float S(float f){//if的判断语句来源于S的first集 
	float Bf,Bv,S1f,S1v,Sv;
	if(str[temp]=='0'|str[temp]=='1'){
		Bf=f;
		Bv=B(Bf);
		S1f=f+1;
		S1v=S(S1f);
		Sv=Bv+S1v; 
	}
	else if(str[temp]=='#')
	Sv=0;
	else{
		cout<<"syntax error!"<<endl;
		exit(0);
	}
	return Sv;
}

//左侧为B的产生式 
float B(float f){//if判断语句来源于B的first集 
	float Bv; 
	if(str[temp]=='0'){
		Match('0');
		Bv=0;
	}
	else if(str[temp]=='1'){
		Match('1');
		Bv=pow(2,-f);
	}
	else{
		cout<<"syntax error!"<<endl;
		exit(0);
	}
	return Bv;
}

//进行字符串匹配的判断 
void Match(char ss){//终结符的匹配 
	if(str[temp]!=ss){//若当前字符不匹配 
    	cout<<"syntax error"<<endl;
    }
	else//若当前字符匹配，进行下一字符 
	temp++;
}

//主函数 
int main(){
	Init();//初始化 
} 

大家若遇到什么问题，请留言说明，谢谢！