2022年编译原理词法分析器语法分析器实验分析方案.docx
精选学习资料 - - - - - - - - - 编译技术 班级网络 0802学 号 3080610052姓 名 叶晨舟指导老师 朱 玉 全2022 年 7 月 4 日一、目的编译技术是理论与实践并重的课程,而其试验课要综合运用一、二年级所学的多门课1 / 21 名师归纳总结 - - - - - - -第 1 页,共 21 页精选学习资料 - - - - - - - - - 程的内容,用来完成一个小型编译程序;从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的熟识和懂得;培育同学对完整系统的独立分析和设计的才能,进一步培育同学的独立编程才能;二、任务及要求基本要求:1词法分析器 产生下述小语言的单词序列这个 小语言 的全部的单词符号,以及它们的种别编码和内部值如下表:单词符号 种别编码 助记符 内码值DIM 1 $DIM - IF 2 $IF - DO 3 $DO - STO 4 $STOP - P 5 $END - END 6 $ID - 标识符 7 $INT 内部字符串常数 <整)8 $ASSIG 标准二进形式= 9 N - + 10 $PLUS - * 11 $STAR - * 12 $POWE- ,13 R - < 14 $COM- )MA $LPAR $RPAR 对于这个 小语言 ,有几点重要的限制:第一 ,全部的关键字 <如 IF WHILE等)都是“ 保留字” ;所谓的保留字的意思是,用户不得使用它们作为自己定义的标示符;例如,下面的写法是肯定禁止的: IF<5)=x 其次 ,由于把关键字作为保留字,故可以把关键字作为一类特别标示符来处理;也就是说,对于关键字不专设对应的转换图;但把它们 <及其种别编码)预先支配在一张表格中 <此表叫作保留字表);当转换图识别出一个标识符时,就去查对这张表,确定它是否为一个关键字;再次 ,假如关键字、标识符和常数之间没有确定的运算符或界符作间隔,就必需至少用一个空白符作间隔 如,一个条件语句应写为<此时,空白符不再是完全没有意义的了);例 IF i>0 i= 1;而肯定不要写成IFi>0 i=1;由于对于后者,我们的分析器将无条件地将IFI 看成一个标识符;这个小语言的单词符号的状态转换图,如下图:2 / 21 名师归纳总结 - - - - - - -第 2 页,共 21 页精选学习资料 - - - - - - - - - 2语法分析器 能识别由加 + 减- 乘* 除/ 乘方 括号 <)操作数所组成的算术 表达式,其文法如下:EE+T|E-T|T TT*F|T/F|F FPF|P pE>|i 使用的算法可以是:猜测分析法;递归下降分析法;算符优先分析法;LR 分析法等;3中间代码生成器产生上述算术表达式的中间代码<四元式序列)三、实现过程给出各题目的具体算法描述,数据结构和函数说明,流程图;3 / 21 名师归纳总结 - - - - - - -第 3 页,共 21 页精选学习资料 - - - - - - - - - 1、词法分析器的流程图 开头输入源文件路径否路径是否有效是打开源文件初始化文件指针识别指针内容文件终止?是终止否回退是空格,空白或换否是字母吗否是数字吗否是界符吗否将字符加入字符数行吗组Word是是是将字符加是是将字符将字符加入字符数将字符跳过该字符入字符数组Word加入字组Word加入字符数组指向下一字符符数组Word指向下一字符指向下一字符Word是字母惑数字识别指针内容输出 word输出Word内容为不吗为界符是数字吗可识别否将word与关键字表 key进行匹输出 word为否配否指向下一字符匹配?输出word一般标示符为常数是输出 word为关键字2、语法分析器主程序图4 / 21 名师归纳总结 - - - - - - -第 4 页,共 21 页精选学习资料 - - - - - - - - - 3、中间代码生成器流程图:四、源程序词法分析器 : #include<string.h> #include<malloc.h> 5 / 21 名师归纳总结 - - - - - - -第 5 页,共 21 页精选学习资料 - - - - - - - - - #include<iostream> using namespace std;typedef struct table / 分析表储备结构 char m100 ;table ;table M100100 ; /定义分析表typedef struct stacknode / 定义栈内元素节点 char data; struct stacknode *next ;stackk ;void initlinkstackk *&s> / 初始化新栈 s=stackk *>mallocsizeofstackk>>; s->next=NULL ; void poplinkstackk *&s> / 顶元素出栈 stackk *p ;char v; ifs->next.=NULL> p=s->next ; v=p->data ; s->next=p->next ; freep>; 带头结点 <为空)的 > void pushlinkstackk *&s,char x> / 新 元 素 入 栈 stackk *p ; p=stackk *>mallocsizeofstackk>>; p->data=x; p->next=s->next ; s->next=p; void displaystackk *s> / 打印 现实显示 栈内元素 6 / 21 名师归纳总结 - - - - - - -第 6 页,共 21 页精选学习资料 - - - - - - - - - stackk *p ; int i=0,j ; char st100 ; p=s->next; whilep.=NULL> sti+=p->data ; p=p->next ; forj=i-1 ;j>=0 ; j-> printf"%c",stj>; forj=0 ; j<16-i ; j+> / 打印 对齐格式 printf"%c",' '> ; char gettopstackk *s> / 返 回 栈 顶 元 素 值 ifs->next=NULL> return 0; else return s->next->data ; int findchar c,char array> / 查找函数, int i ;int flag=0 ;fori=0 ;i<100; i+> ifc=arrayi> flag=1 ; return flag ; int locationchar c,char array> / 定位函数 ,指出字符所在位置 int i ;fori=0 ;i<100; i+> ifc=arrayi> 7 / 21 名师归纳总结 - - - - - - -第 7 页,共 21 页精选学习资料 - - - - - - - - - return i; void error> / 出错函数定义 printf"%15c 出错 .n",' '> ; void analysechar Vn,char Vt> int i,j,m,p,q,length,t,h ; char w,X; char str100 ;opt0: scanf"%s",str> ; fori=0 ; i<strlenstr> ;i+> if.findstri,Vt>> printf" 输入字符串有误 .请重新输入 ."> ; goto opt0 ; break; stackk *st ; initlinkst> ; pushlinkst,'#'> ; pushlinkst,Vn0> ; /#与识别符号入栈 j=0 ; h=1; w=str0 ; printf" 步骤 %-12c分析栈 %-24c剩余输入串 %-12c所用产生式 n",' ',' ',' '> ;opt1: printf"%-16d",h> ; /显示步骤 h+; displayst> ; / 显示分析栈中内容 X=gettopst> ; / 上托栈顶符号放入 X poplinkst> ; forint k=0 ;k<14+j ;k+> / 打印对齐格式 printf"%c",' '> ;8 / 21 名师归纳总结 - - - - - - -第 8 页,共 21 页精选学习资料 - - - - - - - - - fort=j ;t<strlenstr> ;t+> printf"%c",strt>; /显示剩余字符串 iffindX,Vt>&& X.='#'> / ifX=w> 分析栈的栈顶元素和剩余输入串的第一个元素相比较 printf"%15c 匹配 n",X> ; j+ ; w=strj ; goto opt1; else error> ; else ifX='#'> ifX=w> printf"%8c 是该文法的句子!n",' '> ; else error> ; else p=locationX,Vn> ; q=locationw,Vt> ; char *S1="null",*S2="NULL"; ifstrcmpMpq.m,S1>=0|strcmpMpq.m,S2>=0> / 查找产生式 error> ; else char str0100 ; strcpystr0,Mpq.m>; printf"%15c->%sn",X,str0> ifstrcmpstr0,"$">=0> goto opt1; else ; /显示对应的产生式9 / 21 名师归纳总结 - - - - - - -第 9 页,共 21 页精选学习资料 - - - - - - - - - length=strlenstr0> ; /逆序进栈 form=length-1 ;m>=0 ;m-> pushlinkst,str0m> ; goto opt1; int main> int i,k,n,r ; char Vn100,Vt100,select ;printf"*n">; printf" 对任意输入 LL1> 文法的分析表,判定验证字符串是否为该文法的句子 n"> ; printf" 并能给出分析和演示过程; n"> ;printf"*n">;opt2: printf" 请输入各终结符<#号表示终止)Vti:n"> ; fori=0 ;i<100 ;i+> scanf"%c",&Vti>; ifVti='#'> r=i; break; printf" 请输入非终结符个数 :n"> ; scanf"%d",&n> ; getchar>; for i=0 ;i<n ;i+> printf" 请输入非终结符 Vn%d:n",i> ; scanf"%c",&Vni>; getchar>;10 / 21 名师归纳总结 - - - - - - -第 10 页,共 21 页精选学习资料 - - - - - - - - - printf" 请输入此非终结符对应各终结符的产生式右部 串>:n"> ; fork=0 ;k<=r ;k+> scanf"%s",Mik.m>; getchar>; opt3: null 或NULL 表示出错; $表示空 printf" 请输入要分析的字符串,且以 #终止 :n"> ; analyseVn, Vt> ; printf"*请挑选 *n">; printf" 1: 输入字符串 n"> ; printf" 2: 输入新分析表 n"> ; printf" 0: 退 出 n"> ; printf"*n">;opt4: cin>>select; switchselect> case '1': goto opt3 ;break; case '2': goto opt2 ; case '0': break; default: printf" 输入错误 .请重新挑选 :">; goto opt4; break; return 0;运行结果:11 / 21 名师归纳总结 - - - - - - -第 11 页,共 21 页精选学习资料 - - - - - - - - - 语法分析器 源程序:#include<string.h> #include<iostream> using namespace std;char prog100,token10 ;char ch;int syn,p,m=0,n,row,sum=0 ;char *rwtab20="dim","if","do","stop","end" ,"and","begin","bool","case","char", "false","for","int","not","or","set","then","true","until","while" ;void scaner> forn=0 ;n<9;n+> tokenn=NULL;ch=progp+ ;whilech=' '> ch=progp ;p+; ifch>='a'&&ch<='z'>|ch>='A'&&ch<='Z'>> 12 / 21 名师归纳总结 - - - - - - -第 12 页,共 21 页精选学习资料 - - - - - - - - - m=0;whilech>='0'&&ch<='9'>|ch>='a'&&ch<='z'>|ch>='A'&&ch<='Z'>> tokenm+=ch ;ch=progp+ ; tokenm+='0' ;p-;syn=21;forn=0 ;n<20;n+> ifstrcmptoken,rwtabn>=0> syn=n+1;break; else ifch>='0'&&ch<='9'>> sum=0;whilech>='0'&&ch<='9'>> sum=sum*10+ch-'0' ;ch=progp+ ; p-;syn=7+15;ifsum>32767> syn=-1; else switchch> case'=':syn=8+15;token0=ch ;break;case'+':syn=9+15;token0=ch ;break;case'*': m=0;tokenm+=ch ;ch=progp+ ;ifch='*'> 13 / 21 名师归纳总结 - - - - - - -第 13 页,共 21 页精选学习资料 - - - - - - - - - syn=11+15; tokenm+=ch ; else syn=10+15;p-; break;case',':syn=12+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+ ;ifch='>'> syn=17+15;tokenm+=ch ; else ifch='='> syn=16+15;tokenm+=ch ; else syn=15+15;p-; break;case'>':m=0;tokenm+=ch ;ch=progp+ ;ifch='='> syn=19+15;tokenm+=ch ; else syn=18+15;p-;14 / 21 名师归纳总结 - - - - - - -第 14 页,共 21 页精选学习资料 - - - - - - - - - break;case':':m=0; tokenm+=ch ;ch=progp+ ;ifch='='> syn=21+15;tokenm+=ch ; else syn=20+15;p-; break;case'/':syn=22+15; token0=ch ;break;case'-':syn=23+15;token0=ch ;break;case'; ':syn=24+15 ; token0=ch ;break;default: syn=-1 ;break; void main> p=0;row=1 ;cout<<endl<<endl<<endl ;cout<<"*小;型词法分析器*"<<endl<<endlcout<<" 请输入一段程序<以#终止) :" ;do cin.getch>;progp+=ch ; whilech.='#'> ;p=0;cout<<endl<<"*词法分析结果如下*"<<endl;cout<<" 种别编码自身值 "<<endl ;do scaner>;switchsyn> 15 / 21 名师归纳总结 - - - - - - -第 15 页,共 21 页精选学习资料 - - - - - - - - - case 22 : cout<<" "<<syn<<" , "<<sum<<">"<<endl;break; case -1: cout<< " Error in row"<<row<<"."<<endl; break; default: cout<<" "<<syn<<" , "<<token<<">"<<endl;break; while syn.=0> ; 运行结果:中间代码生成器源程序:表达式生成四元式 递归子程序法#include<string> #include <iostream> using namespace std;#define DEFAULT_SIZE 100 char EMachinechar w> ; /表达式 E 的自动机 char TMachinechar w> ; /表达式 T 的自动机16 / 21 名师归纳总结 - - - - - - -第 16 页,共 21 页精选学习资料 - - - - - - - - - char FMachinechar w> ; /表达式 F的自动机 bool ZMachine> ; /表达式 Z 的自动机 string intToStringint a> ; /整形变成字符串形函数class stack /栈类定义 private: int top ; string *stacka ; int maxsize ;public: stackint size=DEFAULT_SIZE>; stack> delete stacka ; void pushconst string &item> ; string popvoid> ; string gettopvoid> const ; bool emptyvoid> const return top=-1>; bool fullvoid> const return top=maxsize-1>; void clearvoid> top=-1; ;stack:stackint size> /栈类的构造函数 top=-1; maxsize=size; stacka=new stringmaxsize ; if.stacka> cerr<<"allocate memory failed."<<endl; exit1> ; void stack:pushconst string &item> / 压栈操作 iffull>> cerr<<"stack full, cannot push."<<endl ; return; top+; stackatop=item ; 17 / 21 名师归纳总结 - - - - - - -第 17 页,共 21 页精选学习资料 - - - - - - - - - string stack:popvoid> /出栈操作 ifempty>> cerr<<"stack empty, cannot pop."<<endl ; exit1> ; string item=stackatop ; top- ; return item ; string stack:gettopvoid> const /取栈顶操作 ifempty>> cerr<<"stack empty, cannot gettop."<<endl ; exit1> ; return stackatop ; static stack wordStack ; /符号栈 /主函数static int noOfQuet=0 ; /静态四元式个数记录static int noOfT = 1 ; /静态状态个数记录void main> /进行一个循环操作掌握char yesOrNo ;do cout<<" 请输入算术表达式:"<<endl ;/每次终止询问noOfT = 1 ;ZMachine> ;cout<<endl<<"Continue.Yes or Not:" ;cin>>yesOrNo ; / 输入“Y” 就连续 whileyesOrNo='y'>;/否就程序终止 bool ZMachine> /Z 自动机 char w;cin>>w ;w = EMachinew> ; /调用 E 自动机 #” 就终止 ifw='#'> / 遇到“return true; 18 / 21 名师归纳总结 - - - - - - -第 18 页,共 21 页精选学习资料 - - - - - - - - - else return false; char EMachinechar w> /E 自动机 string operate,a,b,c;string state5 ;w = TMachinew> ; /调用 T 自动机 whilew='+'|w='-'> /是加或减符号 operate = w;cin>>w ; /调用 T 自动机 /读入下一字符w = TMachinew> ;b = wordStack.pop> ; /字符栈弹出 a = wordStack.pop> ; /两个操作字符 cout<<"""<<operate<<"","<<a<<","<<b<<",t"<<noOfT<<">"<<endl;c = "t"+intToStringnoOfT>; /输出四元式 wordStack.pushc> ; /新状态压栈 noOfT+ ; /状态计数加一 return w; char TMachinechar w> string operate,a,b,c;string state5 ;w = FMachinew> ;/调用 F 自动机 whilew='*'|w='/'> /是乘除号 operate = w;cin>>w ; /调用 F 自动机 /读取下一字符w = FMachinew> ;b = wordStack.pop> ; /符号栈弹出 a = wordStack.pop> ; /两个操作字符 cout<<"""<<operate<<"","<<a<<","<<b<<",t"<<noOfT<<">"<<endl;c = "t"+intToStringnoOfT>; /输出四元式 wordStack.pushc> ; /新状态压栈 noOfT+ ; /状态计数加 1 return w; char FMachinechar w> /F 自动机 string theWord ;ifw>='a'&&w<='z'|w>='A'&&w<='Z'> 19 / 21 名师归纳总结 - - - - - - -第 19 页,共 21 页精选学习资料 - - - - - - - - - theWord = w ; /当前字符是字母 wordStack.pushtheWord> ;/就压栈 else ifw = ''> /是左括号 /就读取下一字符cin>>w ; /调用 E 自动机w = EMachinew> ;ifw.='>'> /不是右括号就输入有误,报错cerr<<"the input is wrong."<<endl;exit0> ; else /否就有误,报错;cerr<<"the input is wrong."<<endlexit0> ; cin>>w ; /读取下一字符 return w; string intToStringint a> /整形变字符串形函数 string d;char b='0',c;int i ;whilea.=0> i = a%10;a = a/10;c = int>b + i ;d = c + d; return d; /Y=a+b*c+-d>*e+f>> /Y=a+b*c-d*e/f+g*h-i*x*j+k*-l>*j+k>>>+w>> /H=d+a-c+b-q>*a>+c-a+b*c+d>> 六、总结通过这次试验,我对编译原理这门专业必修课有了进一步的深层次明白,把理论学问应用于试验中,也让我重新熟识了C+语言的相关内容,加深了对20 / 21 名师归纳总结 - - - - - - -第 20 页,共 21 页精选学习资料 - - - - - - - - - C+语言学问的深化和用途的懂得;信任在以后的毕业设计以及读研自己做工程时可以有更大的提升;21 / 21 名师归纳总结 - - - - - - -第 21 页,共 21 页