词法分析器语法分析器实验报告

《词法分析器语法分析器实验报告》由会员分享，可在线阅读，更多相关《词法分析器语法分析器实验报告（29页珍藏版）》请在装配图网上搜索。

1、山东大学编译技术课程设计班 级软件一班学 号 XX姓 名 软件一班万岁 指导老师贺老师二零一一年三月一、目的编译技术是理论与实践并重的课程，而其实验课要综合运用一、二年级所学的多门 课程的内容，用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分 析、代码生成和报错处理等理论的认识和理解；培养学生对完整系统的独立分析和设计的能 力，进一步培养学生的独立编程能力。二、任务及要求基本要求：1词法分析器 产生下述小语言的单词序列这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表：单词符号种别编码助记符内码值DIM1$DIM-IF2$IF-DO3$DO-STOP4$STOP-

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

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

4、法；递归下降分析法；算符优先分析法；LR分析法等。3. 中间代码生成器 产生上述算术表达式的中间代码（四元式序列）三、实现过程说明给出各题目的详细算法描述，数据结构和函数说明，流程图1、词法分析器的流程图否是木否是是扌旨向下一字符是是输出word 为关键字输 出word 为界符将word与关键 字表key进行匹输 出word 为常数是空格，空白或换是字母惑数字 吗*结束输出word为普通标示符输入源文 件路径路径是否有 效 是文件结束？输 出Word 内容为不 可识别/将字符加入字符数 组Word将字符加入字符数崛 组Word将字符 加入字 符数组 Word将字符 加入字 符数组 Word将字

5、符加入字符数组Word初始化文件指针打开源文件识别指针内容识别指针内容扌旨向下一字符跳过该字符指向下一字符卜扌旨向下一字符回退2、语法分析器主程序图3、四、源程序清单词法分析器#include stdafx.h#include Word.h构造函数，对数据成员初始化，并将关键字以及运算符读入Word:Word()/打开关键字文件fstream keywordfile(keyword.txt);if(!keywordfile)couterror ! cant open keywordfile!tempwordtempencodetempretempvalue; keywordlist.push_

6、back(tempword); keywordencode.push_back(tempencode);keywordre.push_back(tempre); keywordcodevalue.push_back(tempvalue);/关闭关键字文件keywordfile.close();for(int i=0;ikeywordlist.size();i+)coutsetw(16)keywordlistisetw(16)keywordencodeisetw(12)key wordreisetw(12)keywordcodevalueiendl;fstream signwordfile(si

7、gnword.txt);if(!signwordfile) couterror ! cant open signwordfile!tempwordtempencodetempretempvalue; signlist.push_back(tempword);signencode.push_back(tempencode); signre.push_back(tempre);signcodevalue.push_back(tempvalue);/关闭符号文件signwordfile.close();for(int i=0;isignlist.size();i+) coutsetw(16)sign

8、listisetw(16)signencodeisetw(12)signrei setw(12)signcodevalueiendl;将token中的字符串与character中的字符连接作为t oke n中新的字符串 void Word:concatentation()for(int i=0;i100;i+)if(tokeni=NULL)tokeni=s;break;判断character中的字符是否为字母和数字的布尔函数，是则返回true，否则返回false bool Word:letter() if(s=a )return true;else if(s=A)return true;els

9、ereturn false;bool Word:digit()if(s=0)return true;return false;/按token数组中的字符串中的前五项(即判别其是否为保留字)，若是保留字则返回它的编 码int Word:reserve()int leng;/记录token数组中单词的长度for(int i=0;i100;i+)/计算token数组中单词的长度if(tokeni=NULL)leng=i;break;for(int i=0;ikeywordlist.size();i+)for(int j=0;jkeywordlisti.length();j+)if(keywordli

10、stij!二tokenj)/若某个字符不等则终止此次循环 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=tok

11、en0;if(letter()/第一个字符如果为字母,则将标识符登录到符号表中 fstream chartostring(convert.txt);if(!chartostring)coutError! Cant open convert fileendl; system(pause);for(int i=0;i100;i+)if(tokeni=NULL)break;else chartostringtokeni;chartostringendl;chartostring.close();chartostring.open(convert.txt); if(!chartostring)cout

12、Error! Cant open convert filetempre;chartostring.close();indentityre.push_back(tempre);tempword二标识符；tempencode=6;tempvalue=indentityre.size()；indentitylist.push_back(tempword)； indentityencode.push_back(tempencode)； indentitycodevalue.push_back(tempvalue)；fstream indentityfile(indentityword.txt)； if

13、(!indentityfile) coutError! Cant open indentityword fileendl； system(pause)；/先将文件指针移到最后去，再写入一个endlindentityfile.seekg(0,ios:end)；indentityfiletempwordsetw(8)tempencodesetw(12)tempresetw(12) tempvalue；indentityfile.seekg(0，ios:end)；indentityfileendl； indentityfile.close()；else/toke n中存储的是常数将token中的字符

14、数字转换为int类型fstream chartoint(convert.txt)；if(!chartoint)coutError! Cant open convert fileendl； system(pause)；for(int i=0；i100；i+) if(tokeni=NULL)break；elsechartointtokeni；chartointendl；chartoint.close();chartoint.open(convert.txt);if(!chartoint) coutError! Cant open convert filetempconstre; chartoint

15、.close();constlist.push_back(tempword);tempword=常数； tempencode=7;tempvalue=indentityre.size()； constencode.push_back(tempencode)； constre.push_back(tempconstre)； constvalue.push_back(tempvalue)；fstream constdigit(constdigit.txt)；if(!constdigit)coutError! Cant open constdigit file!endl； system(pause)

16、；exit(1)；/先将文件指针移到最后去，再写入一个endlconstdigit.seekg(0,ios:end)；constdigittempwordsetw(8)tempencodesetw(12)tempconstresetw(12) tempvalue；constdigit.seekg(0，ios:end)；constdigitendl；constdigit.close()；coutsetw(16)tempwordsetw(16)tempencodesetw(12)tempconstreset w(12)tempvalueendl；/出现非法字符，显示错误信息void Word:er

17、ror()coutError! Error word!endl；system(pause)；void Word:signinfor()按toke n数组中的字符串中的前五项(即判别其是否为保留字)，若是保留字则返回它 的编码int leng;/记录token数组中单词的长度for(int i=0;i100;i+)/计算token数组中单词的长度if(tokeni=NULL)leng=i; break;for(int i=0;isignlist.size();i+)for(int j=0;jsignlisti.length();j+)if(signlistij!=tokenj)/若某个字符不等则

18、终止此次循环 break;if(j+1=signlisti.length()/若比较字符全部相等，则判断两者是否长 度相等if(leng=signlisti.length()coutsetw(16)signlistisetw(16)signencodeisetw(12)signrei setw(12)signcodevalueiendl;/词法分析的函数void Word:run()coutsetw(16) 单词符号setw(16)种别编码setw(12) 助记符 setw(12) 内码值endl;fstream file(word.txt);if(!file)couterror，cant o

19、pen fileendl; system(pause);exit(1);file.unsetf(ios:skipws);while(s!=# & !file.eof()for(int i=0;is;while(s= )files; switch(s) case a;case b case c case de f g h i j k l m n o p q r s t u v w x y zcase case case case case case case case case case case case case case case case case case case case case

20、 casewhile(letter()|digit() concatentation();/将当前读入的字符送入token数组 files;/继续读字符，直到字符不为数字或字母为止 /扫描指针回退一个字符file.seekg(-1,ios:cur); code=reserve();if(!code) buildlist();elsecoutsetw(16)keywordlistcode-1setw(16)keywordencodecode-1setw (12)keywordrecode-1setw(12)keywordcodevaluecode-1endl;break;case0:case1:

21、case2:case3:case4:case5:case6:case7:case8:case9:while(digit()concatentation();/将当前读入的字符送入token数组 files;/继续读字符，直到字符不为数字为止 /扫描指针回退一个字符file.seekg(-1,ios:cur);buildlist();break;case +:concatentation();signinfor();break;case -:concatentation();signinfor();break;case *:concatentation();signinfor();break;c

22、ase s;if(s!=)/扫描指针回退一个字符file.seekg(-1,ios:cur); signinfor();elseconcatentation(); signinfor();break;case =:concatentation();files;if(s!=)/扫描指针回退一个字符 file.seekg(-1,ios:cur); signinfor();elseconcatentation(); signinfor();break;case ;:concatentation();signinfor();break;case #:coutendl;coutendl;coutsetw

23、(16) 词法分析结束!endl;system(pause);exit(1);default:error();file.close();void main()Word word; word.run(); system(pause);C:W1NDO WSsy5tem32cmd.eMK-Xwhile1uMleelse suitche Ise switch运行结果:casecase申词符号 wlkile if89111 214 种别编码1711助记符wliilei23-B-Tfl 内-语法分析器源程序：#include #include #include typedef structchar R;c

24、har r;int flag;array; typedef structchar E;char e;charLode; typedef structcharLode *base; int top;charstack;char str8080,arr8080,brr8080;array F20;int m,kk,p,ppp,FF=1;char r10;int crr2020,FLAG=0;char ccrr1120,ccrr2201;void Ini tst ack(chars tack &s) 定义栈s.base=new charLode20;s.top=-1;void push(charst

25、ack &s,charLode w)s.top+;s.bases.top.E=w.E;s.bases.top.e=w.e;void pop(charstack &s,charLode &w)w.E=s.bases.top.E;w.e=s.bases.top.e;s.top-;int IsEmpty(charstack s)if(s.top=-1)return 1;else return 0;int IsLetter(char ch)if(ch=A&ch=Z)return 1;else return 0;/judgel是判断是否是算符文法：若产生式中含有两个相继的非终结符则不是 算符文法int

26、judge1(int n)int j=3,flag=0;for(int i=0;i=n;i+)while(strij!=0)char a=strij;char b=strij+1;if(IsLetter(a)&IsLetter(b)flag=1;break;else j+;if(flag=1)return 0;elsereturn 1;judge2是判断文法G是否为算符优先文法：若不是算符文法或若文法中含空字或终结符的优先级不唯一则不是算符优先文法void judge2(int n)for(int i=0;i=n;i+)if(stri 3=T|judge1(n)=0|FLAG=1)/代表空字c

27、out 文法 G 不是算符优先文法!n)cou t文法G是算符优先文法!endl;/search1是査看存放终结符的数组r中是否含有重复的终结符int search1(char r,int kk,char a)for(int i=0;ikk;i+)if(ri=a)break;if(i=kk) return 0;else return 1;/createF函数是用F数组存放每个终结符与非终结符和组合，并且值每队的标 志位为0;F数组是一个结构体void createF(int n)int k=0,i=1;char g;char t10;/1数组用来存放非终结符t0=str00;while(i=n

28、)if(tk!=stri0) k+;tk=stri0;g=tk;i+; else i+;kk=0;char c; for(i=0;i=n;i+) int j=3;while(strij!=0)c=strij; if(IsLetter(c)=0) if(!search1(r,kk,c) rkk=c;kk+;/r数组用来存放终结符 j+; m=0;for(i=0;ik;i+)for(int j=0;jkk-1;j+) Fm.R=ti;Fm.r=rj;Fm.flag=0;m+; /search函数是将在F数组中寻找到的终结符与非终结符对的标志位值为1 void search(charLode w)

29、for(int i=0;im;i+)if(Fi.R=w.E&Fi.r=w.e) Fi.flag=1;break;void FirstVT(int n)/ 求 FirstVTcharstack sta; charLode w; int i=0; Initstack(sta); while(i=n)int k=3;w.E=stri0;char a=strik;char b=strik+1;if(!IsLe tt er(a)/产生式的后选式的第一个字符就是终结符的情况w.e=a;push(sta,w); search(w); i+;else if(IsLe tt er(a)&b!=O&!IsLe t

30、t er(b)/ 产生式的后选式的第 一个字符是非终结符的情况w.e=b;push(sta,w); search(w);i+;else i+;charLode ww;while(!IsEmpty(sta) pop(sta,ww);for(i=O;i=n;i+)w.E=striO;if(stri3=ww.E&stri4=O)w.e=ww.e;push(sta,w);search(w);break;p=O;int k=1;i=1;while(im)if(Fi-1.flag=1)arrpO=Fi-1.R;arrpk=Fi-1.r;while(Fi.flag=O&im)i+;if(Fi.flag=1)

31、if(Fi.R=arrp0)k+;else arrpk+1=0;p+;k=1;i+;void LastVT(int n)/求 LastVTcharstack sta;charLode w;for(int i=0;im;i+)Fi.flag=0;i=0;Initstack(sta);while(i=n)int k=strlen(stri);w.E=stri0;char a=strik-1;char b=strik-2;if(!IsLetter(a)w.e=a;push(sta,w);search(w);i+;else if(IsLetter(a)&!IsLetter(b)w.e=b;push(s

32、ta,w);search(w);i+;else i+;charLode ee;while(!IsEmpty(sta)pop(sta,ee);for(i=0;i=n;i+)w.E=stri0;if(stri3=ee.E&stri4=0) w.e=ee.e; push(sta,w); search(w);int k=1;i=1;ppp=0;while(im)if(Fi-1.flag=1)brrppp0=Fi-1.R;brrpppk=Fi-1.r;while(Fi.flag=0&im)i+;if(Fi.flag=1)if(Fi.R=arrppp0)k+;else brrpppk+1=0;ppp+;k

33、=1; i+;void createYXB(int n)/构造优先表int i,j;for(j=1;j=kk;j+) ccrr10j=rj-1;for( i=1;i=kk;i+)ccrr2i0=ri-1;for(i=1;i=kk;i+) for(j=1;j=kk;j+) crrij=0; int I=0,J=3; while(I=n) if(strIJ+1=0)I+;J=3;elsewhile(strIJ+1!=0)char aa=strIJ;char bb=strIJ+1;if(!IsLetter(aa)&!I sLetter(bb)/优先及等于的情况，用1值表示等于 for(i=1;i=k

34、k;i+) if(ccrr2i0=aa)break;for(j=1;j=kk;j+)if(ccrr10j=bb)break;if(crrij=0)crrij=1;else FLAG=1;I=n+1;J+;if(!IsLetter(aa)&IsLetter(bb )&strIJ+2!=0&!IsLetter(strIJ+2)/优先及等 于的情况for(i=1;i=kk;i+)if(ccrr2i0=aa)break;for(int j=1;j=kk;j+)if(ccrr10j=strIJ+2)break;if(crrij=0)crrij=1;else FLAG=1;I=n+1;if(!IsLett

35、er(aa)&IsLetter(bb)优先及小于的情况，用2值表示小于for(i=1;i=kk;i+)if(aa=ccrr2i0)break; for(j=0;j=p;j+)if(bb=arrj0)break;for(int mm=1;arrjmm!=0;mm+)for(int pp=1;pp=kk;pp+)if(ccrr10pp=arrjmm)break; if(crripp=0) crripp=2; else FLAG=1;I=n+1;J+;f(IsLetter(aa)&!IsLetter(bb)/优先及大于的情况，用3值表示大于 for(i=1;i=kk;i+) if(ccrr10i=b

36、b)break; for(j=0;j=ppp;j+) if(aa=brrj0)break;for(int mm=1;brrjmm!=0;mm+)for(int pp=1;pp=kk;pp+)if(ccrr2pp0=brrjmm)break;if(crrppi=0) crrppi=3;else FLAG=1;I=n+1;J+;/judge3是用来返回在归约过程中两个非终结符相比较的值int judge3(char s,char a)int i=1,j=1;while(ccrr2i0!=s)i+;while(ccrr10j!=a)j+;if(crrij=3) return 3;else if(cr

37、rij=2)return 2;else if(crrij=1)return 1;else return 0;void print(char s,char STR20,int q,int u,int ii,int k)/打印归约的过程coutu ;for(int i=0;i=k;i+)coutsi;cout ;for(i=q;i=ii;i+)coutSTR0i;cout ;void process(char STR20,int ii)对输入的字符串进行归约的过程coutvv步骤 符号栈vvVV输入串 动作vvendl;int k=0,q=0,u=0,b,i,j;char s40,a;sk=#;p

38、rint(s,STR,q,u,ii,k);coutvv预备vvendl;k+;u+;sk=STR0q;q+;print(s,STR,q,u,ii,k);coutvv移进vvendl;while(q=ii)a=STR0q; if(!IsLetter(sk) j=k; else j=k-1;b=judge3(sj,a);if(b=3)大于的情况进行归约while(IsLetter(sj-1)j-;for(i=j;in;for(i=0;ivn;i+)gets(stri);j=strlen(stri);strij=0; stri0=Q; stri1=-; stri2=; stri3=#; stri4=

39、str00; stri5=#;stri6=0;coutvv你定义的产生式如下:vvendl;for(i=0;i=n;i+)coutvvstrivvendl;if(judge1(n)=0)判断文法G是否为算符文法 coutvv文法G不是算符文法!vvendl; if(judge1(n)=1)coutvv文法G是算符文法!vvendl; createF(n);FirstVT(n); LastVT(n); createYXB(n);judge2(n);判断文法G是否为算符优先文法if(FLAG=0)for(i=0;iv=p;i+)/打 印 FirstVT coutvvFirstVT(vvarri0v

40、v)=;for(int l=1;arril+1!=0;l+) coutvvarrilvv,; coutvvarrilvvvvendl;coutvvFirstVT(Q)=#vvendl; for(i=0;iv=ppp;i+)/打印 LastVT coutvvLastVT(vvarri0vv)=;for(int l=1;brril+1!=0;l+) coutvvbrrilvv,;coutvvbrrilvvvvendl;coutvvLastVT(Q)=#vvendl; coutvv优先表如下:vvendl; for(i=1;ivkk;i+)打印优先关系表 coutvv ;coutccrr10i;co

41、utendl;for(i=1;ikk;i+)coutccrr2i0 ;for(j=1;jkk;j+)if(crrij=0)cout ;else if(crrij=1)cout=;else if(crrij=2)cout;else if(crrij=3)cout;cout ;coutE*IE-E-IE-Tfc-T*FI-T/FT-FF-PAFF-PP-XEP-i你定冥的产生式如下E-E*IE-I-IE-T*T 好I-T/FI-P严 FF-PP-XEP-iQ-SEH文法石是算符文法f中间代码生成器源程序：/* 表达式生成四元式 递归子程序法*/#include vstdioh #include v

42、string.h #include vmalloc.h #includeviostream.h#includevstdlib.h#define STACK_INIT_SIZE 50 #define STACKINCREMENT 5 #define ERROR 0#define OVERFLOW -2 #define TRUE 1 #define FALSE 0 #define OK1#define NULL 0 void sub_E(); void sub_F(); void sub_T(); void sub_G(); void GEQ(char m); void PRINT(); type

43、def struct Stack char *base; char *top; int stacksize;Stack;int num=0;char QT104,T=A,c;struct Stack SEM;struct initStack(Stack s)s.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;return OK;/初始化堆栈char pop(Stack &s)char e;if(s.top=s.

44、base)printf(”栈中已无元素!”)；exit(ERROR);e=*-s.top；return e；/出栈struct push(Stack &s,char e)if(s.top-s.base=s.stacksize)s.base=(char *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char)； if(!s.base)exit(OVERFLOW)；s.top=s.base+s.stacksize；s.stacksize+=STACKINCREMENT；*s.top+=e；return OK；/入栈void main()i

45、nitStack(SEM)；printf(表达式应由小写字母、运算符及小括号组成,并以#结束n)；printf(请输入表达式:”)；c=getchar()；sub_E();if(c=#) PRINT();elseprintf(无结束符或漏写运算符!”); exit(0);getchar();void sub_E() sub_T();R1: if(c=+) c=getchar(); sub_T(); GEQ(+); goto R1;else if(c=-) c=getchar();sub_T(); GEQ(-); goto R1;else ;void sub_T() sub_G();R4: if

46、(c=*) c=getchar(); sub_F(); GEQ(*); goto R4;else if(c=/) c=getchar(); sub_F();GEQ(/);goto R4;void sub_F()sub_G();R5: if(c=A，)c=getchar();sub_G();GEQD;goto R5;void sub_G()if(c=a&c=z)push(SEM,c);c=getchar();else if(c=()c=getchar();sub_E();if(c=) c=getchar();elseprintf(括号不匹配!”); exit(0);elseprintf(非法符号

47、!)； exit(0);void GEQ(char m)QTnum0=m;QTnum2=pop(SEM);QTnum1=pop(SEM);QTnum3=T;push(SEM,T);num+;T+;void PRINT()printf(您输入的表达式所对应的四元式为:n);for(int i=0;inum;i+)printf();printf(%c,QTi0);if(QTi1=A)printf(t%c%d,t,QTi1-A+1);elseprintf(t%c,QTi1);if(QTi2=A)printf(t%c%d,t,QTi2-A+1);elseprintf(t%c,QTi2);if(QTi3

48、=A)printf(t%c%d,t,QTi3-A+1);elseprintf(t%c,QTi3);printf()n);六、总结谈谈自己的收获与体会。1、通过这次实验，我对词法分析器有了进一步的了解，把理论知识应用于实验 中。也让我重新熟悉了C语言的相关内容，加深了对C语言知识的深化和用 途的理解。通过这次语义分析的实验, 我对高级语言的学习有了更深的认 识 ，了解得更透彻。2、我了解了高级语言转化为目标代码或汇编指令的过程,。对今后的学习将起很 大的作用,对以后的编程有很大的帮助. 本次实验虽然只是完成了一个简单的 程序，并且程序的主要框架课本上有给出，但在组织程序结构和深入了确上 学到了很多，加深对编译原理的理解,掌握编译程序的实现方法和技术。巩固 了前面所学的知识。