编译原理课程设计--语法分析器

计算机类课程设计报告课程名称：编译原理课程设计题目：语法分析器姓名：系：计算机专业：计算机科学与技术年级：学号：指导教师：职称：副教授2011~2012学年第二学期目录1 正则表达式 (1)1.1 正则表达式 (1)1.2 确定化(化简)后的状态转换图 (1)1.3 分析程序代码 (1)1.4 程序运行截图 (2)1.5 小结 (3)2 LL(1)分析 (4)2.1 LL(1)文法 (4)2.2 LL(1)预测分析表 (4)2.3 分析程序代码 (4)2.4 程序运行截图 (7)2.5 小结 (8)参考文献： (8)1 正则表达式1.1 正则表达式ab(a|b)*ba1.2 确定化(化简)后的状态转换图ab1.3 分析程序代码import java.util.Scanner;import java.util.regex.Matcher;import java.util.regex.Pattern;//导入所需要的包public class RegTest {//创建类RegTeststatic boolean test(String s1,String s2){/*编写测试函数返回布尔类型，用于验证输入字符串与要验证的表达式是否符合*/Pattern p=pile(s1);//正则表达式Matcher m=p.matcher(s2);//操作字符串boolean b=false;//p=pile(s1); ////m=p.matcher(s2);b=m.matches();//判断是否满足是则返回true否返回falseif(b==false){System.out.println("您输入的不符合您要求的正则表达式");}else{System.out.println("符合您所输入的正则表达式");}return b;}public static void main(String[] args) {// 主函数Scanner cin=new Scanner(System.in);//用于输入字符串String s;while(true){System.out.println("请输入正则表达式：");String s1=cin.nextLine();System.out.println("请输入字符串:");String s2=cin.nextLine();//输入表达式和要验证的字符串test(s1,s2);//调用函数，测试是否符合要验证的表达式while(true){System.out.println("是否继续验证该表达式？(yes/no)");s=cin.nextLine();//如果还想继续验证刚才输入的表达式，可以继续输入字符串if(!s.equals("yes")){break;}System.out.println("请输入字符串:");s2=cin.nextLine();test(s1,s2);//调用函数，测试是否符合要验证的表达式}System.out.println("是否继续验证正则表达式？(yes/no)");s=cin.nextLine();//如果需要验证其他字符串的话,可以继续输入if(!s.equals("yes")){break;}}}}1.4 程序运行截图1.5 小结总的来说对于正则表达有一定的了解，正则表达简单来说不算难，但是要深入就很难。

通过这次的报告，我清楚了解到正则表达式在实际的生活中其实还是很有用的，需要用的地方很多，编译原理，不止在编程上有用处，在实际生活中也是用处很大的。

对于现在的我来说正则表达式，只能算是了解，还得继续学习。

