《编译原理》课程设计报告-LALR(1)分析器.doc

编译原理课程设计报告 题目：LALR(1)分析器 2011年6月一 设计目的 1 巩固对语法分析的基本功能和原理的认识。2 通过对语法分析表的自动生成加深语法分析表的认识。3 理解并处理语法分析中的异常和错误。4 熟练掌握LALR(1)语法分析过程。二 设计内容本次课程设计是设计一个LALR(1)语法分析器。LALR(1)是LR(1)的一种改进。为了克服LR(1)中分析表的构造对某些同心集的分裂可能对状态数目引起剧烈的增长，从而导致存储容量的急剧增加，采用对LR(1)项目集规范族合并同心集的方法，若合并同心集后不产生新的冲突，则为LALR(1)项目集。本次课程设计的主要内容有首先生成LR(1)项目族；再合并同心集；然后生成LALR(1)项目族，求出LALR(1)的分析表；最后能判断一个字符串是否是该文法的串，若是则生成该字符串的树。具体实现过程及相关主要实现类如下：类：LR0功能：LR0核心项目集构造输入：产生式的数字化表示输出：LR0核心项目集实现思想：LR0核心项目集构造算法程序如下：public class LR0ArrayListArrayList core;ArrayListArrayList Ary_c;ArrayList producer;private int copy(int a )int val=new inta.length;for(int i=0;ia.length;i+)vali=ai;return val;private ArrayList copy(ArrayLista)ArrayList val=new ArrayList ();for(int i=0;ia.size();i+)val.add(copy(a.get(i);return val;public boolean isEqual(int a,int b)if(a.length!=b.length)return false;for(int i=0;ia.length;i+)if(ai!=bi)return false;return true;public boolean isEqual(ArrayList a,ArrayListb)if(a.size()!=b.size()return false;for(int i=0;ia.size();i+)if(!isEqual(a.get(i),b.get(i)return false;return true;public int indexof(ArrayList a,int b)int index;int s1;for(index=0;indexa.size();index+)s1=a.get(index);if(isEqual(s1,b)=true)return index;return -1;public int indexof(ArrayList ArrayList a,ArrayList b)int index;ArrayList s1;for(index=0;indexa.size();index+)s1=a.get(index);if(isEqual(s1,b)=true)return index;return -1;public int getStartWith(int i)int count=i;ArrayList temp=new ArrayList(3);while(counti)break;count+;int val=new inttemp.size();for(count=0;counttemp.size();count+)valcount=temp.get(count);return val;public void closuer_innal(int item,ArrayList pos)if(item.length=2)return ;int i;int p;for(i=0;iitem.length&itemi!=-1;i+);if(item.length-1=i)return ;if(itemi+11000)p=getStartWith(itemi+1);for(i=0;ip.length;i+)if(pos.indexOf(pi)=-1)pos.add(pi);closuer_innal(producer.get(pi),pos);return ;public ArrayList closure(int a) /求闭包ArrayList val=new ArrayList();ArrayList pos=new ArrayList();closuer_innal(a,pos);for(int i=0;ipos.size();i+)val.add(copy(producer.get(pos.get(i);return val;public ArrayList Goto(ArrayLista,int x)int index1=0,index2=0,index3,bl,index=0;int s1,s2; ArrayList temp1 = new ArrayList (); /临时ArrayList temp2 = new ArrayList ();temp1=copy(a);s1=temp1.get(index1);if(s1=null)return null;while(s1index2!=-1)index2+;if(s1.length=index2)return null;index2+;for(index3=0;index3temp1.size();index3+)s1=copy(temp1.get(index3);if(s1.lengthindex2+1) /防止Array溢出continue;if(s1index2=x&indexof(temp2,s1)0)bl=s1index2-1;s1index2-1=s1index2;s1index2=bl; /-1往后移位temp2.add(copy(s1);bl=temp2.size();for(index=0;indexbl;index+) /求goto函数中的返回值的closure集s1=copy(temp2.get(index);temp1=closure(s1);for(index1=0;index1temp1.size();index1+)s2=temp1.get(index1);if(indexof(temp2,s2)0)temp2.add(s2);return temp2;public LR0(ArrayList p)core =new ArrayListArrayList();Ary_c=new ArrayListArrayList();producer=p;public void total()ArrayList cur=new ArrayList();cur.add(producer.get(0);core.add(cur);int i=0;while(icore.size()cur=core.get(i);LR0Split(cur);i+;update();public void LR0Split(ArrayListcur)ArrayList handle=copy(cur);ArrayList tempal;int temp;int prod;int start;ArrayList result=new ArrayList();ArrayList val=new ArrayList();int j;for(int i=0;icur.size();i+)tempal=closure(cur.get(i);for(j=0;jtempal.size();j+)if(indexof(handle,tempal.get(j)=-1)handle.add(tempal.get(j);while(!handle.isEmpty()prod=(int) handle.get(0);start=getStart(prod); /返回-1之后的数,没有返回-1if(start=-1)handle.remove(0);continue;result=getStartWith(start,handle); /返回handle中所有-1之后是start的产生式,并删除repair(result); /将result中产生式-1以后的数与-1调换 /*returnval=new ArrayList();for(int i=0;iresult.size();i+)temp=(int) result.get(i);val=closure(temp);if(indexof(returnval,temp)0);returnval.add(temp);for(int j=0;jval.size();j+)if(indexof(returnval,val.get(j)0);returnval.add(val.get(j);*/if(indexof(core,result)0)core.add(result);public int getStart(int prod) /返回-1之后的数,没有返回-1int i=0;while(prodi!=-1&iprod.length)i+;if(prod.length-1=i)return -1;else return prodi+1;public ArrayList getStartWith(int start, ArrayListhandle) ArrayList val=new ArrayList() ;int i;for(i=0;ihandle.size();i+)if(isStartWith(start,handle.get(i) val.add(handle.get(i);handle.remove(i);i-;return val; /返回handle中所有-1之后是start的产生式,并删除public boolean isStartWith(int start,int prod) /产生式-1之后是否为start,是返回1，否则返回0；boolean state=false;if(getStart(prod)=start)state=true;return state;public void repair(ArrayList prod) /将result中产生式-1以后的数与-1调换 int num;int i,j=0;for(i=0;iprod.size();i+)j=0;while(prod.get(i)+j!=-1);if(prod.get(i).length=j+1) /遇到空字符的动作continue;num=prod.get(i)j;prod.get(i)j=prod.get(i)j+1;prod.get(i)j+1=num;public void update()ArrayList Ary_n=new ArrayList();ArrayList Ary_r;int index;int prod;for(int i=0;icore.size();i+)Ary_n=core.get(i);Ary_r=new ArrayList();for(index=0;indexAry_n.size();index+)prod=(int) Ary_n.get(index);if(prod0=0|prod1!=-1)Ary_r.add(prod);if(indexof(Ary_c,Ary_r)0)Ary_c.add(Ary_r);System.out.println();类：Phrase功能：为每个项目配备向前搜索符输入：LR0核心项目集输出：LALR(1)核心项目集实现思想：LALR(1)的造核算法 public void sponsor()Queue hq;int i,j;/核心项目lnodeLinkNode lnode;QNode qnode;/核心项目的产生式int p;/-2是一个特殊的标志符，也就是传播符串的标志；int s=-2;calFirst =new CalFirst(producer);hq=new Queue();/开始符号的特殊处理VT.add(#);I0.search=new int1;I0.search0=VT.indexOf(#)+1000;qnode=new QNode(0,0);hq.enq(qnode);for(i=0;i0)for(j=0;j0)for(j=0;jitem.size();j+)qnode=update(item.get(j),lnode.search,hq);/修改传播搜索符并入队/if(qnode!=null)/hq.enq(qnode);/对每一个状态集都进行如此处理/求出项目p的闭包中所有核心项目的自生搜索符private int copy(int a )int val=new inta.length;for(int i=0;ia.length;i+)vali=ai;return val;public boolean closuer_self(int p,int s)int i;int left=-1;/产生式左部int temp;int genrate;int pos;int new_s;/ArrayList pos=new ArrayList();/找到-1(.)之后的第一个符号for(i=1;ip.length&pi!=-1;i+);i+;/p为移进项目if(i=1000)return false;/example:/0 1 -1 1 1003 2 /left = 1/s = first(1003,2,s);i+;/项目p中left之后的符号串加上s的first集就是left -1 XXX的搜索符集new_Snew_s=first(p,i,s);pos=getStartWith(left);/closuer(p,pos);for(i=0;ipos.length;i+)genrate=producer.get(posi);/递归向下求解,暂时定为自生一次即截止，向下传播通过genarate的自生求解if(genrate.length=2)continue;if(!(left=p0)closuer_self(genrate,s);elseif(!isEqual(genrate,p)closuer_self(genrate,s);/搜索符集是自生的if(new_s0!=-2)genrate=copy(genrate);temp=genrate1;genrate1=genrate2;genrate2=temp;item.add(genrate);sstr.add(new_s);return true;public void closuer(int item,ArrayList pos)if(item.length=2)return ;int i;int p;for(i=0;iitem.length&itemi!=-1;i+);if(itemi+11000)p=getStartWith(itemi+1);for(i=0;ip.length;i+)if(pos.indexOf(pi)=-1)pos.add(pi);closuer(producer.get(pi),pos);return ;/返回项目p所能传播到的所有项目public boolean closuer_spread(int p,int s)int i;int left=-1;/产生式左部符号int genrate;/int pos;int new_s;int temp;ArrayList pos=new ArrayList();/找到-1(.)之后的第一个符号for(i=1;ip.length&pi!=-1;i+);i+;/p为移进项目if(i=1000)return false;/example:/0 1 -1 1 1003 2 /left = 1/s = first(1003,2,s);i+;/项目p中left之后的符号串加上s的first集就是left -1 XXX的搜索符集new_Sint tempArr=new int1;tempArr0=-2;new_s=first(p,i,tempArr);tempArr=null;/获得所有以left退出的项目/pos=getStartWith(left);this.closuer(p, pos);for(i=0;i=1个），并在第一个位置之后添加-1/本函数是建立在producer中的产生式的左部按升序基础上的，不可随意使用public int getStartWith(int i)int count=i;ArrayList temp=new ArrayList(3);while(counti)break;count+;int val=new inttemp.size();for(count=0;counttemp.size();count+)valcount=temp.get(count);return val;public int first(int prod,int i,int search)if(i=prod.length)return search;/calFirst.a.clear();/calFirst.firstv(prod, i, search);return calFirst.first(prod, i, search);private intarrCon(inta,int b)boolean isChange=false;ArrayList temp=new ArrayList();int i;if(a!=null)for(i=0;ia.length;i+)temp.add(ai);for(i=0;ib.length;i+)/有所更新if(temp.indexOf(bi)=-1)temp.add(bi);isChange=true;a=new inttemp.size();for(i=0;ia.length;i+)ai=temp.get(i);if(isChange)return a;elsereturn null;public QNode update(int prod,int search,Queue hq)/返回修改的项目是第几个状态集合中的(QNode.state)的第几个项目(QNode.item)(从0记数)LinkNode p;int a;int item;int i=0;while(iI.length)item=0;p=Ii;while(p!=null)if(isEqual(d,prod)a =arrCon(p.search,search);/null表示没有做任何修改if(a!=null)p.search =a;hq.enq( new QNode(i,item);return null;/此处是一个危险点,必须保证不能有一个项目在多个状态中出现,否则,会出现严重的错误item+;p=p.next;i+;return null;public boolean isEqual(int a,int b)if(a.length !=b.length)return false;for(int i=0;ia.length ;i+)if(ai!=bi)return false;return true;类：Analyze功能：整个分析程序的总控程序输入：编译目标文件、输出文件路径输出：语法分析树、三地址代码、错误信息实现思想：LR分析器工作原理class Analyzeprivate ArrayList producer =new ArrayList(); private ArrayList VT=new ArrayList(); private ArrayList VN=new ArrayList(); / private LinkNode I; / 移进均为小于1000的,归约为大于1000的,并且接受状态的内容为-1,空状态用-2表示 private intAction; private intGoto;/Goto private String prods; private ArrayListlalr; DefaultMutableTreeNode root=null; public ArrayList errorInfo=new ArrayList(); public ArrayList errorLine=new ArrayList(); public void analyze(String filePath,File outFile)FileInputStream f = null; try f = new FileInputStream(filePath); catch (FileNotFoundException e) e.printStackTrace(); /打开词法分析流： DataInputStream input = new DataInputStream(f); /lex为词法分析器 TinyCLexer lex=new TinyCLexer(input); try Stack stateStack =new Stack(); /状态栈 Stack tokenStack = new Stack(); /符号栈的内容为：非终结符与VN中相对应，终结符-1000后与VT中相对应 int state; int temp; int prod; int i; int action; TokenNode data; Token token=null; Token oldtoken=null; int tokentype; int end=VT.indexOf(#)+1000;/#入栈 Tree tree=new Tree(); Syntax syn=new Syntax(tree,new FileWriter(outFile); stateStack.push(0);/状态0保证是开始状态 tokenStack.push(end); errorInfo.clear(); errorLine.clear(); token=lex.nextToken();/获得下一个面临的词法符 while(true) state=stateStack.peek();/获得栈顶状态 if(token.getType()=100)/无意义的跳过 continue; if(token.getText()=null) token.setType(VT.indexOf(#); /token.getType()就是面临的输入符号（一定是终结符）,它与VT中相对应 action=Actionstatetoken.getType(); if(action=-1) prod=producer.get(0); stateStack.pop(); if(prod2!=tokenStack.pop() JOptionPane.showMessageDialog(null, 编译程序遇到不能处理的错误！n分析被中止, 提示, JOptionPane.INFORMATION_MESSAGE, new ImageIcon(imageserror.png); return ; tree.Reduce(prod.length-2, VN.get(prod0); syn.SyntaxAnalyze(0); root= tree.getRoot(); JOptionPane.showMessageDialog(null, 编译程序完成编译！, 提示, JOptionPane.INFORMATION_MESSAGE, new ImageIcon(imagesright.png); return ; if(Actionstatetoken.getType()1;i-)/产生式的右部的逆序为出栈顺序 stateStack.pop(); if(prodi!=tokenStack.pop() JOptionPane.showMessageDialog(null, 编译程序遇到不能处理的错误！n分析被中止, 提示, JOptionPane.INFORMATION_MESSAGE, new ImageIcon(imageserror.png); return ; tree.Reduce(prod.length-