?? lr1.cpp
字號(hào):
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 // 產(chǎn)生式節(jié)點(diǎn)
{
char Left; // 產(chǎn)生式左部
char Right[MAX_DATA_LEN]; // 產(chǎn)生式右部
int RLen; // 產(chǎn)生式右邊長(zhǎng)度
} m_Bnf[MAX_DATA_LEN];
int m_nBnfLen;
enum ACTIONTYPE // 動(dòng)作類別
{
Push, // 移進(jìn)
Sumup, // 規(guī)約
Accept, // 接受
Error // 出錯(cuò)
};
struct LR1TABLE
{
int nStatus; // 狀態(tài)
char CurChar; // 當(dāng)前符號(hào)
ACTIONTYPE ActionType; // 動(dòng)作類別
int nNextStatus; // 下一狀態(tài)
} m_Lr1[MAX_DATA_LEN];
int m_nLr1Len;
/*****************************************************
* 以下是詞法分析文件操作
******************************************************/
// 清空鏈表
void ClearWords(WORDNODE *pHeader)
{
WORDNODE *pNode;
while (pHeader != NULL)
{
pNode = pHeader->pNext;
free(pHeader);
pHeader = pNode;
}
}
// 增加結(jié)點(diǎn)
WORDNODE* AddNode(char c[], WORDNODE *pTail)
{
// c第0個(gè)字節(jié)為單詞類別，第1個(gè)為逗號(hào)，第2個(gè)以后是值
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];
// 讀取數(shù)據(jù)
while (!feof(f)) //未到文件尾
{
fscanf(f, "%s\n", c);
pTail = AddNode(c, pTail);
printf("%s\n", c);
}
// 關(guān)閉文件
fclose(f);
// 增加一個(gè)結(jié)束符
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);
// 讀取數(shù)據(jù)
int nRead;
*nLen = 0;
while (!feof(f))
{
nRead = fread(pChar + *nLen, sizeof(char), MAX_DATA_LEN, f);
*nLen += nRead;
if (nRead < MAX_DATA_LEN) // 文件結(jié)尾
break;
pChar = (char *)realloc(pChar, *nLen + sizeof(char) * MAX_DATA_LEN);
}
// 關(guān)閉文件
fclose(f);
return pChar;
}
bool ReadBnfs()
{
// 讀取文件
int nLen;
char *pChar = ReadFile("Bnf.txt", &nLen);
if (pChar == NULL)
return false;
// 解析出文法產(chǎn)生式
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++)
{
// 狀態(tài)
m_Lr1[nIndex].nStatus = atoi(&pChar[nCur]);
for (; pChar[nCur] != ';'; nCur++);
nCur++;
// 符號(hào)
m_Lr1[nIndex].CurChar = pChar[nCur];
nCur += 2;
// 動(dòng)作類別
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++;
// 狀態(tài)轉(zhuǎn)換
m_Lr1[nIndex].nNextStatus = atoi(&pChar[nCur]);
for (; pChar[nCur] != ';'; nCur++);
}
nIndex++;
}
m_nLr1Len = nIndex;
return true;
}
/********************************************************
* 以下是語(yǔ)法分析部分
*********************************************************/
/************************************************
* 獲取當(dāng)前單詞符號(hào)：
* 如果是整數(shù)或標(biāo)識(shí)符，返回'i'
* 如果是算法，返回算法
*************************************************/
char GetCurChar(WORDNODE *pNode)
{
switch (pNode->byType)
{
case WT_OPERATOR: // 操作符
return pNode->Value[0];
case WT_UINT: // 整數(shù)
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;
}
// 打印狀態(tài)
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(); //初始化狀態(tài)棧
PushInt(0); //0狀態(tài)入棧
InitCharStack(); //初始化符號(hào)棧
PushChar('#',NULL); //'#'符號(hào)入棧
WORDNODE * pNode=pHeader->pNext; //pNode指向當(dāng)前單詞結(jié)點(diǎn)
PrintState(pNode,-1); //打印,-1表示第一步不會(huì)為歸約
int LR1_Index; //記錄查詢LR1分析表后得到的數(shù)組下標(biāo)
while(1)
{
LR1_Index=GetLR1Index(TopInt(),GetCurChar(pNode));
//根據(jù)棧頂狀態(tài)TopInt()和當(dāng)前符號(hào)GetCurChar(pNode)，查詢分析表
if(LR1_Index==-1) return false; //查詢不成功
if(m_Lr1[LR1_Index].ActionType==Push)
{
//查詢LR1分析表得到的動(dòng)作為移進(jìn)
PushInt(m_Lr1[LR1_Index].nNextStatus); //將LR1分析表指示的狀態(tài)移進(jìn)狀態(tài)棧
if(GetCurChar(pNode)=='i') PushChar('i',pNode); //若當(dāng)前單詞為數(shù)字或標(biāo)識(shí)符,將當(dāng)前符號(hào)和當(dāng)前單詞指針移進(jìn)符號(hào)棧,
else PushChar(GetCurChar(pNode),NULL); //若當(dāng)前單詞為運(yùn)算符,只將該運(yùn)算符移進(jìn)符號(hào)棧
pNode=pNode->pNext; //指向下一單詞
PrintState(pNode,-1); //打印狀態(tài),因?yàn)榇瞬綖橐七M(jìn)動(dòng)作,所以不會(huì)用到產(chǎn)生式,所以傳遞參數(shù)-1
}
else if(m_Lr1[LR1_Index].ActionType==Sumup)
{
//查詢LR1分析表得到的動(dòng)作為歸約
for(int i=1;i<=m_Bnf[m_Lr1[LR1_Index].nNextStatus].RLen;i++)
{
//從狀態(tài)棧和符號(hào)棧各彈出 m_Bnf[m_Lr1[LR1_Index].nNextStatus].RLen 個(gè)元素
PopChar();
PopInt();
}
PushChar(m_Bnf[m_Lr1[LR1_Index].nNextStatus].Left,NULL); //將產(chǎn)生式左部的非終結(jié)符入符號(hào)棧
int n=GetLR1Index(TopInt(),TopChar()->cCur);
//根據(jù)狀態(tài)棧棧頂狀態(tài)和符號(hào)棧棧頂符號(hào)查詢LR1分析表，確定轉(zhuǎn)移狀態(tài)
if(n==-1)return false; //查詢不成功
PushInt(m_Lr1[n].nNextStatus); //將LR1分析表指示的轉(zhuǎn)移狀態(tài)入狀態(tài)棧
PrintState(pNode,m_Lr1[LR1_Index].nNextStatus); //打印,m_Lr1[LR1_Index].nNextStatus為此步用到的產(chǎn)生式
}
else
{
////查詢LR1分析表得到的動(dòng)作為接受acc,返回true,語(yǔ)法分析成功
return true;
}
}
}
int main(int argc, char* argv[])
{
// 輸入文件名
char FileName[MAX_DATA_LEN];
printf("請(qǐng)輸入詞法分析的文件名：\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("讀取產(chǎn)生式失敗！\n");
ClearWords(pHeader);
return 0;
}
// 讀取LR(1)分析表
if (!ReadLR1())
{
printf("讀取LR(1)分析表失敗！\n");
ClearWords(pHeader);
return 0;
}
// 語(yǔ)法分析
printf("語(yǔ)法分析過程：\n");
printf("狀態(tài)棧 歸約串 輸入串 產(chǎn)生式\n");
if (LR1Analysis(pHeader))
printf("語(yǔ)法分析成功！\n");
else
printf("語(yǔ)法分析失敗！\n");
// 清空鏈表
ClearWords(pHeader);
getchar();
getchar();
return 0;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -