/*************************************** LL1.H ***************************************/

/*--------------------聲明-----------------------*/
/*
 VC6.0下運(yùn)行通過(guò)

此程序?yàn)楸救丝嘈乃觯?qǐng)您在閱讀的時(shí)候，尊重本人的
勞動(dòng)。可以修改，但當(dāng)做的每一處矯正或改進(jìn)時(shí)，請(qǐng)將改進(jìn)
方案，及修改部分發(fā)給本人
(修改部分請(qǐng)注名明：修改字樣)

 Email: jink2005@sina.com
 QQ: 272576320 ——初稿完成：06-5-27 jink2005

補(bǔ)充：
程序存在問(wèn)題：
 (1) follow集不能處理：U->xVyVz的情況;
 (2) 因本人偷懶，本程序?yàn)榧尤胛姆ㄅ袛啵? 輸入的文法必須為L(zhǎng)L(1)文法;
 (3) 您可以幫忙擴(kuò)充：消除左遞歸，提取公因子等函數(shù)
 (4) ……
*/
/*-----------------------------------------------*/
/*參考書(shū)《計(jì)算機(jī)編譯原理——編譯程序構(gòu)造實(shí)踐》
 LL(1)語(yǔ)法分析,例1:
 ERTWF#
 +*()i#
 文法G[E]:(按此格式輸入)
 1 E -> TR
 2 R -> +TR
 3 R ->
 4 T -> FW
 5 W -> * FW
 6 W ->
 7 F -> (E)
 8 F -> i
 分析例句：i*(i)# , i+i#
 例2：
 編譯書(shū)5.6例題1
  SHMA#
  adbe# 
 S->aH
 H->aMd
 H->d
 M->Ab
 M->
 A->aM
 A->e
 分析例句：aaabd#  
*/

/*-------------------LL(1)語(yǔ)法分析--------------------*/
#include "stdio.h"
#include "stdlib.h"

#define MaxRuleNum 8
#define MaxVnNum 5
#define MaxVtNum 5
#define MaxStackDepth 20
#define MaxPLength 20
#define MaxStLength 50
/*-----------------main struct define-----------------*/
/*
聲明：非終結(jié)符序號(hào) = 100 + Vn的下標(biāo)
  終結(jié)符序號(hào) = Vn的下標(biāo)
*/
/*++++++++++文法結(jié)構(gòu)++++++++++*/
struct pRNode /*產(chǎn)生式右部結(jié)構(gòu)*/
{
 int rCursor; /*右部序號(hào)*/
 struct pRNode *next;
};

struct pNode /*產(chǎn)生式結(jié)點(diǎn)結(jié)構(gòu)*/
{
 int lCursor; /*左部符號(hào)序號(hào)*/
 int rLength; /*右部長(zhǎng)度*/
 /*注當(dāng)rLength = 1 時(shí)，rCursor = -1為空產(chǎn)生式*/
 struct pRNode *rHead; /*右部結(jié)點(diǎn)頭指針*/
};

char Vn[MaxVnNum + 1]; /*非終結(jié)符集*/
int vnNum;
char Vt[MaxVtNum + 1]; /*終結(jié)符集*/
int vtNum;
struct pNode P[MaxRuleNum]; /*產(chǎn)生式*/
int PNum; /*產(chǎn)生式實(shí)際個(gè)數(shù)*/
char buffer[MaxPLength + 1];
char ch; /*符號(hào)或string ch;*/
char st[MaxStLength]; /*要分析的符號(hào)串*/

/*++first and follow collect struct++*/
struct collectNode /*集合元素結(jié)點(diǎn)結(jié)構(gòu)*/
{
 int nVt; /*在終結(jié)符集中的下標(biāo)*/
 struct collectNode *next;
};

struct collectNode* first[MaxVnNum + 1]; /*first集*/
struct collectNode* follow[MaxVnNum + 1]; /*follow集*/