2 LL(1)分析2.1 LL(1)文法E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|i2.2 LL(1)预测分析表2.3 分析程序代码import java.util.ArrayList;import java.util.Scanner;public class LL1Analysis {public static void main(String a[]){int id=1;int index1=1;//记录栈最后一个非终结符的位置String topStack,topIn,operation;StringBuffer inString=null;ArrayList<String> list = new ArrayList<String>();System.out.println("请输入一个语句:");Scanner in = new Scanner(System.in);String ins=in.nextLine().trim();if(ins.indexOf("#")<0)//假如最后完了输入#号也没事ins+="#";elseins=ins.substring(0,ins.indexOf("#")+1);//截取#号在内的前部 inString = new StringBuffer(ins);int kong=inString.indexOf(" ");while(kong>=0)//去掉输入串表达式中的空格{inString.delete(kong,kong+1);kong=inString.indexOf(" ");}StringBuffer stack=new StringBuffer("#E");//分析栈，初始放入E String ll[][]={{"","i","+","*","(",")","#"},{"E","E’T/P","","","E’T/P","",""},{"E’","","E’T/N","","","ε/P","ε/P"},{"T","T’F/P","","","T’F/P","",""},{"T’","","ε/P","T’F/N","","ε/P","ε/P"},{"F","ε/N","","",")E/N","",""},{")","","","","","ε/N",""},{"#","","","","","","acc"}};//ll(1)分析矩阵System.out.println("LL(1)分析过程如下：");System.out.println("\n序号\t分析栈"+getBlank(20)+" 输入数据"+getBlank(20)+"动作");StringBuffer liutemp = null;while(stack.length()>0){int x=0,y=0;//记录在分析表中的的横纵坐标if(stack.toString().endsWith("\'")||stack.toString().endsWith("’"))//证明是带了一撇的非终结符index1 = stack.length()-2;//elseindex1=stack.length()-1;topStack=String.valueOf(stack.substring(index1,stack.length()));//栈顶元素if(inString.length()>0)topIn=String.valueOf(inString.charAt(0));//剩余输入串的第一个元素elsetopIn="";for(int i=1;i<ll.length;i++)//计算对应分析表的哪一行if(topStack.equals(ll[i][0])){x=i;break;}for(int i=1;i<ll[0].length;i++)//计算对应分析表的列数if(topIn.equals(ll[0][i])){y=i;break;}operation=ll[x][y];//动作命令if(operation.length()>=3){String first=operation.substring(0,operation.length()-2);//替换部分Stringlast=operation.substring(operation.length()-2,operation.length());//是否换行部分 if(first.equals("ε"))//如果是空字符，有不要加入栈first="";if(operation.equals("acc")){if(stack.length()==1&&inString.length()==1){System.out.println(id+"\t"+stack+getBlank(21-stack.length()-inString.length())+inStrin g+getBlank(11-operation.length())+operation);stack.delete(0,1);inString.delete(0,1);System.out.println("匹配成功！");}else{System.out.println(id+"\t"+stack+getBlank(21-stack.length()-inString.length())+inStrin g+getBlank(6)+"error");System.out.println("不能完整匹配！");}}else if(last.equals("/P")){System.out.println(id+"\t"+stack+getBlank(21-stack.length()-inString.length())+inStrin g+getBlank(11-operation.length())+operation);stack.replace(index1,index1+topStack.length(),first);//把栈顶元素替换为分析表中值if(first.equals(""))list.add(ll[x][0]+"->ε");else{liutemp = new StringBuffer(first);list.add(ll[x][0]+"->"+reverse(liutemp));}id++;}else if(last.equals("/N")){System.out.println(id+"\t"+stack+getBlank(21-stack.length()-inString.length())+inStrin g+getBlank(11-operation.length())+operation);stack.replace(index1,index1+topStack.length(),first);inString.delete(0,1);//相当于读下一个元素liutemp = new StringBuffer(first);list.add(ll[x][0]+"->"+topIn+reverse(liutemp));if(stack.toString().endsWith("\'")||stack.toString().endsWith("’")) index1 = stack.length()-2;//重新设置index1值elseindex1=stack.length()-1;id++;}else {System.out.println("分析表构造出错！");System.exit(0);}}else if(y==0){System.out.println(id+"\t"+stack+getBlank(21-stack.length()-inString.length())+inStrin g+getBlank(6)+"error");System.out.println("输入的符号不符合规定文法！");System.exit(0);}else if(x!=0&&y!=0&&operation.length()==0){System.out.println(id+"\t"+stack+getBlank(21-stack.length()-inString.length())+inStrin g+inString+getBlank(6)+"error");System.out.println("输入符号串不完整！");System.exit(0);}}System.out.println("\n该语句自顶向下构建语法树过程：");for(int i = 0;i<list.size();i++)System.out.println(list.get(i));}public static StringBuffer reverse(StringBuffer buffer){//字母、运算符倒置 StringBuffer buf = new StringBuffer();int ix=-1;int length=0;if(buffer.indexOf("'")<0&&buffer.indexOf("’")<0)buf.append(buffer.reverse());else{while(buffer.length()>0){length = buffer.length();if(buffer.charAt(length-1)=='\''||buffer.charAt(length-1)=='’'){buf.append(buffer.substring(length-2,length));buffer.delete(length-2,length);}else {buf.append(buffer.charAt(length-1));buffer.delete(length-1,length);}}}return buf;}public static String getBlank(int n){//得到n个连续空格String blank="";for(int i=0;i<n;i++)blank+=" ";return blank;}}2.4 程序运行截图2.5 小结对于LL(1)分析法有一定了解，对于完成整个算法还是挺吃力的，查看的相当的一些资料，才慢慢理解，并且慢慢的想出其算法。