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

1、合肥工业大学编译原理实验 LL1分析法实验题目：LL(1)分析法免费下载，不客气班级：学号：姓名：Edited by Magic Yang完成日期：2013-5-28一、实验目的 通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。二、实验内容 根据某一文法编制调试 LL （ 1 ）分析程序，以便对任意输入的符号串进行分析。 构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 分析法的功能是利

2、用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-i3、数据结构及生成的算法描述事先已经构造好的表：Vn数组-非终结符表Vt数组-终结符Gr数组-文法事先定义的表及变量： 非终结符按照在非终结符中的位置与first集follow集对应fi二维数组-first集,为真表示该终结符在该行对应的非终结符的first集中fo二维数组-follow集,为真表示该终结符在该行对应的非终结符的follow集中M二维数组-预测分

3、析表用到的方法：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调用addfivoid fir()-求所以非终结符的first集，fir调用firstvoid addfo(String s,int j)-求关于某一个产生式的follow集void follow(char v)-求非终结

4、符v关于该文法的follow集，follow调用addfovoid fol()-求所以非终结符的follow集,fol调用followvoid MM(int j,int i,String s,int m)-将某一个产生式填入预测分析表中void build_M()-构造预测分析表，build_M调用MMvoid isright(String s)-分析一个符号串是否符合该文法4、算法流程图5、源程序代码和测试的结果package package_two;import java.util.*;import java.io.*;public class LL char Vn=E,T,G,F,S;/

5、非终结符 char Vt=+,-,*,/,(,),i,#,;/终结符 /非终结符按照在非终结符中的位置与first集follow集对应 boolean fi=new booleanVn.lengthVt.length+1;/first集,为真表示该终结符在该行对应的非终结符的first集中 boolean fo=new booleanVn.lengthVt.length+1;/follow集,为真表示该终结符在该行对应的非终结符的follow集中 String M=new StringVn.lengthVt.length-1;/预测分析表 String Gr=E-TG,G-+TG|-TG,G-

6、,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(i=0;iVn.length;i+) if(c=Vni)return i;/在表中，就

