main.java

这是一个模拟编译器词法分析的程序。输入正则表达式

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package regular;

import java.util.*;
//import java.util.Collection;
//import java.util.Scanner;
//import java.util.Collections;
//import java.util.HashSet;
/**
 *
 * @author Administrator
 */
public class Main {

    /**
     * @param args the command line arguments
     */
  
    public static void main(String[] args) {
        
        System.out.println("输入正则表达式");
        Scanner s=new Scanner(System.in);
        String str=s.next();
        System.out.println("输入待判定的字符串：");
        String ss=s.next();
        //Set<String> Cstring=new HashSet<String>();
       /* while(s.hasNext()){
            String ss=s.next();
            Cstring.add(ss);
        }*/
            
         Set<Character> Cset= new HashSet<Character>();
       a: for(int i=0;i<str.length();i++){
            char c=str.charAt(i);
            if(c=='('||c=='|'||c==')'||c=='*')
        		continue a;
            else
                Cset.add(Character.valueOf(c));
        }
      
       int max=100;
            node []ArrayNode=new node[max];
        for(int i=0;i<max;i++)
          ArrayNode[i]=null;              
       Main main=new Main();
       main.initial(ArrayNode,str);
       int num=1;
          main.table(ArrayNode,0, num);
     Set<Integer>NumSet=new HashSet<Integer>();
     NumSet.add(Integer.valueOf(0));
     boolean b=false;
    a: do{//求初始状态的等价状态集合
        b=false;
       c:for(Integer in:NumSet)
         for(node n:ArrayNode){
           if(n==null)
               continue c;
           else if(n.start==in.intValue()&&n.str.equals(" "))
           {  
              NumSet.add(Integer.valueOf(n.end));//如果添加新状态，要重新遍历集合，查找等价状态
              b=true;            
           }
         }
       }while(b);
     
     Map< NewMap ,Set<Integer>> Tmap=new HashMap< NewMap ,Set<Integer>>();
     //记录等价状态集合映射关系
     main.DFA(ArrayNode, Cset, NumSet, Tmap);
     Map<NewIMap,Integer>NTmap=new HashMap<NewIMap,Integer>();
     //记录重命名后的映射关系
     main.Nname(Tmap, NTmap);
     main.token(ss, NTmap);
    }
  void initial(node[]Array,String str){
      Array[0]=new node(0,str,1);
  }
   class node{
      public int start;//初状态
       public String str;//输入字符串
       public int end;//末状态
       node(int a,String b,int c){
           //构造函数
          start=a;
           str=b;
           end=c;
           
       }
       node(){};
   }
   void table(node[]Array,int i,int num){
   //参数是状态数组，待处理的数组元素位置，和现有的状态个数；
   //采用递归处理
	   String str=Array[i].str;
       if(str.length()==1)    
       	   return;     
       if(str.charAt(0)=='(')//字符串的开始字符是“（”
       {
    	 int count=1;
         int j=1;
    	   for(j=1;j<str.length();j++)
    	   {
           // 判定最外层的右括号的位置

    		   if(str.charAt(j)=='(')
    			   count++;
    		   if(str.charAt(j) == ')')
    			   count--;
    		   if(count==0)
    		     break;
    	   }
    	   if(j==str.length()-1)
    	   {
    		  //最外层是括号，去掉括号再调函数处理括号内的字符串
               String temp=str.substring(1,str.length()-1);
    		   Array[i].str=temp;
    		   table(Array,i,num);
    	   }
    	   else{
    		   j++;
    		   if(str.charAt(j)=='*'&&j==str.length()-1)
    	   {
    		 //有闭包，去掉括号和闭包，增加两个空字符的状态
             String temp=str.substring(1, str.length()-2);
    		 int s=Array[i].start;
    		 int e=Array[i].end;
    		 Array[i]=new node(s," ",num+1);
    		 num++;
    		 Array[num-1]=new node(num,temp,num);
    		 Array[num]=new node(num," ",e);
    		 num++;
    		 table(Array,num-2,num);

    		 
    	   }
    	   else if(str.charAt(j)=='*'&&str.charAt(j+1)=='|')
    	   {
    		 //前半部分是闭包，或运算，增加一个输入串不同、起止状态相同的状态
             String temp=str.substring(0, j+1);
      		 int s=Array[i].start;
      		 int e=Array[i].end;
      		 
      		 
      		 Array[i]=new node(s,temp,e);
      		 temp=str.substring(j+2,str.length());
      		 Array[num]=new node(s,temp,e);
      		 num++;
      		
      		 table(Array,i,num); 
      		 table(Array,num-1,num);
    	   }
           else if(str.charAt(j)=='*')
           {
             //前半部分是闭包，无 或运算 ，增加一个新状态
             String temp=str.substring(0, j+1);
      		 int s=Array[i].start;
      		 int e=Array[i].end;
      		
      		 Array[i]=new node(s,temp,num+1);
      		 temp=str.substring(j+1,str.length());
      		 Array[num]=new node(num+1,temp,e);
      		 num++;

      		 table(Array,i,num);
      		 table(Array,num-1,num);

           }
           else if(str.charAt(j)=='|')
           {
              //前半部分在括号里，或运算，增加一个输入串不同、起止状态相同的状态
             String temp=str.substring(0, j);
      		 int s=Array[i].start;
      		 int e=Array[i].end;
      		 
      		 Array[i]=new node(s,temp,e);
      		 temp=str.substring(j+1,str.length());
      		 Array[num]=new node(s,temp,e);
      		 num++;

      		 table(Array,i,num);
      		 table(Array,num-1,num);
           }
           else
           {
             //前半部分在括号中，无 或运算，增加一个新状态
             String temp=str.substring(0, j);
      		 int s=Array[i].start;
      		 int e=Array[i].end;
      		 
      		 Array[i]=new node(s,temp,num+1);
      		 temp=str.substring(j,str.length());
      		 Array[num]=new node(num+1,temp,e);
      		 num++;

      		 table(Array,i,num);
      		 table(Array,num-1,num);
           }
       }
       }
       //开始字符不是括号
       else{
    	  	 int s=Array[i].start;
    		 int e=Array[i].end;
    		 char c=str.charAt(0);
    		String temp=String.valueOf(c);

     		
    	  if(str.charAt(1)=='|') //紧跟其后的是运算符|，增加一个输入串不同、起止状态相同的状态
    	  { 
              Array[i]=new node(s,temp,e);
    		temp=str.substring(2,str.length());
    		Array[num]=new node(s,temp,e);
    		num++;
    		table(Array,num-1,num);
    	  }
    	  else
    	  {   //增加新状态
      		 Array[i]=new node(s,temp,num+1);
            temp=str.substring(1,str.length());
      		Array[num]=new node(num+1,temp,e);
      		num++;
      		table(Array,num-1,num);
    	  }
        }
   }
   class NewMap{
      Set<Integer> NSet;//等价状态集合
      char c;//输入字符
      NewMap(Set<Integer> s,char ch){
          NSet=new HashSet<Integer>();
          NSet.addAll(s);
          c=ch;
      }
  }
  void DFA(node[]Array ,Set<Character> CSet,Set<Integer>NumSet,Map< NewMap ,Set<Integer>> Tmap  )
  {
     //将NFA转化为DFA，输入为NFA状态数组Array，输入串的字符集合 CSet，待处理的状态集合NumSet
      //输出为状态映射表Tmap
     f: for(Character ch:CSet){//针对每一个输入字符
         for(Iterator it=Tmap.entrySet().iterator();it.hasNext();)
      {
         //遍历TMap，如果Imap中有当前集合NumSet和ch的映射结果，则跳入下一个循环，查找集合NumSet
         //与下一个字符的映射结果
          Map.Entry<NewMap,Set<Integer>> entry = (Map.Entry<NewMap,Set<Integer>>) it.next();
          if(entry.getKey().NSet.containsAll(NumSet)&&NumSet.containsAll(entry.getKey().NSet) &&entry.getKey().c==ch.charValue())
           continue f;
      }
          char ctemp=ch.charValue();
        NewMap NMtemp=new NewMap(NumSet,ctemp);
        Set<Integer> NSet=new HashSet<Integer>();//记录转化后的状态集合
        String Stemp=String.valueOf(ctemp);
      a:for(Integer i:NumSet)
      {//针对状态集合的每一个状态，查找相应的转化后状态
          int temp=i.intValue();//当前状态
          for(node ntemp:Array)
          {
              if(ntemp==null)
                  continue a;
              else if(ntemp.start == temp && ntemp.str.equals(Stemp))
                 NSet.add(Integer.valueOf(ntemp.end));//将找到的状态加入到新集合中
          }
          
      }
      boolean b=false;
      do{//向集合中增加等价状态
          b=false;
     a: for(Integer i:NSet)
           for(node ntemp:Array)
          {
               if(ntemp==null)
                 continue a;
               else if(ntemp.start==i.intValue()&&ntemp.str.equals(" ")){
                   if(NSet.contains(Integer.valueOf(ntemp.end)))
                       continue a;
                   else {
                      NSet.add(Integer.valueOf(ntemp.end));
                          b=true;
                   }
              }
          }
       }while(b);
      if(NSet.isEmpty());
      else if(NumSet.containsAll(NSet)&&NSet.containsAll(NumSet)){
           Tmap.put(NMtemp, NSet);
          
      }         
      else
      {
          Tmap.put(NMtemp, NSet);
          DFA(Array ,CSet,NSet,Tmap);
      }
    }   
  }
  class NewIMap{
      Integer k;
      char v;
      NewIMap(Integer i,char j){
          k=new Integer(i.intValue());
          v=j;
      }

  }
  void Nname(Map< NewMap ,Set<Integer> > Tmap,Map<NewIMap,Integer>NTmap){
    //重命名，简化状态映射表  
//输入为原始状态映射表Tmap，输出为简化的映射表NTmap
      Map<Integer,Set<Integer>> tNTmap=new HashMap<Integer,Set<Integer>>();
      //简化后的状态和原状态集合的映射关系表
      Set<Set<Integer>>tSet=new HashSet<Set<Integer>>();
      //原始状态集合的集合
      
      for(Iterator it=Tmap.entrySet().iterator();it.hasNext();)
      {
         //遍历TMap，找出所有状态集合，存储在tSet中 
      
          Map.Entry<NewMap,Set<Integer>> entry = (Map.Entry<NewMap,Set<Integer>>) it.next();
         
           Set<Integer>ttSet=new HashSet<Integer>();
           ttSet.addAll(entry.getKey().NSet);
           tSet.add(ttSet);
      }
     boolean f=false;
     a:do{
         f=false;
         for(Set<Integer>ttSet:tSet){
        if(ttSet.contains(Integer.valueOf(0)))//查找包含初始状态的集合，作为新的初始状态
        {
            Set<Integer> sSet=new HashSet<Integer>();
            sSet.addAll(ttSet);             
            tNTmap.put(Integer.valueOf(0), sSet);//加入到新老状态映射表中
            tSet.remove(ttSet);
            f=true;
            continue a;
            
          }
        else if(ttSet.contains(Integer.valueOf(1))){//查找包含终状态的集合，作为新的终状态。
            Set<Integer> sSet=new HashSet<Integer>();
            sSet.addAll(ttSet);           
           for(Iterator it=tNTmap.entrySet().iterator();it.hasNext();)
          {
             //包含终状态的集合也可能有多个，如果当前的集合ttSet在映射表中能找到包含它的集合，则直接
               //从集合sSet中移除该集合；如果当前的集合ttSet在映射表中能找到它的一个子集合，则替换其子集合；
               //如果当前的集合ttSet在映射表中没有与之有上述关系的集合，则直接加到映射表中。
             Map.Entry<Integer,Set<Integer>> entry = (Map.Entry<Integer,Set<Integer>>) it.next();         
              if(entry.getValue().containsAll(sSet)){
                  tSet.remove(ttSet);
                  f=true;
                  continue a;
              }
              else if(sSet.containsAll(entry.getValue()))
              {               
                  entry.setValue(sSet);
                  tSet.remove(ttSet);
                  f=true;
                  continue a;
              }             
        }     
             tNTmap.put(Integer.valueOf(1), sSet);
             tSet.remove(ttSet);
             f=true;
             continue a;
        }         
      }
     }while(f);
    int count=2;
    b:do{
        f=false;
        for(Set<Integer>ttSet:tSet){//针对每一个状态集合，添加新的映射关系
        Set<Integer> sSet=new HashSet<Integer>();
        sSet.addAll(ttSet);     
        for(Iterator it=tNTmap.entrySet().iterator();it.hasNext();)
          {
            //添加映射关系如同上述添加终态方法相同

             Map.Entry<Integer,Set<Integer>> entry = (Map.Entry<Integer,Set<Integer>>) it.next();
              if(entry.getValue().containsAll(sSet))
              {
                  tSet.remove(ttSet);
                  f=true;
                  continue b;
              }
              else if(sSet.containsAll(entry.getValue()))
              {
                  entry.setValue(sSet);              
                  tSet.remove(ttSet);
                  f=true;
                  continue b;
              }            
        }       
         tNTmap.put(Integer.valueOf(count), sSet);
         tSet.remove(ttSet);
         f=true;
         count++;
         continue b;                
    }
    }while(f);
    
   for(Iterator it=Tmap.entrySet().iterator();it.hasNext();) {
       //简化原始状态集合映射表Tmap。
   //对于原状态集合，从新老状态映射表tNTmap中查找对应的新状态，再加入到新的状态映射表NTMmp中
      Map.Entry<NewMap ,Set<Integer>> entry = (Map.Entry<NewMap ,Set<Integer>>)it.next();
      Integer k=null,j=null;
      char s=0;
         boolean j1=false;
          boolean j2=false;
      a:for(Iterator i=tNTmap.entrySet().iterator();i.hasNext();){
               
          Map.Entry<Integer,Set<Integer>> e = (Map.Entry<Integer,Set<Integer>>)i.next();
          if(e.getValue().containsAll(entry.getKey().NSet)){
              k=new Integer(e.getKey().intValue());
              j1=true;
              s=entry.getKey().c;
          }
           if(e.getValue().containsAll(entry.getValue())){
              j=new Integer(e.getKey().intValue());
              j2=true;
          }
          if(j1&&j2)
              break a;
      }
      NewIMap n=new NewIMap(k,s);
      if(NTmap.containsKey(n)&&NTmap.containsValue(j))
      {}
      else
        NTmap.put(n, j);   
     
      
   }
  }
  void token(String str,Map<NewIMap,Integer>NTmap){
     //判断输入串是否符合正则表达式的规则。如果符合，最后达到某一个终状态 ，否则不符合
      boolean b=true;
      int e=1;
      Integer s=new Integer(0);
    a:  for(int i=0;i<str.length();i++){
      for(Iterator it=NTmap.entrySet().iterator();it.hasNext();){
          Map.Entry<NewIMap,Integer> entry = (Map.Entry<NewIMap,Integer>) it.next();
          char c=str.charAt(i);
          if((entry.getKey().k.equals(s))&&(entry.getKey().v==c)){
              s=new Integer(entry.getValue().intValue());
              b=true;
              continue a;
          }
          else
              b=false;

      }
        if(b==false)
            break a;
    }
      if(b==true)
      System.out.println("token : "+str);
  }
}