编译原理词法语法语义分析器设计

1、编译技术课程设计班 级 计算机0802 学 号 3080602049 姓 名 周勇 指导老师 朱玉全 二零一一年 七 月编译技术课程设计一、目的<<编译技术>>是理论与实践并重的课程，而其实验课要综合运用一、二年级所学的多门课程的内容，用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解；培养学生对完整系统的独立分析和设计的能力，进一步培养学生的独立编程能力。二、任务及要求基本要求：1 词法分析器 产生下述小语言的单词序列这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表： 单词符号种别编码助记符内码值D

2、IMIFDOSTOPEND标识符常数（整）=+*，（）1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR-内部字符串标准二进形式-对于这个小语言，有几点重要的限制：首先，所有的关键字（如IFWHILE等）都是“保留字”。所谓的保留字的意思是，用户不得使用它们作为自己定义的标示符。例如，下面的写法是绝对禁止的： IF（5）=x 其次，由于把关键字作为保留字，故可以把关键字作为一类特殊标示符来处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中

3、（此表叫作保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。再次，如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的了）。例如，一个条件语句应写为 IF i>0 i= 1;而绝对不要写成 IFi>0 i=1;因为对于后者，我们的分析器将无条件地将IFI看成一个标识符。这个小语言的单词符号的状态转换图，如下图： 2 语法分析器 能识别由加+ 减- 乘* 除/ 乘方 括号（）操作数所组成的算术表达式，其文法如下：EE+T|E-T|TTT*F|T/F|FFPF|Pp(E)|i 使用的算法可

4、以是：预测分析法；递归下降分析法；算符优先分析法；LR分析法等。3 中间代码生成器 产生上述算术表达式的中间代码（四元式序列）较高要求：1 扩充上述小语言的单词；2 增加语法分析器的功能，能识别条件语句和循环语句等；3 增加中间代码生成器的功能，能产生条件语句和循环语句等的中间代码（四元式序列）4 增加报错功能；5 将中间代码翻译成汇编语言。三、实现过程说明给出各题目的详细算法描述，数据结构和函数说明，流程图。（1） 词法分析器：1算法描述：词法分析阶段的基本任务是从以字符串表示的源程序中识别出具有独立意义的单词符号。通过DOS环境手动输入字符串序列（以$作为结束标志）作为带分析的源程序，调用

5、词法扫描子程序将字符串以二元组的形式输出（若有不属于该语言单词符号出现，则进行出错处理），词法扫描子程序包括了对源程序的预处理（忽略、回车换行符等字符），以及对单词的识别和分类，以形成（单词种别，单词自身的值）形式的二元组。具体思路如下：首先建立关键字表，将关键字作为特殊标示符处理，把它们预先安排在char *keywords13中，将需要被识别出的关键字存入表中，当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。在主函数中让用户输入要识别的符号串，然后将输入的符号串读入到 program500，遇$结束。再依次扫描program500中的每一个符号

6、，调用Scan ()子函数分析每一个符号，再将分析的结果输出，也是遇$结束。2函数说明和数据结构：在Scan ()子函数中，先全部初始化，然后读一个字符，分析它是什么类型:如果是字母类型，则接着往下读，直到读到非字母的字符，存入words10中，依次对比关键字表中的元素，如果相同，则将flags置为相应的种别码，如果全都扫描后没发现相同的关键字，则为普通的标识符,返回主函数输出。如果是数字类型，首先分析第一个符号，接着读下一个字符串，直到读到一个不是数字的字符串位置，每读一个数字字符，就将他们转化为相应的数字，使用辗转相乘法，每次都让number先自乘10，然后加上这个数字，这样就将字符串表示

7、的数字转化成了相应的数，返回主函数输出。如果是其他单词表的符号，则将他们的flags置为相应的种别码，并将字符存到words 中返回主函数输出。主要变量说明： 用words10存放构成单词符号的字符串，并且用于判断是否为关键字。flags500 存放单词符号的种别码。Number存放整数值，words存放标识符，关键字或者其他符号。cntnum按顺序存放读到的字符，为下面语义分析做准备。Status用于判断是否为关键字，1是，0不是。 3 具体的种别编码和内部值：单词符号种别编码单词值void1main2if3then4break5int6char 7fioat8include9for10wh

8、ile11printf12scanf13标识符100内部字符串常数（整）200二进制数值表示= =401=402>=403>404<=405<406!=407!408 += 409 + 410 +411 -= 412- -413 -414 *=415 *416 /=417 / 418 419 ; 501( 502 ) 503 504 505 506 507: 508 “ 509 %= 510 % 511 , 512 # 513 514 空格 515 $ 04. 流程图：主流程图扫描程序流程图：(a)，标识符词法分析流程图(b), 数字（整）词法分析流程图(c), 其他字

