合肥工业大学编译原理实验LL1分析法.doc

实验题目：LL(1)分析法 免费下载，不客气 班级： 学号： 姓名： Edited by Magic Yang 完成日期：2013-5-28 一、实验目的 通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。 二、实验内容 根据某一文法编制调试 LL （ 1 ）分析程序，以便对任意输入的符号串进行分析。 构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。 文法为 （1）E-TG （2）G-+TG|-TG （3）G-ε （4）T-FS （5）S-*FS|/FS （6）S-ε （7）F-(E) （8）F-i 数据结构及生成的算法描述 事先已经构造好的表： Vn数组------非终结符表 Vt数组------终结符 Gr数组------文法 事先定义的表及变量： 非终结符按照在非终结符中的位置与first集follow集对应 fi二维数组------first集,为真表示该终结符在该行对应的非终结符的first集中 fo二维数组------follow集,为真表示该终结符在该行对应的非终结符的follow集中 M二维数组------预测分析表 用到的方法： int or(int i,String s)---返回最近的在其右边一个“|”位置 int vn(char c)---返回c在非终结符表中的位置 int vt(char c)---返回c在终结符表中的位置 void addfi(String s, int j)---求关于某一个产生式的first集 void first(char v)---求非终结符c关于该文法的first集，first调用addfi void fir()---求所以非终结符的first集，fir调用first void addfo(String s,int j)---求关于某一个产生式的follow集 void follow(char v)---求非终结符v关于该文法的follow集，follow调用addfo void fol()---求所以非终结符的follow集,fol调用follow void MM(int j,int i,String s,int m)---将某一个产生式填入预测分析表中 void build_M()---构造预测分析表，build_M调用MM void isright(String s)---分析一个符号串是否符合该文法 算法流程图 源程序代码和测试的结果 package package_two; import java.util.*; import java.io.*; public class LL { char Vn[]={E,T,G,F,S};//非终结符 char Vt[]={+,-,*,/,(,),i,#,ε};//终结符 //非终结符按照在非终结符中的位置与first集follow集对应 boolean fi[][]=new boolean[Vn.length][Vt.length+1];//first集,为真表示该终结符在该行对应的非终结符的first集中 boolean fo[][]=new boolean[Vn.length][Vt.length+1];//follow集,为真表示该终结符在该行对应的非终结符的follow集中 String M[][]=new String[Vn.length][Vt.length-1];//预测分析表 String Gr[]={E-TG,G-+TG|-TG,G-ε,T-FS,S-*FS|/FS,S-ε,F-(E),F-i};//文法 LL(){ fir();//求first集 fol();//求follow集 build_M();//求预测分析表 } int or(int i,String s){//返回最近的在其右边一个“|”位置 for(i=i+1;is.length();i++){ if(s.charAt(i)==|) return i;//存在，就返回位置 } return -1;//返回-1表示没有“|”在其右边 } int vn(char c){//返回c在非终结符表中的位置 int i; for(