/*+++++++++++++analysis table struct++++++++++++++++*/
int analyseTable[MaxVnNum + 1][MaxVtNum + 1 + 1];
/*預(yù)測(cè)分析表存放為產(chǎn)生式的編號(hào)，+1用于存放結(jié)束符，多+1用于存放#(-1)*/

/*+++++++++++++++analysis stack struct++++++++++++++*/
int analyseStack[MaxStackDepth + 1]; /*分析棧*/
int topAnalyse; /*分析棧頂*/
/*int reverseStack[MaxStackDepth + 1]; /*顛倒順序棧*/
/*int topReverse; /*倒敘棧頂*/

/*------------------function declare---------------*/
void Init();/*初始化*/
int IndexCh(char ch);
/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/
void InputVt(); /*輸入終結(jié)符*/
void InputVn();/*輸入非終結(jié)符*/
void ShowChArray(char* collect, int num);/*輸出Vn或Vt的內(nèi)容*/
void InputP();/*產(chǎn)生式輸入*/
bool CheckP(char * st);/*判斷產(chǎn)生式正確性*/
void First(int U);/*計(jì)算first集,U->xx...*/
void AddFirst(int U, int nCh); /*加入first集*/
bool HaveEmpty(int nVn); /*判斷first集中是否有空(-1)*/
void Follow(int V);/*計(jì)算follow集*/
void AddFollow(int V, int nCh, int kind);/*加入follow集，
 kind = 0表加入follow集，kind = 1加入first集*/
void ShowCollect(struct collectNode **collect);/*輸出first或follow集*/
void FirstFollow();/*計(jì)算first和follow*/
void CreateAT();/*構(gòu)造預(yù)測(cè)分析表*/
void ShowAT();/*輸出分析表*/
void Identify(char *st);/*主控程序,為操作方便*/
/*分析過(guò)程顯示操作為本行變換所用，與教程的顯示方式不同*/
void InitStack();/*初始化棧及符號(hào)串*/
void ShowStack();/*顯示符號(hào)棧中內(nèi)容*/
void Pop();/*棧頂出棧*/
void Push(int r);/*使用產(chǎn)生式入棧操作*/

/********************************* LL1.CPP *************************************/

