编译技术课程设计

1、编译技术实验报告一、 实验要求a) 词法分析器实验概述：设计、编制、调试一个识别简单语言单词的词法分析程序。具体要求：1) 识别该简单语言的单词符号。2) 根据表1-1区分单词符号是该简单语言的基本字、普通标识符、运算符、浮点数以及界符。3） 输入为源程序字符串，以#结束；输出是单词符号的二元组。例如：输入： x=9#，输出：（10，x）（21，=）（20，9）。 单词符号种别编码单词值main1int 2float3double4char5if 6else 7do8while9l(l|d)*10内部字符串 ( +|-| ) dd*(.dd* | )( e ( +|-| ) dd*|) 20二

2、进制数值表示=21+22- 23* 24/ 25(26)272829,30;31>32>=33<34<=35=36!=37'0'1000Error-1表1-1 某简单语言的单词表及其种别码b) 语法分析器实验概述：设计、编制、调试一个识别简单语言单词的语法分析程序。具体要求：1) 根据简单语言单词表以及其种别码（见表1-1）和以下语法结构定义处理用户提交的符合上述文法的源代码序列，进行语法分析，并给出语法是否正确的结论：<表达式> := <项> +<项>|-<项><项> := <因子>

3、;*<因子>|/<因子><因子> :=ID|num|(<表达式>)num:= ( +|-| ) 数字数字*(.数字数字* | )( e ( +|-| ) 数字数字*|)ID:=字母(字母|d数字)*字母:=a|b|c|z|A|B|C|Z数字:=0|1|2|92) 输入为源程序字符串，以#结束；输出为语法是否正确的结论。例如：输入：1+2#，输出：success！二、 实验目的 1) 通过该实验，熟练应用编译原理的基本理论和方法。2) 学会用C/C+高级程序设计语言设计一个词法分析器和语法分析器的技术。3) 加深对编译原理的分析理论的理解，培养动手

4、实践能力。三、 实验步骤1) 画出识别上述简单语言单词的状态转换图。2) 用C/C+语言编写词法分析程序（应考虑能被语法分析程序调用）。3) 完善词法分析程序的预处理，去除忽略输入程序中的注释、多余空格、回车换行符等。4) 设计实现语法分析程序(调用上述词法程序分析单词)，采用递归下降分析法对算术表达式进行语法分析。5) 设计若干用例，上机测试并通过所设计实现的语法分析器。四、 实验整体设计思想本实验的任务是完成编译过程中的词法分析和语法分析两个阶段。其中，词法分析阶段的基本任务是从以字符串表示的源程序中识别出具有独立意义的单词符号，并以二元组的形式输出，以作为语法分析阶段的输入。而语法分析阶

5、段的基本任务是将词法分析阶段产生的二元组作为输入，根据语言的语法规则，识别出各种语法成分，并判断该单词符号序列是否是该语言的一个句子。在词法分析阶段，通过DOS环境手动输入字符串序列（以#作为结束标志）作为带分析的源程序，调用词法扫描子程序将字符串以二元组的形式输出（若有不属于该语言单词符号出现，则进行出错处理），词法扫描子程序包括了对源程序的预处理（忽略多余空格、回车换行符等空白字符），以及对单词的识别和分类，以形成（单词种别，单词自身的值）形式的二元组。在语法分析阶段，采用自上而下的递归下降分析法，根据递归下降分析函数编写规则来编写相应的函数，在各个函数的分析过程中调用词法分析程序中的扫描

6、程序，发出“取下一个单词符号”的命令，以取得下一个单词符号作语法分析。实验的整体设计思想可由以下图示表示： 图4-1实验整体设计思想五、 程序详细算法设计 a) 词法分析部分 词法分析的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。具体思路如下：首先建立关键字表，将关键字作为特殊标示符处理，把它们预先安排在char * rwtab中，将需要被识别出的关键字存入表中，当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。主要变量说明： 用token存放构成单词符号的字符串

7、，sum存放双精度浮点数单词，syn 存放单词符号的种别码，f标识数值的符号，如果是正数，则将f置1，如果是负数，则将f置-1，ef标识指数的符号，如果是正数，则将ef置1，如果是负数，则将ef置-1。在主函数中让用户输入要识别的符号串，然后将输入的符号串读入到prog函数中，遇#结束。再依次扫描prog中的每一个符号，调用 scaner()子函数分析每一个符号，再将分析的结果输出，也是遇#结束。在scaner()子函数中，先将 token 全部置空初始化，然后读一个字符，如果是空格，就接着往下读，直到读到一个非空格的字符，分析它是什么类型。 如果是字母类型，则接着往下读，直到读到非字母且非数

