wordtype.java

本程序利用java语言实现了对英文单词的模拟识别。

/*
 * Created on 2004-10-26
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
package ai.base;
import java.util.*;


/**
 * @author 赵秀成
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class WordType {
	/*
	 *定义谓词系统中的一些常量
	 *谓词、函数、自由变量、约束变量、变量
	 *联结词、数量词、常量、空白、分隔符、终结符、参数等 
	 */
	public static int PREDICATE=256;
	public static int FUNCTION=257;
	
	//变量类型：自由和约束
	public static int FREE_VAR=258;
	public static int UNFREE_VAR=259;
	public static int VAR=260;
	
	//常量
	public static int CONSTANT=263;
	
	//联结符类型:合取、析取、非、蕴含、双条件
	public static int LINKER_WORD=264;
	
	
	public static int NUMERIC=270;
	public static int NUMERIC_ANY=271;
	public static int NUMERIC_EXIST=272;
	
	//分隔符:左括号、右括号、逗号、空格
	public static int DEPART_WORD=273;
	public static int LEFT_BRACKET=274;
	public static int RIGHT_BRACKET=275;
	public static int COMMA=276;
	//public static int SPACE=277;
	
	//public static int TERMINAL=278;
	
	//参数类型：变量、常量、函数的返回值
	public static int PARA=272;
	public static int PARA_TYPE_VAR=279;
	public static int PARA_TYPE_CONSTANT=280;
	public static int PARA_TYPE_FUNCTION=281;
	
	/*特殊符号集：ψЗ→∧∨≒ 
	*任意：ψ
	*存在：З
	*蕴含：→
	*双条件：≒
	*合取：∧
	*析取：∨
	 *
	 */
	//判断给定字符串的类型，如果是非法的字符串输入格式，返回-1
	//可以检查getType(String)的返回值来进行相应的处理
	//如果得到一个值为-1的返回值应该提示用户检查输入的谓词语句的格式
	public static int getType(String word){
		char firstChar=(char)-1;
		if(word.length()>0)
			firstChar=word.charAt(0);
		
		switch(firstChar){
		case 'ψ':
		case 'З':return NUMERIC;
		case '→':
		case '∧':
		case '∨':
		case '≒':
		case '~':return LINKER_WORD;
		case '_':return FUNCTION;
		//case '.':return TERMINAL;
		case '[':return CONSTANT;
		case '(':return LEFT_BRACKET;
		case ')':return RIGHT_BRACKET;
		case ',':return COMMA;
		default:{
			if(Character.isLetter(firstChar)){
				if(Character.isLowerCase(firstChar))
					return PREDICATE;
				else
					return VAR;
			}
			else
				return -1;
		}
		}	
	}
	
	//词法分析器可能抛出句法不合适的若干种异常，调用次访法的方法必须处理这些异常
	//包括：InvalidTerminalException，当句法不以一个英文句点结束时抛出
	//     DismatchException,当有封装符号不配队时抛出
	//     InvalidCharacterException,当出现非法字符时抛出
	//     IDFirstCharException,当标示符的第一个字符是数字0~9时抛出
	public static Vector parse(String sentence)
		throws InvalidTerminalException,DismatchException,
		       InvalidCharacterException,IDFirstCharException
	{
		Vector vec=new Vector();
		sentence.trim();
		if(!sentence.endsWith(".")){
			throw new InvalidTerminalException();
		}
		
		//谓词字符集：不包括结束符号
		String validChars="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
			+"abcdefghijklmnopqrstuvwxyz"
			+"0123456789"
			+"ψЗ→∧∨≒ ~_,()[] \t.";
		char nextChar;
		int curPos=0;
		String temp="";
		do{
			nextChar=sentence.charAt(curPos);
			if(validChars.indexOf((int)nextChar)==-1)
				throw new InvalidCharacterException();
			switch(nextChar){
			
			//如果是分隔符类别的字符，如果文本缓存不是空，就将文本加入容器
			//否则，什么也不用做
			case ' ':
			case '\t':{
				if(temp!=""){
					vec.add(temp);
					temp="";
				}
				break;
			}
			case ',':
			case '(':
			case ')':{
				if(temp!=""){
					vec.add(temp);	
					temp="";
				}
				vec.add(String.valueOf(nextChar));
				break;
			}
			
			//如果是单字符文本，直接将不为空的缓存内容加入容器，并将此字符也加入容器
			case 'ψ':
			case 'З':
			case '→':
			case '∧':
			case '∨':
			case '≒':
			case '~':{
				if(temp!=""){
					vec.add(temp);
					temp="";
				}
				vec.add(String.valueOf(nextChar));
				break;
			}
			
			//检查是否进入文本常量，它可以容纳任意字符，所以要做特殊处理
			case '[':{
				while(nextChar!=']'){
					temp+=nextChar;
					curPos++;
					nextChar=sentence.charAt(curPos);
					if(curPos>=sentence.length()-1){
						throw new DismatchException("请检查输入的谓词语句，很可能是没有完全将常量封装在[]对中");
					}
				}
				temp+=nextChar;
				break;
			}
			
			//其他情况下应直接将该字符累加进缓存器
			default:{
				if(nextChar!='.')
					temp+=nextChar;
			}
			}
			curPos++;
		}while(nextChar!='.');
		
		verifySentence(vec);
		Vector vecNow=new Vector();
		Iterator it=vec.iterator();
		int codeBase=0;
		while(it.hasNext()){
			String str=(String)it.next();

			if(str.equals(")")) 
				codeBase--;	
			else if(str.equals("(")) 
				codeBase++;
			else
				vecNow.add(new CodeString(str,codeBase));
		}
		int freePos=0;
		NextVarName getName=new NextVarName();
		
		for(int i=0;i<vecNow.size();i++){
			CodeString prev=(CodeString)vecNow.get(i);
			if(prev.getType()==NUMERIC){
				freePos=i+1;
				CodeString vars=(CodeString)vecNow.get(freePos);
				String next=getName.NextName();
				renameOne(freePos+1,prev.getLayer(),vars,vecNow,next);
				vars.setValue(next);
				vars.setRename(true);
				getName.getNextName();
			}
		}
		for(int i=0;i<vecNow.size();i++){
			CodeString str=(CodeString)vecNow.get(i);
			if(str.getType()==VAR){
				if(str.getRename()==false){
					freePos=i;
					String next=getName.NextName();
					renameOneFree(freePos,str.getValue(),vecNow,next);
					getName.getNextName();
				}
			}
		}
		return vecNow;
	}
	
	//对自由变量进行更名
	private static void renameOneFree(int pos,String prev,Vector vec,String next){
		for(int i=pos;i<vec.size();i++){
			CodeString now=(CodeString)vec.get(i);
			String nowStr=now.getValue();
			int subs=nowStr.compareTo(prev);
			if(subs==0){
				now.setValue(next);	
				now.setRename(true);
			}
		}
	}
	
	//对约束变量进行更名（约束意指在量词的辖域内）
	private static void renameOne(int pos,int layer,CodeString vars,Vector vec,String next){
		
		String varsValue=vars.getValue();
		
		for(int i=pos;i<vec.size();i++){
			CodeString now=(CodeString)vec.get(i);
			if(now.getLayer()==layer) 
				break;
			String nowStr=now.getValue();
			int subs=nowStr.compareTo(varsValue);
			if(subs==0){
				now.setValue(next);	
				now.setRename(true);
			}
		}
	}
	
	
	//检验parse生成的容器内容是否否和谓词语法
	private static void verifySentence(Vector vec)
		throws IDFirstCharException,DismatchException
	{
		int leftBarcketCnt=0;    //左括号的数目
		int rightBarcketCnt=0;   //右括号的数目
		
		Iterator it=vec.iterator();
		while(it.hasNext()){
			String str=(String)it.next();
			if(str.equals("("))
				leftBarcketCnt++;
			if(str.equals(")"))
				rightBarcketCnt++;
			if(Character.isDigit(str.charAt(0)))
				throw new IDFirstCharException();
			
		}
		if(leftBarcketCnt!=rightBarcketCnt)
			throw new DismatchException("(和)的配对不准确");
	}
}

