LL1语法分析设计原理与实现技术.docx
- 文档编号:13565664
- 上传时间:2023-06-15
- 格式:DOCX
- 页数:19
- 大小:145.38KB
LL1语法分析设计原理与实现技术.docx
《LL1语法分析设计原理与实现技术.docx》由会员分享,可在线阅读,更多相关《LL1语法分析设计原理与实现技术.docx(19页珍藏版)》请在冰点文库上搜索。
LL1语法分析设计原理与实现技术
LL
(1)语法分析设计原理与实现技术
实验报告
变更说明
日期
版本
变更位置
变更说明
作者
2014/4/30
1.0
初稿生成
房皓
一、实验目的:
本实验的目的在于在教师的引导下以问题回朔与思维启发的方式,使学生在不断的探究过程中掌握编译程序设计和构造的基本原理和实现技术,启迪学生的抽象思维、激发学生的学习兴趣、培养学生的探究精神和专业素养,从而提高学生发现问题、分析问题和解决问题的能力。
二、实验内容:
[实验项目]
实现LL
(1)分析中控制程序(表驱动程序);完成以下描述算术表达式的LL
(1)文法的LL
(1)分析程序。
G[E]:
E→TE′
E′→ATE′|ε
T→FT′
T′→MFT′|ε
F→(E)|i
A→+|-
M→*|/
[实验说明]
终结符号i为用户定义的简单变量,即标识符的定义。
[设计要求]
(1)输入串应是词法分析的输出二元式序列,即某算术表达式“实验项目一”的输出结果。
输出为输入串是否为该文法定义的算术表达式的判断结果;
(2)LL
(1)分析过程应能发现输入串出错;
(3)设计两个测试用例(尽可能完备,正确和出错),并给出测试结果。
三、实验环境:
操作系统:
Windows7
软件:
VC++6.0
四、程序功能描述:
●提供了文件输入方式,且输入的内容为二元式序列;
●能够对输入的字符串做出正确的LL
(1)分析判断,并给出判断结果,判断结果输出到文件,并显示在屏幕;
●能发现输入串中的错误,包含非法字符,输入不匹配等;
●能够处理一些可预见性的错误,如文件不存在,输入非法等。
五、数据结构设计:
全局:
局部(main()中):
六、程序结构描述:
●设计方法:
本程序采用从文件读取的输入方式,输入的内容需为二元式序列,然后按照LL
(1)分析的方法对输入的字符串进行分析判断,并输出判断结果,程序通过对输入串的检查能够发现输入串中的错误。
程序规定的单词符号及其种别码见下表:
单词符号及其种别码表
单词符号
种别码
单词符号
种别码
(
1
*
5
)
2
/
6
+
3
i
7
-
4
#
8
分析表
i
+
-
*
/
(
)
#
E
E→TG
E→TG
G
G→ATG
G→ATG
G→ε
G→ε
T
T→FH
T→FH
H
H→ε
H→ε
H→MFH
H→MFH
H→ε
H→ε
F
F→i
F→(E)
A
A→+
A→-
M
M→*
M→/
●主要函数说明:
check_VT(charch):
bool型函数,检查ch是否为终结字符,是则返回true;
create_analyseTable():
构建分析表函数,无返回值;
error(FILE*fp):
输出错误,表示不是该文法的句子,参数fp用于退出前将打开的文件关闭;
getnum_VN(charch):
int型函数,查找ch在非终结字符中的位置并返回;
getnum_VT(charch):
int型函数,查找ch在终结字符中的位置并返回;
justify():
bool型函数,判断文件读取内容是否合法,包括检查非法字符和不匹配现象,出错返回false,否则返回true;
main():
主函数。
●函数调用关系说明:
main()调用check_VT(charch)、create_analyseTable()、error(FILE*fp)、getnum_VN(charch)、getnum_VT(charch)、justify();
●执行框图:
七、实验过程结果截图:
●测试用例一:
i+i*i/i#
●测试用例二:
i+i*i/#
八、实验总结:
●实验心得:
通过本次实验我锻炼了自己的上机操作能力及编程能力,并对理论知识有了进一步的了解。
老师提供的LL
(1)分析法的流程图给了我很大的帮助,使得本实验基本思路变得很清晰,用较为简单的算法就能实现,程序的难点是产生式结构体的构造、分析表的构造、解决实验中遇到的问题也花费了一部分时间,我增长了处理关于文件错误的能力。
●实验中遇到的问题及解决方法:
问题主要有
i.从文件输入二元式时,需要检查输入的内容是否符合程序规定的字符种别码,解决方法是用了两个字符数组token,token2,分别记录种别码和字符,并增加了一个函数justify()根据既定的种别码表判断;
ii.当输入内容不匹配或输入内容非法时要退出程序,此时若不关闭已经打开的文件可能导致文件内容受到破坏;解决方法是给error()函数设置一个文件指针变量参数FILE*fp,在退出程序之前通过fp关闭文件
●程序的自我评价:
此程序实现了要求中的所有功能,并增加了输入串错误检测的功能,但因编程能力及经验的有限,其中有的地方不免有些繁杂,还有一些潜藏的问题,需要进一步测试与修改来提高程序的健壮性。
九、程序清单:
/****************************************************
课题名称:
LL
(1)语法分析设计原理与实现技术
作者:
房皓进修生13410801
最后修改时间:
2014.4.30
***************************************************/
/**************************************************单词符号及其分类编码
单词符号种别码
(1
)2
+3
-4
*5
/6
i7
#8
/**********************文法**********************
G[E]:
E→TE′
E′→ATE′|ε
T→FT′
T′→MFT′|ε
F→(E)|i
A→+|-
M→*|/
/********************改为等价文法**************
G[E]:
E→TG
G→ATG|ε
T→FH
H→MFH|ε
F→(E)|i
A→+|-
M→*|/
/*********************分析表************************
i+-*/()#
EE→TGE→TG
GG→ATGG→ATGG→εG→ε
TT→FHT→FH
HH→εH→εH→MFHH→MFHH→εH→ε
FF→iF→(E)
AA→+A→-
MM→*M→/
/***************************************************/
#include
#include
#include
usingnamespacestd;
#defineMAX50
charanalyseStack[MAX];//分析栈
chartoken[MAX];//输入串
typedefstructCSS//产生式结构体
{
charleft;
charright[5];
intright_length;
}CSS;
CSSE,G,G1,T,H,H1,F,F1,A,A1,M,M1;
CSSanalyseTable[7][8];
voiderror(FILE*fp)
{
fprintf(fp,"%s","FAIL!
");
fclose(fp);
cout<<"FAIL!
"< exit(0); } booljustify(charch,inti)//判断文件读取内容是否合法,包括检查非法字符和不匹配现象 { switch(ch) { case'1': if(token[i]! ='(') returnfalse; break; case'2': if(token[i]! =')') returnfalse; break; case'3': if(token[i]! ='+') returnfalse; break; case'4': if(token[i]! ='-') returnfalse; break; case'5': if(token[i]! ='*') returnfalse; break; case'6': if(token[i]! ='/') returnfalse; break; case'7': if(token[i]! ='i') returnfalse; break; case'8': if(token[i]! ='#') returnfalse; break; default: returnfalse; break; } returntrue; } boolcheck_VT(charch) { if(ch=='i'||ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')') returntrue; returnfalse; } intgetnum_VN(charch) { charVN[7]={'E','G','T','H','F','A','M'}; inti; for(i=0;i<7;i++) if(ch==VN[i]) break; returni; } intgetnum_VT(charch) { charVT[8]={'i','+','-','*','/','(',')','#'}; inti; for(i=0;i<8;i++) if(ch==VT[i]) break; if(i==8) { cout<<"FAIL! "< exit(0); } returni; } voidcreate_analyseTable() { inti,j; E.left='E'; strcpy(E.right,"TG"); E.right_length=2; G.left='G'; strcpy(G.right,"ATG"); G.right_length=3; G1.left='G'; strcpy(G1.right,"NULL"); G1.right_length=0; T.left='T'; strcpy(T.right,"FH"); T.right_length=2; H.left='H'; strcpy(H.right,"MFH"); H.right_length=3; H1.left='H'; strcpy(H1.right,"NULL"); H1.right_length=0; F.left='F'; strcpy(F.right,"(E)"); F.right_length=3; F1.left='F'; strcpy(F1.right,"i"); F1.right_length=1; A.left='A'; strcpy(A.right,"+"); A.right_length=1; A1.left='A'; strcpy(A1.right,"-"); A1.right_length=1; M.left='M'; strcpy(M.right,"*"); M.right_length=1; M1.left='M'; strcpy(M1.right,"/"); M1.right_length=1; for(i=0;i<7;i++) for(j=0;j<8;j++) { analyseTable[i][j].left='N'; analyseTable[i][j].right_length=0; } analyseTable[0][0]=E; analyseTable[0][5]=E; analyseTable[1][1]=G; analyseTable[1][2]=G; analyseTable[1][6]=G1; analyseTable[1][7]=G1; analyseTable[2][0]=T; analyseTable[2][5]=T; analyseTable[3][1]=H1; analyseTable[3][2]=H1; analyseTable[3][3]=H; analyseTable[3][4]=H; analyseTable[3][6]=H1; analyseTable[3][7]=H1; analyseTable[4][0]=F1; analyseTable[4][5]=F; analyseTable[5][1]=A; analyseTable[5][2]=A1; analyseTable[6][3]=M; analyseTable[6][4]=M1; } intmain() { chara,X; inti=0,j=0,m,u=0,v=0;//i指示栈顶位置,j指示剩余串扫描位置 intnum_vn,num_vt; boolflag=true; chartoken1[MAX]; chartoken2[MAX]; FILE*fpin,*fpout; create_analyseTable();//创建分析表 //读文件部分 if((fpin=fopen("input.txt","r"))==NULL) { cout<<"文件打开失败! "< exit(0); } if((fpout=fopen("result.txt","w"))==NULL) { fclose(fpin); cout<<"文件打开失败! "< exit(0); } token1[v++]=fgetc(fpin); while(! feof(fpin)) { token1[v++]=fgetc(fpin); if((v%5)==0) { token2[u]=token1[v-4]; token[u]=token1[v-2]; if(justify(token2[u],u)) u++; else { fclose(fpin); error(fpout); } } } fclose(fpin); if((v-1)%5! =0) error(fpout); cout<<"读入字符串为: "< //分析器部分 analyseStack[i++]='#'; analyseStack[i]='E'; a=token[j]; while(flag) { X=analyseStack[i]; if(check_VT(X)) if(X==a) { a=token[++j]; i--; } else error(fpout); else if(X=='#') if(X==a) flag=false; else { fprintf(fpout,"%s","FAIL! "); cout<<"FAIL! "< fclose(fpout); exit(0); } else { num_vn=getnum_VN(X); num_vt=getnum_VT(a); if(analyseTable[num_vn][num_vt].left! ='N') { if(analyseTable[num_vn][num_vt].right_length! =0) { m=analyseTable[num_vn][num_vt].right_length-1; for(;m>=0;m--) analyseStack[i++]=analyseTable[num_vn][num_vt].right[m]; } i--; } else error(fpout); } } fprintf(fpout,"%s","SUCCESS! "); fclose(fpout); cout<<"SUCCESS! "< return1; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- LL1 语法分析 设计 原理 实现 技术