编译原理实验：语义分析及中间代码⽣成
编译原理实验：语义分析及中间代码⽣成
1. 实验题⽬：语义分析及中间代码⽣成
实验⽬的
1. 通过上机实习，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法范畴变换为某种中间代码的语义翻译⽅法。
2. 掌握⽬前普遍采⽤的语义分析⽅法──语法制导翻译技术。
3. 给出PL/0⽂法规范，要求在语法分析程序中添加语义处理，对于语法正确的表达式，输出其中间代码；对于语法正确的算术表达式，
输出其计算值。
实验内容
  已给PL/0语⾔⽂法，在实验⼆或实验三的表达式语法分析程序⾥，添加语义处理部分，输出表达式的
中间代码，⽤四元式序列表⽰。实验要求
1. 语义分析对象重点考虑经过语法分析后已是正确的语法范畴，本实验重点是语义⼦程序。
2. 在实验⼆或实验三“语法分析器”的⾥⾯添加PL/0语⾔“表达式”部分的语义处理，输出表达式的中间代码，计算表达式的语义值。
3. 中间代码⽤四元式序列表⽰。
输⼊输出
1. PL/0算术表达式的语义计算：
输⼊：
  PL/0算术表达式，例如: 2 + 3 * 5作为输⼊。
输出：
  17
2. PL/0表达式的中间代码表⽰
输⼊：
  PL/0表达式，例如: a *（b +c）
输出：
  ( + b c t1 )
  ( * a t1 t2 )
2. 设计思想
  本次实验我采⽤的递归下降分析器的设计。
  递归下降分析法的原理是利⽤函数之间的递归调⽤来模拟语法树⾃上⽽下的构建过程。从根节点出发，⾃顶向下为输⼊串中寻⼀个最左匹配序列，建⽴⼀棵语法树。在不含左递归和每个⾮终结符的所有候选终结⾸字符集都两两不相交条件下，我们就可能构造出⼀个不带回溯的⾃顶向下的分析程序，这个分析程序是由⼀组递归过程（或函数）组成的，每个过程（或函数）对应⽂法的⽽⼀个⾮终结符。
