词法分析与语法分析程序设计

1、l 实验三 词法分析与语法分析程序设计一实验目的基本掌握计算机语言的词法分析程序和语法分析程序的设计方法。二实验要求、内容及步骤实验要求：1.根据以下的正规式，画出状态图；标识符：<字母>(<字母>|<数字字符>)*关键字：if then else while do十进制整数：0 | （1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*运算符和分隔符：+ - * / > < = ( ) 。2.根据状态图，设计词法分析函数int scan( )，从键盘读入数据，分析出一个单词。3.对于只含有+、*运算的算术表达式的如下

2、文法，编写相应的语法分析程序，要求用LL(1)分析表实现，并以id+id*id为例进行测试：E TE E +TE| T FTT *FT|F （E）| id实验步骤：1.根据状态图，设计词法分析算法；2.采用C+语言，实现该算法；3.调试程序：输入一组单词，检查输出结果；4.编制给定文法的非递归的预测分析程序，并加以测试。 三实验设备计算机、Windows 操作系统、Visual C+ 程序集成环境。四 实验原理1. 词法分析器读入输入串，将其转换成将被语法分析器分析的词法单元序列。产生下述小语言的单词序列。这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表：单词符号种别编码

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

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

5、T|TTT*F|T/F|FFPF|Pp(E)|i使用的算法可以是：预测分析法；递归下降分析法；算符优先分析法；LR分析法等。分析表格式：id+*()$EE TEE TE EE +TEE E TT FTT FT TT T *FTT T FF idF (E)3.中间代码生成器 产生上述算术表达式的中间代码（四元式序列）。五实验代码及结果词法分析代码：#include<string.h>#include<iostream>using namespace std;char prog100,token10;char ch;int syn,p,m=0,n,row,sum=0;cha

6、r *rwtab20="dim","if","do","stop","end" ,"and","begin","bool","case","char","false","for","int","not","or","set","then","true

7、","until","while"void scaner()for(n=0;n<9;n+) tokenn=NULL;ch=progp+;while(ch=' ')ch=progp;p+;if(ch>='a'&&ch<='z')|(ch>='A'&&ch<='Z')m=0;while(ch>='0'&&ch<='9')|(ch>='a

8、'&&ch<='z')|(ch>='A'&&ch<='Z')tokenm+=ch;ch=progp+;tokenm+='0'p-;syn=21;for(n=0;n<20;n+)if(strcmp(token,rwtabn)=0)syn=n+1;break;else if(ch>='0'&&ch<='9')sum=0;while(ch>='0'&&ch<='9

9、')sum=sum*10+ch-'0'ch=progp+;p-;syn=7+15;if(sum>32767)syn=-1;else switch(ch) case'=':syn=8+15;token0=ch;break;case'+':syn=9+15;token0=ch;break;case'*':m=0;tokenm+=ch;ch=progp+;if(ch='*')syn=11+15; tokenm+=ch;elsesyn=10+15;p-; break;case',':syn=1

10、2+15;token0=ch;break;case'(':syn=13+15;token0=ch;break;case')':syn=14+15;token0=ch;break;case'#':syn=0;token0=ch;break;case'<':m=0;tokenm+=ch;ch=progp+;if(ch='>')syn=17+15;tokenm+=ch;else if(ch='=')syn=16+15;tokenm+=ch;elsesyn=15+15;p-;break;case

11、'>':m=0;tokenm+=ch;ch=progp+;if(ch='=')syn=19+15;tokenm+=ch;elsesyn=18+15;p-;break;case':':m=0;tokenm+=ch;ch=progp+;if(ch='=')syn=21+15;tokenm+=ch;elsesyn=20+15;p-;break;case'/':syn=22+15;token0=ch;break;case'-':syn=23+15;token0=ch;break;case'&#

12、39;:syn=24+15;token0=ch;break;default: syn=-1;break;void main()p=0;row=1;cout<<endl<<endl<<endl;cout<<"词法分析"<<endl<<endl;cout<<"请输入一段程序（以#结束）:"docin.get(ch);progp+=ch;while(ch!='#');p=0;cout<<endl<<"词法分析结果如下"

13、<<endl;cout<<"种别编码 自身值"<<endl;doscaner();switch(syn)case 22 : cout<<" ("<<syn<<" , "<<sum<<")"<<endl; break; case -1: cout<< " Error in row"<<row<<"!"<<endl; brea

14、k; default: cout<<" ("<<syn<<" , "<<token<<")"<<endl;break;while (syn!=0);词法分析结果：语法分析代码：#include<string.h>#include<malloc.h>#include<iostream>using namespace std;typedef struct table /分析表存储结构 char m100; table;table M