//私有类的作用是获取系统的下一个变量名，按如下规则：
//从X_00开始到X_99，然后从Y_00~Y_99~Z_00~Z_99，共300个变量
//这限制了一个问题求解过程中变量的数目，但是小型应用已经足够
//可以扩展：从A_00开始到Z_99，则可以容纳2600个变量
class NextVarName{
	String nextName="X_00";
	public NextVarName(){
	}
	public void getNextName(){
		
		char firstChar=nextName.charAt(0);
		char thirdChar=nextName.charAt(2);
		char forthChar=nextName.charAt(3);
		int tens=Integer.parseInt(String.valueOf(thirdChar));
		int ones=Integer.parseInt(String.valueOf(forthChar));
		int cnt=tens*10+ones+1;
		if(cnt==100){
			firstChar=(char)(firstChar+1);
			nextName=firstChar+"_00";
		}
		if(cnt<10){
			nextName=firstChar+"_0"+cnt;
		}
		if(cnt>=10 && cnt<100){
			nextName=firstChar+"_"+cnt;
		}
		//JOptionPane.showMessageDialog(null,nextName);
	}
	public String NextName(){
		return nextName;
	}
	
}


//四个异常类的定义：
class InvalidTerminalException extends Exception{
	public InvalidTerminalException(){
		super("无效的谓词语句结束符:\n\t\t谓词语句必须以英文句点结束!");
	}
}
class IDFirstCharException extends Exception{
	public IDFirstCharException(){
		super("无效的项目开始符:\n\t\t项目不能以数字开头!");
	}
}
class InvalidCharacterException extends Exception{
	public InvalidCharacterException(){
		
		//下属字符串即为字符集
		super("无效的输入字符:\n\t\t谓词语句的字符只能从以下字符集选取：\n\t\t"
				+"大写字母：ABCDEFGHIJKLMNOPQRSTUVWXYZ\n"
				+"小写字母：abcdefghijklmnopqrstuvwxyz\n"
				+"数字：0123456789\n"
				+"特殊字符：ψЗ→∧∨≒ ~_\n");
	}
}
class DismatchException extends Exception{
	public DismatchException(String str){
		super("分隔符不匹配:\n\t\t"+str);
	}
}