9、符流程图 (a)(b) (c)（2） 语法分析器1算法描述：语法分析阶段的基本任务是将词法分析阶段产生的二元组作为输入，根据语言的语法规则，识别出各种语法成分，并判断该单词符号序列是否是该语言的一个句子。在语法分析阶段，采用自上而下的递归下降分析法，根据递归下降分析函数编写规则来编写相应的函数，在各个函数的分析过程中调用词法分析程序中的扫描程序，发出“取下一个单词符号”的命令，以取得下一个单词符号的语法分析。词法分析和语法分析的整体设计思想可由以下图示表示： 语法分析是在词法分析的基础上加上判断是否符合语法规则的语句。语法分析的基本任务是使用词法分析的结果，使用递归下降算法分析是否符合语法规则

10、，如果符合，则输出“分析成功”，若果不符合，则输出“分析失败”。2.函数说明和数据结构在main函数调用e()函数，如果调用之后返回时,如果(flagstemp=0)&&is_right)为真，就输出“分析成功”，否则输出“分析失败”。其中is_right为设定的标志，初值为1，如果在调用子函数的过程中如果有错误，则置is_right为0。e函数: 调用t函数，调用f函数, 调用p函数,返回后看是否是+或-，如果是，则调用 e1函数，再调用e2函数，如果不是，进行出错处理，置is_right为0。e1函数：判断是不是”+”或者“-” 如果是，调用f函数，如果不是，进行出错处理，

11、置is_right为0。t函数: 调用f函数, 调用p函数,返回后看是否是*或/，如果是，则调用t1函数，再调用t2函数，如果不是，进行出错处理，置is_right为0。t1函数：判断是不是”*”或者“/” 如果是，调用f函数，如果不是，进行出错处理，置is_right为0。f函数：调用p函数，f1函数。f1函数：判断是不是”,如果是，调用f函数，如果不是，进行出错处理，置is_right为0。p函数: 检查是否标识符，如果是，调用f1函数，如果不是，检查是否是数值，如果是，调用f1函数，如果不是，检查是否是(，如果不是，进行出错处理，置is_right为0。如果是，调用e函数，返回后检查是否

12、是),如果不是，进行出错处理，置is_right为0。如果是，调用f1函数，返回。3 流程图： 主流程图e函数流程图：调用t函数p函数流程图：t函数流程图：f函数流程图：（3） 中间代码生成器1算法描述：下面以简单算术表达式语句的翻译为例详细说明算法设计。实现简单算术表达式的翻译一般采取下列步骤： i. 分析文法。ii. 设置一系列语义变量，定义语义过程，语义函数。iii. 设计算术表达式的递归下降子程序的程序分析算法。2.函数说明和数据结构：Strn用来存放临时变量的序号。temp用来存放数组的下表，在主程序中语法分析结束后，置0.定义函数newtemp()用于门生一个新的临时变量的名字，具

13、体实现时每产生一个T，就及时送到符号表中，也可以不进符号表，直接将单词值用整数码表示。定义函数siyuan（）,输出一个四元式。定义函数ye() 进行中间代码生成3主流程图（4） 较高要求i. 扩充上述小语言的单词；ii. 增加语法分析器的功能，能识别条件语句和循环语句等；iii. 增加中间代码生成器的功能，能产生条件语句和循环语句等的中间代码（四元式序列）iv. 增加报错功能；v. 将中间代码翻译成汇编语言。 其中1，4功能完成；四实验程序#include "stdafx.h"#include <iostream>#include<string>u

14、sing namespace std;#include<stdio.h>#include<stdlib.h> #include<sstream>int i,j,k,flag,number,status;/*status which is use to judge the string is keywords or not!*/char ch;char words10 = " "char program500;int flags500; /存储输入句子string cnt500;/标识符int temp=0; /数组下标int is_rig

15、ht; /判断输出信息/-词法分析-int Scan(char program) char *keywords13 = "void","main","if","then","break","int","char","float","include","for","while","printf","scanf" /关键字number=0;s

16、tatus=0;j=0;ch=programi+; /遍历if (ch >= 'a') && (ch <= 'z' ) /字母 while (ch >= 'a') && (ch <= 'z' ) wordsj+=ch; ch=programi+; i-; wordsj+ = '0'for (k = 0; k < 13; k+)if (strcmp (words,keywordsk) = 0) /判断是否为关键字switch(k)case 0:flag =