8、字的字符，存入token中，依次对比关键字表中的元素，如果相同，则将syn置为相应的种别码，如果全都扫描后没发现相同的关键字，则为普通的标识符，将syn置为10，返回主函数输出。如果是数字类型或正负符号，首先分析第一个符号，看它是数字还是+,-符号，如果是+,-符号，先判断它们是正负符号还是加减符号，判断的依据是这个符号的前一个符号是不是数字类型或者是)，如果是，则是加减符号，将syn置为相应的种别码，并将它存入token中返回主函数输出，如果不是，则为正负号，如果是正号，则将f置1，如果是符号，则将f置-1。接着读下一个字符串，直到读到一个不是数字的字符串位置，每读一个数字字符，就将他们转化

9、为相应的数字，使用辗转相乘法，每次都让sum先自乘10，然后加上这个数字，这样就将字符串表示的数字转化成了相应的数。这之后看下一个字符是不是小数点，如果是小数点，就接着读下面的数字字符，转化为响应的数字，除以变量p，p初值为10，每再读下一个字符，就让p乘10，直到读到非数字字符。检查下一个字符是否为e或E，如果为e或者E，则读下面的数字字符，将它们存在etemp的整型变量中，如果ef为正，则让sum自乘etemp次的10，如果ef为负，则让sum自除etemp次的10。最后将syn置为20，返回主函数输出。如果是其他单词表的符号，则将他们的 syn 置为相应的种别码，并将字符存到token

10、中返回主函数输出。 b) 语法分析部分 （递归下降算法分析）语法分析的基本任务是使用词法分析的结果，使用递归下降算法分析是否符合语法规则，如果符合，则输出success，若果不符合，则输出error。语法分析是在词法分析的基础上加上判断是否符合语法规则的语句。设置整数 tag1表示'+'/'-'出现的情况，1表示已出现过，0表示第一次出现在main函数最后调用express函数判断，如果调用之后返回时syn = 0且k = 0，就输出success，否则输出error。其中k为设定的标志，初值为0，如果在调用子函数的过程中如果有错误，则置k为1。express函

11、数，调用statement函数，返回后看是否是+或-，如果是，则调用 scaner 函数，再调用statement函数，如果不是，进行出错处理。statement函数，调用factor函数，返回后看是否是*或/，如果是，则调用scaner函数，再调用factor函数，如果不是，进行出错处理。factor函数，检查是否标识符，如果是，调用scaner函数，如果不是，检查是否是数值，如果是，调用scaner函数，如果不是，检查是否是(，如果不是，进行出错处理，如果是，调用scaner函数，再调用express函数，返回后检查是否是),如果不是，进行出错处理，如果是，调用scaner函数，返回。c)

12、语义分析部分语义分析时采用自下而上语法制导翻译，分析时有如下的特点： 1. 当栈顶形成句柄执行归约时，调用相应的语义动作。 2. 语法分析栈与语义分析栈同步操作。下面以简单算术表达式语句的翻译为例详细说明算法设计。实现简单算术表达式的翻译一般采取下列步骤： i. 分析文法的中。ii. 设置一系列语义变量，定义语义过程，语义函数。iii. 修改文法，写出每一规则式的语义子程序。iv. 扩充LR分析栈，构造LR分析表。对文法E->E+TE-TT;T->T*F|T/F|F;F->(E)|id 进行翻译时， c) 设置语义变量：对非终结符E定义语义变量 E.place 。 d) E.

13、place 表示存放E值的变量名在符号表中的入口地址或临时变量名的整数码。e) 定义语义函数newtemp()用于门生一个新的临时变量的名字，具体实现时每产生一个T，就及时送到符号表中，也可以不进符号表，直接将单词值用整数码表示。f) 定义语义过程函数emit(T=arg1 op arg2),产生一个四元式，并及时填进四元式表中。利用上面定义的语义变量、过程、函数等，根据文法，写出每一个规则式的语义过程子程序。 1. E->E+T E.place=newtemp();Emit(E.place=E1.place+T.place);2. E->E-T E.place=newtemp()

14、;Emit(E.place=E1.place-T.place);3. T->T*F T.place=newtemp();E4. T->T/F T.place=newtemp();Emit(T.place=T1.place/F.place);5. F->idp=lookup();if(p!=NULL) F.place=p;else error;6. d)状态转换图六、 程序流程框图开始定义关键字表请用户输入字符串读入用户输入的字符串输出单词二元组调用扫描子程序输入串结束？是结束 扫描子程序部分：1读取下一个字符忽略空格变量初始化321是否字母？拼标识符 否是否关键字

