《2022年编译原理词法分析器语法分析器实验分析方案》由会员分享,可在线阅读,更多相关《2022年编译原理词法分析器语法分析器实验分析方案(21页珍藏版)》请在金锄头文库上搜索。
1、1 / 21 编译技术班级网络 0802学号 3080610052姓名 叶晨舟指导老师朱 玉 全2018 年 7 月 4 日一、目的编译技术是理论与实践并重的课程,而其实验课要综合运用一、二年级所学的多门课精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页,共 21 页2 / 21 程的内容,用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解;培养学生对完整系统的独立分析和设计的能力,进一步培养学生的独立编程能力。二、任务及要求基本要求:1词法分析器产生下述小语言的单词序列这个小语言 的
2、所有的单词符号,以及它们的种别编码和内部值如下表:单词符号种别编码助记符内码值DIM IF DO STOP END 标识符常数 整)= + * * , )1 2 3 4 5 6 7 8 9 10 11 12 13 14 $DIM $IF $DO $STOP $END $ID $INT $ASSIGN $PLUS $STAR $POWER $COMMA $LPAR $RPAR - - - - - - 内部字符串标准二进形式- - - - - - 对于这个 小语言 ,有几点重要的限制:首先,所有的关键字 如 IFWHILE等)都是“保留字”。所谓的保留字的意思是,用户不得使用它们作为自己定义的标示
3、符。例如,下面的写法是绝对禁止的: IF5)=x 其次 ,由于把关键字作为保留字,故可以把关键字作为一类特殊标示符来处理。也就是说,对于关键字不专设对应的转换图。但把它们及其种别编码)预先安排在一张表格中 此表叫作保留字表)。当转换图识别出一个标识符时,就去查对这张表,确定它是否为一个关键字。再次 ,如果关键字、标识符和常数之间没有确定的运算符或界符作间隔,则必须至少用一个空白符作间隔0 i= 1。而绝对不要写成IFi0 i=1。因为对于后者,我们的分析器将无条件地将IFI 看成一个标识符。这个小语言的单词符号的状态转换图,如下图:精选学习资料 - - - - - - - - - 名师归纳总结
4、 - - - - - - -第 2 页,共 21 页3 / 21 2语法分析器 能识别由加 + 减- 乘* 除/ 乘方 括号|i使用的算法可以是:预测分析法;递归下降分析法;算符优先分析法;LR 分析法等。3中间代码生成器产生上述算术表达式的中间代码四元式序列)三、实现过程给出各题目的详细算法描述,数据结构和函数说明,流程图。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页,共 21 页4 / 21 1、词法分析器的流程图开始输入源文件路径路径是否有效是初始化文件指针否将字符加入字符数组Word是空格,空白或换行吗是字母吗是数字吗否否是界符吗
5、否打开源文件跳过该字符是是文件结束?否将字符加入字符数组Word否将字符加入字符数组Word是指向下一字符识别指针内容指向下一字符是字母惑数字吗是将word与关键字表 key进行匹配否匹配?是输出 word为关键字输出 word为普通标示符否将字符加入字符数组Word指向下一字符输出word为常数识别指针内容回退是数字吗是否输出 word为界符指向下一字符结束是输出Word内容为不可识别将字符加入字符数组Word2、语法分析器主程序图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页,共 21 页5 / 21 3、中间代码生成器流程图:四、源程
6、序词法分析器 : #include #include 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页,共 21 页6 / 21 #include using namespace std。typedef struct table / 分析表存储结构 char m100 。table 。table M100100 。 /定义分析表typedef struct stacknode / 定义栈内元素节点 (带头结点 char data。 struct stacknode *next 。stackk 。void initlink(stackk *&s
7、 /初始化新栈 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-next=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 displa
8、y(stackk *s / 打印 现实显示栈内元素 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页,共 21 页7 / 21 stackk *p。 int i=0,j 。 char st100 。 p=s-next。 while(p!=NULL sti+=p-data 。 p=p-next 。 for(j=i-1 。j=0。 j- printf(%c,stj。 for(j=0 。 j / 打印 对齐格式 printf(%c, 。 char gettop(stackk *s / 返 回 栈 顶 元 素 值 if(s-next=NULL ret
9、urn 0。 else return s-next-data。 int find(char c,char array / 查找函数, int i。int flag=0 。for(i=0 。i if(c=arrayi flag=1 。 return flag 。 int location(char c,char array / 定位函数 ,指出字符所在位置 int i。for(i=0 。i if(c=arrayi 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页,共 21 页8 / 21 return i。 void error( / 出错函数
10、定义 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 。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(
11、步骤 %-12c分析栈 %-24c剩余输入串 %-12c所用产生式 n, , , 。opt1: printf(%-16d,h 。 /显示步骤 h+。 display(st。 / 显示分析栈中内容 X=gettop(st 。 /上托栈顶符号放入X poplink(st 。 for(int k=0 。k / 打印对齐格式 printf(%c, 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页,共 21 页9 / 21 for(t=j 。t 。t+ printf(%c,strt。 /显示剩余字符串 if(find(X,Vt& X!=# /分析栈的
12、栈顶元素和剩余输入串的第一个元素相比较 if(X=w printf(%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 char str0100 。 strcpy(str0,Mpq.m。
13、printf(%15c-%sn,X,str0。 /显示对应的产生式 if(strcmp(str0,$=0 goto opt1。 else 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页,共 21 页10 / 21 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(*n。 printf( 对任意输入 LL(1 文法的分析表
14、,判断验证字符串是否为该文法的句子 n。 printf( 并能给出分析和演示过程。 n 。printf(*n。opt2: printf( 请输入各终结符 。 for(i=0 。i scanf(%c,&Vti。 if(Vti=# r=i。 break。 printf( 请输入非终结符个数:n 。 scanf(%d,&n 。 getchar(。 for (i=0 。i printf( 请输入非终结符Vn%d:n,i 。 scanf(%c,&Vni。 getchar(。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页,共 21 页11 / 21
15、printf( 请输入此非终结符对应各终结符的产生式右部(null 或NULL 表示出错。 $表示空串:n 。 for(k=0 。k scanf(%s,Mik.m。 getchar(。 opt3: printf( 请输入要分析的字符串,且以#结束 :n 。 analyse(Vn, Vt 。 printf(*请选择 *n。 printf( 1: 输入字符串 n 。 printf( 2: 输入新分析表 n 。 printf( 0: 退 出 n 。 printf(*n。opt4: cinselect。 switch(select case 1: goto opt3。break。 case 2: go
16、to opt2。 case 0: break。 default: printf( 输入错误 !请重新选择 :。 goto opt4。 break。 return 0。运行结果:精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页,共 21 页12 / 21 语法分析器源程序:#include #include 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,begi
17、n,bool,case,char, false,for,int,not,or,set,then,true,until,while 。void scaner( for(n=0 。n tokenn=NULL。ch=progp+ 。while(ch= ch=progp 。p+。 if(ch=a&ch|(ch=A&ch 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页,共 21 页13 / 21 m=0。while(ch=0&ch|(ch=a&ch|(ch=A&ch tokenm+=ch 。ch=progp+ 。 tokenm+=0 。p-。syn
18、=21。for(n=0 。n if(strcmp(token,rwtabn=0 syn=n+1。break。 else if(ch=0&ch sum=0。while(ch=0&ch sum=sum*10+ch-0 。ch=progp+ 。 p-。syn=7+15。if(sum32767 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=* 精选学习资料 - - - - - - - - - 名师
19、归纳总结 - - - - - - -第 13 页,共 21 页14 / 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 syn=17+15。tokenm+=ch 。 else if(ch= syn=16+15。tokenm+=ch 。 else syn=15+15。p-。 b
20、reak。case:m=0。tokenm+=ch 。ch=progp+ 。if(ch= syn=19+15。tokenm+=ch 。 else syn=18+15。p-。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页,共 21 页15 / 21 break。case:m=0。 tokenm+=ch 。ch=progp+ 。if(ch= syn=21+15。tokenm+=ch 。 else syn=20+15。p-。 break。case/:syn=22+15。 token0=ch 。break。case-:syn=23+15。token
21、0=ch 。break。case 。 :syn=24+15。 token0=ch 。break。default: syn=-1 。break。 void main( p=0。row=1。coutendlendlendl 。cout*小型词法分析器*endlendl。cout 请输入一段程序。progp+=ch 。 while(ch!=# 。p=0。coutendl*词法分析结果如下*endl。cout 种别编码自身值 。switch(syn 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页,共 21 页16 / 21 case 22 : c
22、out (syn , sumendl。break。 case -1: cout Error in rowrow!endl。 break。 default: cout (syn , token 。 运行结果:中间代码生成器源程序:表达式生成四元式递归子程序法#include #include using namespace std。#define DEFAULT_SIZE 100 char EMachine(char w 。 /表达式 E 的自动机char TMachine(char w 。 /表达式 T 的自动机精选学习资料 - - - - - - - - - 名师归纳总结 - - - - -
23、 - -第 16 页,共 21 页17 / 21 char FMachine(char w 。 /表达式 F的自动机bool ZMachine( 。 /表达式 Z 的自动机string intToString(int a 。 /整形变成字符串形函数class stack /栈类定义 private: int top。 string *stacka 。 int maxsize。public: stack(int size=DEFAULT_SIZE。 stack( delete stacka 。 void push(const string &item 。 string pop(void 。 st
24、ring gettop(void const 。 bool empty(void const return (top=-1。 bool full(void const return (top=maxsize-1。 void clear(void top=-1。 。stack:stack(int size /栈类的构造函数 top=-1。 maxsize=size。 stacka=new stringmaxsize 。 if(!stacka cerrallocate memory failed. 。 void stack:push(const string &item / 压栈操作 if(ful
25、l( cerrstack full, cannot push. /出栈操作 if(empty( cerrstack empty, cannot pop. 。 string item=stackatop 。 top-。 return item 。 string stack:gettop(void const /取栈顶操作 if(empty( cerrstack empty, cannot gettop. 。 return stackatop 。 static stack wordStack。 /符号栈static int noOfQuet=0 。 /静态四元式个数记录static int noO
26、fT = 1 。 /静态状态个数记录void main( /主函数char yesOrNo。 /进行一个循环操作控制do cout 请输入算术表达式: 。coutendlyesOrNo 。 /输入“ Y”则继续while(yesOrNo=y。/否则程序结束 bool ZMachine( /Z 自动机char w。cinw 。w = EMachine(w 。 /调用 E 自动机if(w=# /遇到“ #”则结束return true。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页,共 21 页19 / 21 else return fal
27、se。 char EMachine(char w /E 自动机string operate,a,b,c。string state5。w = TMachine(w 。 /调用 T 自动机while(w=+|w=- /是加或减符号operate = w。cinw 。 /读入下一字符w = TMachine(w 。 /调用 T 自动机b = wordStack.pop( 。 /字符栈弹出a = wordStack.pop( 。 /两个操作字符cout(operate,a,b,tnoOfT。 /输出四元式wordStack.push(c 。 /新状态压栈noOfT+ 。 /状态计数加一 return
28、w。 char TMachine(char w string operate,a,b,c。string state5。w = FMachine(w 。/调用 F 自动机while(w=*|w=/ /是乘除号operate = w。cinw 。 /读取下一字符w = FMachine(w 。 /调用 F自动机b = wordStack.pop( 。 /符号栈弹出a = wordStack.pop( 。 /两个操作字符cout(operate,a,b,tnoOfT。 /输出四元式wordStack.push(c 。 /新状态压栈noOfT+ 。 /状态计数加1 return w。 char FMa
29、chine(char w /F 自动机string theWord。if(w=a&w=A&w 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页,共 21 页20 / 21 theWord = w 。 /当前字符是字母wordStack.push(theWord。/则压栈 else if(w = ( /是左括号cinw 。 /则读取下一字符w = EMachine(w 。 /调用 E 自动机if(w!= /不是右括号则输入有误,报错cerrthe input is wrong!。 else /否则有误,报错cerrthe input is w
30、rong!。 cinw 。 /读取下一字符return w。 string intToString(int a /整形变字符串形函数string d。char b=0,c。int i。while(a!=0 i = a%10。a = a/10。c = (intb + 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 页21 / 21 C+语言知识的深化和用途的理解。相信在以后的毕业设计以及读研自己做工程时可以有更大的提升。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页,共 21 页