pl0parser.cpp

一、 pl0文法：适用于递归下降分析算法

// Pl0Parser.cpp: implementation of the CPl0Parser class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "pl0.h"
#include "Pl0Parser.h"
#include "InputData.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CPl0Parser::CPl0Parser()
{

}

CPl0Parser::~CPl0Parser()
{

}

static SymbolTable keys[]={
	"const",MCONST,0,0,-2,0,
	"var",VAR,0,0,-2,0,
	"procedure",PROCEDURE,0,0,-2,0,
	"call",CALL,0,0,-2,0,
	"begin",BEGIN,0,0,-2,0,
	"end",END,0,0,-2,0,
	"if",IF,0,0,-2,0,
	"then",THEN,0,0,-2,0,
	"while",WHILE,0,0,-2,0,
	"do",DO,0,0,-2,0,
	"read",READ,0,0,-2,0,
	"write",WRITE,0,0,-2,0,
	0,0,0,0,-2,0
};

void CPl0Parser::pl0(const char *p)
//编译器主程序，p指向待编译的源程序，以'\0'结束
{
	//编译器初始化
	pCurPosition=p;			//置读位置
	pStrBuf=stringBuf;		//取单词缓冲区
	for(int ix=0;ix<STRBUFLEN;ix++) stringBuf[ix]=0;	//清字符串缓冲区
	lineNo=1;				//源程序行号
	curLev=-1;				//置当前层数
	curParent=-1;			//置当前外层
	errOp=ERR_NUN;			//错误标志
	errStr="";				//错误信息

	for(int i=0;keys[i].pName;i++)	//填写关键字于符号表中
		table[i]=keys[i];
	table[i]=keys[i];

	code.intit(this);				//初始化输出的目标代码表	
	code.gen("j",0,0);				//生成第一条转移指令

	//编译开始
	NextToken();					//预取一个单词，词法分析子程序
	program();						//分析“分程序”
	match(DOT);						//匹配符号"."

	code.modify(0,stCode);			//修改第一条指令转移到程序的第一条语句
	if(!errStr.IsEmpty())
		MessageBox(0,errStr,"错误信息",0);
}

void CPl0Parser::NextToken()
//词法分析
{
	char ch=Getch();		//取一个有效字符
	if(isalpha(ch))
		getID();			//标识符处理
	else if(isdigit(ch))
		getNum();			//整型常数处理
	else
		switch(ch)			//识别分隔符、运算符等
		{
		case ',':
			tokKind=COMMA;
			return;
		case ';':
			tokKind=SEMICOLON;
			return;
		case '=':
			tokKind=EQ;
			return;
		case '(':
			tokKind=LPAREN;
			return;
		case ')':
			tokKind=RPAREN;
			return;
		case ':':
			ch=Getch();
			if(ch!='=')
			{
				errOp=ERR_UNGETC;
				error("赋值语句缺少“=”!");
			}
			tokKind=ASSIGNOP;
			return;
		case '<':
			ch=Getch();
			if(ch=='=')
				tokKind=LE;
			else
			{
				tokKind=LT;
				unGetch();
			}
			return;
		case '>':
			ch=Getch();
			if(ch=='=')
				tokKind=GE;
			else
			{
				unGetch();
				tokKind=GT;
			}
			return;
		case '#':
			tokKind=NE;
			return;
		case '+':
			tokKind=PLUSOP;
			return;
		case '-':
			tokKind=MINUSOP;
			return;
		case '*':
			tokKind=MULTOP;
			return;
		case '/':
			tokKind=DIVOP;
			return;
		case '.':
			tokKind=DOT;
			return;
		}
}

char CPl0Parser::Getch()
{
	while(1)
	{
		switch(*pCurPosition)
		{
		case '\n':
			lineNo++;
		case '\r':
		case ' ':
		case '\t':
			pCurPosition++;
			continue;
		case '\0':
			return ENDF;
		default:
			return *pCurPosition++;
		}
	}
	return ' ';
}

void CPl0Parser::unGetch()
{
	pCurPosition--;
}

void CPl0Parser::match(int kind)
//匹配指定类型的单词，然后取下一个单词
{
	if(kind!=tokKind)
	{
		errOp=ERR_NE;
		error(kind);
	}
	else
		NextToken();
}

