lr1.cpp

以lr1分析法,按照给定的文法分析单词序列是否合乎语法要求,将每一步分析打印出来,并给出最后结果.

1// LR1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "CharStack.h"
#include "IntStack.h"
#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

struct BNFNODE	// 产生式节点
{
	char	Left;					// 产生式左部
	char	Right[MAX_DATA_LEN];	// 产生式右部
	int		RLen;					// 产生式右边长度
} m_Bnf[MAX_DATA_LEN];
int	m_nBnfLen;

enum ACTIONTYPE	// 动作类别
{
	Push,		// 移进
	Sumup,		// 规约
	Accept,		// 接受
	Error		// 出错
};

struct LR1TABLE
{
	int		nStatus;		// 状态
	char	CurChar;		// 当前符号
	ACTIONTYPE	ActionType;	// 动作类别
	int		nNextStatus;	// 下一状态
} m_Lr1[MAX_DATA_LEN];
int		m_nLr1Len;

/*****************************************************
* 以下是词法分析文件操作
******************************************************/
// 清空链表
void ClearWords(WORDNODE *pHeader)
{
	WORDNODE *pNode;

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

// 增加结点
WORDNODE* AddNode(char c[], WORDNODE *pTail)
{
	// c第0个字节为单词类别，第1个为逗号，第2个以后是值

	WORDNODE *pNode = (WORDNODE *)malloc(sizeof(WORDNODE));
	pNode->byType = c[0] - '0';
	pNode->pNext = NULL;

	int nChars = MAX_DATA_LEN - 2;
	memcpy(pNode->Value, &c[2], nChars);

	pTail->pNext = pNode;
	return pNode;
}

bool ReadWords(char FileName[], WORDNODE *pHeader)
{
	// 打开文件
	FILE *f = fopen(FileName, "r");
	if (f == NULL)
	{
		ClearWords(pHeader);
		return false;
	}

	WORDNODE *pTail = pHeader;
	char c[MAX_DATA_LEN];

	// 读取数据
	while (!feof(f))             //未到文件尾
	{
		fscanf(f, "%s\n", c);
		pTail = AddNode(c, pTail);
		printf("%s\n", c);
	}

	// 关闭文件
	fclose(f);

	// 增加一个结束符
	c[0] = WT_OPERATOR + '0';
	c[1] = ',';
	c[2] = '#';
	c[3] = '\0';
	AddNode(c, pTail);

	return true;
}

/*****************************************************
* 以下是文法文件操作
******************************************************/
char *ReadFile(char FileName[], int *nLen)
{
	// 打开文件
	FILE *f = fopen(FileName, "r");
	if (f == NULL)
		return NULL;

	// 读取文件
	char *pChar = (char *)malloc(sizeof(char) * MAX_DATA_LEN);
	
	// 读取数据
	int nRead;
	*nLen = 0;
	while (!feof(f))
	{
		nRead = fread(pChar + *nLen, sizeof(char), MAX_DATA_LEN, f);
		*nLen += nRead;
		if (nRead < MAX_DATA_LEN)	// 文件结尾
			break;

		pChar = (char *)realloc(pChar, *nLen + sizeof(char) * MAX_DATA_LEN);
	}

	// 关闭文件
	fclose(f);

	return pChar;
}

bool ReadBnfs()
{
	// 读取文件
	int nLen;
	char *pChar = ReadFile("Bnf.txt", &nLen);
	if (pChar == NULL)
		return false;
	
	// 解析出文法产生式
	int nBegin, nCur, nIndex = 0;
	for (nBegin = 0, nCur = 0; nCur < nLen; nCur++)
	{
		// 左部
		m_Bnf[nIndex].Left = pChar[nCur];

		// 右部
		nCur += 2;
		nBegin = nCur;
		for (; pChar[nCur] != ';'; nCur++);
		m_Bnf[nIndex].RLen = nCur - nBegin;
		memcpy(m_Bnf[nIndex].Right, pChar + nBegin, m_Bnf[nIndex].RLen);
		m_Bnf[nIndex].Right[m_Bnf[nIndex].RLen] = '\0';

		nIndex++;
	}
	m_nBnfLen = nIndex;

	return true;
}

/*****************************************************
* 以下是LR(1)分析表文件操作
******************************************************/
ACTIONTYPE	GetActionType(char c)
{
	if (c >= '0' && c <= '9')
		return Push;

	switch (c)
	{
	case 'S':
		return Push;
	case 'r':
		return Sumup;
	case 'a':
		return Accept;
	}

	return Error;
}

bool ReadLR1()
{
	// 读取文件
	int nLen;
	char *pChar = ReadFile("Lr1.Lr1", &nLen);
	if (pChar == NULL)
		return false;

	// 解析出分析表
	int nBegin, nCur, nIndex = 0;
	for (nBegin = 0, nCur = 0; nCur < nLen; nCur++)
	{
		// 状态
		m_Lr1[nIndex].nStatus = atoi(&pChar[nCur]);
		for (; pChar[nCur] != ';'; nCur++);
		nCur++;

		// 符号
		m_Lr1[nIndex].CurChar = pChar[nCur];
		nCur += 2;

		// 动作类别
		m_Lr1[nIndex].ActionType = GetActionType(pChar[nCur]);
		if (pChar[nCur] == 'a')
		{
			nCur += 3;
			m_Lr1[nIndex].nNextStatus = 0;
		}
		else
		{
			if (pChar[nCur] == 'S' || pChar[nCur] == 'r')
				nCur++;
			// 状态转换
			m_Lr1[nIndex].nNextStatus = atoi(&pChar[nCur]);
			for (; pChar[nCur] != ';'; nCur++);
		}

		nIndex++;
	}
	m_nLr1Len = nIndex;

	return true;
}

/********************************************************
* 以下是语法分析部分
*********************************************************/
/************************************************
* 获取当前单词符号：
* 如果是整数或标识符，返回'i'
* 如果是算法，返回算法
*************************************************/
char GetCurChar(WORDNODE *pNode)
{
	switch (pNode->byType)
	{
	case WT_OPERATOR:	// 操作符
		return pNode->Value[0];
	case WT_UINT:		// 整数
	case WT_VARIABLE:	// 变量
		return 'i';
	}

	return '\0';
}

int GetLR1Index(int nStatus, char a)
{
	for (int i = 0; i < m_nLr1Len; i++)
	{
		if (m_Lr1[i].nStatus == nStatus && m_Lr1[i].CurChar == a)
			return i;
	}
	return -1;
}

// 打印状态
void PrintState(WORDNODE *pNode, int nBnfIndex)
{
	PrintIntStack();
	PrintCharStack();

	WORDNODE *pPrint = pNode;
	int nCount = 0;
	while (pPrint != NULL)
	{
		printf("%c", GetCurChar(pPrint));
		pPrint = pPrint->pNext;
		nCount++;
	}
	for (; nCount < 12; nCount++)
		printf(" ");

	if (nBnfIndex == -1)
	{
		if (GetCurChar(pNode) == 'i')
			printf("i=%s", pNode->Value);
	}
	else
		printf("%c-->%s", m_Bnf[nBnfIndex].Left, m_Bnf[nBnfIndex].Right);

	printf("\n");
}

bool LR1Analysis(WORDNODE *pHeader)
{
	InitIntStack();				//初始化状态栈
	PushInt(0);					//0状态入栈
	InitCharStack();			//初始化符号栈
	PushChar('#',NULL);			//'#'符号入栈

	WORDNODE * pNode=pHeader->pNext;			//pNode指向当前单词结点
	PrintState(pNode,-1);						//打印,-1表示第一步不会为归约
	
	int LR1_Index;								//记录查询LR1分析表后得到的数组下标
	while(1)
	{
		LR1_Index=GetLR1Index(TopInt(),GetCurChar(pNode));
						//根据栈顶状态TopInt()和当前符号GetCurChar(pNode)，查询分析表
		
		if(LR1_Index==-1) return false;		//查询不成功

		if(m_Lr1[LR1_Index].ActionType==Push)
		{
			//查询LR1分析表得到的动作为移进
			PushInt(m_Lr1[LR1_Index].nNextStatus);			//将LR1分析表指示的状态移进状态栈			
			if(GetCurChar(pNode)=='i') PushChar('i',pNode);	//若当前单词为数字或标识符,将当前符号和当前单词指针移进符号栈,
			else PushChar(GetCurChar(pNode),NULL);			//若当前单词为运算符,只将该运算符移进符号栈

			pNode=pNode->pNext;			//指向下一单词

			PrintState(pNode,-1);		//打印状态,因为此步为移进动作,所以不会用到产生式,所以传递参数-1
		}

		else if(m_Lr1[LR1_Index].ActionType==Sumup)
		{
			//查询LR1分析表得到的动作为归约
			for(int i=1;i<=m_Bnf[m_Lr1[LR1_Index].nNextStatus].RLen;i++)
			{
				//从状态栈和符号栈各弹出 m_Bnf[m_Lr1[LR1_Index].nNextStatus].RLen 个元素
				PopChar();
				PopInt();
			}

			PushChar(m_Bnf[m_Lr1[LR1_Index].nNextStatus].Left,NULL);	//将产生式左部的非终结符入符号栈
			
			int n=GetLR1Index(TopInt(),TopChar()->cCur);
								//根据状态栈栈顶状态和符号栈栈顶符号查询LR1分析表，确定转移状态
			
			if(n==-1)return false;		//查询不成功
			PushInt(m_Lr1[n].nNextStatus);		//将LR1分析表指示的转移状态入状态栈

			PrintState(pNode,m_Lr1[LR1_Index].nNextStatus);		//打印,m_Lr1[LR1_Index].nNextStatus为此步用到的产生式
		}

		else
		{
			////查询LR1分析表得到的动作为接受acc,返回true,语法分析成功
			return true;
		}
	}
	

}

int main(int argc, char* argv[])
{
	// 输入文件名
	char FileName[MAX_DATA_LEN];
	printf("请输入词法分析的文件名：\n");
	scanf("%s", FileName);

	// 读取文件
	printf("单词序列：\n");
	WORDNODE *pHeader = (WORDNODE *)malloc(sizeof(WORDNODE));
	if (!ReadWords(FileName, pHeader))
	{
		printf("读取词法分析文件失败！\n");
		ClearWords(pHeader);
		return 0;
	}

	// 读取文法
	if (!ReadBnfs())
	{
		printf("读取产生式失败！\n");
		ClearWords(pHeader);
		return 0;
	}

	// 读取LR(1)分析表
	if (!ReadLR1())
	{
		printf("读取LR(1)分析表失败！\n");
		ClearWords(pHeader);
		return 0;
	}

	// 语法分析
	printf("语法分析过程：\n");
	printf("状态栈                                       归约串         输入串      产生式\n");
	if (LR1Analysis(pHeader))
		printf("语法分析成功！\n");
	else
		printf("语法分析失败！\n");

	// 清空链表
	ClearWords(pHeader);

	getchar();
	getchar();

	return 0;
}