17、 1;status = 1;break;case 1:flag = 2;status = 1;break;case 2:flag = 3;status = 1;break;case 3:flag = 4;status = 1;break;case 4:flag = 5;status = 1;break;case 5:flag = 6;status = 1;break;case 6:flag = 7;status = 1;break;case 7:flag = 8;status = 1;break;case 8:flag = 9;status = 1;break;case 9:flag = 10

18、;status = 1;break;case 10:flag = 11;status = 1;break;case 11:flag = 12;status = 1;break;case 12:flag = 13;status = 1;break;if (status = 0)flag = 100; /标识符（）else if (ch >= '0') && (ch <= '9') /数字（） number = 0; while (ch >= '0' ) && (ch <= '9'

19、; ) number = number*10+(ch-'0'); ch = programi+;flag = 200;i-;else switch (ch) /运算符和标点符号case '=': if (ch = '=') wordsj+ = ch; wordsj = '0' ch = programi+; if (ch = '=') wordsj+ = ch; wordsj = '0' flag = 401; else i-; flag = 402; break; case'>

20、9;: if (ch = '>') wordsj+ = ch; wordsj = '0' ch = programi+; if (ch = '=') wordsj+ = ch; wordsj = '0' flag = 403; else i-; flag = 404; break; case'<': if (ch = '<')wordsj+ = ch;wordsj = '0'ch = programi+;if (ch = '=')wordsj+ =

21、ch;wordsj = '0'flag = 405;elsei-;flag = 406;break;case'!':if (ch = '!')wordsj+ = ch;wordsj = '0'ch = programi+;if (ch = '=')wordsj+ = ch;wordsj = '0'flag = 407;elsei-;flag = 408;break;case'+':if (ch = '+')wordsj+ = ch;wordsj = '0

22、9;ch = programi+;if (ch = '=')wordsj+ = ch;wordsj = '0'flag = 409;else if (ch = '+')wordsj+ = ch;wordsj = '0'flag = 410;elsei-;flag = 411;break;case'-':if (ch = '-')wordsj+ = ch;wordsj = '0'ch = programi+;if (ch = '=')wordsj+ = ch;words

23、j = '0'flag = 412;else if( ch = '-')wordsj+ = ch;wordsj = '0'flag = 413;elsei-;flag = 414;break;case'*':if (ch = '*')wordsj+ = ch;wordsj = '0'ch = programi+;if (ch = '=')wordsj+ = ch;wordsj = '0'flag = 415;elsei-;flag = 416;break;case&#

24、39;/':if (ch = '/')wordsj+ = ch;wordsj = '0'ch = programi+;if (ch = '=')wordsj+ = ch;wordsj = '0'flag = 417;elsei-;flag = 418;break;case'':wordsj = ch;wordsj+1 = '0'flag = 419;break;case'':wordsj = ch;wordsj+1 = '0'flag = 501;break;

25、case'(':wordsj = ch;wordsj+1 = '0'flag = 502;break;case')':wordsj = ch;wordsj+1 = '0'flag = 503;break;case'':wordsj = ch;wordsj+1 = '0'flag = 504;break;case'':wordsj = ch;wordsj+1 = '0'flag = 505;break;case'':wordsj = ch;wordsj+

26、1 = '0'flag = 506;break;case'':wordsj = ch;wordsj+1 = '0'flag = 507;break;case':':wordsj = ch;wordsj+1 = '0'flag = 508;break;case'"':wordsj = ch;wordsj+1 = '0'flag = 509;break;case'%':if (ch = '%')wordsj+ = ch;wordsj = '

27、;0'ch = programi+;if (ch = '=')wordsj+ = ch;wordsj = '0'flag = 510;elsei-;flag = 511;break;case',':wordsj = ch;wordsj+1 = '0'flag = 512;break;case'#':wordsj = ch;wordsj+1 = '0'flag = 513;break;case'':wordsj = ch;wordsj+1 = '0'flag =

28、 514;break;case' ':/空格 wordsj ='_' wordsj+1 = '0' flag = 515; break;case'$':wordsj = '#'wordsj+1 = '0'flag = 0;break;default:flag = -1;break;return flag;/-语法分析（递归下降）-void e();void e1();void e2();void t();void t1();void t2();void f();void f1();void p();

29、void e()cout<<"E->TE''"<<endl;t();e2();void e1()if(flagstemp=411)cout<<"E'->+T"<<endl;temp+;t();else if(flagstemp=414)cout<<"E'->-T"<<endl;temp+;t();elseis_right=0;void e2()if(flagstemp=411|flagstemp=414)cout&

