下载文档原格式
目录1 问题域描述 (3)2 文法及属性文法的描述 (3)2.1 WHILE循环语句的文法 (3)2.2 WHILE循环语句的属性文法 (4)3 语法分析方法及中间代码形式的描述 (4)3.1语法分析方法 (4)3.2中间代码形式描述 (6)4 编译系统的概要设计 (7)4.1词法分析 (7)4.2语法制导翻译 (8)5 详细的算法描述 (8)5.1 文法设计 (8)5.2 算法描述 (8)5.3 源程序代码 (9)6 软件的调试过程和结果测试 (19)6.1调试过程 (19)6.2结果测试 (19)7 使用说明 (20)8 课设总结 (20)9 参考文献 (22)WHILE循环语句的翻译程序设计（简单优先法、输出三地址表示）1 问题域描述while循环语句的翻译程序设计（简单优先法，输出单地址表示），要求完成：（1）用C++语言正确编写程序，完成WHILE循环语句的翻译程序设计。
（2）求能正确进行词法分析，语法分析，并能正确的输出预期结果。
（3）根据指定的文法，判定程序的正确性。
本次课程设计中要求设计一个WHILE循环语句的词法﹑语法及语义分析程序，语法分析选择简单优先法，采用语法制导翻译输出中间代码三元式。
通过设计、编制、调试一个WHILE循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，实现功能。
while循环语句的格式为：while（P）{do A}，其中A为循环体，可为一个或多个赋值语句；P为循环控制条件。
while循环语句首先根据循环控制条件P进行判断，若满足条件则执行循环体A，否则执行下面的程序段；本次课程设计中系统首先要进行词法分析，即从左到右把源文件的字符序列逐个进行扫描，产生一个个的单词序列，作为语法分析的输入从而继续编译过程。
该程序的语法分析读入词法分析的结果，并判断输入语句是否满足while循环语句的文法所描述的形式。
通过简单优先法对语句进行分析，看是否能通过给定的输入串归约到文法的开始符号。
WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）1 系统描述按照课程设计的要求，写一个能识别while循环语句的文法，通过一定的变换使它符合递归下降法的要求，然后按照这个文法编写一个程序，该程序能识别输入的语句是否符合while语句的文法，或者能不能通过文法的开始符号推导出该语句。
该程序应该包括词法分析器，能对输入的语句进行词法分析，然后再对结果进行语法分析。
词法分析器应能识别关键字，标示符，常量，操作符等。
该程序的语法分析器能对输入的语法进行分析，判断输入语句能否满足while循环语句的文法。
通过递归下降的方法对语句进行分析，看能否通过开始符号推导出来。
该程序的语义分析器就是对分析结果进行输出，要求输出结果是三地址形式的。
2 文法及属性文法的描述2．1文法描述<while语句> ::= while (<条件表达式>) (<赋值语句> | <while语句>)<条件表达式> ::= (<标识符>|<无符号整数>）<条件运算符> (<标识符>|<无符号整数>)<标识符> ::= <字母> (<字母>|<数字>)<条件运算符> ::= > | < | =<无符号整数> ::= <数字>（<数字>)<赋值语句> ::= <标识符>=(<标识符> | <数字>) <算术运算符> (<标识符> | <数字>)<算术运算符> ::= + | - | * | /<赋值语句> ::= <标识符>=<标识符> | <数字>2．2递归文法while语句文法：S -> while (B) S | i=EB -> E relop Erelop -> < | = | >E -> E+E | E-E | E*E | E/E | (E) | i | n在编写程序的时候用到的是递归下降法，而递归下降法对文法的要求是不能包含左递归，对上述的文法进行消除左递归之后，得到如下的递归文法：S -> while (B) S | i=EB -> E relop Erelop -> < | = | >E -> (E)F | iF | nFF -> +EF | -EF | *EF | /EF | ε2．3属性文法的描述产生式属性文法S -> while (B) S1 S.begin:=newlabel;S.next:=newlabel;B.true:=newlabel;B.false:=S.next;S1.next:=S.begin;S.code:=gen(S.begin, ‘:’) || B.code ||gen(S.true, ‘:’) ||S1.code || gen(‘goto’,S.begin) || gen(B.false, ‘:’)|| gen(‘goto Lnext’);B -> E1 relop E2 B.place:=newlabel;B.code:=E1.code || relop.code ||E2.code ||gen(B.place ‘:=’, E1.place , relop. place , E2.place); relop -> < | = | > relop.place:=newlabel;relop.code:=gen(‘<’)||gen(‘=’)||gen(‘>’);E -> (E1)F E.place:=newlabel;E.code:=E1.code ||F.code ||gen(E.place ‘:=’ ,‘(’, E1.place , ‘)’, F.place);E -> iF E.palce:=newlabel;E.code:=i.code ||F.code ||gen(E.palce ‘:=’ ,i.place , F.place);E -> nF E.place:=newlabel;E.code:=n.code ||F.code ||gen(E.place ‘:=’ , n.place , F.place);F -> +EF1 F.place:=newlabel;F.code:=E.code || F1.code ||gen(F.place‘:= + ’, E.place , F1.place);F -> -EF1 F.place:=newlabel;F.code:=E.code || F1.code ||gen(F.place‘:= - ’, E.place , F1.place);F -> *EF1 F.place:=newlabel;F.code:=E.code || F1.code ||gen(F.place‘:= * ’, E.place , F1.place);F -> /EF1 F.place:=newlabel;F.code:=E.code || F1.code ||gen(F.place‘:= / ’, E.place , F1.place);F -> ε F.place:=newlabel;F.code:=gen(F.code‘:= ε’);图1 属性文法3 语法分析方法描述按照递归下降分析技术，递归下降识别程序是由一组子程序组成，每个子程序对应于一个非终结符号。
1．题目：将WHILE语句转换成四元式的程序实现设计内容及要求：设计一个语法制导翻译器，将WHILE语句翻译成四元式。
要求：先确定一个定义WHILE语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。
对用户输入的任意一个正确的WHILE语句，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。
1、系统描述通过设计、编制、调试一个WHILE循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。
用语法制导完成语义分析，并将形成的中间代码以四元式的形式输出。
2 、文法及属性文法的描述2．1 文法的描述该文法的产生式如下所示：(1)S->while(B){E}(2)E->AE(3)E->A(4)A->iPA(5)A->i(6)B->iTi(7)B->i其中while、( 、) 、{ 、} 、P、T 、；和i均为终结符，而S、A、B、E这些大写字母均为非终结符。
T表示比较运算符，P表示算术运算符，i表示合法标识符。
2．2 属性文法的描述对该文法的属性文法描述如下：(1) S->while(B){E} prinf(if B goto E else goto next)(2) E->AE print = ·(3) E->A print =(4) A->i P A print(A= P(5) A->i； = i；(6) B->i T i print(B = T(7) B->i = i3 、语法分析方法描述及语法分析表设计3．1 语法分析表设计3．1．1 文法的DFA3．1．2 LR（0）分析方法描述说明LR分析法的规约过程是规范推到的逆过程，所以LR分析过程是一种规范规约的过程。
其分析过程为：由文法构造出该文法项目集，再根据项目集构造该文法的DFA，再判断是否有移进-规约和规约-规约冲突，若没有冲突则该文法为LR(0)的，若有冲突则该文法是SLR（1）的，最后可以构造出LR(0)分析表。
（二）DO-WHILE循环语句的翻译程序设计（简单优先法、输出四元式）一、1.简单优先法的基本思想根据优先关系的定义，将简单优先文法中各文法符号之间的这种关系用一个矩阵表示，称作简单优先矩阵。
PDA读入一个单词后，比较栈顶符号和该单词的优先级，若栈顶符号优先级低于该单词，继续读入；若栈顶符号优先级高于或等于读入符号，则找句柄进行归约，找不到句柄就继续读入。
直到最后栈内只剩下开始符号，输入串读到“＃”为止。
此时识别正确。
可分点描述如下:（1）、对句型中相邻的文法符号规定优先关系，以寻找句型中的句柄;（2）、规定句柄内各相邻符号之间具有相同的优先级;（3）、规定句柄两端符号优先级要比位于句柄之外而又和句柄相邻的符号的优先级高，以先归约句柄;（4）、对于文法中所有符号，只要它们可能在某个句型中相邻，就要为它们规定相应的优先关系，若某两个符号永远不可能相邻，则它们之间就无关系.2.简单优先矩阵用于表示文法符号之间的简单优先关系的矩阵。
3.简单优先法的优缺点优点：技术简单,当做简单优先矩阵是要求较短。
缺点：适用范围小，分析表尺寸太大。
二、源代码实现：#include<iostream>#define MAX 35#include<list>#include<string>#include<fstream>using namespace std;#define TABLE_LEN 8#define STR_LEN 256int zhlen;char sTable[TABLE_LEN+1] = {"+-*/()i#"};//顺序索引int ShipTable[TABLE_LEN][TABLE_LEN] = //优先表{{ 1, 1,-1,-1,-1, 1,-1, 1},{ 1, 1,-1,-1,-1, 1,-1, 1},{ 1, 1, 1, 1,-1, 1,-1, 1},{ 1, 1, 1, 1,-1, 1,-1, 1},{-1,-1,-1,-1,-1, 0,-1,-2},{ 1, 1, 1, 1,-2, 1,-2, 1},{ 1, 1, 1, 1,-2, 1,-2, 1},{-1,-1,-1,-1,-1,-2,-1, 0}};char X,a;char VN[11]={'K','L','P','S','E','G','T','R','F','Q','\0'};char VT[15]={'i','=','<','>','+','-','*','/','(',')','d','w',';','#','\0'};charp[18][6]={"dLwS\0","SP\0",";SP\0","\0","iQE\0","TG\0","+TG\0","-TG\0","\0","FR\0", "*FR\0","/FR\0","\0","(E)\0","i\0","=\0","<\0",">\0"};char stack[MAX];char queue[MAX];int sp,front;intM[10][14]={ {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,-1,-1,-1},{1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,2,-1},{4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{5,-1,-1,-1,-1,-1,-1,-1,5,-1,-1,-1,-1,-1},{-1,-1,-1,-1,6,7,-1,-1,-1,-1,-1,8,8,8},{9,-1,-1,-1,-1,-1,-1,-1,9,-1,-1,-1,-1,-1},{-1,-1,-1,-1,12,12,10,11,-1,-1,-1,12,12,12},{14,-1,-1,-1,-1,-1,-1,-1,13,-1,-1,-1,-1,-1},{-1,15,16,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},};int f=0; int count=0;int c=0;char arr_i[MAX];char var[MAX]; //表格管理int td[MAX];int t=0;int opd=-1;int opr=-1;int id=0;int d=0;char arr[MAX][4];//存放待输出的四元式//char keyword[2][7]={"do\0","while\0"};bool IsCharInStr(char c,char s[]){for(int i=0;s[i]!='\0';i++){if(s[i]==c)return true;}return false;}int GetIndex(char s[],char c){for(int i=0;s[i]!='\0';i++){if(c==s[i])return i;}return -1;}//string GetSubString(char s[],int from,int to){string st;for(int i=from;i<to;i++){st+=s[i];}return st;}/*******************************************翻译赋值表达式********************************************/void translatefuzhi(char *sInput){//栈结构的初始化char Stack[STR_LEN]={0};int index = 0;int top = 1;Stack[0] = '#';list<char> rPolish;list<string> Num;int begin=0;while(sInput[begin]!='='){if(IsCharInStr(sInput[begin],sTable)){cout<<"Equal expression is illegal!"<<endl;return ;}begin++;}Num.push_back(GetSubString(sInput,0,begin));int now = begin+1;int before = begin;rPolish.push_back('i');while(sInput[now]!='\0'){if(IsCharInStr(sInput[now],sTable)){char temp[3]={0};if(now-before>1){temp[0] = 'i';temp[1] = sInput[now];Num.push_back(GetSubString(sInput,before+1,now));}else{temp[0] = sInput[now];}int i=0;while(temp[i]!=0){int left = GetIndex(sTable,Stack[index]);int right = GetIndex(sTable,temp[i]);switch(ShipTable[left][right]){case -1://移入Stack[top++] = temp[i];index = top-1;i++;break;case 0://脱括号if(Stack[index]=='('){Stack[top++] = ')';Stack[index] = 'E';top = index+1;index--;}else//规约{if(top!=2){return;}rPolish.push_back('=');list<char>::iterator iter;list<string>::iterator siter=Num.begin();string fuzhi[256];int d=0,m;for(iter=rPolish.begin();iter!=rPolish.end();iter++){if(*iter=='i'){fuzhi[d++]=*siter;siter++;}else{fuzhi[d++]=*iter;}}m=d;string op1,op2;int flag,xiabiao=0;for(d=0;d<m;d++)cout<<"("<<fuzhi[d]<<","<<op1<<","<<op2<<","<<"T"<<xiabiao<<")"<<endl;fuzhi[d] = "T";fuzhi[d]+=(xiabiao+'0');xiabiao++;}//cout<<fuzhi[d];}return;}i++;break;case 1://归约if(Stack[index]=='i'){rPolish.push_back('i');Stack[index] = 'E';index--;}else{rPolish.push_back(Stack[index]);Stack[index-1] = 'E';top = index;index-=2;}break;default:return;}}before=now;}now++;}}int len(char str[]){int i=0;while(str[i]!='\0')i++;return i;}int index(char ch,char str[]){int i=0;while(str[i]!='\0'){if(ch!=str[i])i++;else break;}if(str[i]=='\0')return -1;return i;}void err(int n){if(n==1)cout<<"字符不匹配"<<endl;else if(n==2)cout<<"字符没有出现在产生式中"<<endl;else if(n==3)cout<<"没有找到合适的¨选产式"<<endl;else cout<<"该句子是文法语言的句子"<<endl;}void print(){cout<<"(";if(count<10)cout<<'0';cout<<count<<")";int i;for(i=0;i<=sp;i++)cout<<stack[i];for(;i<=20;i++)cout<<" ";for(i=0;i<front;i++)cout<<" ";for(;queue[i]!='#';i++)cout<<queue[i];cout<<queue[i];for(;i<=20;i++)cout<<" ";}void semantic(){if(VT[opr]=='='){arr[d][0]='=';arr[d][1]=arr_i[opd];arr[d][2]=id;arr[d][3]='--';id++;} else if(opr==-2){arr[d][0]='=';arr[d][1]=id-1;arr[d][2]=arr_i[opd];arr[d][3]='--';}else {arr[d][0]=VT[opr];arr[d][1]=arr_i[opd];arr[d][2]=id;if(VT[opr]!='<'&&VT[opr]!='>')arr[d][3]=id-1;else arr[d][3]=id+1;id++;}d++;}void syntax(){//语法分析int n;count++;print();X=stack[sp];a=queue[front];if(X=='#'&&a=='#')f=4;if(X<'A'||X>'Z'){if(X==a){sp--;front++;if(a!='i'){if(a!='d'&&a!='w'&&a!=';'&&a!='#'){opr=index(a,VT);semantic();}else if(a==';'||a=='w'||a=='#'){opr=-2;semantic();}cout<<'\t'<<'\''<<a<<"'匹配"<<endl;}else {opd=c;cout<<'\t'<<'\''<<arr_i[c++]<<"'匹配"<<endl;}}else f=1;}else {int tx=index(X,VN);int ta=index(a,VT);n=M[tx][ta];td[t++]=M[tx][ta];if(ta==-1){f=2;cout<<a<<endl;}else if(n==-1)f=3;else {sp--;cout<<'\t'<<X<<"->";if(len(p[n])!=0){for(inti=len(p[n])-1;i>=0;i--){stack[++sp]=p[n][i];cout<<p[n][len(p[n])-1-i];}cout<<endl;}else cout<<"空串"<<endl;}}if(f==0)syntax();else {td[t]='-1';err(f);}}void lexical(){ //词法分析int i,j,d;char ch;j=d=0;for(i=0;var[i]!='#';i++){ch=var[i];if(ch=='d'&&var[i+1]=='o'){cout<<"do"<<'\t'<<"keword"<<endl;queue[j++]='d';i+=1;}else if(ch=='w'){ch=var[i+1];if(ch=='h'){ch=var[i+2];if(ch=='i'){ch=var[i+3];if(ch=='l'){ch=var[i+4];if(ch=='e'){ch=var[i+5];}}}}cout<<"while"<<'\t'<<"keyword"<<endl;queue[j++]='w';i+=4;}else if(index(ch,VT)<=0){if(ch!='{'&&ch!='}'&&ch!='('&&ch!=')'){cout<<ch<<'\t'<<"variable:i["<<d++<<"]"<< endl;arr_i[d-1]=ch;queue[j++]='i';}else cout<<ch<<'\t'<<"bound"<<endl;}else if(index(ch,VT)>0){cout<<ch<<'\t'<<"operator"<<endl;queue[j++]=ch;} }queue[j]='#';for(i=0;queue[i]!='#';i++)cout<<queue[i];cout<<endl;}int main(){int i=0,j=0;int len,length;char temp;char S='K';sp=front=0;stack[0]='#';sp++;stack[1]='K';cout<<" ****************************"<<endl;cout<<" * DO-WHILE循环语句*"<<endl;cout<<" * (简单优先法输出四元式) *"<<endl;cout<<" ****************************"<<endl;ifstream table;table.open("dowhile.txt");if(!table){cout<<"error!";}table.seekg(0,ios::end);length = table.tellg();table.seekg(0,ios::beg);while(length!=table.tellg()){table.read((char*)&temp,1);var[i]=temp;i++;if(var[i]==' ')i--;if(var[i]=='#')break;}table.close();len=i;var[i]='\0';cout<<"词法分析"<<endl;lexical();char fuzhi[20];int flag1,fuzhilen;int s=0; for(i=0;i<len;i++){if(var[i]==';'){flag1=i;}}fuzhilen=flag1-2;for(i=3;i<flag1;i++){fuzhi[s++]=var[i];}fuzhi[s]='#';char shuru;char zh[100];int kaishi=0; zh[0]='d';for(kaishi=1;kaishi<s+1;kaishi++){zh[kaishi]=fuzhi[kaishi-1];}zh[kaishi++]=';';zh[kaishi++]='W';for(i=flag1+8;i<len;i++){if(var[i]=='}')break;else{zh[kaishi++]=var[i];}}zh[kaishi++]='#';zhlen=kaishi;cout<<"输出四元式"<<endl;cout<<"do"<<endl;translatefuzhi(fuzhi);cout<<"("<<var[flag1+9]<<","<<var[flag1+8]<<","<<var[flag1+10]<<","<<"T2"<<") "<<endl;cout<<"if T2=true goto T0"<<endl;return 0;}三、测试结果：词法分析部分：输出四元式：四、课程小结：这次编译原理课程设计的题目是用简单优先分析法进行DO-WHILE循环语句的语法分析,并输出四元式.设计的特点是利用定义每个终极符和非终极符之间优先关系,来进行符号的移进与规约,如果栈顶符号优先级低于该单词，继续读入；若栈顶符号优先级高于或等于读入符号，则找句柄进行归约，找不到句柄就继续读入。
WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）1 系统描述按照课程设计的要求，写一个能识别while循环语句的文法，通过一定的变换使它符合递归下降法的要求，然后按照这个文法编写一个程序，该程序能识别输入的语句是否符合while语句的文法，或者能不能通过文法的开始符号推导出该语句。
该程序应该包括词法分析器，能对输入的语句进行词法分析，然后再对结果进行语法分析。
词法分析器应能识别关键字，标示符，常量，操作符等。
该程序的语法分析器能对输入的语法进行分析，判断输入语句能否满足while循环语句的文法。
通过递归下降的方法对语句进行分析，看能否通过开始符号推导出来。
该程序的语义分析器就是对分析结果进行输出，要求输出结果是三地址形式的。
2 文法及属性文法的描述2．1文法描述语句 > ::= while (< 条件表达式 > (< 赋值语句 > | 语句 ><条件表达式> ::= (<标识符>|<无符号整数>）<条件运算符> (<标识符>|<无符号整数><标识符> ::= <字母> (<字母>|<数字><条件运算符> ::= > | < | =<无符号整数> ::= <数字>（<数字><赋值语句> ::= <标识符>=(<标识符> | <数字> <算术运算符> (<标识符> | <数字><算术运算符> ::= + | - | * | /<赋值语句> ::= <标识符>=<标识符> | <数字>2．2递归文法while语句文法：S -> while (B S | i=EB -> E relop Erelop -> < | = | >E -> E+E | E-E | E*E | E/E | (E | i | n在编写程序的时候用到的是递归下降法，而递归下降法对文法的要求是不能包含左递归，对上述的文法进行消除左递归之后，得到如下的递归文法：S -> while (B S | i=EB -> E relop Erelop -> < | = | >E -> (EF | iF | nFF -> +EF | -EF | *EF | /EF | ε2．3属性文法的描述产生式属性文法S -> while (B S1S.begin:=newlabel;S.next:=newlabel;B.true:=newlabel;B.false:=S.next;S1.next:=S.begin;S.code:=gen(S.begin, ‘:’ || B.code||gen(S.true, ‘:’ ||S1.code || gen(‘goto’,S.begin ||gen(B.false, ‘:’|| gen(‘goto Lnext’;B -> E1 relop E2 B.place:=newlabel;B.code:=E1.code || relop.code ||E2.code ||gen(B.place ‘:=’ , E1.place , r elop.place , E2.place;relop -> < | =relop.place:=newlabel;| >relop.code:=gen(‘<’||gen(‘=’||gen(‘>’;E -> (E1F E.place:=newlabel;E.code:=E1.code ||F.code ||gen(E.place ‘:=’ ,‘(’, E1.place , ‘’, F.place;E -> iF E.palce:=newlabel;E.code:=i.code ||F.code ||gen(E.palce ‘:=’ ,i.place , F.place;E -> nF E.place:=newlabel;E.code:=n.code ||F.code ||gen(E.place ‘:=’ , n.place , F.place;F -> +EF1 F.place:=newlabel;F.code:=E.code || F1.code ||gen(F.place‘:= + ’, E.place , F1.place;F -> -EF1 F.place:=newlabel;F.code:=E.code || F1.code ||gen(F.place‘:= - ’, E.place , F1.place;F -> *EF1 F.place:=newlabel;F.code:=E.code || F1.code ||gen(F.place‘:= * ’, E.place , F1.place;F -> /EF1 F.place:=newlabel;F.code:=E.code || F1.code ||gen(F.place‘:= / ’, E.place , F1.place;F -> ε F.place:=newlabel;F.code:=gen(F.code‘:= ε’;图1 属性文法3 语法分析方法描述按照递归下降分析技术，递归下降识别程序是由一组子程序组成，每个子程序对应于一个非终结符号。
控制语句的翻译四元式例题及答案
1. 例题：if语句
高级语言代码：
python
if x > 5:
y = x + 10
else:
y = x - 10
翻译四元式：
1: if x > 5 goto 4
2: y = x + 10
3: goto 5
4: y = x - 10
5: (end if)
答案解析：
- 第1行表示条件判断，如果x大于5，则跳转到第4行执行。
- 第2行为if语句为真时的语句，将x加10赋值给y。
- 第3行为跳转到if语句结束位置的标记。
- 第4行为if语句为假时的语句，将x减10赋值给y。
- 第5行为if语句结束位置的标记。
2. 例题：while循环语句
高级语言代码：
python
while x > 0:
y = y + x
x = x - 1
翻译四元式：
1: (start while)
2: if x > 0 goto 4
3: goto 5
4: y = y + x
5: x = x - 1
6: goto 2
7: (end while)
答案解析：
- 第1行为while循环的起始位置。
- 第2行为条件判断，如果x大于0，则跳转到第4行执行循环体内的语句。
- 第3行为否则跳转到while循环结束位置的标记。
- 第4行为循环体内的语句，将y加上x的值。
- 第5行为循环体内的语句，将x减1。
- 第6行为跳转回while循环起始位置的标记。
- 第7行为while循环结束位置的标记。
实验3 语义分析实验报告一、实验目的二、通过上机实习, 加深对语法制导翻译原理的理解, 掌握将语法分析所识别的语法成分变换为中间代码的语义翻译方法。
三、实验要求四、采用递归下降语法制导翻译法, 对算术表达式、赋值语句进行语义分析并生成四元式序列。
五、算法思想1.设置语义过程。
（1）emit(char *result,char *ag1,char *op,char *ag2)该函数的功能是生成一个三地址语句送到四元式表中。
四元式表的结构如下:struct{ char result[8];char ag1[8];char op[8];char ag2[8];}quad[20];(2) char *newtemp()该函数回送一个新的临时变量名, 临时变量名产生的顺序为T1, T2, …char *newtemp(void){ char *p;char m[8];p=(char *)malloc(8);k++;itoa(k,m,10);strcpy(p+1,m);p[0]=’t’;return(p);}六、 2.函数lrparser 在原来语法分析的基础上插入相应的语义动作: 将输入串翻译成四元式序列。
在实验中我们只对表达式、赋值语句进行翻译。
源程序代码:#include<stdio.h>#include<string.h>#include<iostream.h>#include<stdlib.h>struct{char result[12];char ag1[12];char op[12];char ag2[12];}quad;char prog[80],token[12];char ch;int syn,p,m=0,n,sum=0,kk; //p是缓冲区prog的指针, m是token的指针char *rwtab[6]={"begin","if","then","while","do","end"};void scaner();char *factor(void);char *term(void);char *expression(void);int yucu();void emit(char *result,char *ag1,char *op,char *ag2);char *newtemp();int statement();int k=0;void emit(char *result,char *ag1,char *op,char *ag2){strcpy(quad.result,result);strcpy(quad.ag1,ag1);strcpy(quad.op,op);strcpy(quad.ag2,ag2);cout<<quad.result<<"="<<quad.ag1<<quad.op<<quad.ag2<<endl;}char *newtemp(){char *p;char m[12];p=(char *)malloc(12);k++;itoa(k,m,10);strcpy(p+1,m);p[0]='t';return (p);}void scaner(){for(n=0;n<8;n++) token[n]=NULL;ch=prog[p++];while(ch==' '){ch=prog[p];p++;}if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){m=0;while((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){token[m++]=ch;ch=prog[p++];}token[m++]='\0';p--;syn=10;for(n=0;n<6;n++)if(strcmp(token,rwtab[n])==0){syn=n+1;break;}}else if((ch>='0'&&ch<='9')){{sum=0;while((ch>='0'&&ch<='9')){sum=sum*10+ch-'0';ch=prog[p++];}}p--;syn=11;if(sum>32767)syn=-1;}else switch(ch){case'<':m=0;token[m++]=ch;ch=prog[p++];if(ch=='>'){syn=21;token[m++]=ch;}else if(ch=='='){syn=22;token[m++]=ch;}else{syn=23;p--;}break;case'>':m=0;token[m++]=ch;ch=prog[p++];if(ch=='='){syn=24;token[m++]=ch;}else{syn=20;p--;}break;case':':m=0;token[m++]=ch;ch=prog[p++];if(ch=='='){syn=18;token[m++]=ch;}else{syn=17;p--;}break;case'*':syn=13;token[0]=ch;break; case'/':syn=14;token[0]=ch;break; case'+':syn=15;token[0]=ch;break; case'-':syn=16;token[0]=ch;break; case'=':syn=25;token[0]=ch;break; case';':syn=26;token[0]=ch;break; case'(':syn=27;token[0]=ch;break; case')':syn=28;token[0]=ch;break; case'#':syn=0;token[0]=ch;break; default: syn=-1;break;}}int lrparser(){//cout<<"调用lrparser"<<endl;int schain=0;kk=0;if(syn==1){scaner();schain=yucu();if(syn==6){scaner();if(syn==0 && (kk==0))cout<<"success!"<<endl;}else{if(kk!=1)cout<<"缺end!"<<endl;kk=1;}}else{cout<<"缺begin!"<<endl;kk=1;}return(schain);}int yucu(){// cout<<"调用yucu"<<endl;int schain=0;schain=statement();while(syn==26){scaner();schain=statement();}return(schain);}int statement(){//cout<<"调用statement"<<endl;char *eplace,*tt;eplace=(char *)malloc(12);tt=(char *)malloc(12);int schain=0;switch(syn){case 10:strcpy(tt,token);scaner();if(syn==18){scaner();strcpy(eplace,expression());emit(tt,eplace,"","");schain=0;}else{cout<<"缺少赋值符!"<<endl;kk=1;}return(schain);break;}return(schain);}char *expression(void){char *tp,*ep2,*eplace,*tt;tp=(char *)malloc(12);ep2=(char *)malloc(12);eplace=(char *)malloc(12);tt =(char *)malloc(12);strcpy(eplace,term ()); //调用term分析产生表达式计算的第一项eplacewhile((syn==15)||(syn==16)){if(syn==15)strcpy(tt,"+");else strcpy(tt,"-");scaner();strcpy(ep2,term()); //调用term分析产生表达式计算的第二项ep2strcpy(tp,newtemp()); //调用newtemp产生临时变量tp存储计算结果emit(tp,eplace,tt,ep2); //生成四元式送入四元式表strcpy(eplace,tp);}return(eplace);}char *term(void){// cout<<"调用term"<<endl;char *tp,*ep2,*eplace,*tt;tp=(char *)malloc(12);ep2=(char *)malloc(12);eplace=(char *)malloc(12);tt=(char *)malloc(12);strcpy(eplace,factor());while((syn==13)||(syn==14)){if(syn==13)strcpy(tt,"*");else strcpy(tt,"/");scaner();strcpy(ep2,factor()); //调用factor分析产生表达式计算的第二项ep2strcpy(tp,newtemp()); //调用newtemp产生临时变量tp存储计算结果emit(tp,eplace,tt,ep2); //生成四元式送入四元式表strcpy(eplace,tp);}return(eplace);}char *factor(void){char *fplace;fplace=(char *)malloc(12);strcpy(fplace,"");if(syn==10){strcpy(fplace,token); //将标识符token的值赋给fplacescaner();}else if(syn==11){itoa(sum,fplace,10);scaner();}else if(syn==27){scaner();fplace=expression(); //调用expression分析返回表达式的值if(syn==28)scaner();else{cout<<"缺)错误!"<<endl;kk=1;}}else{cout<<"缺(错误!"<<endl;kk=1;}return(fplace);}void main(){p=0;cout<<"**********语义分析程序**********"<<endl;cout<<"Please input string:"<<endl;do{cin.get(ch);prog[p++]=ch;}while(ch!='#');p=0;scaner();lrparser();}七、结果验证1、给定源程序begin a:=2+3*4; x:=(a+b)/c end#输出结果2、源程序begin a:=9; x:=2*3-1; b:=(a+x)/2 end#输出结果八、收获（体会）与建议通过此次实验, 让我了解到如何设计、编制并调试语义分析程序, 加深了对语法制导翻译原理的理解, 掌握了将语法分析所识别的语法成分变换为中间代码的语义翻译方法。
1、系统描述 (2)1.1、实验思想 (2)1.2、设计内容 (2)1.3、翻译过程 (2)1.3.1、词法分析： (2)1.3.2、语法分析： (3)1.3.3、中间代码生成： (4)1.3.4、属性文法： (4)2、递归下降法 (4)2.1、递归下降法的主要思想： (4)2.2、用程序表示递归子程序的内部结构： (4)2．3、递归下降法对文法的限制： (5)3、语法制导翻译 (5)3.1、翻译任务的处理过程 (5)3.2、语法制导翻译： (5)3．3、基于属性文法的处理方法 (6)4、中间代码形式的描述及中间代码序列的结构设计 (6)5、简要的分析与概要设计 (6)5.1、词法分析： (6)5.2源代码 (8)5.3 运行结果 (9)6、测试方法和测试结果 (15)6.1测试过程 (15)6.2测试结论 (17)7、课程设计总结 (18)8、参考文献 (19)1、系统描述1.1、实验思想通过设计、编制、调试一个FOR循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，实现词法分析程序对单词序列的词法检查和分析，并且实现对单词序列的语法分析、语义分析以及中间代码生成。
1.2、设计内容本设计按照要求设计出for语句的简单文法，并使用递归下降分析法对用户输入的程序进行分析和翻译。
对下列正确的程序输入：for i=1 step 1 until 10 do k=j #结果程序要对该输入进行词法分析，然后利用递归下降的分析法对词法分析得到的单词序列进行语法分析，经过语法制导翻译显示出等价的三地址表示的中间代码。
对于错误的程序输入，如：For i=1 step 1 until 10 k=j#结果程序要指出程序出错。
1.3、翻译过程1.3.1、词法分析：词法分析是计算机科学中将字符序列转换为单词（Token）序列的过程。
进行语法分析的程序或者函数叫作词法分析器（Lexical analyzer，简称Lexer），也叫扫描器（Scanner）。
课程设计题目WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）学院计算机科学与技术学院专业计算机科学与技术班级0806姓名张方纪指导教师郭羽成2010 年 1 月7 日课程设计任务书学生姓名：张方纪专业班级：计算机0806班指导教师：郭羽成工作单位：计算机科学与技术学院题目: WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。
实践：计算机实验室提供计算机及软件环境。
如果自己有计算机可以在其上进行设计。
要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1）写出符合给定的语法分析方法的文法及属性文法。
（2）完成题目要求的中间代码三地址表示的描述。
（3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。
（4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。
（5）设计报告格式按附件要求书写。
课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。
时间安排：设计安排一周：周1、周2：完成系统分析及设计。
周3、周4：完成程序调试及测试。
周5：撰写课程设计报告。
设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。
设计报告书收取时间：设计周的次周星期一上午10点。
指导教师签名： 2010年 11月 23日系主任（或责任教师）签名： 2010年 11月 23日WHILE循环语句的翻译程序设计（递归下降法、输出三地址表示）1任务使用C++语言编写一个while循环语句的翻译程序，使用递归下降法进行语法分析，输出三地址码表示。
武汉理工大学《数据结构》课内实践报告学号：0121210340314课内实践报告课程名称编译原理WHILE 循环语句的翻译程序设计设计题目（递归下降法，输出四元式）学院计算机科学与技术专业班级计算机1203班姓名闵丹枫指导教师林泓2014年12月8 日武汉理工大学《数据结构》课内实践报告课程设计任务书学生姓名：闵丹枫专业班级：计算机1203班指导教师：林泓工作单位：计算机科学与技术学院题目：WHILE循环语句的翻译程序设计（递归下降法、输出四元式）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。
实践：计算机实验室提供计算机及软件环境。
如果自己有计算机可以在其上进行设计。
要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1）写出符合给定的语法分析方法的文法及属性文法。
（2）完成题目要求的中间代码四元式的描述。
（3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。
（4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。
（5）设计报告格式按附件要求书写。
课程设计报告书正文的内容应包括：1系统描述（问题域描述）；2文法及属性文法的描述；3语法分析方法描述及语法分析表设计；4按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5编译系统的概要设计；6详细的算法描述（流程图或伪代码）；7软件的测试方法和测试结果；8研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）9参考文献（按公开发表的规范书写）。
时间安排：设计安排一周：周1、周2:完成系统分析及设计。
周3、周4:完成程序调试及测试。
周5:撰写课程设计报告。
设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。
设计报告书收取时间：设计周的次周星期一上午10点。
指导教师签名: 2014 年9月1日WHILE循环语句的翻译程序设计（递归下降法、输出四元式）一.系统描述1.1问题描述设计一个WHIL B布尔表达式〉DO〈赋值语句〉循环语句的词法、语法及语义分析程序，语法分析选择递归下降法，采用用语法制导翻译输出中间代码四元式。
1.2主要任务设计一个能识别while循环语句的文法，消除左递归，使文法符合LL（1）文法。
利用递归下降法编写一个集词法分析，语法分析和语义分析为一体的程序。
该程序首先可以检查输入语句是否符合词法要求，若符合则继续识别输入的语句是否符合while语句的文法，若符合则进行语义分析，输出用四地址代码表示的中间代码。
文法及属性文法的描述2.1文法的描述扩充巴科斯-瑙尔范式（EBNF :vwhile语句> ::=while （< 条件语句>）do{ < 赋值语句> }<条件语句> ::= < 表达式><条件运算符> < 表达式>< 表达式> ::= < 表达式> + <表达式2> | < 表达式> - < 表达式2> | < 表达式2><表达式2>::=<表达式2> * <表达式3> |<表达式2> / <表达式3> | <表达式3><表达式3>::=（<表达式>）| <标识符>|<数字><赋值语句>::=< 标识符>=<表达式>;根据以上写出来的While循环语句的文法表示如下：1. S -> while （A） do {B}2. A -> CDC3. D -> > | = | < | >= |<=4. C -> C+E | C-E | E5. E -> E*F | E/F | E6. F -> （C） | i | n对以上文法消除左递归，最后得到的文法为:1. S->while (A) do {B}2. A->CDC3. D-> > | = | < | >= | <=4. C->EG5. G->+EG | -EG | &6. E->FH7. H->*FH | / F H | &8. F->(C) | i | n9. B->i=C;2.1属性文法的描述(1)任一非终结符B都不是左递归的，否则会产生死循环。
⑵对 A 的任意两个右部B i , B j ,有：first( B i) A first( B j)= ©, First( B i)表B i所能导出串的第一个符号的集合。
显然，每个 B i的first( B i)是互不相同的，否则则无法判断应执行哪个( i )C-->EG{C.PIace:=n ewtemp;Emit(C.PIace':='E.PIace G.place)}G->+EG{G.Place:=newtemp;Emit(G1.Place':=''+'E.Place G2.place)}G->-EG{G.Place:=newtemp;Emit(G1.Place':=''-'E.Place G2.place)}G-> £{G.Place:=newtemp; Emit(G.Place':='''}H->*FH{H.Place:=newtemp;Emit(H1.Place':=''*'F.Place H2.place)}H-> / FH{H.Place:=newtemp;Emit(H1.Place':=''+'F.Place H2.place)}H-> £{G.Place:=newtemp;Emit(H1.Place':=''+'E.Place H2.place)}F->(C){F.Place:=C.Place}B->i=C;{p:=lookup(i. name) If p!=nil the n Emit(p':='C.PIace Elseerror)}语法分析方法描述3. 1语法分析方法描述递归下降法是一种比较简单直观，易于构造的语法分析方法。
他要求文法满足LL( 1) 文法，他的设计思想是对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的单词(或串)，当某非终结符的产生式有多个候选时，能够按LL (1) 形式可唯一地确定选择某个候选进行推导。
它的优点是简单直观，易于构造，很多编译系统所实现缺点是对文法要求很高，由于递归调用多，影响分析器的效率。
递归下降程序是由一组子程序组成，每个子程序对应于一个非终结(S,A,B,C,D,E,F,G,H) 每个子程序处理相应句型中相对于此非终结符号的产生式。
在定义文法时，是递归定义的，所以这些子程序也是递归的。
当一个子程序调用另一个子程序时，原子程序顺序执行语句，即总是先执行被调用的子程序，然后再执行后继的程序。
程序中9个子程序，其中S是开始符号，也是递归下降分析的入口，通过调用词法分析器进行单词分析，并通过word=I.Yufa_Queue.fro nt() 来得到当前所分析到的单词，然后在递归语法分析中根据这个单词分析下一步要执行的子程序。
其中要注意的是，当子程序G()和H()中出现匹配的是空字符串时，不做单词处理，该所取得的单词，应该为下一个匹配产生做准备。
3. 2递归下降法实现的原理设A是一个非终结符：1A—B2A fpn则写((A) - if char € first( B 1 then Z ( B 1 )else if char€ first( B 2tl)en Z ( B 2 )else …if char € first( B n ) then Z ( B n)else ERROR其中Z ( B i)表示调用处理符号串B i的子程序。
对A的任一右部i设为：B i = y1 y2 , yn 则定义Z ( B i) begin Z (y1); Z (y2); , ; Z (yn) end其中yj可分为下列两种情况(j=1, , ,n):1) yj € VT,则Z ( yj) if char 工yj then ERROR else READ(char)2) yj € VN,则Z (yj)表示调用关于yj的递归子程序。
四•中间代码形式的描述及中间代码序列的结构设计4.1四元式形式中间代码为四元式，按照要求，要输出四元式一个四元式是一个带有四个域的记录结构，这四个域分别称为op、arg1、arg2及result。
域op包含一个代表运算符的内部码。
语句while a<b do a=a+b 的四元式输出：1 ( <, a , b , 3 )2 ( j，亠,6 )3 ( + , a , b , n )4 (=,n，—,a)5 ( j , _ , _ , 1)6五.编译系统的概要设计5.1全局程序的概要设计递归下降分析技术就是通过对每个非终结符编写一个子程序来实现它的操作，然后通过递归的调用来实现对输入字符串的分析，这其中还包括对输入字符串的词法分析。
在词法分析的时，得到的字符单词要和关键字比较，看是否是关键字，根据比较结果进行返回相应的单词类型。
单词类型主要包括界限符，关键字，常量，标识符，运算符等，每种符号都是一种类型。
在语法分析程序中，根据词法得到的结果，进行判断是否是当前需要的单词类型，如果不是就说明输入字符串不能由该文法推导出来；如果是当前需要的类型，就相应得做该单词类型分支程序。
根据文法可以得到这个递归下降程序可以分析while语句，在文法的开始符号S开始进行递归调用，因此这个文法的递归中就要考虑到调用以及递归。
在递归子程序中，在嵌套调用其他子程序时都是有一定条件的，当满足这个条件的时候该程序可以按照满足的条件执行下去，当没有满足程序中的条件时就会显示语法错误。
5.2词法分析词法分析程序的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号的中间程序。
词法分析检查的错误主要是挑出源程序中出现的非法符号。
所谓非法符号是指不是程序设计语言中允许出现的符号，就像自然语句中的错字。
5.3递归下降翻译器的设计对每个非终结符A构造一个函数过程，对A的每个继承属性设置一个形式参数，函数的返回值为A的综合属性，A对应的函数过程中，为出现在A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。