15、100100; /定义分析表typedef struct stacknode /定义栈内元素节点 (带头结点（为空）的) char data; struct stacknode *next;stackk;void initlink(stackk *&s) /初始化新栈 s=(stackk *)malloc(sizeof(stackk); s->next=NULL;void poplink(stackk *&s) /顶元素出栈 stackk *p;char v; if(s->next!=NULL) p=s->next; v=p->data; s->n

16、ext=p->next; free(p);void pushlink(stackk *&s,char x) /新 元 素 入 栈 stackk *p; p=(stackk *)malloc(sizeof(stackk); p->data=x; p->next=s->next; s->next=p;void display(stackk *s) /打印 现实显示 栈内元素 stackk *p; int i=0,j; char st100; p=s->next; while(p!=NULL) sti+=p->data; p=p->next;

17、for(j=i-1;j>=0;j-) printf("%c",stj); for(j=0;j<16-i;j+) /打印 对齐格式 printf("%c",' '); char gettop(stackk *s) /返 回 栈 顶 元 素 值 if(s->next=NULL) return 0; else return s->next->data; int find(char c,char array) /查找函数，int i;int flag=0;for(i=0;i<100;i+)if(c=arrayi

18、) flag=1;return flag;int location(char c,char array) /定位函数,指出字符所在位置int i;for(i=0;i<100;i+)if(c=arrayi) return i;void error() /出错函数定义 printf("%15c出错!n",' ');void analyse(char Vn,char Vt) int i,j,m,p,q,length,t,h; char w,X; char str100;opt0: scanf("%s",str); for(i=0;i<

19、;strlen(str);i+) if(!find(stri,Vt) printf("输入字符串有误!请重新输入!"); goto opt0; break; stackk *st; initlink(st); pushlink(st,'#'); pushlink(st,Vn0); /#与识别符号入栈 j=0; h=1; w=str0; printf("步骤%-12c分析栈%-24c剩余输入串%-12c所用产生式n",' ',' ',' ');opt1: printf("%-16d&

20、quot;,h); /显示步骤 h+; display(st); /显示分析栈中内容 X=gettop(st); /上托栈顶符号放入X poplink(st); for(int k=0;k<14+j;k+) /打印对齐格式 printf("%c",' '); for(t=j;t<strlen(str);t+) printf("%c",strt); /显示剩余字符串 if(find(X,Vt)&& X!='#') /分析栈的栈顶元素和剩余输入串的第一个元素相比较 if(X=w) printf(&q

21、uot;%15c匹配n",X); j+; w=strj; goto opt1; else error(); else if(X='#') if(X=w) printf("%8c是该文法的句子！n",' '); else error(); else p=location(X,Vn); q=location(w,Vt); char *S1="null",*S2="NULL" if(strcmp(Mpq.m,S1)=0|strcmp(Mpq.m,S2)=0) /查找产生式 error(); else

22、 char str0100; strcpy(str0,Mpq.m); printf("%15c->%sn",X,str0); /显示对应的产生式 if(strcmp(str0,"$")=0) goto opt1; else length=strlen(str0); /逆序进栈 for(m=length-1;m>=0;m-) pushlink(st,str0m); goto opt1; int main() int i,k,n,r; char Vn100,Vt100,select; printf("对任意输入LL(1)文法的分析表，判

23、断验证字符串是否为该文法的句子 n"); printf("并能给出分析和演示过程。 n"); /printf("*n");opt2: printf("请输入各终结符（#号表示结束 ）Vti:n"); for(i=0;i<100;i+) scanf("%c",&Vti); if(Vti='#') r=i; break; printf("请输入非终结符个数:n"); scanf("%d",&n); getchar(); for (i

24、=0;i<n;i+) printf("请输入非终结符Vn%d:n",i); scanf("%c",&Vni); getchar(); printf("请输入此非终结符对应各终结符的产生式右部(null或NULL表示出错;$表示空串):n"); for(k=0;k<=r;k+) scanf("%s",Mik.m); getchar(); opt3: printf("请输入要分析的字符串，且以#结束:n"); analyse(Vn, Vt); printf("请选择n&

25、quot;); printf("1: 输入字符串n"); printf("2: 输入新分析表n"); printf("0: 退 出n");opt4:cin>>select; switch(select) case '1': goto opt3;break; case '2': goto opt2; case '0': break; default: printf("输入错误!请重新选择:"); goto opt4; break; return 0;语法分析

26、结果：六实验小结通过实验了解到了词法分析和语法分析二者的不同：1.词法规则通常非常简单，不必动用强大的文法来描述；2.对于词法记号，正规式比上下文无关文法提供了更简洁且易于理解的定义；3.从正规式可以自动的构造出有效的词法分析器，从任何文法都很难构造词法分析器；4.把语言的语法结构分成词法和非词法两部分为编译器前端的模块划分提供了方便的途径。 一、目的<<编译技术>>是理论与实践并重的课程，而其实验课要综合运用一、二年级所学的多门课程的内容，用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解；培养学生对完整系统的

27、独立分析和设计的能力，进一步培养学生的独立编程能力。二、任务及要求基本要求：1 词法分析器 产生下述小语言的单词序列这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表： 单词符号种别编码助记符内码值DIMIFDOSTOPEND标识符常数（整）=+*，（）1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR-内部字符串标准二进形式-对于这个小语言，有几点重要的限制：首先，所有的关键字（如IFWHILE等）都是“保留字”。所谓的保留字的意思是，用户不得使用它们作为自己定义的

28、标示符。例如，下面的写法是绝对禁止的： IF（5）=x 其次，由于把关键字作为保留字，故可以把关键字作为一类特殊标示符来处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中（此表叫作保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。再次，如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的了）。例如，一个条件语句应写为 IF i>0 i= 1;而绝对不要写成 IFi>0 i=1;因为对于后者，我们的分析器将无条件地将IFI看成一个标识符。这个小语言

29、的单词符号的状态转换图，如下图： 2 语法分析器 能识别由加+ 减- 乘* 除/ 乘方 括号（）操作数所组成的算术表达式，其文法如下：EE+T|E-T|TTT*F|T/F|FFPF|Pp(E)|i 使用的算法可以是：预测分析法；递归下降分析法；算符优先分析法；LR分析法等。3 中间代码生成器 产生上述算术表达式的中间代码（四元式序列）三、实现过程说明给出各题目的详细算法描述，数据结构和函数说明，流程图。1、词法分析器的流程图2、语法分析器主程序图3、中间代码生成器流程图：四、源程序清单词法分析器#include "stdafx.h"#include "Word.h

30、"/构造函数,对数据成员初始化,并将关键字以及运算符读入Word:Word()/打开关键字文件fstream keywordfile("keyword.txt");if(!keywordfile)cout<<"error ! can't open keywordfile!"<<endl;system("pause");exit(1);/设置临时变量将关键字、符号文件中的内容存储string tempword;int tempencode;string tempre;int tempvalue;

31、/开始读关键字文件while(!(keywordfile.eof() keywordfile>>tempword>>tempencode>>tempre>>tempvalue;keywordlist.push_back(tempword);keywordencode.push_back(tempencode);keywordre.push_back(tempre);keywordcodevalue.push_back(tempvalue);/关闭关键字文件keywordfile.close();for(int i=0;i<keywordli

32、st.size();i+)cout<<setw(16)<<keywordlisti<<setw(16)<<keywordencodei<<setw(12)<<keywordrei<<setw(12)<<keywordcodevaluei<<endl;fstream signwordfile("signword.txt");if(!signwordfile) cout<<"error ! can't open signwordfile!&q

33、uot;<<endl;system("pause");exit(1);/开始读符号文件while(!(signwordfile.eof()signwordfile>>tempword>>tempencode>>tempre>>tempvalue;signlist.push_back(tempword);signencode.push_back(tempencode);signre.push_back(tempre);signcodevalue.push_back(tempvalue);/关闭符号文件signword

34、file.close();for(int i=0;i<signlist.size();i+)cout<<setw(16)<<signlisti<<setw(16)<<signencodei<<setw(12)<<signrei<<setw(12)<<signcodevaluei<<endl;/将token中的字符串与character中的字符连接作为token中新的字符串void Word:concatentation()for(int i=0;i<100;i+)if(tok

35、eni=NULL)tokeni=s;break;/判断character中的字符是否为字母和数字的布尔函数，是则返回true，否则返回falsebool Word:letter() if(s<='z' && s>='a' )return true;else if(s<='Z' && s>='A')return true;elsereturn false;bool Word:digit() if(s<='9' && s>='0

36、')return true;return false;/按token数组中的字符串中的前五项(即判别其是否为保留字),若是保留字则返回它的编码int Word:reserve()int leng;/记录token数组中单词的长度for(int i=0;i<100;i+)/计算token数组中单词的长度if(tokeni=NULL)leng=i;break;for(int i=0;i<keywordlist.size();i+)for(int j=0;j<keywordlisti.length();j+)if(keywordlistij!=tokenj)/若某个字符不等

37、则终止此次循环break;if(j+1=keywordlisti.length()/若比较字符全部相等,则判断两者是否长度相等if(leng=keywordlisti.length()return i+1;elsereturn 0;return 0;/将标识符登录到符号表中或将常数登录到常数表中void Word:buildlist()/设置临时变量将标识符的助记符保存string tempword;int tempencode;string tempre;/标识符助记int tempvalue;int tempconstre;/常数助记s=token0;if(letter()/第一个字符如果

38、为字母,则将标识符登录到符号表中 fstream chartostring("convert.txt");if(!chartostring)cout<<"Error! Can't open convert file"<<endl;system("pause");for(int i=0;i<100;i+)if(tokeni=NULL)break;elsechartostring<<tokeni;chartostring<<endl;chartostring.close();c

39、hartostring.open("convert.txt");if(!chartostring)cout<<"Error! Can't open convert file"<<endl;system("pause");chartostring>>tempre;chartostring.close();indentityre.push_back(tempre);tempword="标识符"tempencode=6;tempvalue=indentityre.size();

40、indentitylist.push_back(tempword);indentityencode.push_back(tempencode);indentitycodevalue.push_back(tempvalue);fstream indentityfile("indentityword.txt");if(!indentityfile) cout<<"Error! Can't open indentityword file"<<endl;system("pause");/先将文件指针移到最后去,

41、再写入一个endlindentityfile.seekg(0,ios:end);indentityfile<<tempword<<setw(8)<<tempencode<<setw(12)<<tempre<<setw(12)<<tempvalue;indentityfile.seekg(0,ios:end);indentityfile<<endl;indentityfile.close();else/token中存储的是常数/将token中的字符数字转换为int类型fstream chartoint

42、("convert.txt");if(!chartoint)cout<<"Error! Can't open convert file"<<endl;system("pause");for(int i=0;i<100;i+) if(tokeni=NULL)break;elsechartoint<<tokeni;chartoint<<endl;chartoint.close();chartoint.open("convert.txt");if(!chart

43、oint) cout<<"Error! Can't open convert file"<<endl;system("pause");exit(1);chartoint>>tempconstre;chartoint.close();constlist.push_back(tempword);tempword="常数"tempencode=7;tempvalue=indentityre.size();constencode.push_back(tempencode);constre.push_

44、back(tempconstre);constvalue.push_back(tempvalue);fstream constdigit("constdigit.txt");if(!constdigit)cout<<"Error! Can't open constdigit file!"<<endl;system("pause");exit(1);/先将文件指针移到最后去,再写入一个endlconstdigit.seekg(0,ios:end);constdigit<<tempword<

45、;<setw(8)<<tempencode<<setw(12)<<tempconstre<<setw(12)<<tempvalue;constdigit.seekg(0,ios:end);constdigit<<endl;constdigit.close();cout<<setw(16)<<tempword<<setw(16)<<tempencode<<setw(12)<<tempconstre<<setw(12)<<te

46、mpvalue<<endl;/出现非法字符,显示错误信息void Word:error()cout<<"Error! Error word!"<<endl;system("pause");void Word:signinfor()/按token数组中的字符串中的前五项(即判别其是否为保留字),若是保留字则返回它的编码int leng;/记录token数组中单词的长度for(int i=0;i<100;i+)/计算token数组中单词的长度if(tokeni=NULL)leng=i;break;for(int i=

47、0;i<signlist.size();i+)for(int j=0;j<signlisti.length();j+)if(signlistij!=tokenj)/若某个字符不等则终止此次循环break;if(j+1=signlisti.length()/若比较字符全部相等,则判断两者是否长度相等if(leng=signlisti.length()cout<<setw(16)<<signlisti<<setw(16)<<signencodei<<setw(12)<<signrei<<setw(12)

48、<<signcodevaluei<<endl;/词法分析的函数void Word:run()cout<<setw(16)<<"单词符号"<<setw(16)<<"种别编码"<<setw(12)<<"助记符"<<setw(12)<<"内码值"<<endl;fstream file("word.txt");if(!file)cout<<"error

49、,can't open file"<<endl;system("pause");exit(1);file.unsetf(ios:skipws);while(s!='#' && !file.eof()for(int i=0;i<100;i+)tokeni=NULL;file>>s;while(s=' ')file>>s;switch(s)case 'a'case 'b':case 'c':case 'd':

50、case 'e':case 'f':case 'g':case 'h':case 'i':case 'j':case 'k':case 'l':case 'm':case 'n':case 'o':case 'p':case 'q':case 'r':case 's':case 't':case 'u':case 'v

51、':case 'w':case 'x':case 'y':case 'z':while(letter()|digit()concatentation();/将当前读入的字符送入token数组file>>s;/继续读字符,直到字符不为数字或字母为止/扫描指针回退一个字符file.seekg(-1,ios:cur);code=reserve();if(!code)buildlist();elsecout<<setw(16)<<keywordlistcode-1<<setw(16)

52、<<keywordencodecode-1<<setw(12)<<keywordrecode-1<<setw(12)<<keywordcodevaluecode-1<<endl;break;case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':while(digit()concatentation();/将当前读入的字符送入token数组file>>s;/继续读字符,直到字符不为数字为止/扫描指针回退一个字符file.seekg(-1,ios:cur);buildlist(