WHILE循环语句的翻译程序设计(简单优先法,三地址输出)_百度文库

1、目录1 问题域描述.32 文法及属性文法的描述.32.1 WHILE循环语句的文法.32.2 WHILE循环语句的属性文法.43 语法分析方法及中间代码形式的描述.43.1语法分析方法.43.2中间代码形式描述.64 编译系统的概要设计.74.1词法分析.74.2语法制导翻译.85 详细的算法描述.85.1 文法设计.85.2 算法描述.85.3 源程序代码.96 软件的调试过程和结果测试.196.1调试过程.196.2结果测试.197 使用说明.208 课设总结.209 参考文献.22WHILE循环语句的翻译程序设计（简单优先法、输出三地址表示）1 问题域描述while循环语句的翻译程序设计

2、（简单优先法，输出单地址表示），要求完成：（1） 用C+语言正确编写程序，完成WHILE循环语句的翻译程序设计。（2） 求能正确进行词法分析，语法分析，并能正确的输出预期结果。（3） 根据指定的文法，判定程序的正确性。本次课程设计中要求设计一个WHILE循环语句的词法语法及语义分析程序，语法分析选择简单优先法，采用语法制导翻译输出中间代码三元式。通过设计、编制、调试一个 WHILE循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，实现功能。while循环语句的格式为：while（P）do A，其中A为循环体，可为一个或多个赋值语句；P为循环控制条件。while循环语句首先根据循环控