15、？是否数字或正负号？ Syn=10Syn为对应关键字的单词种别码是否运算符、界符等符号？ 否 是对不同符号给出相应的syn值返回报错返回2是+? 是应为负号？应为正号？ 否 否是-? 是Syn=22是+? 否 否 是返回f=1 否是-?Syn=23返回f=-1 否读取下一个字符是否数字？拼数到sum读取下一个字符4443是否是e？是否数字？是否小数点？读取下一个字符读取下一个字符拼数到sum是ef=1?是否数字？是否-?是否+?ef=1 是否efl=-1 是 否拼数到etmp读取下一个数 Sum自除etmp次10Sum自乘etmp次104Syn=20回退一个字符返回a) 语法分析部分 （递归下

16、降算法分析）开始定义关键字表请用户输入字符串读入用户输入的字符串调用扫描子程序调用语法检查子程序已到字符串末尾且无错误？ 输出error输出success 是结束扫描子程序流程图见词法分析部分语法检查子程序express流程图如下：调用statement函数是否加减符号号？ 否出错处理 是调用scaner调用statement函数Factor函数流程图如下：调用factor函数是否乘除符号号？ 否出错处理 是调用scaner调用factor函数是否（是否是数值是否标识符 是 否 是 否出错处理 否 是调用scaner55调用express函数是否） 否出错处理调用scaner七、 函数相关说明

17、scaner() 函数相关说明： scaner() 函数的作用是扫描输入字符串，并作出逻辑判断。1) 首先将 token 数组置空，然后将读输入字符串的第一个字符； 2) 如果读入的是一个数字，则调用 handleNum() 函数； 3) 如果输入的是一个字母字符，则继续读入下一个字符，直到读入的字符不是字母字符或数字字符。如果读入的是 "begin", "if", "then", "while", "do", "end" 其中的一个，则按照他们各自对应的编号输出；如果读入的

18、不是上述情况，则将这一串字符作为变量输出； 4) 如果输入的是 “+” “-”， 则需要判断其后面跟的是不是数字。若输入的不是数字，则输出“+” “-”； 若输出的是数字，则应该进行判断：若“+”“-” 之前不是数字字符、字母字符和）时，“+”“-” 应该作为正负号处理，否则，应该作为加减符号处理； 5) 若输入的是#，则表示输入的字符串已经读完，返回码是0；6) 若输入的是除上的其他情况，则分别对应他们各自的种别码依次输出到屏幕上。 a) 词法分析部分uvoid main()该函数输出提示字符，接收输入的字符串放入 prog 数组中，通过循环调用scaner函数直到syn=0(即接收到#).

19、uvoid scaner r()该函数是用来识别单词符号(词法分析器表格中给出)同时给出syn的值。b) 语法分析部分 （递归下降算法分析） 该程序共有四个函数uvoid main()该函数输出提示字符，接收输入的字符串放入prog 数组中，调用expression来判断输入的字符串是否是合法的表达式。最后根据K的值来输出success或者error，k=0成功，k=1失败。uvoid scaner()该函数和词法分析器中scaner函数的功能一致，都是扫描输入的字符串识别单词符号。Factor() 函数相关说明： factor () 函数的作用是判断出输入的是各种字符单位。 1) 如果输入的

20、种类码是10、11、或者99，则说明输入的是变量、整数或者浮点型数，将他们输出后继续扫描； 2) 如果输入的种类码是27，说明输入的是（，则判断接下来输入的是不是满足 expression() 函数。若不满足则发生错误，若满足，则分析接下来的是不是），若不是依旧报错； 3) 若满足文法 Fà(E)|id 所对应的识别函数，则开辟内存空间，将对应的四元式保存并输出，若不满足，则把kk置1；term()函数相关说明： term()函数的作用是判断输入的是否是由*/连接成的因式。 1）如果输入的是*/， 则判断接下来输入的是不是满足 factor() 函数，若不满足，则函数结束；若满足，则

21、继续循环； 2）若满足文法T=T*F|T/F|F所对应的识别函数，则开辟内存空间，将对应的四元式保存并输出，若不满足，则把kk置1；Expression() 函数相关说明：expression () 函数的作用是判断输入的是否是由 +- 连接成的因式。1）如果输入的是+-，则 判断接下来输入的是不是满足 term()函数，若不满足，则函数结束,若满足，则继续循环；2）若满足文法E=E+T|E-T|T所对应的识别函数，则开辟内存空间，将对应的四元式保存并输出，若不满足，则把kk置1；八、 程序运行结果（屏幕截图） 八 语法分析器使用说明1）安装VC+6.0软件2）打开语法分析器源程序3）编译运行

