1、LL1语法分析设计原理与实现技术LL(1)语法分析设计原理与实现技术实验报告变更说明日期版本变更位置变更说明作者2014/4/301.0初稿生成房皓一、实验目的：本实验的目的在于在教师的引导下以问题回朔与思维启发的方式，使学生在不断的探究过程中掌握编译程序设计和构造的基本原理和实现技术，启迪学生的抽象思维、激发学生的学习兴趣、培养学生的探究精神和专业素养，从而提高学生发现问题、分析问题和解决问题的能力。二、实验内容：实验项目 实现LL(1)分析中控制程序（表驱动程序）；完成以下描述算术表达式的LL(1)文法的LL(1)分析程序。GE: ETEEATE|TFTTMFT|F (E)|iA+|-M*
2、|/实验说明终结符号i 为用户定义的简单变量,即标识符的定义。设计要求（1）输入串应是词法分析的输出二元式序列，即某算术表达式“实验项目一”的输出结果。输出为输入串是否为该文法定义的算术表达式的判断结果；（2）LL(1)分析过程应能发现输入串出错；（3）设计两个测试用例（尽可能完备，正确和出错），并给出测试结果。三、实验环境：操作系统：Windows 7软件： VC+6.0四、程序功能描述：提供了文件输入方式，且输入的内容为二元式序列；能够对输入的字符串做出正确的LL(1)分析判断，并给出判断结果，判断结果输出到文件，并显示在屏幕；能发现输入串中的错误，包含非法字符，输入不匹配等；能够处理一些
3、可预见性的错误，如文件不存在，输入非法等。五、数据结构设计：全局：局部（main()中）：六、程序结构描述：设计方法：本程序采用从文件读取的输入方式，输入的内容需为二元式序列，然后按照LL(1)分析的方法对输入的字符串进行分析判断，并输出判断结果，程序通过对输入串的检查能够发现输入串中的错误。程序规定的单词符号及其种别码见下表：单词符号及其种别码表单词符号种别码单词符号种别码（1*5）2/6+3i7-4#8分析表i+-*/()#EETGETGGGATGGATGGGTTFHTFHHHHHMFHHMFHHHFFiF(E)AA+A-MM*M/主要函数说明：check_VT(char ch)：bool
4、型函数，检查ch是否为终结字符，是则返回true；create_analyseTable()：构建分析表函数，无返回值；error(FILE *fp)：输出错误，表示不是该文法的句子,参数fp用于退出前将打开的文件关闭；getnum_VN(char ch)：int型函数，查找ch在非终结字符中的位置并返回；getnum_VT(char ch)：int型函数，查找ch在终结字符中的位置并返回；justify()：bool型函数，判断文件读取内容是否合法，包括检查非法字符和不匹配现象，出错返回false，否则返回true；main()：主函数。函数调用关系说明：main()调用check_VT(c
5、har ch)、create_analyseTable()、error(FILE *fp)、getnum_VN(char ch)、getnum_VT(char ch)、justify()；执行框图：七、实验过程结果截图：测试用例一：i+i*i/i# 测试用例二：i+i*i/#八、实验总结：实验心得：通过本次实验我锻炼了自己的上机操作能力及编程能力，并对理论知识有了进一步的了解。老师提供的LL(1)分析法的流程图给了我很大的帮助，使得本实验基本思路变得很清晰，用较为简单的算法就能实现，程序的难点是产生式结构体的构造、分析表的构造、解决实验中遇到的问题也花费了一部分时间，我增长了处理关于文件错误的
6、能力。实验中遇到的问题及解决方法：问题主要有i.从文件输入二元式时，需要检查输入的内容是否符合程序规定的字符种别码，解决方法是用了两个字符数组token,token2，分别记录种别码和字符，并增加了一个函数justify()根据既定的种别码表判断；ii.当输入内容不匹配或输入内容非法时要退出程序，此时若不关闭已经打开的文件可能导致文件内容受到破坏；解决方法是给error()函数设置一个文件指针变量参数FILE* fp，在退出程序之前通过fp关闭文件程序的自我评价：此程序实现了要求中的所有功能，并增加了输入串错误检测的功能，但因编程能力及经验的有限，其中有的地方不免有些繁杂，还有一些潜藏的问题，
7、需要进一步测试与修改来提高程序的健壮性。九、程序清单：/*课题名称：LL(1)语法分析设计原理与实现技术作者：房皓 进修生 13410801最后修改时间：2014.4.30*/*单词符号及其分类编码单词符号 种别码 ( 1 ) 2 + 3 - 4 * 5 / 6i 7# 8/*文法* GE:E TEEATE|T FTTMFT|F (E)|iA +|-M *|/ /*改为等价文法*GE:ETGGATG|TFHHMFH|F(E)|iA+|-M*|/ /*分析表* i + - * / ( ) #E ETG ETG G GATG GATG G GT TFH TFH H H H HMFH HMFH H
8、HF Fi F(E) A A+ A- M M* M/ /*/#include#include#includeusing namespace std;#define MAX 50char analyseStackMAX; /分析栈char tokenMAX; /输入串typedef struct CSS /产生式结构体 char left; char right5; int right_length;CSS;CSS E,G,G1,T,H,H1,F,F1,A,A1,M,M1;CSS analyseTable78;void error(FILE *fp) fprintf(fp,%s,FAIL!);
9、fclose(fp); coutFAIL!endl; exit(0);bool justify(char ch,int i) /判断文件读取内容是否合法，包括检查非法字符和不匹配现象 switch(ch) case 1: if(tokeni!=() return false; break; case 2: if(tokeni!=) return false; break; case 3: if(tokeni!=+) return false; break; case 4: if(tokeni!=-) return false; break; case 5: if(tokeni!=*) retu
10、rn false; break; case 6: if(tokeni!=/) return false; break; case 7: if(tokeni!=i) return false; break; case 8: if(tokeni!=#) return false; break; default: return false; break; return true;bool check_VT(char ch) if(ch=i | ch=+ | ch=- | ch=* | ch=/ | ch=( | ch=) return true; return false;int getnum_VN
11、(char ch) char VN7=E,G,T,H,F,A,M; int i; for(i=0;i7;i+) if(ch=VNi) break; return i;int getnum_VT(char ch) char VT8=i,+,-,*,/,(,),#; int i; for(i=0;i8;i+) if(ch=VTi) break; if(i=8) coutFAIL!endl; exit(0); return i;void create_analyseTable() int i,j; E.left=E; strcpy(E.right,TG); E.right_length=2; G.l
12、eft=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.
13、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;i7;i+) for(j=0;j8;j+) analyseTableij.left=N; analys
14、eTableij.right_length=0; analyseTable00=E; analyseTable05=E; analyseTable11=G; analyseTable12=G; analyseTable16=G1; analyseTable17=G1; analyseTable20=T; analyseTable25=T; analyseTable31=H1; analyseTable32=H1; analyseTable33=H; analyseTable34=H; analyseTable36=H1; analyseTable37=H1; analyseTable40=F1
15、; analyseTable45=F; analyseTable51=A; analyseTable52=A1; analyseTable63=M; analyseTable64=M1;int main() char a,X; int i=0,j=0,m,u=0,v=0; /i指示栈顶位置，j指示剩余串扫描位置 int num_vn,num_vt; bool flag=true; char token1MAX; char token2MAX; FILE *fpin,*fpout; create_analyseTable(); /创建分析表 /读文件部分 if(fpin=fopen(input.
16、txt,r)=NULL) cout文件打开失败！endl; exit(0); if(fpout=fopen(result.txt,w)=NULL) fclose(fpin); cout文件打开失败！endl; exit(0); token1v+=fgetc(fpin); while(!feof(fpin) token1v+=fgetc(fpin); if(v%5)=0) token2u=token1v-4; tokenu=token1v-2; if(justify(token2u,u) u+; else fclose(fpin); error(fpout); fclose(fpin); if(
17、v-1)%5 != 0) error(fpout); cout读入字符串为：tokenendl; /分析器部分 analyseStacki+=#; analyseStacki=E; a=tokenj; while(flag) X=analyseStacki; 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!); coutFAIL!=0;m-) analyseStacki+=analyseTablenum_vnnum_vt.rightm; i-; else error(fpout); fprintf(fpout,%s,SUCCESS!); fclose(fpout); coutSUCCESS!endl; return 1;