/*-----------------------------------------------*/
#include "LL1.h"
/*-------------------main function--------------------*/
void main(void)
{
 char todo,ch;
 
 Init();

 InputVn();
 InputVt();
 InputP();

 getchar();

 FirstFollow();
 printf("所得first集為：");
 ShowCollect(first);
 printf("所得follow集為：");
 ShowCollect(follow);

 CreateAT();
 ShowAT();

 todo = 'y';
 while('y' == todo)
 {
  printf("\n是否繼續(xù)進(jìn)行句型分析？(y / n):");
  todo = getchar();
  while('y' != todo && 'n' != todo)
  {
   printf("\n(y / n)? ");
   todo = getchar();
  }
  if('y' == todo)
  {
   int i;
   InitStack();
   printf("請(qǐng)輸入符號(hào)串(以#結(jié)束) : ");
   ch = getchar();
   i = 0;
   while('#' != ch && i < MaxStLength)
   {
    if(' ' != ch && '\n' != ch)
    {
     st[i++] = ch;
    }
    ch = getchar();
   }
   if('#' == ch && i < MaxStLength)
   {
    st[i] = ch;
    Identify(st);
   }
   else 
    printf("輸入出錯(cuò)！\n");
  }
 }

 getchar();
}
/*---------------function definition------------------*/
void Init()
{
 int i,j;
 vnNum = 0;
 vtNum = 0;
 PNum = 0;
 for(i = 0; i <= MaxVnNum; i++)
  Vn[i] = '\0';
 for(i = 0; i <= MaxVtNum; i++)
  Vt[i] = '\0';
 for(i = 0; i < MaxRuleNum; i++)
 {
  P[i].lCursor = NULL;
  P[i].rHead = NULL;
  P[i].rLength = 0;
 }
 PNum = 0;
 for(i = 0; i <= MaxPLength; i++)
  buffer[i] = '\0';
 for(i = 0; i < MaxVnNum; i++)
 {
  first[i] = NULL;
  follow[i] = NULL;
 }
 for(i = 0; i <= MaxVnNum; i++)
 {
  for(j = 0; j <= MaxVnNum + 1; j++)
   analyseTable[i][j] = -1;
 }
}
/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/
int IndexCh(char ch) 
{
 int n;
 n = 0; /*is Vn?*/
 while(ch != Vn[n] && '\0' != Vn[n])
  n++;
 if('\0' != Vn[n])
  return 100 + n;
 n = 0; /*is Vt?*/
 while(ch != Vt[n] && '\0' != Vt[n])
  n++;
 if('\0' != Vt[n])
  return n;
 return -1;
}
/*輸出Vn或Vt的內(nèi)容*/
void ShowChArray(char* collect)
{
 int k = 0;
 while('\0' != collect[k])
 {
  printf(" %c ", collect[k++]);
 }
 printf("\n");
}
/*輸入非終結(jié)符*/
void InputVn()
{
 int inErr = 1;
 int n,k;
 char ch;
 while(inErr)
 {
  printf("\n請(qǐng)輸入所有的非終結(jié)符，注意：");
  printf("請(qǐng)將開(kāi)始符放在第一位，并以#號(hào)結(jié)束:\n"); 
  ch = ' ';
  n = 0;
  /*初始化數(shù)組*/
  while(n < MaxVnNum)
  {
   Vn[n++] = '\0';
  }
  n = 0;
  while(('#' != ch) && (n < MaxVnNum))
  {
   if(' ' != ch && '\n' != ch && -1 == IndexCh(ch))
   {
    Vn[n++] = ch;
    vnNum++;
   }
   ch = getchar();
  }
  Vn[n] = '#'; /*以“#”標(biāo)志結(jié)束用于判斷長(zhǎng)度是否合法*/
  k = n; /*k用于記錄n以便改Vn[n]='\0'*/
  if('#' != ch)
  {
   if( '#' != (ch = getchar()))
   {
    while('#' != (ch = getchar()))
     ;
    printf("\n符號(hào)數(shù)目超過(guò)限制！\n");
    inErr = 1;
    continue;
   }
  }
  /*正確性確認(rèn)，正確則，執(zhí)行下下面，否則重新輸入*/
  Vn[k] = '\0';
  ShowChArray(Vn);
  ch = ' ';
  while('y' != ch && 'n' != ch)
  {
   if('\n' != ch)
   {
    printf("輸入正確確認(rèn)?(y/n):");
   }
   scanf("%c", &ch);
  }
  if('n' == ch)
  {
   printf("錄入錯(cuò)誤重新輸入！\n");
   inErr = 1;
  }
  else
  {
   inErr = 0;
  }
 }
}
/*輸入終結(jié)符*/
void InputVt()
{
 int inErr = 1;
 int n,k;
 char ch;
 while(inErr)
 {
  printf("\n請(qǐng)輸入所有的終結(jié)符，注意：");
  printf("以#號(hào)結(jié)束:\n"); 
  ch = ' ';
  n = 0;
  /*初始化數(shù)組*/
  while(n < MaxVtNum)
  {
   Vt[n++] = '\0';
  }
  n = 0;
  while(('#' != ch) && (n < MaxVtNum))
  {
   if(' ' != ch && '\n' != ch && -1 == IndexCh(ch))
   {
    Vt[n++] = ch;
    vtNum++;
   }
   ch = getchar();
  }
  Vt[n] = '#'; /*以“#”標(biāo)志結(jié)束*/
  k = n; /*k用于記錄n以便改Vt[n]='\0'*/
  if('#' != ch)
  {
   if( '#' != (ch = getchar()))
   {
    while('#' != (ch = getchar()))
     ;
    printf("\n符號(hào)數(shù)目超過(guò)限制！\n");
    inErr = 1;
    continue;
   }
  }
  /*正確性確認(rèn)，正確則，執(zhí)行下下面，否則重新輸入*/
  Vt[k] = '\0';
  ShowChArray(Vt);
  ch = ' ';
  while('y' != ch && 'n' != ch)
  {
   if('\n' != ch)
   {
    printf("輸入正確確認(rèn)?(y/n):");
   }
   scanf("%c", &ch);
  }
  if('n' == ch)
  {
   printf("錄入錯(cuò)誤重新輸入！\n");
   inErr = 1;
  }
  else
  {
   inErr = 0;
  }
 }
}
/*產(chǎn)生式輸入*/
void InputP()
{
 char ch;
 int i = 0, n,num;
 printf("請(qǐng)輸入文法產(chǎn)生式的個(gè)數(shù)：");
 scanf("%d", &num);
 PNum = num;
 getchar(); /*消除回車(chē)符*/
 printf("\n請(qǐng)輸入文法的%d個(gè)產(chǎn)生式,并以回車(chē)分隔每個(gè)產(chǎn)生式：", num);
 printf("\n");
 while(i < num)
 {
  printf("第%d個(gè)：", i);
  /*初始化*/
  for(n =0; n < MaxPLength; n++)
   buffer[n] = '\0';
  /*輸入產(chǎn)生式串*/
  ch = ' ';
  n = 0;
  while('\n' != (ch = getchar()) && n < MaxPLength)
  {
   if(' ' != ch)
    buffer[n++] = ch;    
  }
  buffer[n] = '\0';
/*  printf("%s", buffer);*/
  if(CheckP(buffer))
  {
   /*填寫(xiě)入產(chǎn)生式結(jié)構(gòu)體*/
   pRNode *pt, *qt;
   P[i].lCursor = IndexCh(buffer[0]);
   pt = (pRNode*)malloc(sizeof(pRNode));
   pt->rCursor = IndexCh(buffer[3]);
   pt->next = NULL;
   P[i].rHead = pt;
   n = 4;
   while('\0' != buffer[n])
   {
    qt = (pRNode*)malloc(sizeof(pRNode));
    qt->rCursor = IndexCh(buffer[n]);
    qt->next = NULL;
    pt->next = qt;
    pt = qt;
    n++;
   }
   P[i].rLength = n - 3;
   i++;
   /*調(diào)試時(shí)使用*/
  }
  else
   printf("輸入符號(hào)含非法在成分，請(qǐng)重新輸入！\n");
 }
}
/*判斷產(chǎn)生式正確性*/
bool CheckP(char * st)
{
 int n;
 if(100 > IndexCh(st[0]))
  return false;
 if('-' != st[1])
  return false;
 if('>' != st[2])
  return false;
 for(n = 3; '\0' != st[n]; n ++)
 {
  if(-1 == IndexCh(st[n]))
   return false;
 }
 return true;
}
/*====================first & follow======================*/
/*計(jì)算first集,U->xx...*/
void First(int U)
{
 int i,j;
 for(i = 0; i < PNum; i++)
 {
  if(P[i].lCursor == U)
  {
   struct pRNode* pt;
   pt = P[i].rHead;
   j = 0;
   while(j < P[i].rLength)
   {
    if(100 > pt->rCursor)
    {
     /*注:此處因編程出錯(cuò),使空產(chǎn)生式時(shí)
     rlength同樣是1,故此處同樣可處理空產(chǎn)生式*/
     AddFirst(U, pt->rCursor);
     break;
    }
    else
    {
     if(NULL == first[pt->rCursor - 100])
     {
      First(pt->rCursor);
     }     
     AddFirst(U, pt->rCursor);
     if(!HaveEmpty(pt->rCursor))
     {
      break;