#include?“stdio.h“
#include?“stdlib.h“
#define?MaxRuleNum?8
#define?MaxVnNum?5
#define?MaxVtNum?5
#define?MaxStackDepth?20
#define?MaxPLength?20
#define?MaxStLength?50
struct?pRNode?/*產生式右部結構*/
{
?int?rCursor;?/*右部序號*/
?struct?pRNode?*next;
};
struct?pNode?/*產生式結點結構*/
{
?int?lCursor;?/*左部符號序號*/
?int?rLength;?/*右部長度*/
?/*注當rLength?=?1?時，rCursor?=?-1為空產生式*/
?struct?pRNode?*rHead;?/*右部結點頭指針*/
};
char?Vn[MaxVnNum?+?1];?/*非終結符集*/
int?vnNum;
char?Vt[MaxVtNum?+?1];?/*終結符集*/
int?vtNum;
struct?pNode?P[MaxRuleNum];?/*產生式*/
int?PNum;?/*產生式實際個數*/
char?buffer[MaxPLength?+?1];
char?ch;?/*符號或string?ch;*/
char?st[MaxStLength];?/*要分析的符號串*/

struct?collectNode?/*集合元素結點結構*/
{
?int?nVt;?/*在終結符集中的下標*/
?struct?collectNode?*next;
};
struct?collectNode*?first[MaxVnNum?+?1];?/*first集*/
struct?collectNode*?follow[MaxVnNum?+?1];?/*follow集*/
struct?collectNode*?select[MaxVnNum?+?1];?/*select集*/

int?analyseTable[MaxVnNum?+?1][MaxVtNum?+?1?+?1];
/*預測分析表存放為產生式的編號，+1用于存放結束符，多+1用于存放#（-1）*/
int?analyseStack[MaxStackDepth?+?1];?/*分析棧*/
int?topAnalyse;?/*分析棧頂*/
/*int?reverseStack[MaxStackDepth?+?1];?/*顛倒順序棧*/
/*int?topReverse;?/*倒敘棧頂*/

void?Init（）;/*初始化*/
int?IndexCh（char?ch）;/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/
void?InputVt（）;?/*輸入終結符*/
void?InputVn（）;/*輸入非終結符*/
void?ShowChArray（char*?collect?int?num）;/*輸出Vn或Vt的內容*/
void?InputP（）;/*產生式輸入*/
bool?CheckP（char?*?st）;/*判斷產生式正確性*/
void?First（int?U）;/*計算first集U->xx...*/
void?AddFirst（int?U?int?nCh）;?/*加入first集*/
bool?HaveEmpty（int?nVn）;?/*判斷first集中是否有空（-1）*/
void?Follow（int?V）;/*計算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（）;/*計算first和follow*/
void?CreateAT（）;/*構造預測分析表*/
void?ShowAT（）;/*輸出分析表*/
void?Identify（char?*st）;/*主控程序為操作方便*/
/*分析過程顯示操作為本行變換所用，與教程的顯示方式不同*/
void?InitStack（）;/*初始化棧及符號串*/
void?ShowStack（）;/*顯示符號棧中內容*/
void?Pop（）;/*棧頂出棧*/
void?Push（int?r）;/*使用產生式入棧操作*/
void?Init（）;/*初始化*/
void?Select（）;
void?ShowSelect（）;

int?checkselect（）;

void?main（void）
{
?char?todoch;
?Init（）;
?InputVn（）;
?InputVt（）;
?InputP（）;
?getchar（）;
?FirstFollow（）;
?printf（“所得first集為：“）;
?ShowCollect（first）;
?printf（“所得follow集為：“）;
?ShowCollect（follow）;
?printf（“所得select集為:“）;
?Select（）;
?ShowSelect（）;
?if（checkselect（））
?{
	?printf（“\n該文法是LL1\n\n“）;
?CreateAT（）;
?ShowAT（）;
?todo?=?‘y‘;
?while（‘y‘?==?todo）
?{
??printf（“\n是否繼續進行句型分析？（y?/?n）:“）;
??todo?=?getchar（）;
??while（‘y‘?!=?todo?&&?‘n‘?!=?todo）
??{
???printf（“\n（y?/?n）??“）;
???todo?=?getchar（）;
??}
??if（‘y‘?==?todo）
??{
???int?i;
???InitStack（）;
???printf（“請輸入符號串（以#結束）?:?“）;
???ch?=?getchar（）;
???i?=?0;
???while（‘#‘?!=?ch?&&?i????{
????if（‘?‘?!=?ch?&&?‘\n‘?!=?ch）
????{
?????st[i++]?=?ch;
????}
????ch?=?getchar（）;
???}
???if（‘#‘?==?ch?&&?i????{
????st[i]?=?ch;
????Identify（st）;
???}
???else?
????print