![编译原理_LL文法源代码(实验三)(doc)_第1页](http://file2.renrendoc.com/fileroot_temp3/2021-5/7/bfce3977-e77a-490c-81fa-818c045a3ce9/bfce3977-e77a-490c-81fa-818c045a3ce91.gif)
![编译原理_LL文法源代码(实验三)(doc)_第2页](http://file2.renrendoc.com/fileroot_temp3/2021-5/7/bfce3977-e77a-490c-81fa-818c045a3ce9/bfce3977-e77a-490c-81fa-818c045a3ce92.gif)
![编译原理_LL文法源代码(实验三)(doc)_第3页](http://file2.renrendoc.com/fileroot_temp3/2021-5/7/bfce3977-e77a-490c-81fa-818c045a3ce9/bfce3977-e77a-490c-81fa-818c045a3ce93.gif)
![编译原理_LL文法源代码(实验三)(doc)_第4页](http://file2.renrendoc.com/fileroot_temp3/2021-5/7/bfce3977-e77a-490c-81fa-818c045a3ce9/bfce3977-e77a-490c-81fa-818c045a3ce94.gif)
![编译原理_LL文法源代码(实验三)(doc)_第5页](http://file2.renrendoc.com/fileroot_temp3/2021-5/7/bfce3977-e77a-490c-81fa-818c045a3ce9/bfce3977-e77a-490c-81fa-818c045a3ce95.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、一、实验目的及要求1掌握ll(1)分析法的基本原理; 2掌握ll(1)分析表的构造方法;3用ll(1)分析法分析高级语言表达式。4、了解ll(1)分析器的工作过程。文法:无二义性的算术表达式的文法(1)把词法分析作为语法分析的子程序实现(5分)(2)独立的语法分析程序(4分)(3)对表达式文法消除左递归、构造ll(1)分析表(4)ll(1)分析表可以直接输入(4分),也可以用程序实现(5分)(5)给一个表达式,给出分析过程(分析栈、输入串、所用规则)(4分)(6)生成一个棵语法树(5分)用二叉树的形式表示出来2、 实验内容及原理 1、 实验原理(1)、ll(1)文法的定义ll(1)分析法属于确
2、定的自顶向下分析方法。ll(1)的含义是:第一个l表明自顶向下分析是从左向右扫描输入串,第2个l表明分析过程中将使用最左推导,1表明只需向右看一个符号便可决定如何推导,即选择哪个产生式(规则)进行推导。ll(1)文法的判别需要依次计算first集、follow集和sellect集,然后判断是否为ll(1)文法,最后再进行句子分析。需要预测分析器对所给句型进行识别。即在ll(1)分析法中,每当在符号栈的栈顶出现非终极符时,要预测用哪个产生式的右部去替换该非终极符;当出现终结符时,判断其与剩余输入串的第一个字符是否匹配,如果匹配,则继续分析,否则报错。ll(1)分析方法要求文法满足如下条件:对于任
3、一非终极符a的两个不同产生式aa,ab,都要满足下面条件:select(aa)select(ab)=(2)、预测分析表构造ll(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。它的行对应文法的非终极符,列对应终极符,表中的值有两种:一是产生式的右部的字符串,一是null。若用m表示ll(1)分析表,则m可表示如下:m: vnvtperrorm(a, t) = a,当tselect(a) ,否则m(a, t) = error其中p表示所有产生式的集合。(3)、语法分析程序构造ll(1)分析中x为符号栈栈顶元素,a为输入流当前字符,e为给定测试数据的开始符号,#为句子括
4、号即输入串的括号。分析表用一个二位数组m表示,数组元素ma,a中的下标a表示非终结符,a为终结符或句子括号#,二维数组中存放的是一条关于a 的产生式,表明当非终结符a向下推导时,面临输入符a时,所采用的候选产生式,当元素内容无产生式时,则表明用a 的左部向下推导时出现了不该出现的符号,因此元素内容转向出错处理的信息。ll(1)分析过程主要包括以下四个动作:替换:当xvn时选相应产生式的右部b去替换x。此时x出栈,b逆序入栈。匹配:当xvt时它与a进行匹配,其结果可能成功,也可能失败,如果成功则符号栈中将x退栈并将输入流指针向前移动一位,否则报错。接受:当格局为(#,空#)时报告分析成功。报错:
5、出错后,停止分析。并给出相应的错误提示信息。2、实验内容根据某一文法编制调试ll(1)分析程序,以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析ll(1)分析法的理解。 对下列文法,用ll(1)分析法对任意输入的符号串进行分析:(1)e-tg(2)g-+tg(3)g-(4)t-fs(5)s-*fs(6)s-(7)f-(e)(8)f-i程序输入一以#结束的符号串(包括+*()i#),如:i+i*i#。3、 实验过程及步骤1. 总体思路分析及流程图给定一个正规文法g,在ll(1)预测分析中,必须先求出first集和follow集, 构造预测分析表。求出预测分析表之后,再输入一个字
6、符串,依据ll1分析表单步输出字符串的分析过程。功能模块分解图(1)主程序流程图(2)核心算法流程图 1.计算非终结符的first集的算法及流程:first集合的构造算法:(1)若xvt,则first(x)=x。(2)若xvn,且有产生式xa,则把a加入到first (x)中;若x也是一条产生式,则把也加到first (x)中。(3)若xy是一个产生式且yvn,则把first (y)中的所有非-元素都加到first (x)中;若xy1y2yk是一个产生式,y1,yi-1都是非终结符,而且,对于任何j,1ji-1,first (yj)都含有(即y1yi-1* ),则把first (yj)中的所有
7、非-元素都加到first (x)中;特别是,若所有的first (yj)均含有,j=1,2,,k,则把加到first (x)中。连续使用上面的规则,直至每个集合first不再增大为止。2.计算非终结符的follow集:follow集合的具体构造算法如下:(1)对于文法的开始符号s,置#于follow(s)中;(2)若ab是一个产生式,则把first()|加至follow(b)中;(3)若ab是一个产生式,或ab是一个产生式而 (即first()),则把follow(a)加至follow(b)中。连续使用上面的规则,直至每个集合follow不再增大为止。3.预测分析控制程序的算法流程 ll(1)
8、文法(源代码)#include stdio.h#include stdlib.h#define maxrulenum 8#define maxvnnum 5#define maxvtnum 5#define maxstackdepth 20#define maxplength 20#define maxstlength 50struct prnode /*产生式右部结构*/ int rcursor; struct prnode *next;struct pnode int lcursor; int rlength; /*右部长度*/ struct prnode *rhead; /*右部结点头指
9、针*/;char vnmaxvnnum + 1; /*非终结符集*/int vnnum;char vtmaxvtnum + 1; /*终结符集*/int vtnum;struct pnode pmaxrulenum; int pnum; char buffermaxplength + 1;char ch; char stmaxstlength; /*要分析的符号串*/struct collectnode int nvt; struct collectnode *next;struct collectnode* firstmaxvnnum + 1; /*first集*/struct collec
10、tnode* followmaxvnnum + 1; /*follow集*/int analysetablemaxvnnum + 1maxvtnum + 1 + 1;int analysestackmaxstackdepth + 1; /*分析栈*/int topanalyse; /*分析栈顶*/void init();/*初始化*/int indexch(char ch);void inputvt(); /*输入终结符*/void inputvn();/*输入非终结符*/void showcharray(char* collect, int num);/*输出vn或vt的内容*/void i
11、nputp();/*产生式输入*/bool checkp(char * st);/*判断产生式正确性*/void first(int u);void addfirst(int u, int nch); /*加入first集*/bool haveempty(int nvn); void follow(int v);/*计算follow集*/void addfollow(int v, int nch, int kind);void showcollect(struct collectnode *collect);/*输出first或follow集*/void firstfollow();/*计算f
12、irst和follow*/void createat();/*构造预测分析表*/void showat();/*输出分析表*/void identify(char *st);void initstack();void showstack();void pop();void push(int r);void main(void) char todo,ch; init(); inputvn(); inputvt(); inputp(); getchar(); firstfollow(); printf(所得first集为:); showcollect(first); printf(所得follow
13、集为:); showcollect(follow); createat(); showat(); todo = y; while(y = todo) printf(n是否继续进行句型分析?(y / n):); todo = getchar(); while(y != todo & n != todo) printf(n(y / n)? ); todo = getchar(); if(y = todo) int i; initstack(); printf(请输入符号串(以#结束) : ); ch = getchar(); i = 0; while(# != ch & i maxstlength
14、) if( != ch & n != ch) sti+ = ch; ch = getchar(); if(# = ch & i maxstlength) sti = ch; identify(st); else printf(输入出错!n); getchar();void init() int i,j; vnnum = 0; vtnum = 0; pnum = 0; for(i = 0; i = maxvnnum; i+) vni = 0; for(i = 0; i = maxvtnum; i+) vti = 0; for(i = 0; i maxrulenum; i+) pi.lcursor
15、 = null; pi.rhead = null; pi.rlength = 0; pnum = 0; for(i = 0; i = maxplength; i+) bufferi = 0; for(i = 0; i maxvnnum; i+) firsti = null; followi = null; for(i = 0; i = maxvnnum; i+) for(j = 0; j = maxvnnum + 1; j+) analysetableij = -1; int indexch(char ch) int n; n = 0; /*is vn?*/ while(ch != vnn &
16、 0 != vnn) n+; if(0 != vnn) return 100 + n; n = 0; /*is vt?*/ while(ch != vtn & 0 != vtn) n+; if(0 != vtn) return n; return -1;/*输出vn或vt的内容*/void showcharray(char* collect) int k = 0; while(0 != collectk) printf( %c , collectk+); printf(n);/*输入非终结符*/void inputvn() int inerr = 1; int n,k; char ch; wh
17、ile(inerr) printf(n请输入所有的非终结符,注意:); printf(请将开始符放在第一位,并以#号结束:n); ch = ; n = 0; /*初始化数组*/ while(n maxvnnum) vnn+ = 0; n = 0; while(# != ch) & (n maxvnnum) if( != ch & n != ch & -1 = indexch(ch) vnn+ = ch; vnnum+; ch = getchar(); vnn = #; /*以“#”标志结束用于判断长度是否合法*/ k = n; if(# != ch) if( # != (ch = getcha
18、r() while(# != (ch = getchar() ; printf(n符号数目超过限制!n); inerr = 1; continue; /*正确性确认,正确则,执行下下面,否则重新输入*/ vnk = 0; showcharray(vn); ch = ; while(y != ch & n != ch) if(n != ch) printf(输入正确确认?(y/n):); scanf(%c, &ch); if(n = ch) printf(录入错误重新输入!n); inerr = 1; else inerr = 0; /*输入终结符*/void inputvt() int ine
19、rr = 1; int n,k; char ch; while(inerr) printf(n请输入所有的终结符,注意:); printf(以#号结束:n); ch = ; n = 0; /*初始化数组*/ while(n maxvtnum) vtn+ = 0; n = 0; while(# != ch) & (n maxvtnum) if( != ch & n != ch & -1 = indexch(ch) vtn+ = ch; vtnum+; ch = getchar(); vtn = #; k = n; if(# != ch) if( # != (ch = getchar() whil
20、e(# != (ch = getchar() ; printf(n符号数目超过限制!n); inerr = 1; continue; vtk = 0; showcharray(vt); ch = ; while(y != ch & n != ch) if(n != ch) printf(输入正确确认?(y/n):); scanf(%c, &ch); if(n = ch) printf(录入错误重新输入!n); inerr = 1; else inerr = 0; /*产生式输入*/void inputp() char ch; int i = 0, n,num; printf(请输入文法产生式的
21、个数:); scanf(%d, &num); pnum = num; getchar(); /*消除回车符*/ printf(n请输入文法的%d个产生式,并以回车分隔每个产生式:, num); printf(n); while(i num) printf(第%d个:, i); /*初始化*/ for(n =0; n maxplength; n+) buffern = 0; /*输入产生式串*/ ch = ; n = 0; while(n != (ch = getchar() & n rcursor = indexch(buffer3); pt-next = null; pi.rhead = p
22、t; n = 4; while(0 != buffern) qt = (prnode*)malloc(sizeof(prnode); qt-rcursor = indexch(buffern); qt-next = null; pt-next = qt; pt = qt; n+; pi.rlength = n - 3; i+; else printf(输入符号含非法在成分,请重新输入!n); /*判断产生式正确性*/bool checkp(char * st) int n; if(100 indexch(st0) return false; if(- != st1) return false;
23、 if( != st2) return false; for(n = 3; 0 != stn; n +) if(-1 = indexch(stn) return false; return true;void first(int u) int i,j; for(i = 0; i pnum; i+) if(pi.lcursor = u) struct prnode* pt; pt = pi.rhead; j = 0; while(j pt-rcursor) addfirst(u, pt-rcursor); break; else if(null = firstpt-rcursor - 100)
24、first(pt-rcursor); addfirst(u, pt-rcursor); if(!haveempty(pt-rcursor) break; else pt = pt-next; j+; if(j = pi.rlength) /*当产生式右部都能推出空时*/ addfirst(u, -1); /*加入first集*/void addfirst(int u, int nch) struct collectnode *pt, *qt; int ch; /*用于处理vn*/ pt = null; qt = null; if(nch nvt = nch) break; else qt =
25、pt; pt = pt-next; if(null = pt) pt = (struct collectnode *)malloc(sizeof(struct collectnode); pt-nvt = nch; pt-next = null; if(null = firstu - 100) firstu - 100 = pt; else qt-next = pt; /*qt指向first集的最后一个元素*/ pt = pt-next; else pt = firstnch - 100; while(null != pt) ch = pt-nvt; if(-1 != ch) addfirst
26、(u, ch); pt = pt-next; bool haveempty(int nvn) if(nvn nvt) return true; pt = pt-next; return false;void follow(int v) int i; struct prnode *pt ; if(100 = v) /*当为初始符时*/ addfollow(v, -1, 0 ); for(i = 0; i rcursor != v) pt = pt-next; if(null != pt) pt = pt-next; if(null = pt) if(null = followpi.lcursor
27、 - 100 & pi.lcursor != v) follow(pi.lcursor); addfollow(v, pi.lcursor, 0); else while(null != pt & haveempty(pt-rcursor) addfollow(v, pt-rcursor, 1); pt = pt-next; if(null = pt) if(null = followpi.lcursor - 100 & pi.lcursor != v) follow(pi.lcursor); addfollow(v, pi.lcursor, 0); else addfollow(v, pt-
28、rcursor, 1); void addfollow(int v, int nch, int kind) struct collectnode *pt, *qt; int ch; pt = null; qt = null; if(nch nvt = nch) break; else qt = pt; pt = pt-next; if(null = pt) pt = (struct collectnode *)malloc(sizeof(struct collectnode); pt-nvt = nch; pt-next = null; if(null = followv - 100) fol
29、lowv - 100 = pt; else qt-next = pt; /*qt指向follow集的最后一个元素*/ pt = pt-next; else if(0 = kind) pt = follownch - 100; while(null != pt) ch = pt-nvt; addfollow(v, ch, 0); pt = pt-next; else pt = firstnch - 100; while(null != pt) ch = pt-nvt; if(-1 != ch) addfollow(v, ch, 1); pt = pt-next; /*输出first或follow
30、集*/void showcollect(struct collectnode *collect) int i; struct collectnode *pt; i = 0; while(null != collecti) pt = collecti; printf(n%c:t, vni); while(null != pt) if(-1 != pt-nvt) printf( %c, vtpt-nvt); else printf( #); pt = pt-next; i+; printf(n);/*计算first和follow*/void firstfollow() int i; i = 0;
31、while(0 != vni) if(null = firsti) first(100 + i); i+; i = 0; while(0 != vni) if(null = followi) follow(100 + i); i+; /*构造预测分析表*/void createat() int i; struct prnode *pt; struct collectnode *ct; for(i = 0; i rcursor) ct = firstpt-rcursor - 100; while(null != ct) if(-1 != ct-nvt) analysetablepi.lcurso
32、r - 100ct-nvt = i; ct = ct-next; pt = pt-next; if(null = pt) ct = followpi.lcursor - 100; while(null != ct) if(-1 != ct-nvt) analysetablepi.lcursor - 100ct-nvt = i; else analysetablepi.lcursor - 100vtnum = i; ct = ct-next; else if(100 rcursor) /*不含空的非终结符*/ ct = firstpt-rcursor - 100; while(null != c
33、t) analysetablepi.lcursor - 100ct-nvt = i; ct = ct-next; else /*终结符或者空*/ if(-1 = pt-rcursor) ct = followpi.lcursor - 100; while(null != ct) if(-1 != ct-nvt) analysetablepi.lcursor - 100ct-nvt = i; else /*当含有#号时*/ analysetablepi.lcursor - 100vtnum = i; ct = ct-next; else /*为终结符*/ analysetablepi.lcurs
34、or - 100pt-rcursor = i; /*输出分析表*/void showat() int i,j; printf(构造预测分析表如下:n); printf(t|t); for(i = 0; i vtnum; i+) printf(%ct, vti); printf(#tn); printf(- - -t|- - -t); for(i = 0; i = vtnum; i+) printf(- - -t); printf(n); for(i = 0; i vnnum; i+) printf(%ct|t, vni); for(j = 0; j analysestacktopanalyse) if(analysestacktopanalyse = indexch(stcurrent) pop(); current+; step+; printf(%dt, step); showstack(); printf(tt%ctt出栈、后移n, stcurrent); else printf(%c-
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 商丘市粮食和物资储备局招聘笔试真题2023
- 林芝市审批引进菁英人才笔试真题2023
- 结构力学优化算法:拓扑优化:拓扑优化算法原理
- 结构力学数值方法:解析法:结构振动控制技术教程
- 中小学2024年开学第一课(巴黎奥运)主题班会课件
- 2022年苍南县中、小学教师招聘《信息技术基础知识》试题
- 强风天气应急预案
- 住院患者护理干预
- 黄金卷06(参考答案)-【赢在高考·黄金8卷】备战2024年高考地理模拟卷(湖北专用)
- 内瘘感染护理
- 光伏发电工程建设标准工艺手册(2023版)
- MOOC 颈肩腰腿痛中医防治-暨南大学 中国大学慕课答案
- 国家中小学智慧教育平台培训专题讲座
- 保持教学生命力读后感
- 混凝土双曲拱坝水电站施工组织设计
- 高支模巡视检查记录
- 50篇英语阅读理解
- 卫生部手术分级目录(2023年1月份修订)
- GB/T 36004-2018食品接触表面清洗消毒效果试验方法三磷酸腺苷生物发光法
- 实习证明模板免费下载【8篇】
- 苏科版劳动与技术一年级上册全一册全部教案(定稿)
评论
0/150
提交评论