精华内容
下载资源
问答
  • 编译原理算符优先矩阵的构造

    千次阅读 2018-07-12 12:20:03
    算符优先法中算符优先矩阵的构造需要求出firstTerm以及lastTerm,由于这个是在预测分析法上进行修改的,结构体的定义并未进行修改,其中包含该非终结符a以及其对应的first(即为firstTerm)和follow(即为lastTerm)...

    算符优先法中算符优先矩阵的构造需要求出firstTerm以及lastTerm,由于这个是在预测分析法上进行修改的,结构体的定义并未进行修改,其中包含该非终结符a以及其对应的first(即为firstTerm)和follow(即为lastTerm),输入格式如下(以#结束输入)
    Z::=E
    E::=T|E+T
    T::=F|T*F
    F::=(E)|i
    #

    #include<bits/stdc++.h>
    using namespace std;
    //判断终结符和非终结符 返回1是非终结符 返回0是终结符 
    int Norterminal(char c)
    {
        if(c>='A'&&c<='Z') 
            return 1;
        else if(c!=':'&&c!='='&&c!='<'&&c!='>'&&c!=' '&&c!='|') 
            return 0; 
    
    }  
    struct GRAM
    {
        //$代表空 
        string  a;
        string first;
        string follow;
    };
    struct LIST
    {
        int num;
        string s;
    };
    int main()
    {
        GRAM gram[50]; 
        string grammer; 
        cout<<"请输入文法(以#结束)"<<endl;
        std::vector<string> strN;
        cin>>grammer;//输入规则 
        strN.push_back(grammer); 
        char str[10][80];  
        const char *ch = "|";  
        char *result;  
        vector<string> strN1;  //存处理过“|”规则的 
    
        for(int i=0;i<grammer.length();i++)
        {
            str[0][i]=grammer[i];
        } 
        for(int h=grammer.length();h<80;h++)
        {
                str[0][h]=NULL;
        }
        result = strtok(str[0],ch);  
        while(result!=NULL)  
        {  
            strN1.push_back(result);  
            result = strtok(NULL,ch);  
        }  
        for(int i=1;grammer!="#";i++)
        {
            cin>>grammer;
            strN.push_back(grammer); 
            /*处理转换的规则形式输入部分*/
            for(int h=0;h<grammer.length();h++)
            {
                str[i][h]=grammer[h];
            } 
            for(int h=grammer.length();h<80;h++)
            {
                str[i][h]=NULL;
            }
            result = strtok(str[i],ch);  
            while(result!=NULL)  
            {  
                strN1.push_back(result);  
                result = strtok(NULL,ch);  
            }  
        } 
        /*
        获取firstTerm集合 
        */
        //直接获取firstTerm
        for(unsigned i=0;i<strN.size();i++)
        {
            gram[i].a=strN[i][0];
            gram[i].first="";
            if(!Norterminal(strN[i][4]))
            {
                gram[i].first=strN[i][4];
            }
            else
            {
                if(!Norterminal(strN[i][5]))
                {
                    gram[i].first=strN[i][5];
                }
            }
            for(unsigned k=5;k<strN[i].length();k++)
            {
                if(strN[i][k]=='|')
                {
    
                    if(!Norterminal(strN[i][k+1]))
                    {
    
                        gram[i].first+=strN[i][k+1];
                    }
                    else
                    {
                        if(!Norterminal(strN[i][k+2]))
                        {
                            gram[i].first+=strN[i][k+2];
                        }
                    }
                }
            } 
    
        } 
        int num=strN1.size();
        //当第一个字符是非终结符时 
        for(int i=num-1;i>=0;i--)
        {
            for(unsigned l=0;l<strN.size()-1;l++)
            {
                if(gram[l].a[0]==strN1[i][0])
                {
                        for(unsigned h=0;h<strN.size()-1;h++)
                        {
                            if(strN1[i][4]==gram[h].a[0]&&strN1[i][4]!=strN1[i][0])
                            {
    
                                gram[l].first+=gram[h].first; 
                                string ustr(gram[l].first);
                                sort(ustr.begin(), ustr.end());
                                ustr.erase(unique(ustr.begin(), ustr.end()), ustr.end() );
                                gram[l].first=ustr; 
                                break;
                            }       
                        }
                }
            }        
    
        }
        cout<<"firstTerm集合为:"<<endl;
        for(unsigned i=0;i<strN.size()-1;i++)
        {
            for(int k=0;k<gram[i].first.length();k++)
            {
                if(gram[i].first[k]==NULL)
                {
                    gram[i].first.erase(gram[i].first.begin()+k);
                }
            }
            cout<<gram[i].a<<" "<<gram[i].first<<endl;
        }
        string term="";
        cout<<"终结符为:"<<endl;
        for(unsigned i=0;i<strN.size()-1;i++)
        {
            for(int j=0;j<strN[i].length();j++)
            {
                if(!Norterminal(strN[i][j])&&strN[i][j]!='$')
                   term+=strN[i][j];
            }
            string ustr(term);
            sort(ustr.begin(), ustr.end());
            ustr.erase(unique(ustr.begin(), ustr.end()), ustr.end() );
            term=ustr;
        }
        cout<<term<<endl;
        /*转换规则形式*/
        cout<<"转换后的规则形式为:"<<endl; 
        int listnumber =0; 
        for(unsigned i=0;i<strN1.size()-1&&i-1>=0;i++)
        {
    
            if(strN1[i].find("::")==-1)
            {
                string add="";
                add=add+strN1[i-1][0]+"::="+strN1[i];
                strN1[i]=add;
    
            }   
            cout<<strN1[i]<<endl;
        }
        /*获取lastTerm*/
        //直接获取lastTerm
        for(int i=0;i<num-1;i++)
        {
            for(unsigned l=0;l<strN.size()-1;l++)
            {
                    if(gram[l].a[0]==strN1[i][0])
                    {
                            for(unsigned h=0;h<strN.size()-1;h++)
                            {
                                int k=strN1[i].length();
                                if(!Norterminal(strN1[i][k-1]))
                                {
    
                                    gram[l].follow+=strN1[i][k-1]; 
                                    string ustr(gram[l].follow);
                                    sort(ustr.begin(), ustr.end());
                                    ustr.erase(unique(ustr.begin(), ustr.end()), ustr.end() );
                                    gram[l].follow=ustr;    
                                    break;
                                }
                                else
                                {
                                    if(!Norterminal(strN1[i][k-2]))
                                    {
                                        gram[l].follow+=strN1[i][k-2]; 
                                        string ustr(gram[l].follow);
                                        sort(ustr.begin(), ustr.end());
                                        ustr.erase(unique(ustr.begin(), ustr.end()), ustr.end() );
                                        gram[l].follow=ustr;    
                                        break;
                                    }
                                }       
                            }
                    }
            }        
       }
       for(int i=num-1;i>=0;i--)
       {
            for(unsigned l=0;l<strN.size()-1;l++)
            {
                if(gram[l].a[0]==strN1[i][0])
                {
                        for(unsigned h=0;h<strN.size()-1;h++)
                        {
                                int k=strN1[i].length();
                                if(Norterminal(strN1[i][k-1]))
                                {
    
                                     for(unsigned h1=0;h1<strN.size()-1;h1++)
                                     if(gram[h1].a[0]==strN1[i][k-1])
                                     {
                                            gram[l].follow+=gram[h1].follow; 
                                            string ustr(gram[l].follow);
                                            sort(ustr.begin(), ustr.end());
                                            ustr.erase(unique(ustr.begin(), ustr.end()), ustr.end() );
                                            gram[l].follow=ustr;    
                                            break;
                                     }
    
                                }
                        }   
                }
            }        
    
        }
        cout<<"lastTerm集合为:"<<endl; 
        for(unsigned i=0;i<strN.size()-1;i++)
        {
            cout<<gram[i].a<<" "<<gram[i].follow<<endl;
        } 
        int list[term.length()][term.length()]; 
        for(int i=0;i<term.length();i++)
        {
            for(int j=0;j<term.length();j++)
            {
                list[i][j]=0;
            }
        }
        cout<<"相等的关系为:"<<endl; 
       for(int i=num-1;i>=0;i--)
       {
            for(int k=0;k<strN1[i].length()&&k+1<strN1[i].length();k++)
            {
                if(Norterminal(strN1[i][k]))
                {
                    if(!Norterminal(strN1[i][k-1])&&!Norterminal(strN1[i][k+1]))
                    {
                        cout<<strN1[i][k-1]<<strN1[i][k+1]<<endl;;
                        for(int h=0;h<term.length();h++)
                        {
                            if(strN1[i][k-1]==term[h])
                            for(int g=0;g<term.length();g++)
                            {
                                if(strN1[i][k+1]==term[g])
                                {
                                    list[h][g]=1;
                                }
                            }
                        }
                    }
                }
                else
                {
                    if(!Norterminal(strN1[i][k+1]))
                    {
                        cout<<strN1[i][k]<<strN1[i][k+1]<<endl;
                        for(int h=0;h<term.length();h++)
                        {
                            if(strN1[i][k]==term[h])
                            for(int g=0;g<term.length();g++)
                            {
                                if(strN1[i][k+1]==term[g])
                                {
                                    list[h][g]=1;
                                }
                            }
                        }
                    }
                }
            }   
       } 
       //cout<<"小于关系为:"<<endl;
       for(int i=0;i<num-1;i++)
       {
            for(int k=0;k<strN1[i].length();k++)
            {
                if(!Norterminal(strN1[i][k]))
                {
                    if(Norterminal(strN1[i][k+1]))
                    {
                        for(int h=0;h<term.length();h++)
                        {
                            if(strN1[i][k]==term[h])
                            {
                                for(int j=0;j<num-1;j++)
                                {
                                    if(strN1[i][k+1]==gram[j].a[0])
                                    {
                                        for(int g=0;g<term.length();g++)
                                        {
                                            for(int f=0;f<gram[j].first.length();f++)
                                            if(gram[j].first[f]==term[g])
                                            {
                                                list[h][g]=2;
                                            }
                                        }
                                    }
                                }
                            }
                        }
    
                    }
                }
            }
    
    
       } 
       //大于关系    
       for(int i=0;i<num-1;i++)
       {
            for(int k=0;k<strN1[i].length();k++)
            {
                if(Norterminal(strN1[i][k]))
                {
                    if(!Norterminal(strN1[i][k+1]))
                    {
                        for(int h=0;h<term.length();h++)
                        {
                            if(strN1[i][k+1]==term[h])
                                for(int j=0;j<num-1;j++)
                                {
                                    if(strN1[i][k]==gram[j].a[0])
                                    {
                                        for(int g=0;g<term.length();g++)
                                        {
                                            for(int f=0;f<gram[j].first.length();f++)
                                            if(gram[j].follow[f]==term[g])
                                            {
                                                list[g][h]=3;
                                            }
                                        }
                                    }
                                }
                        }
    
                    }
                }
            }
       } 
       for(int i=0;i<term.length();i++)
        {
            for(int j=0;j<term.length();j++)
            {
                cout<<list[i][j]<<" ";
            }
            cout<<endl;
        }
    
        cout<<"算符优先矩阵为:"<<endl;
        cout<<"    |";
        for(int i=0;i<term.length();i++)
        {
            cout<<setw(10)<<term[i];
            cout<<"|";
        }
        cout<<endl; 
        cout<<"____________________________________________________________________________"<<endl;
    
        for(int i=0;i<term.length();i++)
        {
            printf("%2c",term[i]);
            cout<<"  "<<"|";
            for(int j=0;j<term.length();j++)
            {
                if(list[i][j]==0)
                cout<<setw(10)<<" "<<"|";
                if(list[i][j]==1)
                cout<<setw(10)<<"="<<"|";
                if(list[i][j]==2)
                cout<<setw(10)<<"<"<<"|";
                if(list[i][j]==3)
                cout<<setw(10)<<">"<<"|";
    
            }
            cout<<endl;
            cout<<"____________________________________________________________________________"<<endl;
    
        }
    
    } 

    运行结果如下:
    这里写图片描述

    展开全文
  • //⑥求解算符优先矩阵 System.out.println("算符优先关系矩阵"); System.out.println("-------------------------------------------------------------------"); System.out.print("\t"); for(int i=0;i;i++){...
    /**共有三个类**①主类Op.java*②处理算法的关键类GetFL.java*③读取信息类ReadInfo.java从TXT文件中读取文法**
    /*
     * author:Ack訾
     * Date:15/11/2012
     * Attention:
     */
    package com.algorithm;
    import java.io.IOException;
    import java.util.ArrayList;
    import java.util.Scanner;
    public class OP {
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args)throws IOException {
    		String fileName="H:\\大三实验课\\编译原理\\实验3\\input.txt";
    		ReadInfo ri=new ReadInfo();
            String[][] ll = ri.gettext(fileName);
            GetFL fl=new GetFL(ll);
          //①读取的文法放在ll[][]二维数组中,可根据下面的注释语句进行打印
            System.out.println(" 文法G"+"["+ll[0][0]+"]"+":");
            System.out.println(" "+ll[0][0]+"'"+"->"+"#"+ll[0][0]+"#");
            for(int i=0;i<ll[0].length;i++){
            	 System.out.print(" "+ll[0][i]);
            	 System.out.print("->");
        	     System.out.println(ll[1][i]);
            } 
            System.out.println(" ");
          //②终结符放在NT[]中(not terminate)可通过下面注释语句进行打印
            String[]NT = fl.getNT();
             System.out.print(" 非终结符集:");System.out.print("{");
             for(int i=0;i<NT.length;i++){
             	//if(NT[i]=="\\'"){System.out.print("亲!咱解决不了含有“‘”的文法");}
             	if(NT.length-1==i)
             		System.out.print(NT[i]);
             	else
                 System.out.print(NT[i]+",");
                 }
             System.out.println("}");
             
           //③终结符放在T[]中(teminate) 可通过下面注释语句进行打印
           String[]T = fl.getT();
           System.out.print(" 终结符集:");System.out.print("{");
            for(int i=0;i<T.length;i++){
         	   if(T.length-1 ==i)
         		   System.out.print(T[i]);
         	   else
            System.out.print(T[i]+",");   
            }
            System.out.println("}");
            System.out.println(" ");
            
            
            //④FIRSTVT求解过程
            String[][] FirstVT = fl.getFirstVT();
            System.out.println(" FIRSTVT集:");
            System.out.println(" LASTVT("+FirstVT[0][0]+"'"+")"+"="+"{"+"#"+"}");
            for(int i=0;i<FirstVT[0].length;i++){
            	 System.out.print(" FIRSTVT("+FirstVT[0][i]+")"+"="+"{");
            	 //System.out.println(FirstVT[1][i]);
            	//if(NT[i]=="\\'"){System.out.print("亲!咱解决不了含有“‘”的文法");}
            	 char[] ch=FirstVT[1][i].toCharArray();
          	   for(int j=0;j<ch.length;j++){
          		   if(ch.length-1 ==j)
          			   System.out.print(ch[j]);
          		   else System.out.print(ch[j]+",");
          	   }
              System.out.println("}");
            }
            System.out.println(" ");
            //⑤LASTVT求解过程
            String[][] LastVT = fl.getLastVT();
            
            System.out.println(" LASTVT集:");
            System.out.println(" LASTVT("+LastVT[0][0]+"'"+")"+"="+"{"+"#"+"}");
            for(int i=0;i<LastVT[0].length;i++){
            	 System.out.print(" LASTVT("+LastVT[0][i]+")"+"="+"{");
            	 //System.out.println(FirstVT[1][i]);
            	//if(NT[i]=="\\'"){System.out.print("亲!咱解决不了含有“‘”的文法");}
            	 char[] ch=LastVT[1][i].toCharArray();
          	   for(int j=0;j<ch.length;j++){
          		   if(ch.length-1 ==j)
          			   System.out.print(ch[j]);
          		   else System.out.print(ch[j]+",");
          	   }
              System.out.println("}");
            }
            System.out.println();
          //⑥求解算符优先矩阵
            System.out.println("算符优先关系矩阵");
            System.out.println("-------------------------------------------------------------------");
            System.out.print("\t");
               for(int i=0;i<T.length;i++){
            	System.out.print(T[i]+"\t");
            	}
               System.out.println();
               System.out.println("-------------------------------------------------------------------");
    
            String[][] Op=fl.getMatrix();
            for(int i=0;i<Op[0].length;i++){
            	System.out.print(" "+T[i]);
            	for(int j=0;j<Op[0].length;j++){
                	System.out.print("\t"+Op[i][j]);
                }
            	System.out.println();
                System.out.println("-------------------------------------------------------------------");
            }
            if(fl.isOP==false)System.out.print("此文发非算符优先文法");
            //⑦分析句子
            Scanner sc=new Scanner(System.in);
            String sentence =sc.next();
            char[] ch=sentence.toCharArray();
            //s用于存放读入的语句
            ArrayList<String>  s=new ArrayList<String>();
            for(int i=0;i<ch.length;i++){
         	   s.add(String.valueOf(ch[i]));
            }
            //判断输入的符号串是否是本文法的终结符
            boolean isExisted=true;
            String NotExist="";
            String stringT="";
            for(int i=0;i<T.length;i++){
            	stringT=stringT.concat(T[i]);
            }
        
        		   for(int i=0;i<ch.length;i++){
        			   if(!stringT.contains(String.valueOf(ch[i])))
        			   { if(ch[i]!='#')
        				   {isExisted=false;
        				   NotExist= String.valueOf(ch[i]);
        				   }
        			   }
        	       }
        
           // s.add("#");
            //System.out.print(s.toString());
            //stack用于存放分析栈
        	if(isExisted==false){
        		System.out.print(NotExist+"不是此文法的的终极符");
        	}
        	else{
            ArrayList<String>  stack=new ArrayList<String>();
            stack.add("#");
            String temp =s.remove(0);
            ArrayList<String>  sentence_result=new ArrayList<String>();
            String s_result=new String();
            s_result=s_result.concat(stack+"\t"+temp+"\t"+s+"\t");
           boolean isSuccess=false;
           boolean isFailed=false;
            for(int k=0;k<ch.length;k++){
         	  for(int i=0;i<T.length;i++){
         	   if(T[i].equals(stack.get(stack.size()-1))){
         		   for(int j=0;j<T.length;j++){
         			   if(T[j].equals(temp)){
         				   if(Op[i][j].equals("<")){
         					  s_result=s_result.concat("移近"); sentence_result.add(s_result);s_result="";
         					  stack.add(temp);temp=s.remove(0);
         					  s_result=s_result.concat(stack+"\t"+temp+"\t"+s+" \t");
         					 
         				   }
         				   else if(Op[i][j].equals(">")){
         					  s_result=s_result.concat("规约"); sentence_result.add(s_result);s_result="";
         					  if(stack.size()>1)
         					  stack.remove(stack.get(stack.size()-1));
         					  s_result=s_result.concat(stack+"\t"+temp+"\t"+s+"\t");
         				   }
         				   else if(stack.get(stack.size()-1)=="#"&&isSuccess==false){
         					  s_result=s_result.concat("分析成功");isSuccess=true; sentence_result.add(s_result);
         				   }
         				   else if(isSuccess!=true&&isFailed==false){
         					  s_result=s_result.concat("分析失败");isFailed=true; sentence_result.add(s_result);
         				   }
         			   }
         		   }
         	   }
         	   
          } 
    	}
          
      //  System.out.print(sentence_result.size());
            for(int i=0;i<sentence_result.size();i++){
         	   System.out.print("("+(i+1)+")");
         	   System.out.print("\t");
         	   System.out.println(sentence_result.get(i));
            }
        	}
            
    	}
    
    }
    
    
    //**关键类GetFL.java**/
    package com.algorithm;
    
    import java.util.HashMap;
    
    public class GetFL {
       public String [][]str;
    	static String FIRSRVTstring="";
    	static String LASTVTstring="";
    	  boolean isOP=true;
    	//static String Tstringselect="";
    	//构造函数对象进行初始化
    	GetFL(String[][] ll){
    		str=ll;
    	}
    	//①求FIRSTVT
    	String [][] getFirstVT(){
    		String[][] FirstVT = new String[2][str[0].length];
    			for(int i=0;i<str[0].length;i++){
    			FirstVT[0][i]=str[0][i];
    			getFVT(str[0][i],str[1][i]);
    			FirstVT[1][i]=FIRSRVTstring;
    			FIRSRVTstring="";
    		}
    		return FirstVT;
    	}
    	//获取非终结符放到NT数组中
    		String[] getNT(){
    		//String [][] Follow=getFollow();
    			String[] NT=new String[str[0].length];
    			for(int i=0;i<str[0].length;i++){
    				NT[i]=str[0][i];
    			}
    			return NT;
    		}
    	//获取终结符  放到T数组中
    	String[] getT(){
    		String[] NT1 = getNT();
    		String temp=new String();
    		for(int i=0;i<str[1].length;i++){
    			temp=temp+str[1][i];
    		}
    		for(int i=0;i<NT1.length;i++){
    			temp=temp.replaceAll(NT1[i],"");
    		}
    		temp=temp.replaceAll("\\|","");
    		temp=temp.replaceAll("\\'","");
    		//System.out.println(temp);
    		char[] ch=new char[temp.length()];
    		ch=temp.toCharArray();
    		
    		String resultString = new String();
    		for(int i=0;i<ch.length;i++){
    			if(!resultString.contains(String.valueOf(ch[i])))
    					resultString=resultString.concat(String.valueOf(ch[i]));
    		}
    		//System.out.println(resultString);
    		String[] T=new String[resultString.length()+1];
    		T[resultString.length()]="#";
    		for(int i=0;i<resultString.length();i++){
    		T[i]=(String)String.valueOf(resultString.charAt(i));
    		//System.out.println(T[i]);
    		}
    		return T;
    	}
    	//递归
    	void getFVT(String str3 ,String str4){
    		String[] s =null;
    		if(str4.contains("|")){
    			 s=str4.split("\\|");
    		 for(int j=0;j<s.length;j++){
    			getFVT(str3,s[j]);
    		  }
    		}
    		 else{
    	//1	//*str4的长度为1
    		 if(str4.length()==1){//*str4的长度为1且为终结符的时候直接加入
    			 if(!('A'<=str4.charAt(0)&&str4.charAt(0)<='Z')){
    				 if(!FIRSRVTstring.contains(String.valueOf(str4.charAt(0))))
    				FIRSRVTstring=FIRSRVTstring.concat(String.valueOf(str4.charAt(0)));
    			 }
    	//2	//*str4的长度为1且为非终结符,此时应查找其str[2][]中str[0][i]为str4的右边表达式getFVT(str[1][i])
    			 else{      
    					for(int i=0;i<str[0].length;i++){
    					   if(str[0][i].equals(String.valueOf(str4.charAt(0)))){
    						if(!str3.equals(String.valueOf(str4.charAt(0))))
    						getFVT(str[0][i],str[1][i]);
    					   }
    					}
    				}
    		 }
    	//3	//*str4的长度大于2
    		if(str4.length()>=2){
    			//①第一个为终结符时
    			  if(!('A'<=str4.charAt(0)&&str4.charAt(0)<='Z')){
    				  if(!FIRSRVTstring.contains(String.valueOf(str4.charAt(0))))
    					FIRSRVTstring=FIRSRVTstring.concat(String.valueOf(str4.charAt(0)));
    				}
    			//②第一个非终结符且第二个为终结符
    			  if('A'<=str4.charAt(0)&&str4.charAt(0)<='Z'&&!('A'<=str4.charAt(1)&&str4.charAt(1)<='Z')){
    				  //先加入这个终结符号
    				  if(!FIRSRVTstring.contains(String.valueOf(str4.charAt(1))))
    				  FIRSRVTstring=FIRSRVTstring.concat(String.valueOf(str4.charAt(1)));
    			      //再循环查找这个非终极符的情况
    				//**找到第一个为终结符
    				   for(int i=0;i<str[0].length;i++){
    					   //if条件用于消除自身进行循环
    						if(str[0][i].equals(String.valueOf(str4.charAt(0))))//&&!str[0][i].equals(String.valueOf(str[1][i].charAt(0))))
    							if(!str3.equals(String.valueOf(str4.charAt(0))))
    							getFVT(str[0][i],str[1][i]);
    						}
    			  }
    			//③第一个非终结符且第二个也为非终结符
    			  if('A'<=str4.charAt(0)&&str4.charAt(0)<='Z'&&'A'<=str4.charAt(1)&&str4.charAt(1)<='Z'){
    				  for(int i=0;i<str[0].length;i++){
    					   //if条件用于消除自身进行循环
    						if(str[0][i].equals(String.valueOf(str4.charAt(0))))//&&!str[0][i].equals(String.valueOf(str[1][i].charAt(0))))
    							if(!str3.equals(String.valueOf(str4.charAt(0))))
    							getFVT(str[0][i],str[1][i]);
    						if(str[0][i].equals(String.valueOf(str4.charAt(1))))//&&!str[0][i].equals(String.valueOf(str[1][i].charAt(0))))
    							if(!str3.equals(String.valueOf(str4.charAt(1))))
    							getFVT(str[0][i],str[1][i]);
    					
    						}
    				        
    				   //**第二个也为非终结符
    				  // if('A'<=str4.charAt(0)&&str4.charAt(1)<='Z'){//第二个也非终结符
    					/*
    					   for(int i=0;i<str[0].length;i++){
    							if(	str[0][i].equals(str4))
    								getFVT(str[0][i],str[1][i]);
    							}*/
    				//   }
    
    				 /*  else{
    					   FIRSRVTstring=FIRSRVTstring.concat(String.valueOf(str4.charAt(1)));
    				       	}*/
    				   }
    		   }  
    	   }
      }
    	
    	//②求LASTVT
    	String [][] getLastVT(){
    		String[][] LastVT = new String[2][str[0].length];
    			for(int i=0;i<str[0].length;i++){
    			LastVT[0][i]=str[0][i];
    			getLVT(str[0][i],str[1][i]);
    			LastVT[1][i]=LASTVTstring;
    			LASTVTstring="";
    		}
    		return LastVT;
    	}
    	//递归
    	private void getLVT(String string1, String string2) {
    		String[] s=null;
    		if(string2.contains("|")){
    			 s=string2.split("\\|");
    		  for(int j=0;j<s.length;j++){
    			getLVT(string1,s[j]);
    		  }
    		}
    		else{
    		//1	   //*string2的长度为1
    			 if(string2.length()==1){//*string2的长度为1且为终结符的时候直接加入
    				 if(!('A'<=string2.charAt(0)&&string2.charAt(0)<='Z')){
    					 if(!LASTVTstring.contains(String.valueOf(string2.charAt(string2.length()-1))))
    						 LASTVTstring=LASTVTstring.concat(String.valueOf(string2.charAt(string2.length()-1)));
    				 }
    		//2	  //*string2的长度为1且为非终结符,此时应查找其str[2][]中str[0][i]为string2的右边表达式getLVT(str[1][i])
    				 else{      
    						for(int i=0;i<str[0].length;i++){
    						   if(str[0][i].equals(String.valueOf(string2.charAt(string2.length()-1)))){
    							if(!string1.equals(String.valueOf(string2.charAt(string2.length()-1))))
    							getLVT(str[0][i],str[1][i]);
    						   }
    						}
    					}
    			 }
    		//3   //*string2的长度大2	 
    	if(string2.length()>=2){
    			//①当string2最后一个为终结符时
    			if(!('A'<=string2.charAt(string2.length()-1) && string2.charAt(string2.length()-1)<='Z')){
    				if(!LASTVTstring.contains(String.valueOf(string2.charAt(string2.length()-1))))
    					LASTVTstring=LASTVTstring.concat(String.valueOf(string2.charAt(string2.length()-1)));
    			}
    			
    			//②当string2倒数第二个为终结符时且最后一个为非终结符时
    			if(('A'<=string2.charAt(string2.length()-1) && string2.charAt(string2.length()-1)<='Z')&&(!('A'<=string2.charAt(string2.length()-2) && string2.charAt(string2.length()-2)<='Z'))){	
    		        //将终结符加入
    				if(!LASTVTstring.contains(String.valueOf(string2.charAt(string2.length()-2))))
    					LASTVTstring=LASTVTstring.concat(String.valueOf(string2.charAt(string2.length()-2)));
    				//循环中后一个非终结符加入
    				 for(int i=0;i<str[0].length;i++){
    					   //if条件用于消除自身进行循环
    						if(str[0][i].equals(String.valueOf(string2.charAt(string2.length()-1))))//&&!str[0][i].equals(String.valueOf(str[1][i].charAt(0))))
    							if(!string1.equals(String.valueOf(string2.charAt(string2.length()-1))))
    							getLVT(str[0][i],str[1][i]);
    						}
    			}
    			③当string2倒数第二个为终结符时且最后一个也为终结符时
    			 if(('A'<=string2.charAt(string2.length()-1) && string2.charAt(string2.length()-1)<='Z')&&('A'<=string2.charAt(string2.length()-2) && string2.charAt(string2.length()-2)<='Z')){
    				  for(int i=0;i<str[0].length;i++){
    					   //if条件用于消除自身进行循环
    						if(str[0][i].equals(String.valueOf(string2.charAt(string2.length()-1))))//&&!str[0][i].equals(String.valueOf(str[1][i].charAt(0))))
    							if(!string1.equals(String.valueOf(string2.charAt(string2.length()-1))))
    							getLVT(str[0][i],str[1][i]);
    						if(str[0][i].equals(String.valueOf(string2.charAt(string2.length()-2))))//&&!str[0][i].equals(String.valueOf(str[1][i].charAt(0))))
    							if(!string1.equals(String.valueOf(string2.charAt(string2.length()-2))))
    							getLVT(str[0][i],str[1][i]);
    						}
    			    }
    			}
    		}	
    	}
        //③求各终结符的算符优先关系
    	//利用二维矩阵来存放算符优先关系-1表示无关系,0表示相等关系,1表示小于关系,2表示大于关系
    	//先找到形如A—>…a…和A->…aBb…  相等关系 放入equal[][]数组中
    	//再找到形如A->…aB…       小于关系   放入lessthan[][]数组中
    	//最后找到形如A->…Bb…    大于关系   放入 morethan[][]数组中
    	//将以上封装到函数中返回二维数组放到int型op_matrix中
    	String[][] getMatrix(){
    		 String[][] LastVT = getLastVT();
    		 String[][] FirstVT = getFirstVT();
    		 String[] T=getT();
    		String[][] op_matrix=new String[T.length][T.length];
    		//先找到形如A—>…ab…和A->…aBb…  相等关系 放入equal[][]数组中
    		HashMap<String,String> equal= new HashMap<String,String>();
    		equal.put("#","#");
    		for(int i=0;i<str[0].length;i++){
    			if(str[1][i].length()==2){
    				for(int j=0;j<str[1][i].length()-1;j++){
    					if(!('A'<=str[1][i].charAt(j)&&str[1][i].charAt(j)<'Z')&&(str[1][i].charAt(j)!='|'&&str[1][i].charAt(j+1)!='|')&&!('A'<=str[1][i].charAt(j+1)&&str[1][i].charAt(j+1)<'Z')){
    						equal.put(String.valueOf(str[1][i].charAt(j)),String.valueOf(str[1][i].charAt(j+1)));
    					}	
    				}
    			}
    			if(str[1][i].length()>=3){
    				for(int j=0;j<str[1][i].length()-2;j++){
    					if((str[1][i].charAt(j+2)!='|'&&str[1][i].charAt(j+1)!='|'&&str[1][i].charAt(j)!='|')&&!('A'<=str[1][i].charAt(j+2)&&str[1][i].charAt(j+2)<'Z')&&!('A'<=str[1][i].charAt(j)&&str[1][i].charAt(j)<'Z')&&('A'<=str[1][i].charAt(j+1)&&str[1][i].charAt(j+1)<'Z')){
    						equal.put(String.valueOf(str[1][i].charAt(j)),String.valueOf(str[1][i].charAt(j+2)));
    					}	
    				}
    			}
    		 }
    		//再找到形如A->…aB…       小于关系   放入lessthan<String><String> HashTable中
    		HashMap<String,String> lessthan= new HashMap<String,String>();
    		lessthan.put("#",FirstVT[1][0]);
    		for(int i=0;i<str[0].length;i++){
    			if(str[1][i].length()>=2){
    				for(int j=0;j<str[1][i].length()-1;j++){
    				if(!('A'<=str[1][i].charAt(j)&&str[1][i].charAt(j)<='Z')&&str[1][i].charAt(j)!='|'&&('A'<=str[1][i].charAt(j+1)&&str[1][i].charAt(j+1)<='Z')){
    					for(int k=0;k<str[1].length;k++){
    						if(str[0][k].equals(String.valueOf(str[1][i].charAt(j+1))))
    					      lessthan.put(String.valueOf(str[1][i].charAt(j)),FirstVT[1][k]);
    					}
    				}
    			}
    		 }
    		}
    		//最后找到形如A->…Bb…    大于关系   放入 morethan[][]数组中
    		HashMap<String,String> morethan= new HashMap<String,String>();
    		morethan.put("#",LastVT[1][0]);
    		for(int i=0;i<str[0].length;i++){
    			if(str[1][i].length()>=2){
    				for(int j=0;j<str[1][i].length()-1;j++){
    				if(('A'<=str[1][i].charAt(j)&&str[1][i].charAt(j)<='Z')&&!('A'<=str[1][i].charAt(j+1)&&str[1][i].charAt(j+1)<='Z')&&str[1][i].charAt(j+1)!='|'){
    					for(int k=0;k<str[1].length;k++){
    						if(str[0][k].equals(String.valueOf(str[1][i].charAt(j))))
    					      morethan.put(String.valueOf(str[1][i].charAt(j+1)),LastVT[1][k]);
    					}
    				}
    			}
    		 }
    		}//将morethan转化为数组more中便于以下操作
    		  Object[] str=morethan.keySet().toArray();
    		  Object[] str1=morethan.values().toArray();
    		  String[][] more=new String[2][morethan.size()];
    		  for(int i=0;i<str.length;i++){
    			  more[0][i]=str[i].toString();
    			  more[1][i]=str1[i].toString();
    		  }
    		//给二维数组赋初值-1,尚未发生关系
    		for(int i=0;i<T.length;i++){
    			for(int j=0;j<T.length;j++){
    				op_matrix[i][j]="\f";
    			}
    		}
    		//进行逻辑赋值
    		
    		for(int i=0;i<T.length;i++){
    		          //查找eaual中两个相等关系符号在T中的位置
    			
    			  //  for(int k=0;k<equal.size();k++){
    				  if(equal.containsKey(T[i])){
    					  for(int j=0;j<T.length;j++){
    				      if(equal.get(T[i]).contains(T[j]))
    				    	  if (op_matrix[i][j]!=">"&&op_matrix[i][j]!="<")
    				    	  op_matrix[i][j]="=";
    				    	  else isOP=false;
    			         }	
    			    }	
    		
    				//查找lessthan中两个小于关系符号在T中的位置
    			 
    			    //for(int k=0;k<lessthan.size();k++){
    					  if(lessthan.containsKey(T[i])){
    						  for(int j=0;j<T.length;j++){
    					      if(lessthan.get(T[i]).contains(T[j]))
    					    	  if (op_matrix[i][j]!=">"&&op_matrix[i][j]!="=")
    					    	  op_matrix[i][j]="<";
    					    	  else isOP=false;
    				        }	
    					  }
    				  // }	
    			 
    				//查找morethan中两个小于关系符号在T中的位置
    		
    			 for(int k=0;k<more[0].length;k++){
    					String temp=more[1][k];
    						  if(temp.contains(T[i])){
    							  for(int j=0;j<T.length;j++){
    						        if(more[0][k].contains(T[j]))
    						        	if (op_matrix[i][j]!="<"&&op_matrix[i][j]!="=")
    						    	    op_matrix[i][j]=">";
    						        	else isOP=false;
    					         }	
    					      }	
    						}
    					  
    		}
    		//返回二维数组
    		//System.out.print(equal.toString());
    		//System.out.print(lessthan.toString());
    		//System.out.print(morethan.toString());
    		return op_matrix;
    	}
    	
         //④对句子进行分析
    	
    	
    }
    *****读取信息类ReadInfo.java****
    
    package com.algorithm;
    import java.io.BufferedReader;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.ArrayList;
    class ReadInfo{
    	//读取input.txt文件中的内容
    	String[][] gettext(String str) throws IOException{
    		FileReader fr=new FileReader(str);
    		BufferedReader br=new BufferedReader(fr);
    		String temp;
    		ArrayList<String> list =new ArrayList<String>();
    		while((temp=br.readLine())!=null){
    			list.add(temp);
    		}
    		br.close();
    		String arr[]=new String[list.size()];
    		String arrNT[]=new String[list.size()];//非终结符数组
    		String arrT[]=new String[list.size()];//终结符号数组
    		for(int i=0;i<list.size();i++){
    			
    			arr[i]=(String) list.get(i);
    			//System.out.println(arr[i]);
    		}
    		for(int i=0;i<arr.length;i++){
    			String[] temp1;
    			temp1=arr[i].split("->");
    			arrNT[i]=temp1[0];
    			arrT[i]=temp1[1];
    		}
    		String[][] ll=new String[2][list.size()];
    		for(int i=0;i<list.size();i++){
    			ll[0][i]=arrNT[i];
    			ll[1][i]=arrT[i];
    		}
    		return ll;
    	}
    }
    展开全文
  • java实现算符优先文法ll1文法

    千次阅读 2019-06-04 21:22:27
    实验要求: 1.[实验项目] 实现LL(1)分析中控制程序(表驱动程序);完成以下描述赋值语句的LL(1)文法的LL(1...(1)构造该算符优先文法的优先关系矩阵或优先函数; (2)输入串应是词法分析的输出二元式序列,即某算...

    实验要求:

    1.[实验项目]

    实现LL(1)分析中控制程序(表驱动程序);完成以下描述赋值语句的LL(1)文法的LL(1)分析过程。

    G[E]:

    E →E+T∣E-T∣T

    T→T*F∣T/F∣F

    F→(E)∣i

    2.[设计说明]

    终结符号i 为用户定义的简单变量,即标识符的定义。

    3.[设计要求]

    (1)构造该算符优先文法的优先关系矩阵或优先函数;

    (2)输入串应是词法分析的输出二元式序列,即某算术表达式“专题
    1”的输出结果。输出为输入串是否为该文法定义的算术表达式的判断结果。

    (3)算符优先分析过程应能发现输入串出错。

    (4)设计两个测试用例(尽可能完备,正确和出错),并给出测试结果;

    (5)考虑编写程序根据算符优先文法构造算符优先关系矩阵,并添加到你的算符优先分析程序中。

    实验过程:

    1、算符优先分析程序设计说明

    1.1设计要求:

    (1)构造该算符优先文法的优先关系矩阵或优先函数;

    (2)输入串应是词法分析的输出二元式序列,即某算术表达式“专题
    1”的输出结果。输出为输入串是否为该文法定义的算术表达式的判断结果。

    (3)算符优先分析过程应能发现输入串出错。

    (4)设计两个测试用例(尽可能完备,正确和出错),并给出测试结果;

    (5)考虑编写程序根据算符优先文法构造算符优先关系矩阵,并添加到你的算符优先分析程序中。

    1.2设计说明:

    (1)该语言大小写不敏感;

    (2)字母为a-zA-Z,数字为0-9;

    (3)对文法进行扩充和改造;

    (4)根据FIRSTVT集和LASTVE集的构造规则,构造出文法的FIRSTVT集和LASTVT集

    (5)根据FIRSTVT集和LASTVT集构造算符优先矩阵;

    (6)根据分析规则,构造算符优先矩阵分析器。

    3、程序功能描述

    (1)、能够录入一个.tys文件中的二元式内容;二元式内容为表达式

    (2)、根据.tys文件内容进行算符优先分析,可识别

    (3)、根据输入的二元式内容进行分析语法分析,并打印结果;

    (4)、打印分析过程(分析栈和保留串)和错误提示;

    (5)、根据文法构造FIRSTVT集和LASTVT集;

    (6)、根据构造FIRSTVT集和LASTVT集,构造出算符优先矩阵分析表;

    (7)、算符优先矩阵分析器。

    4、主要的数据结构描述

    4.1主要使用的java数据结构类型
    4.1.1 List

    //终结符号集

    private List<Character> Vt = new ArrayList<Character>();

    //非终结符号集

    private List<Character> Vn = new ArrayList<Character>();

    使用List保存文法的非终结符号和终结符号,一旦文法给定,非终结符号集合和终结符号集合也就确定,所以对Vt、Vn的操作一般是查找元素和遍历元素。

    List添加元素

    //设置非终结符号

    Vn.add(‘S’);

    Vn.add(‘E’);

    Vn.add(‘T’);

    Vn.add(‘F’);

    //设置终结符号

    Vt.add(’#’);

    Vt.add(’+’);

    Vt.add(’-’);

    Vt.add(’*’);

    Vt.add(’/’);

    Vt.add(’(’);

    Vt.add(’)’);

    Vt.add(‘i’);

    使用add()方法即可添加元素,上面的程序保存了Vt、Vn集合。

    list中是否包含某个元素

    方法:.contains(Object o); 返回true或者false

    例如下面在程序中使用到的:

    Vn.contains(nArryStr[i].charAt(0))&&Vt.contains(nArryStr[i].charAt(1))

    list获取长度:

    Vt.size()

    使用size()即可返回List的长度

    list中查看(判断)元素的索引

    注意:.indexOf(); 和 lastIndexOf()的不同;

    List<String> names=new ArrayList<>();

    names.add(“刘备”); //索引为0

    names.add(“关羽”); //索引为1

    names.add(“张飞”); //索引为2

    names.add(“刘备”); //索引为3

    names.add(“张飞”); //索引为4

    System.out.println(names.indexOf(“刘备”));

    System.out.println(names.lastIndexOf(“刘备”));

    System.out.println(names.indexOf(“张飞”));

    System.out.println(names.lastIndexOf(“张飞”));

    根据元素索引位置进行的判断
    if (names.indexOf("刘备")==0) {
        System.out.println("刘备在这里");
    }else if (names.lastIndexOf("刘备")==3) {
        System.out.println("刘备在那里");
    }else {
        System.out.println("刘备到底在哪里?");
    }
    
    

    在程序中使用OPGtable[Vt.indexOf(Vt1)][Vt.indexOf(Vt2)]

    判断list是否为空

    //空则返回true,非空则返回false

    
    if (person.isEmpty()) {
        System.out.println("空的");
    }else {
        System.out.println("不是空的");
    }
    
    
    4.1.2 Map
    HashMap

    最常用的Map,它根据键的HashCode
    值存储数据,根据键可以直接获取它的值,具有很快的访问速度。HashMap最多只允许一条记录的键为Null(多条会覆盖);允许多条记录的值为
    Null。非同步的。

    常用API
    clear()从 Map 中删除所有映射
    remove(Object key)从 Map 中删除键和关联的值
    put(Object key, Object value)将指定值与指定键相关联
    putAll(Map t)将指定 Map 中的所有映射复制到此 map
    entrySet()返回 Map 中所包含映射的 Set 视图。Set 中的每个元素都是一个 Map.Entry 对象,可以使用 getKey() 和 getValue() 方法(还有一个 setValue() 方法)访问后者的键元素和值元素
    keySet()返回 Map 中所包含键的 Set 视图。删除 Set 中的元素还将删除 Map 中相应的映射(键和值)
    values()返回 map 中所包含值的 Collection 视图。删除 Collection 中的元素还将删除 Map 中相应的映射(键和值)
    get(Object key)返回与指定键关联的值
    containsKey(Object key)如果 Map 包含指定键的映射,则返回 true
    containsValue(Object value)如果此 Map 将一个或多个键映射到指定值,则返回 true
    isEmpty()如果 Map 不包含键-值映射,则返回 true
    size()返回 Map 中的键-值映射的数目

    在程序中使用了MAP:

    //文法

    private Map<String, String> grammar = new HashMap<String, String>();

    //FIRSTVT集

    private Map<Character,Set<Character>> FIRSTVT = new
    HashMap<Character,Set<Character>>();

    //LASTVT集

    private Map<Character,Set<Character>> LASTVT = new
    HashMap<Character,Set<Character>>();

    使用map保存文法,和FIRSTVT,LASTVT。

    Map添加元素

    grammar.put(“S”, “#E#”);

    grammar.put(“E”, “E+T|E-T|T”);

    grammar.put(“T”, “T*F|T/F|F”);

    grammar.put(“F”, “(E)|i”);

    上面程序将题目要求的文法保存到map对象grammar中

    Map的遍历
    
    		grammar.forEach((k,v)->{
    			String []nArryStr = v.split("\\|");
    			for(int i=0 ;i<nArryStr.length;i++)
    				
    			{
    				//System.out.println(nArryStr[i]);
    				if(Vt.contains(nArryStr[i].charAt(0)))
    				{
    					char b= nArryStr[i].charAt(0);
    					FIRSTVT.get(k.charAt(0)).add(b);
    				}
    				if(nArryStr[i].length()>=2)
    				if(Vn.contains(nArryStr[i].charAt(0))&&Vt.contains(nArryStr[i].charAt(1)))
    				{
    					char b=nArryStr[i].charAt(1);
    					FIRSTVT.get(k.charAt(0)).add(b);
    				}
    			}
    			
    			
    		});
    
    

    使用forEach方法,参数(k,v)

    其中k为每个values的索引值,通过forEach的方法,遍历map的所有元素,就返回每个元素的key和values,并赋给参数(k,v)。

    Map获取元素

    Map获取元素一般根据key值获取对应的values:

    例如:

    LASTVT.get(k.charAt(0))

    结果返回的是,key对应的values,而且values是声明map时设置的类型对应,

    比如:

    private Map<Character,Set<Character>> LASTVT = new
    HashMap<Character,Set<Character>>();

    key的类型为Character

    values的类型为Set<Character>

    所以通过LASTVT.get(key)获得values时,得到类型为Set<Character>。

    4.2 二元式文件结构

    二元式文件通过专题1的词法分析程序得到:

    其中一个测试用例为:

    (1,a)
    (4,+)
    (1,b)
    (10,*)
    (3,()
    (1,c)
    (5,-)
    (2,34)
    (3,))
    (11,/)
    (1,num5)

    二元式文件内容被录入到

    br = new BufferedReader(new InputStreamReader(new FileInputStream(fp.getName())));
    			String erYuanShi = "";
    			while((erYuanShi=br.readLine())!=null) {
    				//截取符号串
    				String substr=erYuanShi.substring(erYuanShi.indexOf("(") + 1, erYuanShi.lastIndexOf(","));
    				if(substr.equals("1")||substr.equals("2"))
    				{		
    					s+="i";
    				}
    				else 
    				{
    					s+=erYuanShi.substring(erYuanShi.indexOf(",") + 1, erYuanShi.lastIndexOf(")"));
    				}
    
    			}
    
    

    二元式文件的录入和专题2一样,InputStream是一个Java
    List列表的一个对象,list列表是一系列的String类型的字符串,具体的操作:

    br = new BufferedReader(new InputStreamReader(new FileInputStream(fp.getName())));
    			String erYuanShi = "";
    			while((erYuanShi=br.readLine())!=null) {
    				//截取符号串
    				InputStream.add(erYuanShi.substring(erYuanShi.indexOf(",") + 1, erYuanShi.lastIndexOf(")")));
    			}
    			InputStream.add("#");  //末尾添加#号
    
    

    br为一个文件的读入流,通过使用br.readLine()方法读入二元式文件当前行内容并返回给String类型的变量erYuanShi,然后每一行的内容类似为(1,num1)的形式,但是我们需要就是num1,所以通过erYuanShi.substring(erYuanShi.indexOf(",")+ 1,
    erYuanShi.lastIndexOf(")"))方法将num1截取下来,放入List列表对象中,继续读文件,直到读取结束。这样就将二元式文件的内容读取到了字符串s中。1
    和2表示标识符和数字在符号表中的序号,也即1表示当前二元式的实际内容为标识符,2表示为数字,所以如果是标识符和数字时,就将内容转换为i保存到s中。

    最后得到字符串s类似为: i+i*(i-i)/i

    但是实际算术表达式为:a+a*(b-c)/2。

    也就是将用户定义的标识符和数字都转为i。

    4.5 FIRSTVT 集

    private Map<Character,Set<Character>> FIRSTVT = new HashMap<Character,Set<Character>>();

    根据构造规则:

    U∈Vn

    FIRSTVT(U)=

    {b∣U=+>b…, 或U =+> Vb…, b∈Vt,V∈Vn }

    则形如W→…aU…的规则 a < b

    b ∈ FIRSTVT(U)

    在这里插入图片描述

    编写代码:

    //遍历文法。进行非终结符号的FIRSTVT的初始化
    		grammar.forEach((k,v)->{
    			String []nArryStr = v.split("\\|");
    			for(int i=0 ;i<nArryStr.length;i++)
    				
    			{
    				//System.out.println(nArryStr[i]);
    				if(Vt.contains(nArryStr[i].charAt(0)))
    				{
    					char b= nArryStr[i].charAt(0);
    					FIRSTVT.get(k.charAt(0)).add(b);
    				}
    				if(nArryStr[i].length()>=2)
    				if(Vn.contains(nArryStr[i].charAt(0))&&Vt.contains(nArryStr[i].charAt(1)))
    				{
    					char b=nArryStr[i].charAt(1);
    					FIRSTVT.get(k.charAt(0)).add(b);
    				}
    			}
    			
    			
    		});
    		
    		do 
    		{
    			FIRSTVTAllNochange=1;
    			grammar.forEach((k,v)->{
    				String []nArryStr = v.split("\\|");
    				for(int i=0 ;i<nArryStr.length;i++)
    					
    				{
    					char U=k.charAt(0);
    					char V=nArryStr[i].charAt(0);
    					if(Vn.contains(U)&&U!=V&&Vn.contains(V))
    					{
    						
    							FIRSTVT.get(V).forEach(values->{
    								if(!FIRSTVT.get(U).contains(values))
    								{
    								//	System.out.println(values);
    								 FIRSTVT.get(U).add(values);
    								 FIRSTVTAllNochange = 0;
    								}
    							
    							});
    							
    						
    					}
    					
    				}
    				
    				
    			});
    			if(FIRSTVTAllNochange==1)
    				break;
    		}while(true);
    
    

    获得FIRSTVT集:

    S:[#]
    T:[(, i, *, /]
    E:[(, i, *, +, -, /]
    F:[(, i]

    4.6 LASTVT 集

    //LASTVT集 private Map<Character,Set<Character>> LASTVT = new
    HashMap<Character,Set<Character>>();

    LASTVT构造规则:

    U∈Vn

    LASTVT(U)=

    {a∣U=+>…a, 或U =+>…aV, a∈Vt, V ∈Vn }

    则形如W→…Ub…的规则 a > b

    a ∈LASTVT(U)

    编写代码:

    //遍历文法。进行非终结符号的LASTVT的初始化
    		grammar.forEach((k,v)->{
    			String []nArryStr = v.split("\\|");
    			for(int i=0 ;i<nArryStr.length;i++)
    				
    			{
    				//System.out.println(nArryStr[i]);
    				int len= nArryStr[i].length();
    				if(Vt.contains(nArryStr[i].charAt(len-1)))
    				{
    					char b= nArryStr[i].charAt(len-1);
    					LASTVT.get(k.charAt(0)).add(b);
    				}
    				if(nArryStr[i].length()>=2)
    				if(Vt.contains(nArryStr[i].charAt(len-2))&&Vn.contains(nArryStr[i].charAt(len-1)))
    				{
    					char b=nArryStr[i].charAt(len-2);
    					LASTVT.get(k.charAt(0)).add(b);
    				}
    			}
    			
    			
    		});
    		
    		do 
    		{
    			FIRSTVTAllNochange=1;
    			grammar.forEach((k,v)->{
    				String []nArryStr = v.split("\\|");
    				for(int i=0 ;i<nArryStr.length;i++)
    					
    				{
    					int len =nArryStr[i].length();
    					char U=k.charAt(0);
    					char V=nArryStr[i].charAt(len-1);
    					if(Vn.contains(U)&&U!=V&&Vn.contains(V))
    					{
    						
    						LASTVT.get(V).forEach(values->{
    								if(!LASTVT.get(U).contains(values))
    								{
    									//System.out.println(values);
    									LASTVT.get(U).add(values);
    								 FIRSTVTAllNochange = 0;
    								}
    							
    							});
    							
    						
    					}
    					
    				}
    				
    				
    			});
    			if(FIRSTVTAllNochange==1)
    				break;
    		}while(true);
    
    

    最后得到LASTVT集:

    S:[#]

    T:[), i, *, /]

    E:[), i, *, +, -, /]

    F:[), i]

    4.7 算符优先矩阵

    /算符优先权关系表
    /**
    * 在OPGtable中,用-1,0,1,2表示优先权关系
    * 0 表示优先关系等于
    * 1 表示优先关系小于
    * 2 表示优先关系大于
    * -1 表示不存在优先权关系
    * *
    */
    private int [][]OPGtable = new int [N][N];

    在这里插入图片描述

    构造规则:

    编写代码:

    /**
    		 * 在OPGtable中,用-1,0,1,2表示优先权关系
    		 * 0 表示优先关系等于
    		 * 1 表示优先关系小于
    		 * 2 表示优先关系大于
    		 * -1 表示不存在优先权关系
    		 * *
    		 */
    		grammar.forEach((k,v)->{
    			String []nArryStr = v.split("\\|");
    			
    			for(int i=0 ;i<nArryStr.length;i++)			
    			{		
    				String ruleRight=nArryStr[i];
    				int  len = ruleRight.length();
    				if(len>=2)
    				{
    					for(int i1= 0 ;i1<len-1 ;i1++)
    					{
    						char X1=ruleRight.charAt(i1);
    						char X2=ruleRight.charAt(i1+1);
    						
    						if(Vt.contains(X1)&&Vt.contains(X2))				
    							OPGtable[Vt.indexOf(X1)][Vt.indexOf(X2)]=0;//0 表示优先关系等于
    						if(Vt.contains(X1)&&Vn.contains(X2))
    						{
    							FIRSTVT.get(X2).forEach(values->{
    								OPGtable[Vt.indexOf(X1)][Vt.indexOf(values)]=1;//1 表示优先关系小于
    							});
    						}
    						if(Vn.contains(X1)&&Vt.contains(X2))				
    						{
    							LASTVT.get(X1).forEach(values->{
    								OPGtable[Vt.indexOf(values)][Vt.indexOf(X2)]=2;//2 表示优先关系大于
    							});
    						}
    						if(len>=3&&i1<len-2)
    						{
    							char X3=ruleRight.charAt(i1+2);
    							if(Vt.contains(X1)&&Vn.contains(X2)&&Vt.contains(X3))
    							{	
    								OPGtable[Vt.indexOf(X1)][Vt.indexOf(X3)]=0; //0 表示优先关系等于
    							}
    						}
    							
    							
    					}
    					
    				}
    				
    			}
    			
    			
    		});
    
    

    最终的算符优先矩阵:

    在这里插入图片描述

    5、程序结构描述

    5.1Java 主类:OPGMain

    在这里插入图片描述

    5.1.1全局变量
    变量类型变量名称变量作用
    private List<Character>Vt保存终结符号集,需要手动设置
    Private List<Character>Vn保存非终结符号集。需要手动设置
    private Map<Character, String>grammar保存文法,需要手动设置
    private Map<Character,Set<Character>>FIRSTVT保存非终结符号的FIRSTVT集,由函数生成内容
    private Map<Character,Set<Character>>LASTVT保存非终结符号的LASTVT集,有相应的生成函数生成其内容
    private Map<String,Set<Character>>OPGtable//算符优先权关系矩阵 /** * 在OPGtable中,用-1,0,1,2表示优先权关系 * 0 表示优先关系等于 * 1 表示优先关系小于 * 2 表示优先关系大于 * -1 表示不存在优先权关系 * * */
    5.1.2函数
    类型返回值函数名功能
    publicOPGMain构造函数,初始化文法,Vt和Vn
    publicvoidCreate_FIRSTVT构造FIRSTVT集
    publicvoidCreate_LASTVT输出LASTVT集
    publicvoidCreate_OPGTable构造算符优先关系矩阵
    publicvoidOPGanalysis算符优先文法分析器
    publicintget_PriorityRelationship获得两个终结符号的优先关系
    publicstatic voidmain类的主函数,实例化主类,并传入中间文件。
    ./media/image5.png

    5.1.3函数调用关系图
    在这里插入图片描述

    绿色虚线为调用

    6、程序测试

    6.1 正确用例

    测试用例为二元式文件结构部分的用例

    (1,a)
    (4,+)
    (1,b)
    (10,*)
    (3,()
    (1,c)
    (5,-)
    (2,34)
    (3,))
    (11,/)
    (1,num5)

    结果为:

    在这里插入图片描述

    在这里插入图片描述

    6.2 错误用例

    通过修改测试用例1使其不符合赋值语句语法:

    6.2.1缺少操作符

    在这里插入图片描述

    6.2.2缺少 ‘)’符号

    在这里插入图片描述
    源代码:https://github.com/Topdu/Compilation-principle/tree/master/16281002-杜永坤-专题4

    展开全文
  • 算符优先算法中优先函数的构造

    千次阅读 2020-11-04 10:29:09
    算符优先分析中“优先函数的简单构造!”


            这里我介绍的是一种简单的方法,不是书本的那个方法。是我后面那个参考资料上面的作者想出来的。因为这个是在知网上面找到的,是1997年的一篇文章。我就是一个总结,然后画几个比较清楚的图而已(因为从知网上下载的的pdf上面的图有点不太清楚)

    优先函数树形构造法

            我们教材上面的就是陈火旺老师的那本,然后方法就是找节点。这个方法虽然简单,但是操作起来的却有些麻烦,因为我们作图的时候,难免就会看不清楚,或者数错。下面介绍的树形构造法就可以避免这个问题,仅仅只需要根据优先矩阵就可以得出正确结果。

    操作步骤

    对于一个优先表先做如下几个步骤(假设优先函数存在)
    1 ) 对于f(a)对应行中“a>=b 的所有终结符b , 把g(b)作为f(a) 的子树。
    2) 对g(a) 对应列中有b <=a 的. 把f(a) 作为g(b)的子树.
    3 ) 对f(a)重做第( 1 ) 步, 对g(b) 重做第( 2 ) 步。
    4) 重复出现的f或g , 作记号不再对其执行第( 1) , ( 2) 步
    方向图
    5) 构造f(a)函数时, 以f(a) 为根结点, 按( 1 ) ,(2 ),( 3),( 4) 执行.
    6) 构造g(b)函数时, 以g(b) 为根结点, 按(2 ) ,( 1 ) , ( 3 ) , ( 4 ) 执行.
    按照以上5步先画出树,然后查树的节点数(包括根节点,做记号的不查),即可以得到根节点的优先函数值。
    但是我觉得这个操作步骤2有点问题。应该是b>=a的时候,就把f(a)作为g(b)的子树。我也自己做了实验,发现这样做才是正确的。不过也可能是我没有理解原作者的意思。反正,就目前看来,我都是按照如果b<=a,就把f(a)作为g(b)的子树。
    所以,下面我举例的例子,第(2)步都是按照“b>=a的时候,就把f(a)作为g(b)的子树”这个来做的。

    举例操作

            假如现有一个优先矩阵是这样的:这个例子是《编译原理》陈火旺老师(下面我说的教材,没有特别说明也是指的这本教材)那本书上面的。在90页。
    在这里插入图片描述
    那么我们现在用树形构造法来试试怎么得到这个优先函数。因为最后的答案是去掉了 i 和 # 之后得到的,所以我下面也将不会考虑 i 和 # 号。至于为什么不考虑 i 和 #,,就是因为这两个不是算符,我们算符优先函数主要针对的就是算符直接的优先级。但是优先关系矩阵中是给出了 i 和 # 与其他算符之间的优先关系的。我这里其实是有一个疑问的:因为在优先函数这里没有 i 的优先关系,那么在使用优先函数来分析一个句子是不是这个文法定义的合法的句子的时候,那么什么时候该移进这个 i 呢?希望知道的小伙伴可以在下面留言,我们讨论一下。

            计算f(+)的优先函数值。

    1. 从优先矩阵中可以得到:’+‘ >= 的算符有;’+’,’)’,’#'三个。因为不考虑i 和 #(下面就不提醒这一点了),所以f(+)的孩子节点有两个,分别是g(+)和g()),如下图所示。
      在这里插入图片描述
    2. 现在就来找g(’+’) 的子树。我这里还是采用的是如果b>=a,就把f(a)作为g(b)的子树。从优先表中可以看到的就是’+‘ >= 的算符有:’(’。注意,我这里说的’+‘是g(’+‘),也就是从’+‘那一列中寻找。在这里插入图片描述
      所以,g(’+’)的子树就是f(’(’);在这里插入图片描述
    3. 然后找到g(’)’) >=的算符:在这里插入图片描述
      但是f(’(’)已经出现过了(作为g(’+’)子树出现的),所以就不用画出来了。
    4. 然后就是寻找f(’(’) >=的算符。在这里插入图片描述但是g(’)’)也已经出现过了,所以这里也不用画出来了。
    5. 最后每一个节点我们都已经检查过了,没有可以重新添加的了。也就是趋于稳定了(编译原理里面好多都是这样子的,得使所有都不再变化的时候,算法就算结束了)。我们数一下节点的个数,就是4个,和书本95页给出的答案是一样的。

            同理,g(’+’)的树也可以这样画出来。我就给出最后的树,就不一一分析了。
    在这里插入图片描述

    自己的思考

            本质上书本上的画图和这里的画一颗树,都是优先级高的指向优先级低的,所以入度为0的节点,给的优先函数值应大一点,出度为0的,给出的优先函数值应该小一点。

            上面提到的这个简单的方法其本质善和我们教材上的方法是一样的。你可以将教材上的方法中的图给截取一部分出来。例如,你截取以g(’+’)作为顶点的树去看,发现就是和我上面画的一样。

            还有注意的一点就是:我们求出一组优先函数之后,就可以构造出无数组优先函数。所以,如果你求出来的和参考答案给出的不是一样的,也不一定是你错了。只要你的优先函数之间的关系和参考答案上给出的关系是一样的就可以了。

    参考资料

    构造优先函数的更简单方法_树型构造_潘群娜
    这个知网上我找到的一篇关于这个优先函数构造比较简单的方法,如果大家对上面的博客解释的不太清楚的话,可以去知网上看这个原作者写的文章。

    展开全文
  • 算符优先算法

    2016-10-24 11:32:03
  • 编译原理:算符优先分析法

    千次阅读 2020-05-28 08:22:45
    编译原理:算符优先分析文法
  • 2)采用由定义构造算符优先关系集合并构造矩阵 由以上公式,先得到对应的FIRSTVT与LASTVT集合,再依次遍历文法找到所需的…aV…或者…Vb…产生式,与FIRSTVT(V)或者LASTVT(V)卡氏积,得到>,<,=的算符优先...
  • 编译原理之算符优先分析

    千次阅读 2019-06-20 11:57:29
    文章目录一. 什么是算符文法?... 算符优先分析法最左规约串的确定1. 最左素短语的定义是什么?2. 最左素短语的特征?如何根据其特征确定当前句型的最左可归约串?3. 什么是“单非产生式”,算符优...
  • 检查语法错误,从文件中输入文法,出错语法错误到文件中,对算符优先文法适用
  • 编译原理 算符优先

    2016-03-20 15:54:06
    编译原理 课程设计实验---算符优先,情景分析和算法实现
  • 算符优先过程的模拟 输入一个文法可以的出相应的移进规约表
  • 算符优先分析算法及其代码实现

    千次阅读 2020-11-06 23:01:52
    算符优先分析的步骤 构造优先关系矩阵(通过FIRSTVT和LASTVT集构造) 构造一个输入串(要在两边加上#)和一个符号栈 当栈内首个终结符的优先级或=栈外终结符的优先级时,移进;当栈内首个终结符的优先级>栈外终结...
  • 这是一个用c++语言实现的编译原理里面实现算符优先分析法的程序,包括创建FIRSTVT,LASTVT,和分析表。
  • 算符优先分析法-思路方法在这里

    千次阅读 多人点赞 2020-05-16 20:48:28
    3.构造并输出算符优先分析表,判断是否为算符优先文法,若不是提示无法进行分析; 4.任意输入一个输入串,可得到成功的分析或错误的提示,输出其分析过程或打印语法 分析树。 实验运行结果 算符优先文法的特点: ...
  • (1)构造该算符优先文法的优先关系矩阵 (2)对给定的表达式,能够检查有无语法错误,并指出出错位置。 (3)将语法分析过程输出。 5.实验步骤 (1)根据文法构造算符优先关系表。 (2)编写总控程序实现语法分析。 (3)...
  • 自底向上分析之算符优先分析法 说明:以老师PPT为标准,借鉴部分教材内容,AlvinZH学习笔记。 基本过程 1. 一般方法:采用自左向右地扫描和分析输入串,从输入符号串开始,通过反复查找当前句型的句柄(最左简单短语...
  • 算符优先文法分析

    2013-03-14 00:40:37
    对用户自定义的文法进行算符优先的分析,友好的人际交互界面,计算FIRStVT和LASTVT,并且对一段输入进行分析
  • 算符优先语法分析程序

    热门讨论 2012-07-07 21:27:39
    (1)构造该算符优先文法的优先关系矩阵或优先函数; (2)输入串应是词法分析的输出二元式序列,即某算术表达式“实验项目一”的输出结果。输出为输入串是否为该文法定义的算术表达式的判断结果。 (3)算符优先...
  • 编译原理之算符优先分析语法程序

    千次阅读 2016-11-07 10:39:58
    https://github.com/Ggmatch/The-principle-to-compile体验算法优先分析法能达到的效果算符优先分析法只考虑算符(广义为终结符)之间的优先关系,例如若有文法G为: (1)E->E+E (2)E->E*E (3)E->
  • 输入算符优先文法,输出FIRSTVT、LASTVT、算符优先关系表 对输入串,输出分析过程
  • 算符优先分析法-java实现

    千次阅读 多人点赞 2019-12-03 17:50:33
    算符优先分析器-java实现 一、判断是否是算符文法 算符文法定义:一个文法,如果它的任一产生式的右部都不含两个相继(并列)的非终结符,即不含如下形式的产生式右部:…QR…,则称该文法为算符文法 二、求Firstvt和...
  • 算符优先分析法(构造算法优先关系表) 算法描述 算符优先关系主要用于界定右句型的句柄: 标记句柄的左端; =出现在句柄的内部; >标记句柄的右端。 发现句柄的过程: 从左端开始扫描串,直到遇到第一个>为止。...
  • 算符优先分析

    2021-03-09 19:07:14
    1. 已知算符优先关系矩阵如下表:+*i()#+><<<>>*>><<>>i>>>>(<<<<=)>>>>#<<<<=写出符号串(i+i)*i#的算符优先分析过程。2.接...
  • 算符优先法之优先表构造

    千次阅读 2019-07-02 11:27:00
    算符优先分析不是一种规范规约法,但是该方法特别有利于表达式分析,宜于手工实现。 算符优先分析法和计算的过程相同,由此判断一个符号的左右符号优先级,从而确定是否可以规约。 对于任何两个可能相继出现的终结...
  • 算符优先文法

    千次阅读 2020-11-28 16:40:58
    算符优先文法概述自底向上分析优先关系算符文法算符优先文法构造算符优先表的算法确定算符优先关系构造集合FIRSTVT(P)FIRSTVT(P)FIRSTVT(P)的算法构造集合LASTVT(P)LASTVT(P)LASTVT(P)的算法构造算符优先表实例算符...
  • 如果是自动生成并打印输出其算符优先矩阵; 5) 模拟分析过程。 如输入一个句子,如果该句子合法则输出与句子 对应的语法树;能够输出分析过程中每一步符号 栈的变化情况以及根据当前最左素短语进行归约 的过程...
  • 算符优先分析法中,文法终结符之间的优先关系是用优先矩阵表示的,这样需要占用大量的内存空间,当文法有n个终结符时,就需要(n+1)^2个内存单元,因此,在实际实现中使用优先函数来代替优先矩阵表示优先关系。...
  • (1)根据给定文法,先求出FirstVt和LastVt集合,构造算符优先关系表(要求算符优先关系表 输出到显示器或者输出到文件); (2)根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式(要求输出...
  • 内含代码片段。原理包括算符优先的三种优先关系定义与判断方法,FIRSTVT集和LASTVT集的构造步骤;判断算符关系,构造算符优先关系矩阵的说明;根据矩阵分析句子合法性的步骤说明;实验结果包含输入与输出

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 654
精华内容 261
关键字:

算符优先矩阵