/*

  * LR 转换表

  * + Goto 记录表

  * + 状态转换表

  */

 #include <stdio.h>

 #include <stdlib.h>

 #include <string.h>

 #include "Common.h"

 #include "Closure.h"

 #include "LRCal.h"

 #include "LRMigrate.h"

 extern char *Grammer[];

 extern char ***GrammerRule;

 /*

  * 创建Goto记录表

  */

 struct Record *CreateRecordTable()

 {

     struct Record *RecordTable = (struct Record *)malloc(sizeof(struct Record));

     memset(RecordTable, '\0', sizeof(struct Record));

     RecordTable->RecordRow = -;

     RecordTable->RecordRowMax = ;

     RecordTable->Record = (int **)malloc(sizeof(int) * );

     memset(RecordTable->Record, '\0', sizeof(int) * );

     return RecordTable;

 }

 /*

  * 记录 Goto[CCi, symbol]->CCj

  * RecordTable : struct Record* 记录表

  * CCi : int 当前项集 ID

  * Symbol : unsigned char 转移符号

  * CCj : int 转移目的项集 ID

  */

 void Record(struct Record *RecordTable, int CCi, unsigned char Symbol, int CCj)

 {

     // [CCi, Symbol] -> CCj

     if (RecordTable->RecordRow < CCi)        // 新请求的位置大于最大项位，需要更新项位

     {

         // 一次分配 32 条记录空间

         if (RecordTable->RecordRowMax <= CCi)    // 新请求的位置超过最大可使用项数，追加新的项表空间

         {

             int NewSize = ((int)(CCi / ) + ) * ;

             int** NewRecordTable = (int**)malloc(NewSize * sizeof(int));

             memset(NewRecordTable, '\0', NewSize * sizeof(int));

             memcpy(NewRecordTable, RecordTable->Record, RecordTable->RecordRowMax * sizeof(int));

             RecordTable->RecordRowMax = NewSize;

             RecordTable->Record = NewRecordTable;

         }

         RecordTable->RecordRow = CCi;

         int *tmp_spc = (int*)malloc(sizeof(int) * );

         memset(tmp_spc, '\0', sizeof(int) * );

         RecordTable->Record[CCi] = tmp_spc;

     }

     if (RecordTable->Record[CCi][Symbol] == CCj)

     {

         // printf("Find Repeat.\n");

     }

     else if (RecordTable->Record[CCi][Symbol] != )

     {

         printf("Find Conflict.\n");

     }

     else

     {

         RecordTable->Record[CCi][Symbol] = CCj;

         printf("[CC%d, %c] -> CC%d\n", CCi, Symbol, CCj);

     }

 }

 /*

  * 查找产生式序号

  * s : unsigned char* 要查找的产生式

  */

 int FindGrammer(unsigned char *s)

 {

     int i;

     for (i = ; Grammer[i][] != '\0'; i++)

     {

         if (strcmp((char*)Grammer[i], (char*)s) == )

         {

             return i;

         }

     }

     return -;

 }

 /*

  * 检查产生式是否为最终接受

  * s : unsigned char* 要检查的产生式

  */

 bool CheckIsAccept(unsigned char *s)

 {

     // 默认第一行语法产生式左非终结符为起始符号

     int l = strlen((char*)s);

     return (Grammer[][] == s[] && s[l - ] == SYM_PLACEHOLDER && s[l - ] == SYM_EOF);

 }

 /*

  * 添加转换项

  * LRTable : struct LRElement** LR转换表

  * StateID : int 状态ID

  * Symbol : unsigned int 转换符号

  * Action : enum ActionEnum 转换动作

  * ActionValue : int 动作值

  */

 void AddState(struct LRElement **LRTable, int StateID, unsigned int Symbol, enum ActionEnum Action, int ActionValue)

 {

     if (LRTable[StateID] != NULL)

     {

         // 不存在 None 和 Accept 参与的冲突

         if (LRTable[StateID][Symbol].Action == None)

         {

             LRTable[StateID][Symbol].Action = Action;

             LRTable[StateID][Symbol].ActionValue = ActionValue;

         }

         else if (!(LRTable[StateID][Symbol].Action == Action && LRTable[StateID][Symbol].ActionValue == ActionValue))

         {

             int ConflictType = (int)(LRTable[StateID][Symbol].Action) + (int)Action;

             switch (ConflictType)

             {

             case :        // 移进-归约

                 printf("Found Shift-Reduce Conflicting.\n");

                 if (Action == Shift)

                 {

                     LRTable[StateID][Symbol].Action = Action;

                     LRTable[StateID][Symbol].ActionValue = ActionValue;

                 }

                 break;

             case :        // 归约-归约

                 printf("Found Reduce-Reduce Conflicting.\n");

                 break;

             default:

                 printf("Found Undefined Conflicting.\n");

                 break;

             }

         }

     }

 }

 /*

  * 通过生成的核心项集 CC 填充状态转移表

  * CC : struct CoreCollection* 核心项集

  * CoreCollectionCount : int 核心项集个数

  * RecordTable : struct Record* Goto记录表

  */

 struct LRElement **LRFillTable(struct CoreCollection *CC, int CoreCollectionCount, struct Record *RecordTable)

 {

     // 虽然 Action 表和 Goto 表的表项存在一定的差异，但是还是可以使用同一个结构体作为元素结构

     // 因为每个核心项集生成一项 LR 转移项，所以 LR 转移表的项数和核心项集的个数是一样的

     // Goto 表不会使用 Action 字段，因为 ActionValue 字段的值必须为正整数

     struct LRElement **LRTable = (struct LRElement**)malloc(sizeof(int) * CoreCollectionCount);

     int LRIndex = ;

     while (LRIndex < CoreCollectionCount)

     {

         LRTable[LRIndex] = (struct LRElement*)malloc(sizeof(struct LRElement) * );

         memset(LRTable[LRIndex], '\0', sizeof(struct LRElement) * );

         LRIndex++;

     }

     struct CoreCollection *CCPtr;

     for (CCPtr = CC; CCPtr != NULL; CCPtr = CCPtr->next) // for each CCi∈CC

     {

         struct Collection *SPtr;

         for (SPtr = CCPtr->S; SPtr != NULL; SPtr = SPtr->next) //  for each item I∈CCi

         {

             unsigned char *Placeholder = (unsigned char*)strchr((char*)SPtr->Expression, SYM_PLACEHOLDER);

             unsigned char PrevSymbol = *(Placeholder + );

             if (*(Placeholder + ) != '\0' && *(Placeholder + ) != '\0' &&

                 (PrevSymbol < 'A' || PrevSymbol > 'Z') &&

                 RecordTable->RecordRow >= CCPtr->id && RecordTable->Record[CCPtr->id][PrevSymbol] != ) //   if I is [A -> β·cγ, α] and goto(CCi, c) = CCj then

             {

                 //    Action[i, c] <- "shift j"

                 AddState(LRTable, CCPtr->id, PrevSymbol, Shift, RecordTable->Record[CCPtr->id][PrevSymbol]);

             }

             else if (CheckIsAccept(SPtr->Expression) == true) //   else if I is [S' -> S·, eof] then

             {

                 //    Action[i, eof] <- "accept"

                 AddState(LRTable, CCPtr->id, SYM_EOF, Accept, );

             }

             else if (*(Placeholder + ) != '\0' && *(Placeholder + ) == '\0') //   else if I is [A -> β·, α] then

             {

                 //    Action[i, α] <- "reduce A -> β"

                 int i = ;

                 unsigned char *SExpr = SPtr->Expression;

                 unsigned char *Expr = (unsigned char*)malloc(strlen((char*)SExpr));

                 while (*SExpr != '\0')

                 {

                     if (*SExpr != SYM_PLACEHOLDER)

                     {

                         Expr[i++] = *SExpr;

                     }

                     SExpr++;

                 }

                 Expr[--i] = '\0';

                 AddState(LRTable, CCPtr->id, PrevSymbol, Reduce, FindGrammer(Expr) + );

             }

         }

         int NTPtr;

         for (NTPtr = ; NTPtr < ; NTPtr++)

         {

             if (GrammerRule[NTPtr] != NULL) //  for each n∈NT

             {

                 if (RecordTable->Record[CCPtr->id] != NULL) //   if goto(CCi, n) = CCj then

                 {

                     LRTable[CCPtr->id][NTPtr].ActionValue = RecordTable->Record[CCPtr->id][NTPtr]; //    Goto[i, n] <- j

                 }

             }

         }

     }

     return LRTable;

 }

 /*

  * 打印状态转移表

  * LRMigrateTable : struct LRElement** LR状态转移表

  * CoreCollectionCount : int 核心项集个数

  */

 void PrintLRMigrate(struct LRElement **LRMigrateTable, int CoreCollectionCount)

 {

     // 为了方便压缩打印，将行链表转换为列链表

     struct LRElement **LRCompression[];

     int index, ItemPtr;

     for (index = ; index < ; index++)

     {

         LRCompression[index] = NULL;

     }

     for (index = ; index < CoreCollectionCount; index++)    // 行

     {

         for (ItemPtr = ; ItemPtr < ; ItemPtr++)            // 列

         {

             if (LRMigrateTable[index][ItemPtr].Action != None || LRMigrateTable[index][ItemPtr].ActionValue != )

             {

                 if (LRCompression[ItemPtr] == NULL)        // 如果该列自始自终没有任何表项，那么不创建该列的指针表

                 {

                     LRCompression[ItemPtr] = (struct LRElement**)malloc(sizeof(int) * CoreCollectionCount);

                     memset(LRCompression[ItemPtr], '\0', sizeof(int) * CoreCollectionCount);

                 }

                 LRCompression[ItemPtr][index] = &LRMigrateTable[index][ItemPtr];

             }

         }

     }

     // 此时列表头若为 NULL 则该列无数据

     printf("State");

     for (index = ; index < ; index++)

     {

         if (LRCompression[index] != NULL)

         {

             if (index != )

             {

                 printf("\t%c", index);

             }

             else

             {

                 printf("\t<eof>");

             }

         }

     }

     printf("\n");

     for (index = ; index < CoreCollectionCount; index++)

     {

         printf("%d", index);

         for (ItemPtr = ; ItemPtr < ; ItemPtr++)

         {

             if (LRCompression[ItemPtr] != NULL)

             {

                 if (LRCompression[ItemPtr][index] != NULL)

                 {

                     printf("\t");

                     switch (LRCompression[ItemPtr][index]->Action)

                     {

                     case None:

                         // printf("");

                         break;

                     case Shift:

                         printf("s");

                         break;

                     case Reduce:

                         printf("r");

                         break;

                     case Accept:

                         printf("acc");

                         break;

                     }

                     if (LRCompression[ItemPtr][index]->Action != Accept)

                     {

                         printf("%d", LRCompression[ItemPtr][index]->ActionValue);

                     }

                 }

                 else

                 {

                     printf("\t");

                 }

             }

         }

         printf("\n");

     }

 }