// 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; // 下一狀態移進(push)或規約(sumup)產生式序號
} 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));//GetCurChar()查詢單詞對應的文法符號
   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)
{
char CurChar;
int LR1Index;
int nBnfIndex;
int nLen;
CHARNODE *Top;

InitIntStack();
PushInt(0);// 狀態棧初始化

InitCharStack();
PushChar('#', NULL);// 文法符號棧初始化

   WORDNODE *pNode = pHeader->pNext;// 單詞鏈表指向第一個單詞

PrintState(pNode, -1);// 打印堆棧

while(pNode){// 輸入串
    CurChar = GetCurChar(pNode);
    LR1Index = GetLR1Index(TopInt(), CurChar);//根據棧頂狀態和當前符號,查詢分析表中的動作序號

    switch (m_Lr1[LR1Index].ActionType){//m_Lr1[]該數組在讀出LR1分析表時產生
    case Push:
      PushInt(m_Lr1[LR1Index].nNextStatus);
      PushChar(m_Lr1[LR1Index].CurChar, pNode);
      pNode = pNode->pNext;
      PrintState(pNode, -1);
      break;
    case Sumup://規約過程！
      nBnfIndex = m_Lr1[LR1Index].nNextStatus;//取出下一個狀態的產生式序號
      nLen = m_Bnf[nBnfIndex].RLen;//取出產生式右部的長度
     
      PopIntN(nLen);
      PopCharN(nLen);//將狀態棧和符號棧的N個元素出棧
      
      PushChar(m_Bnf[nBnfIndex].Left, NULL);//將產生式的左部壓入符號棧
     
      Top = TopChar();//得到符號棧的棧頂
      LR1Index = GetLR1Index(TopInt(), Top->cCur);//根據狀態棧棧頂狀態和符號棧棧頂符號查詢分析表，確定轉移狀態；
      
      if(LR1Index == -1)
       return false;
      else
       PushInt(m_Lr1[LR1Index].nNextStatus);//壓入狀態棧
      PrintState(pNode, nBnfIndex);//打印
                    break;
    case Accept:
      return true;
    default: return false;
    }
}
}

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;
}