wordanalysis.cpp

一个超级经典的词法和语法分析程序（附加源代码）．从词法分析的输出过渡到语法分析. 高手编的

// WordAnalysis.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <malloc.h>
#include <memory.h>
#include <stdio.h>

#define MAX_DATA_LEN	256	// 数据缓冲区长度

// word type
#define WT_OPERATOR		0	// 操作符
#define WT_UINT			1	// 非负整数
#define WT_VARIABLE		2	// 变量

#define DFA_STATUS_ERR	255	// 错误状态

struct WORDNODE
{
	unsigned short byType;		// 类别
	char Value[MAX_DATA_LEN];	// 值
	WORDNODE *pNext;			// 下一结点
};

/***********************************************
* 字符类别判断
************************************************/
// c是否为英文字符
bool IsEnglishChar(char c)
{
	return ((c >= 'a' && c <= 'z')
		|| (c >= 'A' && c <= 'Z'));
}

// c是否为数字
bool IsNumChar(char c)
{
	return (c >= '0' && c <= '9');
}

// c是否为运算符
bool IsOperator(char c)
{
	switch (c)
	{
	case '+':
	case '-':
	case '*':
	case '/':
		return true;
	}

	return false;
}

// 预处理：将多余空格去掉
void Prefix(char c[])
{
	for (int i = 0, j = 0; j < MAX_DATA_LEN && c[j] != '\0'; j++)
	{
		if (c[j] != ' ')
			c[i++] = c[j];
	}
	c[i] = '\0';
}

/*****************************************
* 函数功能：非负整数状态跳转。为与DFA相一致，此函数未优化。
* 入口参数：c 当前字符
*			nStatus 当前状态
* 返 回 值：下一状态
*****************************************/
int	GetIntStatus(char c, int nStatus)
{
	switch (nStatus)
	{
	case 0:
		if (IsNumChar(c))
			return 1;
		else
			return DFA_STATUS_ERR;
	case 1:
		if (IsNumChar(c))
			return 1;
		else
			return 2;
	}

	return DFA_STATUS_ERR;
}

/*****************************************
* 函数功能：非负整数识别
* 入口参数：c 缓冲区
*			nCur 扫描器当前字符位置
* 返 回 值：整数结束位置，-1表示出错
*****************************************/
int GetInt(char c[], int nCur)
{
	int nStatus = 0;

	for (; nCur < MAX_DATA_LEN; nCur++)
	{
		nStatus = GetIntStatus(c[nCur], nStatus);
		switch (nStatus)
		{
		case 2:
			return nCur - 1;
		case DFA_STATUS_ERR:
			return -1;
		}
	}

	return nCur;
}

/*****************************************
* 函数功能：标识符（变量）状态跳转。为与DFA相一致，此函数未优化。
* 入口参数：c 当前字符
*			nStatus 当前状态
* 返 回 值：下一状态
*****************************************/
int	GetVariableStatus(char c, int nStatus)
{
	switch (nStatus)
	{
	case 0:
		if (IsEnglishChar(c) || c == '_')
			return 1;
		else
			return DFA_STATUS_ERR;
	case 1:
		if (IsNumChar(c) || IsEnglishChar(c) || c == '_')
			return 1;
		else
			return 2;
	}

	return DFA_STATUS_ERR;
}

/*****************************************
* 函数功能：标识符（变量）识别
* 入口参数：c 缓冲区
*			nCur 扫描器当前字符位置
* 返 回 值：整数结束位置，-1表示出错
*****************************************/
int GetVariable(char c[], int nCur)
{
	int nStatus = 0;

	for (; nCur < MAX_DATA_LEN; nCur++)
	{
		nStatus = GetVariableStatus(c[nCur], nStatus);
		switch (nStatus)
		{
		case 2:
			return nCur - 1;
		case DFA_STATUS_ERR:
			return -1;
		}
	}

	return nCur;
}

// 清空链表
void Clear(WORDNODE *pHeader)
{
	WORDNODE *pNode;

	while (pHeader != NULL)
	{
		pNode = pHeader->pNext;
		free(pHeader);
		pHeader = pNode;
	}
}

// 增加结点
WORDNODE* AddNode(char c[], int nBegin, int nEnd, unsigned short byType, WORDNODE *pTail)
{
	WORDNODE *pNode = (WORDNODE *)malloc(sizeof(WORDNODE));
	pNode->byType = byType;
	pNode->pNext = NULL;

	int nChars = nEnd - nBegin + 1;
	memcpy(pNode->Value, &c[nBegin], nChars);
	pNode->Value[nChars] = '\0';

	pTail->pNext = pNode;
	return pNode;
}

// 词法分析
WORDNODE* WordAnalysis(char c[])
{
	// 第一个结点作为头结点，不使用
	WORDNODE *pHeader = (WORDNODE *)malloc(sizeof(WORDNODE));
	pHeader->pNext = NULL;
	WORDNODE *pTail = pHeader, *pNode = NULL;

	// 词法分析
	char cCur;
	for (int nCur = 0, nEnd; nCur < MAX_DATA_LEN; nCur++)
	{
		cCur = c[nCur];		// 空间换时间，防止每个if都要计算数组下标

		if (IsNumChar(cCur))	// 整数
		{
			if ((nEnd = GetInt(c, nCur)) == -1)	// 出错
			{
				Clear(pHeader);
				return NULL;
			}
			pTail = AddNode(c, nCur, nEnd, WT_UINT, pTail);
			nCur = nEnd;
		}
		else if (IsEnglishChar(cCur) || cCur == '_')	// 标识符
		{
			if ((nEnd = GetVariable(c, nCur)) == -1) // 出错
			{
				Clear(pHeader);
				return NULL;
			}
			pTail = AddNode(c, nCur, nEnd, WT_VARIABLE, pTail);
			nCur = nEnd;
		}
		else if (IsOperator(cCur))		// 操作符
			pTail = AddNode(c, nCur, nCur, WT_OPERATOR, pTail);
		else if (cCur == '\0')		// 结束
			return pHeader;
		else	// 出错
		{
			Clear(pHeader);
			return NULL;
		}
	}

	return pHeader;
}

bool Save(WORDNODE *pHeader)
{
	// 打开文件
	FILE *f = fopen("Words.txt", "w");
	if (f == NULL)
	{
		Clear(pHeader);
		return false;
	}

	// 空出第一个结点
	WORDNODE *pNode = pHeader->pNext;

	// 保存数据
	while (pNode != NULL)
	{
		fprintf(f, "%c,%s\n", pNode->byType + '0', pNode->Value);
		pNode = pNode->pNext;
	}

	// 关闭文件
	fclose(f);

	return true;
}

// 主函数
int main(int argc, char* argv[])
{
	// 输入
	char c[MAX_DATA_LEN];
	printf("请输入表达式：\n");
	gets(c);

	// 预处理
	Prefix(c);

	// 词法分析
	WORDNODE *pHeader = WordAnalysis(c);
	if (pHeader == NULL)
	{
		printf("\n词法分析错误!\n");
		return 0;
	}

	// 保存
	if (!Save(pHeader))
	{
		printf("\n保存文件失败\n");
		return 0;
	}

	// 清空数据
	Clear(pHeader);

	// 完成
	printf("\n词法分析成功，并已保存到文件Word.txt\n", c);
	printf("按任意键退出\n", c);
	getchar();
	return 0;
}