30、lt;<"E''->E'E''"<<endl; e1(); e2(); else if (flagstemp!=0|flagstemp!=503) cout<<"E''->"<<endl; return ; elseis_right=0;void t()cout<<"T->FT''"<<endl;f();t2();void t1()if(flagstemp=416)cout<

31、<"T'->*F"<<endl;temp+;f();else if(flagstemp=418)cout<<"T'->/F"<<endl;temp+;f();else is_right=0;void t2()if(flagstemp=416|flagstemp=418)cout<<"T''->T'T''"<<endl;t1();t2();else if (flagstemp!=0|flagstem

32、p!=503) cout<<"T''->"<<endl; return ; else is_right=0;void f()cout<<"F->PF'"<<endl;p(); f1();void f1() if(flagstemp=419) cout<<"F'->F"<<endl;temp+;f(); else if (flagstemp!=0&&flagstemp!=503&&fl

33、agstemp!=411&&flagstemp!=414&&flagstemp!=416&&flagstemp!=418) cout<<"F'->"<<endl;is_right=0; void p()if(flagstemp=100|flagstemp=200)cout<<"P->i"<<endl;temp+;elseif(flagstemp=502)cout<<"P->(E)"<<end

34、l;temp+;e();if(flagstemp=503)cout<<"P->(E)"<<endl;temp+;elseis_right=0;else is_right =0;/-语义分析以及中间代码生成-int ye();int ye1(int a);int ye2(int a);int yt();int yt1(int a);int yt2(int a);int yf();int yf1(int a);int yp();int v=-1;int num=0;int ww;string strn;int nn;int newTemp()num

35、+;nn+; stringstream stream;stream<<nn;stream>>strn;stream.clear();cntnum-1="temp" cntnum-1.operator+=(strn);/把字符串s连接到当前字符串的结尾 /cntnum-1=strcat("Temp",strn); / cntnum-1="temp"return num-1;void siyuan(int a,int b,int c,int d)/输出四元cout<<"("<&

36、lt;cnta<<","<<cntb<<","<<cntc<<","<<cntd<<")"<<endl;int ye()int rt,t1;rt=yt();t1=rt;rt=ye2(t1);return rt;int ye1(int a)int rt,t1;t1=a; if(flagstemp=411) /加法temp+;int tt=v+1;v+;int t2=yt();int rr=newTemp();siyuan(

37、tt,t1,t2,rr);rt=rr;return rt;else if(flagstemp=414) /减法temp+;int tt=v+1;v+;int t2=yt();int rr=newTemp();siyuan(tt,t1,t2,rr);rt=rr;return rt;else return t1;int ye2(int a)int rt,t1;t1=a;if(flagstemp=411|flagstemp=414) rt=ye1(t1); t1=rt; rt=ye2(t1); return rt; else if (flagstemp!=0|flagstemp!=503) retu

38、rn t1; else return t1;int yt()int rt,t1;rt=yf();t1=rt;rt=yt2(t1);return rt;int yt1(int a)int rt,t1;t1=a;if(flagstemp=416) /乘法int tt=v+1;v+;temp+;int t2=yf();int rr=newTemp();siyuan(tt,t1,t2,rr); rt=rr;return rt;else if(flagstemp=418) /除法temp+;int tt=v+1;v+; int t2=yf();int rr=newTemp();siyuan(tt,t1,

39、t2,rr);rt=rr; return rt;else return t1;int yt2(int a)int rt,t;t=a;if(flagstemp=416|flagstemp=418)rt=yt1(t);t=rt; rt=yt2(t);return rt;else return t;int yf()int t1,rt; rt=yp();t1=rt; rt=yf1(t1); return rt;int yf1(int a) /乘方int rt,t1;t1=a; if(flagstemp=419)temp+;int tt=v+1;v+;int t2=yf();int rr=newTemp

40、();siyuan(tt,t1,t2,rr);rt=rr;return rt;else return t1;int yp()int rt,t1;if(flagstemp=100|flagstemp=200)v+;rt=v; temp+; return rt;else if(flagstemp=502) /(v+; temp+; rt=ye();if(flagstemp=503) /)v+; temp+;return rt;else return ww;else return ww;void main() int i=0; cout<<"请输入测试程序或者表达式，以$结束&

41、quot;<<endl; do ch =getchar(); programi+ = ch; while(ch != '$'); i = 0; cout<<"词法分析："<<endl; do flag = Scan(program);/词法分析 if (flag = 200) cout<<"("<<flag<<","<<number<<")"<<endl;flagsnum=flag;stringstream stream;stream<<number; stream>>cntnum;stream.clear();num+; else if (flag = -1) cout<<"error!"<<endl; else cout<<&qu