22、源程序4）若正确运行，根据提示字符输入一个字符串，以#结尾5）若输入的是一个正确的表达式，则输出提示符success！否则，输出提示符error！。九、 总结 体会由于课堂上的上，学习的东西比较浅，难免眼高手低，故而，通过实验和课程，遇到了很多课本上面见不到的问题，完成实验后，个人在成就感的同时，也学习到了编程的具体过程中的很多知识。 通过一定的程序编辑，可以将我们输入的一个句子进行分离和剖析来检查一定内容的错误，也能判断我们输入的某段东西的对错。 然后，对代码的规格化有了更新的认识。 需要很多层次的判断。最后，代码规范化很重要，好的代码，在复查和测试中能够给我们很大帮助。.十、 源程序清单#

23、include <stdio.h>#include <stdlib.h>#include<math.h>#include<string.h>struct Quadchar result12;char ag112;char op12;char ag212;char prog80,token8;char *temp9="main","int","float","double","char","if","else"

24、,"do","while"char ch;int sum,syn,p,m,n;int intOrDou;double dou;int Flag;int IsSuccess=0;int NXQ=0,suffix=0,ntc,nfc; struct Quad *quad;void lrparser();void lanblock(int *a);void lanbar(int *a);void statement(int *a);char *expression();char *term();void condition();char *factor();i