void CPl0Parser::getID()
{
	//读取一个单词于单词缓冲区中
	pCurPosition--;
	char *p=pStrBuf;
	while(isalnum(*pCurPosition))
	{
		*p++=*pCurPosition++;
	}
	*p='\0';
	//查填空填符号表
	tokVal=lookUp(pStrBuf);
	//置单词的类型
	tokKind=table[tokVal].kind;
}

void CPl0Parser::getNum()
//取常数
{
	pCurPosition--;
	tokVal=0;
	while(isdigit(*pCurPosition))
	{
		tokVal=10*tokVal+*pCurPosition++-'0';
	}
	tokKind=NUMBER;
}

int CPl0Parser::lookUp(const char *p)
//如果符号不在符号表中，将符号插入到符号表中，返回单词在符号表中的位置
{
	int *parents=new int[curLev+2];
	int *pos=new int[curLev+2];
	int lev=curLev+1,par=curParent;

	//构造直接外层链，最外层之外层为保留字
	for(;lev>0;lev--,par=table[par].parent)
	{
		parents[lev]=par;
		pos[lev]=-1;
	}
	parents[0]=-2;pos[0]=-1;

	//查找出现在外层链中的相同符号，返回最近外层位置
	int i,b=-1;
	for(i=0;table[i].pName!=0;i++)
	{
		if(strcmp(table[i].pName,p)==0)
		{
			b=i;							//符号已出现
			if(table[i].parent==-2) 
				pos[0]=i;					//保留字
			lev=table[i].level+1;			//查找到的符号所在层数
			if(parents[lev]==table[i].parent)
				pos[lev]=i;					//查找符号在某个外层中定义
		}
	}

	//确定符号在符号堆中的位置
	if(b>=0)
		token=table[b].pName;
	else
	{
		pStrBuf+=strlen(p)+1;
		token=p;
	}

	for(b=curLev+1;b>=0;b--)
	{
		if(pos[b]>=0) 
		{
			b=pos[b];
			delete parents;
			delete pos;
			return b;
		}
	}

	table[i].kind=IDENT;
	table[i].level=curLev;
	table[i].pName=token;
	table[i].parent=curParent;
	table[i+1].pName=0;

	delete parents;
	delete pos;

	return i;
}

void CPl0Parser::error(const char *errMsg)
{
	static int n=1;
	switch(errOp)
	{
	case ERR_UNGETC:
		unGetch();
		break;
	}
	char buf[512];
	sprintf(buf,"第%d行错误：%s\n",lineNo,errMsg);
	errStr+=buf;
}

void CPl0Parser::error(int kind)
{
	CString s;
	switch(kind)
	{
	case SERVERKEY:
		error("不应该出现保留字!");
		break;
	case CONSTANT:
		error("常量定义错误!");
		while(tokKind!=SEMICOLON)
			NextToken();
		break;
	case VARIABLE:
		error("变量定义错误!");
		while(tokKind!=SEMICOLON)
			NextToken();
		break;
	case PROCEDURE:
		error("非法过程名或变量重定义!");
		break;
	case FACTOR:
		if(tokKind==IDENT)
		{
			s="变量";
			s=s+token+"未定义错误!";
			error(s);
		}
		else
			error("需要常量、变量或(!");
		break;
	case ROP:


	case RPAREN:
		error("括号不匹配，缺少“)”!");
		break;
	case DOT:
		error("程序非法结束!");
		break;
	case THEN:
		error("IF语句缺少THEN!");
		break;
	case DO:
		error("WHILE语句缺少DO!");
		break;
	case END:
		error("缺少END!");
		break;
	case SEMICOLON:
		error("缺少“;”!");
		break;
	}
}

void CPl0Parser::program()
{
	curLev++;
	addr=3;
	constPart();
	varPart();
	int taddr=addr;
	procedure();
	stCode=code.getCodeAddr();
	if(curParent>=0)
	{
		int t,pos=table[curParent].val;
		while(pos>=0)
		{
			t=pos;
			pos=code.codes[t].addr;
			code.codes[t].addr=stCode;
		}
		table[curParent].val=stCode;
		table[curParent].size=taddr;
	}
	int n=code.gen("int",0,taddr);
	word();
	code.gen("opr",0,0);
	curLev--;
}