3、制条件P进行判断，若满足条件则执行循环体A，否则执行下面的程序段；本次课程设计中系统首先要进行词法分析，即从左到右把源文件的字符序列逐个进行扫描，产生一个个的单词序列，作为语法分析的输入从而继续编译过程。该程序的语法分析读入词法分析的结果，并判断输入语句是否满足while循环语句的文法所描述的形式。通过简单优先法对语句进行分析，看是否能通过给定的输入串归约到文法的开始符号。在语法分析的同时进行语义分析，最后输出三元式的代码。2 文法及属性文法的描述2.1WHILE循环语句的文法定义一个文法，文法G(S如下：S-> while(PA;A->id=E;E->TE'E

4、9;->+TE' | -TE' | eT->FT'T'->*FT' | /FT' | eF->(E | idP->E rop idrop-> > | < | >= | <= | != | =2.2 WHILE循环语句的属性文法产生式语义规则Swhile PA S.addr:=newlabel;E.true:=newlabel;E.false:=S.next;S1.next:=S.begin;S.code:=gen(S.begin:E。codegen(E.true: S1.codegen(

5、goto S.begin3 语法分析方法及中间代码形式的描述3.1语法分析方法简单优先分析法是按照文法符号（终结符和非终结）的优先关系确定句柄的，因此我们首先介绍任意两个文法符号之间的优先关系是怎样确定的，及如何构造优先关系表。首先定义优先关系的表示：X=Y 表示X和Y的优先关系相等X>Y 表示X的优先性比Y的优先性大X 表示 X 的优先性比 Y 的优先性小 这样我们就可对已知文法中的任意两个文法符号X，Y按其在举行中可能会出现的相邻关系确定他们的优先关系。对文法的要求高，而且也要把文法符号的关系首先表示出来，这普遍性不是太好。/* S w h i l e E d o B a = + 1

6、 ; > ( b c # */* S */ N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 1 ,/* w/ N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N ,/* h*/ N, N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N ,/* i/ N, N, N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N

7、, N, N, N, -1, N, N ,/* l/ N, N, N, N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N ,/* e */ N, N, N, N, N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N , /* E*/ N, N, N, N, N, N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N ,/* d*/ N, N, N, N, N, N, N, N, 0, N, N, N, N, N, N

8、, N, N, N, N, N, N, N, N ,/* o*/ N, N, N, N, N, N, N, N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N, N ,/* N, N, N, N, N, N, N, N, N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N ,/* A/ N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 0, N, N, N, N ,/*/ N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N,

9、 N, N, N, N, N, 0, N ,/* a */ N, N, N, N, N, N, N, N, N, N, N, N, N, N, 0, N, N, 0, N, N, N, N, N ,/* = */ N, N, N, N, N, N, N, N, N, N, N, N, 0, N, N, N, N, N, N, N, N, N, N ,/* + */ N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 0, N, N, N, N, N, N, N ,/* 1 */ N, N, N, N, N, N, N, N, N, N, N, N, N,

10、N, N, N, 0, N, N, N, N, N, N ,/* ; */ N, N, N, N, N, 1, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N ,/* > */ N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 0, N, N, N ,/* ( */ N, N, N, N, N, N, N, N, N, N, N, 0, -1, N, N, N, N, N, N, N, N, N, N ,/* b */ N, N, N, N, N, N, N, N, N,

11、N, N, N, N, N, N, N, N, N, N, N, N, 1, N ,/* c */ N, N, N, N, N, N, N, N, N, N, N, N, N, 0, N, N, N, N, N, N, N, N, N ,/* */ N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 1 ,/* # */ -1, -1, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 0 ;其中N表示的是没有优先关系， -1表示优先级小于，0表

12、示优先级相同，1表示优先级大于3.2中间代码形式描述三元式是一种普遍采用的中间代码形式。它由三个部分组成：算符op，第一和第二运算对象ARG1和ARG2。运算对象有时候指用户自己定义的变量。对c=a+1翻译结果如下1）（+，a，1）2），（=, c, (1）为方便和直观，将while语句翻译为if a> b goto do.addr4 编译系统的概要设计本程序开始，需先对输入字符串进行词法分析，将其识别为一个个独立的单词序列，得到的字符单词要和关键字比较，看是否是关键字，根据比较结果进行返回相应的单词类型。单词类型主要包括标识符，关键字，常量，运算符和分界符。在语法分析程序中，根据词法分

13、析得到的结果，进行判断是否是当前需要的单词类型，如果不是就说明输入字符串不能由该文法推导出来；如果是当前需要的类型，就相应得做该单词类型分支程序。根据简单优先法分析的字符串，看是否能得到接受状态。此外，在进行语法分析的同时进行语义分析，审查程序有无语义错误，每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。在进行了上述的语法分析和语义分析阶段的工作之后，将源文件变成三元式表示。源程序目录下建立“input.txt”文本文档，在文档中输入while(PA格式的WHILE语句，再通过调用程序中的get_word(string word函数进行对文本文档中语句的读取操作

14、。4.1词法分析词法分析是编译的第一阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个单词序列，用于语法分析。编程中，建立操作数栈和运算符栈，设定运算符优先级。对于读取的字符进行判定，若是运算符，就与栈顶符号比较优先级，高则入栈，否则栈内运算符出栈；若是非运算符，则送入操作数栈。4.2语法制导翻译在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译。属性文法的每个符号有属性，所以每个符号入栈时，必须连属性一起入栈，这样，栈符号就由文法符号及存放该符号属性的域所组成。由于属性类型不同，属性域存放的内容就要根据属性的类型来定。有的

15、可能直接存放属性值，也有的存放的是指向属性值的指针。对于综合属性，其属性域不存放其属性值，而是存放一个指针，指向存贮该属性值的单元。对于继承属性，其属性域直接保存其属性值。继承属性的属性域刚入栈时为空，但是在该栈符号变成栈顶符号之前的某一时刻，它们必须接受相应的属性值，即在成为栈顶时，继承属性的属性域必须有值。5 详细的算法描述5.1 文法设计为顺利完成本次课程设计，实现要求的功能，设计测试文法G(S如下：S-> while(P A;A->id=E;E->TE'E'->+TE' | -TE' | eT->FT'T'-

16、>*FT' | /FT' | eF->(E | idP->E rop idrop-> > | < | >= | <= | != | =5.2 算法描述（1）word_node * word_link(word_node,word_node,string/给结点赋值，并设置type值。（2）void get_word(string word函数设计：从文本文档中读取字符，存入word_array（3）简单优先子程序如下：void rop(word_node *&p /rop-> > | < | >=

17、| <= | != | =void F(word_node *&p /F->(E | idvoid extend_T(word_node *&p /T'->*FT' | /FT' | evoid T(word_node *&p /T->FT'void extend_E(word_node *&p /E'->+TE' | -TE' | evoid E(word_node *&p /E->TE'void P(word_node *&p /P->E

18、 rop bvoid A(word_node *&p /A->id=E;bool S(word_node *&p / while(p doA; 5.3 源程序如下#include"Stack.h" /定义栈，便于归约时运用。#include #include /文件输入#include using namespace std;#define norw 13 /关键字的个数#define nmax 14 /数字的最大位数#define al 10 /符号的最大长度#define N -10 #define getchdo if(getch(=-1retu

19、rn -1#define getsymdo if(getsym(=-1return -1ifstream *fin;SeqStack Sym,Opt,Opr;char *p,ch;char str20; char inputstr100; /保存从文件读入的所有字符char buf520;int count1=0,count2=0;int ip=0,row,line;enum symbol sym; /当前的符号int num; /当前numberchar aal+1; /临时符号char idal+1; /当前identchar wordnorwal; /保留字enum symbol wsy

20、mnorw; /关键字的符号值enum symbol ssym256; /单字符的符号值 enum symbol nul, ident, number, plus, minus, times,slash, oddsym, eql, neq, lss, leq, gtr, geq, lparen, rparen, lbrace, rbrace,comma, semicolon, period, becomes, beginsym, endsym,ifsym, elsesym, whilesym, writesym, readsym, dosym,callsym, constsym, varsym

21、, procsym ，greater， less; void ThreeAddr(;void init(/设置单字符符号for(int i=0;i<=255;i+ssymi=nul;ssym'+'=plus;ssym'-'=minus;ssym'*'=times;ssym'/'=slash;ssym'('=lparen;ssym''=rparen;ssym''=lbrace;ssym''=rbrace;ssym'='=eql;ssym',

22、'=comma;ssym'.'=period;ssym'#'=neq;ssym''=semicolon;ssym > =greater;ssym < =less;/设置保留字名字，strcpy(&(word00,"begin"strcpy(&(word10,"call"strcpy(&(word20,"const"strcpy(&(word30,"do"strcpy(&(word40,"end&qu

23、ot;strcpy(&(word50,"if"strcpy(&(word60,"odd"strcpy(&(word70,"procedure"strcpy(&(word80,"read"strcpy(&(word90,"then"strcpy(&(word100,"var"strcpy(&(word110,"while"strcpy(&(word120,"write"/设置

24、保留字符号wsym0=beginsym;wsym1=callsym;wsym2=constsym;wsym3=dosym;wsym4=endsym;wsym5=ifsym;wsym6=oddsym;wsym7=procsym;wsym8=readsym;wsym9=elsesym;wsym10=varsym;wsym11=whilesym;wsym12=writesym;char rule1220="S-> while(E do B/0; "B->d=C;0","C->A+A0","C->A-A0",

25、"C->A*A0","C->A/A0","C->A0","E->A>A0","E->A "E->A=A0","E->A0","A->d0",; /文法int getch(if(fin->get(chif(ch!=' ' && ch!=9 && ch!=10inputstrip=ch; ip+; cout< return 0;else

26、return -1;/词法分析int getsym(int i,j,k;while(ch=' '|ch=10|ch=9getchdo;sym=nul; if(ch>='a'&&ch<='z'k=0;doif(k ak=ch;k+;getchdo;while(ch>='a'&&ch<='z'|ch>='0'&&ch<='9'ak=0;strcpy(id,a;i=0;j=norw-1;do /搜索当前符号

27、是否为保留字k=(i+j/2;if(strcmp(id,wordk<=0 j=k-1;if(strcmp(id,wordk>=0 i=k+1;while(i<=j;if(i-1>j sym=wsymk;elsesym=ident; /搜索失败，则是名字或数字 elseif(ch>='0'&&ch<='9' /检测是否为数字k=0;num=0;sym=number;donum=num*10+ch-'0'k+;getchdo;while(ch>='0'&&ch&

28、lt;='9'k-;if(k>nmaxcout<<"error:too large number!"< else if(ch='=' /检测赋值符号sym=becomes;getchdo;elseif(ch='<' /检测小于或小于等于符号getchdo;if(ch='='sym=leq;getchdo;elsesym=lss;elseif(ch='>' /检测大于或大于等于符号getchdo;if(ch='='sym=geq;getchdo;

29、elsesym=gtr;elsesym=ssymch;if(sym!=periodgetchdo;return 0;/优先关系模块/定义优先关系int PreTable2323 =/* S w h i l e E d o B a = + 1 ; > ( b c # */* S */ N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 1 ,/* w/ N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N ,/* h*/ N, N

30、, N, 0, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N ,/* i/ N, N, N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, -1, N, N ,/* l/ N, N, N, N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N ,/* e */ N, N, N, N, N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N , /* E*/

31、 N, N, N, N, N, N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N ,/* d*/ N, N, N, N, N, N, N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N, N, N ,/* o*/ N, N, N, N, N, N, N, N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N, N ,/* N, N, N, N, N, N, N, N, N, N, 0, N, N, N, N, N, N, N, N, N, N, N, N ,/* A/

32、N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 0, N, N, N, N ,/*/ N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 0, N ,/* a */ N, N, N, N, N, N, N, N, N, N, N, N, N, N, 0, N, N, 0, N, N, N, N, N ,/* = */ N, N, N, N, N, N, N, N, N, N, N, N, 0, N, N, N, N, N, N, N, N, N, N ,/* +

33、 */ N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 0, N, N, N, N, N, N, N ,/* 1 */ N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 0, N, N, N, N, N, N ,/* ; */ N, N, N, N, N, 1, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N ,/* > */ N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 0, N,

34、 N, N ,/* ( */ N, N, N, N, N, N, N, N, N, N, N, 0, -1, N, N, N, N, N, N, N, N, N, N ,/* b */ N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 1, N ,/* c */ N, N, N, N, N, N, N, N, N, N, N, N, N, 0, N, N, N, N, N, N, N, N, N ,/* */ N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N

35、, N, N, N, 1 ,/* # */ -1, -1, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 0 ;int Compare(char m,char n/定义矩阵switch (mcase 'S': row=0;break;case 'w: row=1;break;case 'h: row=2;break;case 'i row=3;break;case 'l: row=4;break;case 'e: row=5;break;case 'E: r

36、ow=6;break;case 'd: row=7;break;case 'o row=8;break;case ': row=9;break;case 'A: row=10;break;case ': row=11;break;case 'a': row=12;break;case '=': row=13;break;case '+': row=14;break;case '1': row=15;break;case '': row=16;break;case '&

37、gt;': row=17;break;case '(': row=18;break;case 'b': row=19;break;case 'c': row=20;break;case '': row=21;break;case '#': row=22;break;default: return -100;break;switch (ncase 'S': line=0;break;case 'w: line=1;break;case 'h: line=2;break;case

38、 'i line=3;break;case 'l: line=4;break;case 'e: line=5;break;case 'E: line=6;break;case 'd: line=7;break;case 'o: line=8;break;case ': line=9;break;case 'A: line=10;break;case ': line=11;break;case 'a': line=12;break;case '=': line=13;break;case &#

39、39;+': line=14;break;case '1': line=15;break;case '': line=16;break;case '>': line=17;break;case '(': line=18;break;case 'b': line=19;break;case 'c': line=20;break;case '': line=21;break;case '#': line=22;break;default: return -1

40、00;break;return PreTablerowline;void Error(/规约不成功 cout<<"归约失败,语法有错误!"< void Succeed(/规约成功 cout<<"归约成功,语法正确."< char Reduce(char c /将终极符或非终极符规约为非终极符 if (c = 'd' return 'S' else if (c = 'c' return 'B' else if (c = 'a' return

41、'E' else return NULL;void Parse(/简单优先语法分析char c; /保存栈顶元素char t1; /规约时判断是否规约的栈顶元素char t2; /规约时判断是否规约的次栈顶元素cout<<"归约过程如下:"< Sym.Push('#'while (*p!='0' c=Sym.TopValue(;if (c='S'/如果栈顶为S或#,规约成功 Succeed(;cout<<"语法分析完成!n"< cout<<&q

42、uot;三地址码如下所示:"< ThreeAddr(;cout< return;else switch (Compare(c, *p /如果优先符是小于或等于则压栈,否则进栈case -1:case 0: Sym.Push(*p;/压栈Sym.PrintStack(;p+;break; case 1: do t1 = Sym.TopValue(;bufcount10=0;bufcount1count2=t1;count2+;t2 = Sym.NextTop(;Sym.Pop(c;/栈顶出栈while(Compare(t2, t1 != -1;count1+;t1 = Reduce(t1;Sym.Push(t1;Sym.PrintStack(;break; default: Error(;cout<<"语法分析完成!n"cout< return; void ThreeAddr( /产生并输出三地址码i