parsing.cpp

中文信息处理方面的一个源码

#include "stdafx.h"
#include "BottomUpParser.h"
#include "parsing.h"

CObArray rules,edges;
int wordNum;
CString myTrace; // 2002-12-18,用于记录分析的中间结果，全局变量

CRule::CRule(CString Line)
{
	int i=Line.Find("->");
	Ls=Line.Left(i);
	Ls.TrimRight();
	Ls.TrimLeft();
	Line=Line.Mid(i+3);
	Line.TrimLeft();
	
	i=Line.Find(' '); // 找空格
	if(i<0) {
		Rs1=Line;
		Rs2="";
	}
	else {
		Rs1=Line.Left(i);
		Line=Line.Mid(i+1);
		Line.TrimLeft();
		Rs2=Line;
	}
}

CEdge::CEdge(CString wt, int wid)
{// 为词语建立一个局部分析
	int i=wt.Find('/');
	if(i<0) 
		Root=wt;
	else
		Root=wt.Mid(i+1)+'('+wt.Left(i)+')'; // 将原来的 word/tag形式转换为 tag(word)形式，即将word上升为词性标记
	First=Last=wid;
	Sub1=Sub2=-1;
}

CEdge::CEdge(CEdge *p,int pid, CString r)
{// 用提升规则建立一个局部分析
	Root=r;
	First=p->First;
	Last=p->Last;
	Sub1=pid;
	Sub2=-1;
}

CEdge::CEdge(CEdge *p1,CEdge *p2,int pid1,int pid2,CString r)
{// 用捆绑规则建立一个局部分析
	Root=r;
	First=p1->First;
	Last=p2->Last;
	Sub1=pid1;
	Sub2=pid2;
}

// 全程函数 --> 分析句子（自底向上）

BOOL GetRule(CString &ls,CString rs1, CString rs2)
{ // 查找规则
	CRule *r;//规则指针
	for(int i=0;i<rules.GetSize();i++) {
		r=(CRule *)rules[i];
		if(r->Rs1==rs1 && r->Rs2==rs2) {
			ls=r->Ls;
			return TRUE; // 找到第一条右部匹配的规则就返回，因此只找到一条规则
		}
	}
	return FALSE;
}

void Expanding()
{// 根据规则，增加局部分析
	int i=edges.GetSize()-1, j=0;
	CString nr;
	CEdge *e, *e2;
	BOOL Raising=FALSE;
	while(i<edges.GetSize()) {
		e=(CEdge *)edges[i]; // 右子树
		e2=(CEdge *)edges[j]; // 左子树
		if(!Raising && GetRule(nr,e->GetRoot())) {
			edges.Add(new CEdge(e,i,nr));
			Raising=TRUE;
		}
		if(e2->Last+1==e->First && GetRule(nr,e2->GetRoot(),e->GetRoot())) 
			// 找到箭头右部匹配上的第一条规则
			// 实际的规则库中可能有多条能够匹配上的规则，但目前没有处理
			edges.Add(new CEdge(e2,e,j,i,nr)); // 用捆绑规则将新的边加入到chart中
		j++;
		if(e2->Last==e->First) { // 左子树的终点位置与右子树的起点位置重合，就停止扩展 
			i++;
			j=0;
			Raising=FALSE;
		}
	}
}

CString Parsing(CString s)
{// 分析一个句子
	CEdge * e=NULL; // 局部分析指针
	int wid=1;
	CString t;
	for(int i=0;i<edges.GetSize();i++)
		if(edges[i]!=NULL)
			delete edges[i];
	edges.RemoveAll(); // 以上是清除分析上一个句子留下的局部分析结果

	while(s.GetLength()>0) {
		int i=s.Find(' ');
		if(i<0) {
			t=s;
			s="";
		}
		else {
			t=s.Left(i);
			s=s.Mid(i+1);
			s.TrimLeft();
		}
		e=new CEdge(t,wid); // 为当前词t建立一个局部分析（t是s中最左边的词）
		edges.Add(e);
		wid++;
		Expanding(); // 以当前分析的词位置为起点，根据规则库中的规则，尽可能多地向chart中加入新边
	}
	
	e->WordNumber=wid-1; // 句子中的词数
	wordNum = e->WordNumber;
	
	return GetTrees(wid-1);
}

CString GetTrees(int wid)
{ // 获取分析结果树
	CString s="",tmp,tmp2,tmpFirst,tmpLast,tmpSub1,tmpSub2;
	CEdge *e;
	myTrace=""; // 记录分析过程的中间结果，2002-12-18

	for(int i=0;i<edges.GetSize();i++) {
		e=(CEdge *)edges[i];

		// 打印中间结果到myTrace变量中，2002-12-18
		
		tmp2.Format("%d",i+1);
		tmpFirst.Format("%d",e->First);
		tmpLast.Format("%d",e->Last);
		tmpSub1.Format("%d",e->Sub1+1);
		tmpSub2.Format("%d",e->Sub2+1);
		myTrace=myTrace+tmp2+"\t"+(e->GetRoot())+"\t"+tmpFirst+"\t"+tmpLast+"\t";
		if (e->Sub1==-1 && e->Sub2==-1)
			myTrace=myTrace+"\n";
		else
			myTrace=myTrace+"["+tmpSub1+","+tmpSub2+"]"+"\n";
		
		// 打印中间结果过程结束

		if(e->First==1 && e->Last==wid && e->GetRoot()=="S") // 如果edges[i]覆盖全句，并且根为S，就作为分析结果输出
			s+=GetOneTree(e)+"\n\n"; // 调用GetOneTree递归输出每个子树
	}
	tmp.Format("局部分析%d个；",edges.GetSize());
	if(s.IsEmpty())
		s=tmp+"句子不合语法"+"\n\n";
	else
		s=tmp+'\n'+s;
	return s;
}

CString GetOneTree(CEdge *e)
{ // 获取一棵分析结果树
	if(e->Sub1==-1 && e->Sub2==-1)
		return e->Root;
	CEdge *e1,*e2;
	CString s=e->Root+'(';
	e1=(CEdge *)edges[e->Sub1];
	s+=GetOneTree(e1);
	if(e->Sub2>=0) {
		e2=(CEdge *)edges[e->Sub2];
		s+='+'+GetOneTree(e2);
	}
	s+=')';
	return s;
}