语法：
<；表达式> -> [+|-]<；项>{<；加法运算符> <；项>}
<；项> -><；因⼦>{<；乘法运算符> <；因⼦>}
<；因⼦> -> <；标识符>|<⽆符号整数>|(<；表达式>)
<；加法运算符> -> +|-
<；乘法运算符> -> *|/
计算FIRST集：
FIRST(<；表达式>)={ +， -， (， <；标识符>， <⽆符号整数> }
FIRST(<；因⼦>)={ <；标识符>， <⽆符号整数>， ( }
FIRST(<；项>)={ <；标识符>， <⽆符号整数>， ( }
FIRST(<；加法运算符>)={ +， - }
FIRST(<；乘法运算符>)={ *， / }
计算FOLLOW集：
FOLLOW(<；表达式>)={ ) }
FOLLOW (<；项>)={ +，- }
FOLLOW (<；因⼦>)={ *，/ }
FOLLOW (<；加法运算符>)={ <；标识符>， <⽆符号整数>， ( }
FOLLOW (<；乘法运算符>)={ <；标识符>， <⽆符号整数>， ( }
可以改成如下拓⼴⽂法：
<；表达式>-><；项> | <；表达式>+<；项> | <；表达式>-<；项>
<；项>-><；因⼦> | <；项>*<；因⼦> | <；项>/<；因⼦>
<；因⼦>->(<；表达式>) | <；标识符> | <⽆符号整数>
将语法消除左递归可得(⽤E代表<；表达式>，T代表<；项>，F代表<；因⼦>)
E->TE’
E’->ɛ|+TE’|-TE’
T->FT’
T’->ɛ|*FT’|/FT’
F->ident|(E)|number
属性⽂法：是在上下⽂⽆关⽂法的基础上为每个⽂法符号（终结符或⾮终结符）配备若⼲个相关的“值”（称为属性）。
属性：代表与⽂法符号相关的信息，和变量⼀样，可以进⾏计算和传递。
综合属性
⽤于“⾃下⽽上”传递信息
在语法树中，⼀个结点的综合属性的值，由其⼦结点的属性值确定
S—属性⽂法：仅仅使⽤综合属性的属性⽂法
语义规则： 属性计算的过程即是语义处理的过程
对于⽂法的每⼀个产⽣式配备⼀组属性的计算规则，则称为语义规则。
(1)终结符只有综合属性，它由词法分析器提供
(2)⾮终结符既可以有综合属性也可以有继承属性，⽂法开始符号的所有继承属性作为属性计算前的初始值。
(3) 产⽣式右边符号的继承属性和产⽣式左边符号的综合属性都必须提供⼀个计算规则
(4) 产⽣式左边符号的继承属性和产⽣式右边符号的综合属性不由所给的产⽣式的属性计算规则进⾏计算，它们由其它产⽣式的属性规则计算
⼀遍扫描的处理⽅法： 与树遍历的属性计算⽅法不同，⼀遍扫描的处理⽅法是在语法分析的同时计算属性值，⽽不是语法分析构造语法树之后进⾏属性的计算，⽽且⽆需构造实际的语法树。
因为⼀遍扫描的处理⽅法与语法分析器的相互作⽤，它与下⾯两个因素密切相关：
1.所采⽤的语法分析⽅法
2.属性的计算次序
如下为递归下降分析器的设计实现思想
1. 对每个⾮终结符A构造⼀个函数过程，对A的每个继承属性设置⼀个形式参数，函数的返回值为A的综合属性（作为记录，或指向记录
的⼀个指针，记录中有若⼲域，每个属性对应⼀个域）。
2. ⾮终结符A 对应的函数过程中，根据当前的输⼊符号决定哪个产⽣式候选。
3. 每个产⽣式对应的代码中，按照从左到右的次序，对于单词符号（终结符），⾮终结符和语义分析分别做以下的⼯作。
（1）对于带有综合属性x的终结符X，把x的值存⼊为X.x设置的变量中。然后产⽣⼀个匹配X的调⽤，并继续读⼊⼀个输⼊符号。
（2）对于每个⾮终结符号B，产⽣⼀个右边带有函数调⽤的赋值语句c=B(b1,b2,…，bk)
（3）对于语义动作，把动作的代码抄进分析器中，⽤代表属性的变量来代替对应属性的每⼀次引⽤。
3.算法流程
1. 每⼀个⾮终结符对应于⼀个函数（⼦过程）；
2. ⾮终结符所对应的右侧产⽣式为函数体；
3. 每遇到⼀个终结符，则需要判断所输⼊字符是否与之匹配，若匹配则读取下⼀个，若不匹配，则进⾏出错处理。
算法过程：
PROCEDURE <；表达式>:
BEGIN
IF SYM=’+’ OR SYM=’-’ THEN
BEGIN
ADVANCE; <；项>;
WHILE SYM=’+’ OR SYM=’-’ DO
BEGIN
isalpha 函数ADVANCE; <；项>;
END
END
ELSE IF SYM=FIRST(<；项>) THEN
BEGIN
<；项>;
WHILE SYM=’+’ OR SYM=’-’ DO
BEGIN
ADVANCE; <；项>;
END
END
ELSE ERROR
END
PROCEDURE <；项>:
BEGIN
IF SYM=’*’ OR SYM=’/’ THEN
BEGIN
ADVANCE; <；因⼦>;
WHILE SYM=’*’ OR SYM=’/’ DO
BEGIN
ADVANCE; <；因⼦>;
END
END
ELSE IF SYM=FIRST(<；因⼦>) THEN
BEGIN
<；因⼦>;
WHILE SYM=’*’ OR SYM=’/’ DO
BEGIN
ADVANCE; <；因⼦>;
END
END
ELSE ERROR
END
PROCEDURE <；因⼦>:
BEGIN
IF SYM=’标识符’ OR SYM=<⽆符号整数> THEN
BEGIN
ADVANCE;
END
ELSE IF SYM=’(’ THEN
BEGIN
<；表达式>
IF SYM=’)’ THEN
BEGIN
ADVANCE;
END
ELSE ERROR
END
ELSE ERROR
END
PROGRAM PAESER
BEGIN
ADVANCE;
<；表达式>；
IF SYM<>’#’ THEN ERROR
END
因此要在如上的基础上构造函数过程，函数中会包含计算属性。
4. 源程序
#include<bits/stdc++.h>
using namespace std;
ifstream infile("F:\\编译原理\\第四次实验\\");//⽂件流
ifstream infile2("F:\\编译原理\\第四次实验\\");//⽂件流
ofstream outfile("F:\\编译原理\\第四次实验\\");//⽂件输出流
map<string,string> word;//应⽤map数据结构形成⼀个string->string的对应
std::map<string,string>::iterator it;//⽤来遍历整个对应关系的迭代器
string str;//读⼊的字符串
string sym;//⽤来指⽰读⼊的符号
string sym2;//⽤来指⽰读⼊的符号
int count1=0,k=0,flag=0,conterr=0,lpnum=0;
string expressionAnalysis();//表达式分析，表达式的中间代码表⽰
string termAnalysis();//项分析，表达式的中间代码表⽰
string factorAnalysis();//因⼦分析，表达式的中间代码表⽰
int expressionAnalysis2();//表达式分析，算数表达式的语义计算
int termAnalysis2();//项分析，算数表达式的语义计算
int factorAnalysis2();//因⼦分析，算数表达式的语义计算
struct quad{//定义四元式
string result;
string arg1;
string arg2;
string op;
};
struct quad quad[50];
void map_init(){//对应关系进⾏初始化，如下只包括了表达式的相关符号
word["+"]="plus";
word["-"]="minus";
word["*"]="times";
word["/"]="slash";
word["="]="eql";
word["("]="lparen";
word[")"]="rparen";
}
void lexanalysis(){//词法分析
char ch;
char a;
string word1;//string变量识别单词
string str;//string变量进⾏字符识别
ostringstream buf;
while(buf&&(ch)) buf.put(ch);//将⽂件中的字符读出来
str= buf.str();//将得到的字符储存到string类型变量中
int csize=str.length();
for(int i=0;i<csize;i++){//对整个字符串进⾏遍历
while(str[i]==' '||str[i]=='\n') i++;//若最开始为空格或换⾏符，则将指针的位置往后移if(isalpha(str[i])){//对标识符和基本字进⾏识别，调⽤库函数isalpha()
word1=str[i++];
while(isalpha(str[i])||isdigit(str[i])){
word1+=str[i++];
}
it=word.find(word1);
it=word.find(word1);
if(it!=d()){//判断是不是基本字，若为基本字则进⾏输出
outfile<<"("<<word[word1]<<","<<word1<<")"<<endl;
}
else{//否则直接输出
outfile<<"(ident"<<","<<word1<<")"<<endl;
}
i--;
}
else if(isdigit(str[i])){//判断是不是常数，调⽤库函数isdigit()
word1=str[i++];
while(isdigit(str[i])){
word1+=str[i++];
}
if(isalpha(str[i])){
outfile<<"error"<<endl;
break;
}
else{
outfile<<"(number"<<","<<word1<<")"<<endl;
}
i--;
}else{//对其他的基本字依次进⾏判断
word1=str[i];
it=word.find(word1);
if(it!=d()){
outfile<<"("<<word[word1]<<","<<word1<<")"<<endl;
}else{
outfile<<"error"<<endl;
break;
}
}
}
infile2.close();
}
int advance(){//⽤来读⼊下⼀个符号
int found1,found2;
if(!getline(infile,str)){
return0;
}
found1=str.find(',',0);
if(found1==-1){
conterr++;
cout<<"语法错误识别字符错误"<<endl;
return-1;
}
found2=str.length();
sym=str.substr(1,found1-1);
sym2=str.substr(found1+1,found2-found1-2);
return1;
}
string newtemp(){//产⽣新变量名t1,t2等
char*p;
char m[12];
p=(char*)malloc(12);
k++;
itoa(k,m,10);
strcpy(p+1,m);
p[0]='t';
string s;
s=p;
return s;
}
void emit(string op,string arg1,string arg2,string result){//产⽣四元式⽤于显⽰    quad[count1].op=op;
quad[count1].arg1=arg1;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。