7、返回位置 return -1;/返回-1表示不在表中 int vt(char c)/返回c在终结符表中的位置 int i; for(i=0;iVt.length;i+) if(c=Vti)return i;/在表中，就返回位置 return -1;/返回-1表示不在表中 void addfi(String s, int j)/求关于某一个产生式的first集 int v=vn(s.charAt(0);/v为产生式左边的非终结符 int i; if(vt(s.charAt(j)!=-1)/产生式右边第一个为终结符 fivvt(s.charAt(j)=true;/就把s.charAt(j)加入s.

8、charAt(0)的first集 else/产生式右边第一个为非终结符 if(!fivn(s.charAt(j)Vt.length)/如果s.charAt(j)的first集没有求，先求s.charAt(j)的first集 first(s.charAt(j); for(i=0;iVt.length;i+)/把s.charAt(j)的first集中不为的加入s.charAt(0)的first集 if(fivn(s.charAt(j)i&Vti!=) fivi=true; if(vt()!=-1)/终结符中有 if(fivn(s.charAt(j)vt()/如果属于当前s.charAt(j)的fi

9、rst集 if(j=s.length()-1)/j=s.length()-1就将加入s.charAt(0)的first集 fivvt()=true; return ; if(s.charAt(j+1)!=|)/s.charAt(j+1)不是“|”就将s.charAt(j+1)的first集加入s.charAt(0)的first集 j+; addfi(s,j); else/s.charAt(j+1)是“|”就将加入s.charAt(0)的first集 fivvt()=true; void first(char v)/求非终结符v关于该文法的first集 int i,j; String s; fo

10、r(i=0;iGr.length;i+) s=Gri; if(s.charAt(0)=v)/产生式的左边是要求的非终结符 j=3; if(s.charAt(0)!=s.charAt(j)/要求的非终结符与右边第一个不同时，求first集 addfi(s,j); /求关于此产生式的first集 while(or(j,s)!=-1&js.length()/判断有无|，有就继续求first集 j=or(j,s);/得到|位置 if(s.charAt(0)!=s.charAt(j+1)/要求的非终结符与右边第一个不同时，求first集 addfi(s,j+1);/求关于此产生式的first集 fivn

11、(v)Vt.length=true;/将fivn(v)Vt.length设为true，表示已求v的first集 void fir()/求所以非终结符的first集 int i,j; for(i=0;iVn.length;i+)/非终结符的first集未求时，求该非终结符的first集 if(!fiiVt.length) first(Vni); System.out.println(first集); for(i=0;iVn.length;i+)/输出非终结符的first集 System.out.println(Vni); for(j=0;jVt.length;j+) if(fiij) Syste

12、m.out.print( +Vtj); System.out.println(); void addfo(String s,int j)/求关于某一个产生式的follow集 int i; /考察字符位于产生式末尾时将产生式左边的那个字符的follow集加到考察字符的follow集中 if(j=s.length()-1|(js.length()-1&s.charAt(j+1)=|) if(s.charAt(0)!=s.charAt(j)/考察字符与产生式左边的非终结符不同时 if(!fovn(s.charAt(0)Vt.length)/产生式左边的非终结符的follow集未求时，先求产生式左边的

13、非终结符的follow集 follow(s.charAt(0); for(i=0;iVt.length;i+)/产生式左边的非终结符的follow集加到考察字符的follow集中 if(fovn(s.charAt(0)i) fovn(s.charAt(j)i=true; /将考察字符右边第一个字符的first集加到考察字符的follow集中 if(js.length()-1&s.charAt(j+1)!=|) if(vt(s.charAt(j+1)!=-1)/该字符为终结符 if(Vtvt(s.charAt(j+1)!=)/该字符不为，将该字符加入考察字符的follow集中 fovn(s.ch

14、arAt(j)vt(s.charAt(j+1)=true; else/该字符不为终结符 for(i=0;iVt.length;i+)/该字符的first集中除的非终结符加入考察字符的follow集中 if(fivn(s.charAt(j+1)i&Vti!=) fovn(s.charAt(j)i=true; if(vt()!=-1)/非终结符中有 /当考察字符右边的字符串的first集中有将产生式左边的那个字符的follow集加到考察字符的follow集中 if(s.charAt(0)=s.charAt(j) return;/考察字符与产生式左边的非终结符时同时，返回 boolean m=tru

15、e;/当考察字符右边的字符串的first集中有，m为真，没有时，m为假 for(i=j+1;is.length();i+) if(vt(s.charAt(i)!=-1)/当考察字符右边的字符串中有终结符，m为假 m=false; break; if(s.charAt(i)=|)/遇到|跳出 break; if(!fivn(s.charAt(i)vt()/当考察字符右边的字符串中的有一非终结符的first集中不含，m为假 m=false; if(m)/m为真，将产生式左边的那个字符的follow集加到考察字符的follow集中 if(!fovn(s.charAt(0)Vt.length)/产生式

16、左边的非终结符的follow集未求时，先求产生式左边的非终结符的follow集 follow(s.charAt(0); for(i=0;iVt.length;i+)/产生式左边的非终结符的follow集加到考察字符的follow集中 if(fovn(s.charAt(0)i) fovn(s.charAt(j)i=true; void follow(char v)/求非终结符v关于该文法的follow集 if(v=E)/v为开始符号时，将#加入v的follow集中 fovn(v)vt(#)=true; int i,j; String s; for(i=0;iGr.length;i+) s=Gri

17、; for(j=3;js.length();j+) if(s.charAt(j)=v)/产生式右边有考察字符 addfo(s,j);/求关于该产生式的follow集 fovn(v)Vt.length=true;/将fovn(v)Vt.length设为true，表示已求v的first集 void fol()/求所以非终结符的follow集 int i,j; for(i=0;iVn.length;i+)/非终结符的follow集未求时，求该非终结符的ffollow集 if(!foiVt.length) follow(Vni); System.out.println(follow集); for(i=

18、0;iVn.length;i+)/输出非终结符的follow集 System.out.println(Vni); for(j=0;jVt.length;j+) if(foij) System.out.print( +Vtj); System.out.println(); void MM(int j,int i,String s,int m)/将某一个产生式填入预测分析表中 char u=Gri.charAt(0); int k; if(vt(Gri.charAt(j)!=-1)/Gri.charAt(j)为终结符 if(Gri.charAt(j)!=)/Gri.charAt(j)不为时将s加到

19、Mvn(u)vt(Gri.charAt(j)中 Mvn(u)vt(Gri.charAt(j)=s; else for(k=0;kVt.length-1;k+)/Gri.charAt(j)为，将属于s的follow集的b将s加到Mvn(u)vt(b)中 if(fovn(u)k)Mvn(u)k=s; else/Gri.charAt(j)为非终结符 for(k=0;kVt.length-1;k+)/对于终结符a属于Gri.charAt(j)的first集时，将s加到Mvn(u)vt(a)中 if(fivn(Gri.charAt(j)k)Mvn(u)k=s; if(fivn(Gri.charAt(j)

20、vt()/当属于Gri.charAt(j)的first集时，将属于s的follow集的b将s加到Mvn(u)vt(b)中 if(j=m-1) for(k=0;kVt.length-1;k+) if(fovn(u)k)Mvn(u)k=s; else j=j+1; MM(j,i,s,m); void build_M()/构造预测分析表 int i,j,m; String s; for(i=0;iGr.length;i+) j=3; while(jGri.length() m=or(j,Gri); if(m=-1) m=Gri.length(); s=Gri.substring(j, m);/将j到

21、m-1赋值到s MM(j,i,s,m); j=m+1; void isright(String s)/分析一个字符串是否符合该文法 Stack temp=new Stack();/分析栈 temp.setSize(20); temp.push(new Character(#);/初始化将#入栈 temp.push(new Character(E);/初始化将E入栈 char u,v; int i=0,j,k=0; String m,action=初始化,rule= ; while(is.length() u=s.charAt(i); System.out.print(k+ ); for(j=0

22、;j+m; if(!m.equals()/产生式不为 action=action+,push(; for(j=m.length()-1;j-1;j-)/将产生式反序入栈 action=action+m.charAt(j); temp.push(new Character(m.charAt(j); action=action+); else/分析表中没有产生式，提示错误 rule= ; System.out.println(wrong : +u+不在+v+对应的分析表中); return; else/栈顶元素为终结符时 rule=; if(v=u)/栈顶元素与输入符匹配 if(v=#)/栈顶元素

23、为#时，成功 System.out.println(accept); return; else i+; action=getnext(I); else/栈顶元素与输入符不匹配，提示错误 System.out.println(wrong : +u+与+v+不等); return; k+; public static void main(String args)throws IOException LL one=new LL(); String s; BufferedReader sin=new BufferedReader(new InputStreamReader(System.in); s=sin.readLine(); s=s.concat(#); System.out.println(s); one.isright(s); sin.close(); 测试方法和测试结果 测试方法：命令行输入符号串测试结果：6、实验的评价、收获与体会