25、nt degit(char ch);int letter(char ch);int Int();void Double();void scaner();void main()p=0;printf("nPlease enter a string,and end with # :n");doch=getchar();progp+=ch;while(ch!='#');p=0;m=0;n=0;intOrDou=0; sum=0;dou=0.0;Flag=2;syn=0;quad=(Quad *)malloc(strlen(prog)*sizeof(Quad);NXQ

26、=1;suffix=0;ntc=nfc=1;scaner();lrparser();void emit(char *op,char *ag1,char *ag2,char *result) /生成四元式sprintf(quadNXQ.op,op);sprintf(quadNXQ.ag1,ag1);sprintf(quadNXQ.ag2,ag2);sprintf(quadNXQ.result,result);NXQ+;return;void Printemit() /打印四元式int nloop;for(nloop=1;nloop<NXQ;nloop+)printf("n(%s:

27、 %s,t%s,t%s)",quadnloop.op,quadnloop.ag1,quadnloop.ag2,quadnloop.result);char *newtemp() /产生临时变量char*p;char m8;p=(char *)malloc(8);suffix+;itoa(suffix,m,10);strcpy(p+1,m);p0='t'return(p);int merg(int p1,int p2)int p,Result;if(p2=0) Result=p1;elseResult=p=p2;while(atoi(quadp.result)p=ato

28、i(quadp.result);sprintf(quadp.result,"%s",p1);return Result;void bp(int p,int t)int w,q=p;while(q)w=atoi(quadq.result);sprintf(quadq.result,"%d",t);q=w;return;char *factor()char *fplace;fplace=(char *)malloc(12);strcpy(fplace,"");if(syn=10)strcpy(fplace,token);scaner();

29、elseif(syn=20)if(intOrDou=1)itoa(sum,fplace,10); if(intOrDou=2) gcvt(dou,5,fplace);scaner();elseif(syn=26)scaner();fplace=expression();if(syn=27)scaner();return (fplace);void condition(int *etc,int *efc)char *op,*ep1,*ep2,*tp;char strtemp4;op=(char *)malloc(3);ep1=(char *)malloc(12);ep2=(char *)mall

30、oc(12);tp=(char *)malloc(12);ep1=expression();if(syn=32|syn=33|syn=34|syn=35|syn=36|syn=37)sprintf(op,"%s",token); scaner();ep2=expression();*etc=NXQ;*efc=NXQ+1;sprintf(strtemp,"j%s",op);emit(strtemp,ep1,ep2,"0");emit("j","","","0"

31、;);char * term()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(1)if(syn=24|syn=25)strcpy(tt,token);scaner();strcpy(ep2,factor();strcpy(tp,newtemp();emit(tt,eplace,ep2,tp);strcpy(eplace,tp);else break

32、;return eplace;char * expression()char *tp,*ep2,*eplace,*tt;tp=(char *)malloc(12);ep2=(char *)malloc(12);eplace=(char *)malloc(12);tt=(char *)malloc(12);strcpy(eplace,term();while(1)if(syn=22|syn=23)strcpy(tt,token);scaner();strcpy(ep2,term();strcpy(tp,newtemp();emit(tt,eplace,ep2,tp);strcpy(eplace,

33、tp);else break;return eplace;void statement(int *nchain)char *str,*ep1;str=(char *)malloc(255);ep1=(char *)malloc(255);int nchaintemp,nwquad;if(syn=10)strcpy(str,token);scaner();if(syn=21)scaner();strcpy(ep1,expression();emit("=",ep1,"",str);*nchain=0;return;else return;elseif(sy

34、n=6)scaner();condition(&ntc,&nfc);bp(ntc,NXQ);lanblock(&nchaintemp);*nchain=merg(nchaintemp,nfc);return;elseif(syn=9)scaner();nwquad=NXQ;condition(&ntc,&nfc);bp(ntc,NXQ);lanblock(&nchaintemp);sprintf(str,"%d",nwquad);emit("j","","",str)

35、;*nchain=nfc;return;else return;void lanbar(int nchain)statement(&nchain);while(syn=31)scaner();bp(nchain,NXQ); statement(&nchain);bp(nchain,NXQ);return;void lanblock(int *nchain)if(syn=28)scaner();lanbar(*nchain);if(syn=29)IsSuccess=1;scaner();return;else return;else return;void lrparser()i

36、nt nchain=0;if(syn=1)scaner();if(syn=26)scaner();if(syn=27)scaner();lanblock(&nchain);if(syn=0&&IsSuccess=1)Printemit();else printf("n Failed!n");else printf("n Failed!n");else printf("n Failed!n");else printf("n Failed!n");int degit(char ch)if(ch&

37、gt;='0'&&ch<='9')return 1;else return -1;int letter(char ch)if(ch>='a'&&ch<='z'|ch>='A'&&ch<='Z')return 1;elsereturn -1;int Int()int sum1=0;while(degit(ch)=1)sum1=sum1*10+ch-'0'tokenm+=ch;ch=progp+;return

38、sum1;void Double()int sum1=0;while(degit(ch)=1)dou=dou*10+ch-'0'tokenm+=ch;ch=progp+;if(ch='.')tokenm+=ch;ch=progp+;int count=1;while(degit(ch)=1)dou=dou+(ch-'0')/pow(10,count);count+;tokenm+=ch;ch=progp+;if(ch='e')char flag;tokenm+=ch;ch=progp+;if(ch='-'|ch=&

39、#39;+')flag=ch;tokenm+=ch;ch=progp+;if(ch='+'|ch='-')tokenm+=ch;ch=progp+;while(degit(ch)=1)tokenm+=ch;ch=progp+;p-;syn=-1;return;elsewhile(degit(ch)=1)sum1=sum1*10+ch-'0'tokenm+=ch;ch=progp+;if(flag='+')dou=dou*pow(10,sum1);elsedou=dou/pow(10,sum1);p-;syn=20;intO

40、rDou=2;return;elsewhile(degit(ch)=1)sum1=sum1*10+ch-'0'tokenm+=ch;ch=progp+;dou=dou*pow(10,sum1);syn=20;intOrDou=2;return;syn=20;intOrDou=2;p-;void scaner()for(int i=0;i<8;i+)tokeni=NULL;m=0;sum=0;dou=0.0;ch=progp+;intOrDou=0;while(ch=' '|ch=10|ch=9)ch=progp+;if(letter(ch)=1)while

41、(ch>='a'&&ch<='z'|ch>='0'&&ch<='9')tokenm+=ch;ch=progp+;p-;syn=10;tokenm+='0'for(int i=0;i<9;i+)if(strcmp(token,tempi)=0)syn=i+1;break;elseif(degit(ch)=1)int r=p;while(degit(ch)=1)ch=progr+;if(ch!='e'&&ch!='.&

42、#39;)ch=progp-1;sum=Int();if(letter(ch)=1)syn=-1;while(letter(ch)=1)ch=progp+;p-;return;p-;syn=20;intOrDou=1;return;elsech=progp-1;Double();intOrDou=2;return;else switch(ch)case '+':m=0; tokenm+=ch; ch=progp+; if(ch='+'|ch='-')&&Flag=2) Flag-; syn=22; p-; tokenm+='

43、;0' return; if(Flag=1&&degit(ch)=1) Flag=2; int r=p; while(degit(ch)=1) ch=progr+; if(ch!='e'&&ch!='.') ch=progp-1; sum=Int(); if(letter(ch)=1) syn=-1; while(letter(ch)=1) ch=progp+; p-; return; p-; syn=20; intOrDou=1; return; else ch=progp-1; Double(); intOrDou=2; return; tokenm+='0' syn=22; p-; break;case '-':m=0; tokenm+=ch; ch=progp+; if(ch='+'