自顶向下的语法分析LL1分析法.docx
- 文档编号:18303234
- 上传时间:2023-08-15
- 格式:DOCX
- 页数:38
- 大小:23.99KB
自顶向下的语法分析LL1分析法.docx
《自顶向下的语法分析LL1分析法.docx》由会员分享,可在线阅读,更多相关《自顶向下的语法分析LL1分析法.docx(38页珍藏版)》请在冰点文库上搜索。
自顶向下的语法分析LL1分析法
《编译原理》课程实验
实验三:
自顶向下的语法分析:
LL
(1)分析法
1、实验目的:
用LL
(1)分析法分析高级语言表达式。
了解LL
(1)分析器的工作过程
2、实验要求:
文法:
无二义性的算术表达式的文法
(1)把词法分析作为语法分析的子程序实现(5分)
(2)独立的语法分析程序(4分)
(3)对表达式文法消除左递归、构造LL
(1)分析表
(4)LL
(1)分析表可以直接输入(4分),也可以用程序实现(5分)
(5)给一个表达式,给出分析过程(分析栈、输入串、所用规则)(4分)
(6)生成一个棵语法树(5分)用二叉树的形式表示出来
LL
(1)分析表算法:
(1)构造所有侯选式的FIRST集合,构造所有非终结符的FOLLOW集合
(2)对于文法G的每个产生式A→α,执行(3)和(4)
(3)对于每个终结符a∈FIRST(α),把A→α加至M[A][a]
(4)若ε∈FIRST(α),则对于每个终结符b∈FOLLOW(A),把A→α加至M[A][b]
(5)把所有未定义的M[A][c]标上“出错标志”(c∈VT)
/*--------------------声明-----------------------*/
/*
阅读程序请从LL1.h开始。
补充:
程序存在问题:
(1)follow集不能处理:
U->xVyVz的情况;
(2)因本人偷懒,本程序为加入文法判断,故
输入的文法必须为LL
(1)文法;
(3)您可以帮忙扩充:
消除左递归,提取公因子等函数
(4)……
*/
/*-----------------------------------------------*/
#include"LL1.h"
/*-------------------mainfunction--------------------*/
voidmain(void)
{
chartodo,ch;
Init();
InputVn();
InputVt();
InputP();
getchar();
FirstFollow();
printf("所得first集为:
");
ShowCollect(first);
printf("所得follow集为:
");
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)
{
inti;
InitStack();
printf("请输入符号串(以#结束):
");
ch=getchar();
i=0;
while('#'!
=ch&&i { if(''! =ch&&'\n'! =ch) { st[i++]=ch; } ch=getchar(); } if('#'==ch&&i { st[i]=ch; Identify(st); } else printf("输入出错! \n"); } } getchar(); } /*---------------functiondefinition------------------*/ voidInit() { inti,j; vnNum=0; vtNum=0; PNum=0; for(i=0;i<=MaxVnNum;i++) Vn[i]='\0'; for(i=0;i<=MaxVtNum;i++) Vt[i]='\0'; for(i=0;i { P[i].lCursor=NULL; P[i].rHead=NULL; P[i].rLength=0; } PNum=0; for(i=0;i<=MaxPLength;i++) buffer[i]='\0'; for(i=0;i { first[i]=NULL; follow[i]=NULL; } for(i=0;i<=MaxVnNum;i++) { for(j=0;j<=MaxVnNum+1;j++) analyseTable[i][j]=-1; } } /*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置,-1表示未找到*/ intIndexCh(charch) { intn; n=0;/*isVn? */ while(ch! =Vn[n]&&'\0'! =Vn[n]) n++; if('\0'! =Vn[n]) return100+n; n=0;/*isVt? */ while(ch! =Vt[n]&&'\0'! =Vt[n]) n++; if('\0'! =Vt[n]) returnn; return-1; } /*输出Vn或Vt的内容*/ voidShowChArray(char*collect) { intk=0; while('\0'! =collect[k]) { printf("%c",collect[k++]); } printf("\n"); } /*输入非终结符*/ voidInputVn() { intinErr=1; intn,k; charch; while(inErr) { printf("\n输入所有的非终结符: "); printf("并以$号结束: \n"); ch=''; n=0; /*初始化数组*/ while(n { Vn[n++]='\0'; } n=0; while(('$'! =ch)&&(n { if(''! =ch&&'\n'! =ch&&-1==IndexCh(ch)) { Vn[n++]=ch; vnNum++; } ch=getchar(); } Vn[n]='$';/*以“$”标志结束用于判断长度是否合法*/ k=n;/*k用于记录n以便改Vn[n]='\0'*/ if('$'! =ch) { if('$'! =(ch=getchar())) { while('#'! =(ch=getchar())) ; printf("\n符号数目超过限制! \n"); inErr=1; continue; } } /*正确性确认,正确则,执行下下面,否则重新输入*/ Vn[k]='\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; } } } /*输入终结符*/ voidInputVt() { intinErr=1; intn,k; charch; while(inErr) { printf("\n输入所有的终结符: "); printf("以$号结束: \n"); ch=''; n=0; /*初始化数组*/ while(n { Vt[n++]='\0'; } n=0; while(('$'! =ch)&&(n { if(''! =ch&&'\n'! =ch&&-1==IndexCh(ch)) { Vt[n++]=ch; vtNum++; } ch=getchar(); } Vt[n]='$';/*以“$”标志结束*/ k=n;/*k用于记录n以便改Vt[n]='\0'*/ if('$'! =ch) { if('$'! =(ch=getchar())) { while('$'! =(ch=getchar())) ; printf("\n符号数目超过限制! \n"); inErr=1; continue; } } /*正确性确认,正确则,执行下下面,否则重新输入*/ Vt[k]='\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; } } } /*产生式输入*/ voidInputP() { charch; inti=0,n,num; printf("输入文法产生式的个数: "); scanf("%d",&num); PNum=num; getchar();/*消除回车符*/ printf("\n输入文法的%d个产生式,并以回车分隔每个产生式: ",num); printf("\n"); while(i { printf("第%d个: ",i); /*初始化*/ for(n=0;n buffer[n]='\0'; /*输入产生式串*/ ch=''; n=0; while('\n'! =(ch=getchar())&&n { if(''! =ch) buffer[n++]=ch; } buffer[n]='\0'; if(CheckP(buffer)) { /*填写入产生式结构体*/ pRNode*pt,*qt; P[i].lCursor=IndexCh(buffer[0]); pt=(pRNode*)malloc(sizeof(pRNode)); pt->rCursor=IndexCh(buffer[3]); pt->next=NULL; P[i].rHead=pt; n=4; while('\0'! =buffer[n]) { qt=(pRNode*)malloc(sizeof(pRNode)); qt->rCursor=IndexCh(buffer[n]); qt->next=NULL; pt->next=qt; pt=qt; n++; } P[i].rLength=n-3; i++; /*调试时使用*/ } else printf("输入符号含非法在成分,请重新输入! \n"); } } /*判断产生式正确性*/ boolCheckP(char*st) { intn; if(100>IndexCh(st[0])) returnfalse; if('-'! =st[1]) returnfalse; if('>'! =st[2]) returnfalse; for(n=3;'\0'! =st[n];n++) { if(-1==IndexCh(st[n])) returnfalse; } returntrue; } /*====================first&follow======================*/ /*计算first集,U->xx...*/ voidFirst(intU) { inti,j; for(i=0;i { if(P[i].lCursor==U) { structpRNode*pt; pt=P[i].rHead; j=0; while(j { if(100>pt->rCursor) { /*注: 此处因编程出错,使空产生式时 rlength同样是,故此处同样可处理空产生式*/ AddFirst(U,pt->rCursor); break; } else { if(NULL==first[pt->rCursor-100]) { First(pt->rCursor); } AddFirst(U,pt->rCursor); if(! HaveEmpty(pt->rCursor)) { break; } else { pt=pt->next; } } j++; } if(j>=P[i].rLength)/*当产生式右部都能推出空时*/ AddFirst(U,-1); } } } /*加入first集*/ voidAddFirst(intU,intnCh)/*当数值小于时nCh为Vt*/ /*当处理非终结符时,AddFirst不添加空项(-1)*/ { structcollectNode*pt,*qt; intch;/*用于处理Vn*/ pt=NULL; qt=NULL; if(nCh<100) { pt=first[U-100]; while(NULL! =pt) { if(pt->nVt==nCh) break; else { qt=pt; pt=pt->next; } } if(NULL==pt) { pt=(structcollectNode*)malloc(sizeof(structcollectNode)); pt->nVt=nCh; pt->next=NULL; if(NULL==first[U-100]) { first[U-100]=pt; } else { qt->next=pt;/*qt指向first集的最后一个元素*/ } pt=pt->next; } } else { pt=first[nCh-100]; while(NULL! =pt) { ch=pt->nVt; if(-1! =ch) { AddFirst(U,ch); } pt=pt->next; } } } /*判断first集中是否有空(-1)*/ boolHaveEmpty(intnVn) { if(nVn<100)/*为终结符时(含-1),在follow集中用到*/ returnfalse; structcollectNode*pt; pt=first[nVn-100]; while(NULL! =pt) { if(-1==pt->nVt) returntrue; pt=pt->next; } returnfalse; } /*计算follow集,例: U->xVy,U->xV.(注: 初始符必含#——"-1")*/ voidFollow(intV) { inti; structpRNode*pt; if(100==V)/*当为初始符时*/ AddFollow(V,-1,0); for(i=0;i { pt=P[i].rHead; while(NULL! =pt&&pt->rCursor! =V)/*注此不能处理: U->xVyVz的情况*/ pt=pt->next; if(NULL! =pt) { pt=pt->next;/*V右侧的符号*/ if(NULL==pt)/*当V后为空时V->xV,将左符的follow集并入V的follow集中*/ { if(NULL==follow[P[i].lCursor-100]&&P[i].lCursor! =V) { Follow(P[i].lCursor); } AddFollow(V,P[i].lCursor,0); } else/*不为空时V->xVy,(注意: y->),调用AddFollow加入Vt或y的first集*/ { while(NULL! =pt&&HaveEmpty(pt->rCursor)) { AddFollow(V,pt->rCursor,1);/*y的前缀中有空时,加如first集*/ pt=pt->next; } if(NULL==pt)/*当后面的字符可以推出空时*/ { if(NULL==follow[P[i].lCursor-100]&&P[i].lCursor! =V) { Follow(P[i].lCursor); } AddFollow(V,P[i].lCursor,0); } else/*发现不为空的字符时*/ { AddFollow(V,pt->rCursor,1); } } } } } /*当数值小于时nCh为Vt*/ /*#用-1表示,kind用于区分是并入符号的first集,还是follow集 kind=0表加入follow集,kind=1加入first集*/ voidAddFollow(intV,intnCh,intkind) { structcollectNode*pt,*qt; intch;/*用于处理Vn*/ pt=NULL; qt=NULL; if(nCh<100)/*为终结符时*/ { pt=follow[V-100]; while(NULL! =pt) { if(pt->nVt==nCh) break; else { qt=pt; pt=pt->next; } } if(NULL==pt) { pt=(structcollectNode*)malloc(sizeof(structcollectNode)); pt->nVt=nCh; pt->next=NULL; if(NULL==follow[V-100]) { follow[V-100]=pt; } else { qt->next=pt;/*qt指向follow集的最后一个元素*/ } pt=pt->next; } } else/*为非终结符时,要区分是加first还是follow*/ { if(0==kind) { pt=follow[nCh-100]; while(NULL! =pt) { ch=pt->nVt; AddFollow(V,ch,0); pt=pt->next; } } else { pt=first[nCh-100]; while(NULL! =pt) { ch=pt->nVt; if(-1! =ch) { AddFollow(V,ch,1); } pt=pt->next; } } } } /*输出first或follow集*/ voidShowCollect(structcollectNode**collect) { inti; structcollectNode*pt; i=0; while(NULL! =collec
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 向下 语法分析 LL1 分析
![提示](https://static.bingdoc.com/images/bang_tan.gif)