void CPl0Parser::word()
{
	switch(tokKind)
	{
	case VARIABLE:
		assignWord();
		break;
	case CALL:
		callWord();
		break;
	case BEGIN:
		beginWord();
		break;
	case IF:
		ifWord();
		break;
	case WHILE:
		whileWord();
		break;
	case READ:
		readWord();
		break;
	case WRITE:
		writeWord();
		break;
	}
}

void CPl0Parser::constPart()
{
	bookMark();
	match(tokKind);
	match(tokKind);
	if(tokKind!=EQ)
	{
		retMark();
		return;
	}
	retMark();
	int n;
	if(tokKind!=MCONST)
	{
		error("常量说明，需要以const开始!");
		match(tokKind);
	}
	else
		match(MCONST);
	while(1){
		if(tokKind==IDENT)
		{
			tokKind=table[n=tokVal].kind=CONSTANT;
		}
		else
		{
			if(table[tokVal].parent==-2)
				error("保留字不能是常量名!");
			else
				if(getParent())
					error("非法标识符或标识符已定义!");
				else
					n=fillTable(CONSTANT);
			tokKind=CONSTANT;
		}
		match(CONSTANT);
		match(EQ);
		table[n].val=tokVal;
		match(NUMBER);

		if(tokKind!=COMMA)
			break;
		match(COMMA);
	}
	match(SEMICOLON);
}

void CPl0Parser::varPart()
{
	switch(tokKind)
	{
	case VAR:
		break;
	case PROCEDURE:
	case BEGIN:
		return;
	default:
		bookMark();
		match(tokKind);
		match(tokKind);
		if(tokKind==COMMA)
		{
			retMark();
			break;
		}
		else
		{
			retMark();
			return;
		}
	}
	int n;
	if(tokKind!=VAR)
	{
		error("变量定义应该以var开始!");
		tokKind=VAR;
	}
	match(VAR);
	while(1){
		if(tokKind==IDENT)
		{
			tokKind=table[n=tokVal].kind=VARIABLE;
		}
		else
		{
			if(table[tokVal].parent==-2)
				error("保留字不能是变量名!");
			else
				if(getParent())
					error("非法标识符或标识符已定义!");
				else
					n=fillTable(VARIABLE);
			tokKind=VARIABLE;
		}
		match(VARIABLE);
		table[n].val=addr++;
		if(tokKind!=COMMA)
			break;
		match(COMMA);
	}
	match(SEMICOLON);
}

void CPl0Parser::procedure()
{
	while(1)
	//while(tokKind==PROCEDURE)
	{
		bookMark();
		match(tokKind);
		match(tokKind);
		if(tokKind!=SEMICOLON)
		{
			retMark();
			return;
		}
		retMark();
		int n;
		if(tokKind!=PROCEDURE)
		{
			error("过程定义应该以procedure开始!");
			tokKind=PROCEDURE;
		}
		match(PROCEDURE);
		if(tokKind==IDENT)
		{
			tokKind=table[n=tokVal].kind=PROCEDURE;
		}
		else
		{
			if(table[n=tokVal].parent==-2)
				error(SERVERKEY);
			else
				if(getParent())
					error(PROCEDURE);
				else
					n=fillTable(PROCEDURE);
			tokKind=PROCEDURE;
		}
		match(PROCEDURE);
		match(SEMICOLON);
		table[n].size=-1;
		table[n].val=-1;
		curParent=n;
		program();
		match(SEMICOLON);
		curParent=table[curParent].parent;
	}
}

int CPl0Parser::getParent()
{
	for(int i=0;table[i].pName;i++)
		if(strcmp(table[i].pName,token)==0 && curParent==table[i].parent)
			return 1;
	return 0;
}

int CPl0Parser::fillTable(int kind)
{
	for(int i=0;table[i].pName;i++);
	table[i].pName=token;
	tokKind=table[i].kind=kind;
	table[i].level=curLev;
	table[i].parent=curParent;
	table[i+1].pName=0;
	return i;
}

void CPl0Parser::assignWord()
{
	int n=tokVal;
	int err=0;
	match(VARIABLE);