编译原理实验报告
编译原理实验报告
LR(0)算法的实现及应用
学生姓名：
学 号：
专 业：计算机科学与技术
学 院：计算机学院
完成时间：2016年11月20
【分工】
胡安忠：整个程序的架构设计；
冯 扬：项目集规范族的构造；
刘 以：分析表中ACTION、GOTO函数的实现；
罗子成：分析表的输出及文法输入函数；
【问题描述】
选题名为LR0算法的实现，LR0分析法的归约过程是规范推到的逆过程，即规范归约的过程。
LR0分析法的作用是对给出一种能根据当前分析栈中符号串（通常以状态表示）就可以唯一确定分析器的动作是移进还是规约和用哪个规则规约，因而也就能唯一确定句柄。并且LR0算法是LR1，SLR1，LALR1算法的基础。
1.2、LR(0)算法研究的现状
LR(0)算法[1]是一种基础的语法分析算法[1]，无论国内还是国外都有对其的研究。由于其限制条件并不适合大多数高级语言的要求，所以在LR0算法基础上对这种规范归约[2]进行了演化出现了LR1[1]，SLR1[1]，LALR1[1]等算法。并且现在主流编译器的词法分析基于LALR[1]原理产生的YACC(Yet Another Compiler —Compiler)，是一个经典的生成语法分析器的工具。输入L语言的YACC[1]规格说明，产生L语言语法分析器。根据产生的L语言语法分析器就可以分析L语言的输入串是否符合语法
【设计的目的】
在做LR(0)文法毕业设计中主要的目的是实现LR(0)算法的实现，主要工作是程序的实现。在程序程序实现过程中主要有一下几个阶段：1总体设计，2核心算法的设计，3数据结构的设计，4编码的实现及调试。
【LR(0)文法的工作原理】
#此部分为小组成员共同完成部分。
LR分析法是一种自下而上进行规范归约的语法分析法，L指从左到右扫描输入符号串，R是指构造最右推导的逆过程。对大多数无二义性上下文无关文法描述的语言都可用它进行有效的分析。主要分析器有LR（0），SLR（1），LR（1），LALR（1）。
LR（0）：在分析的每一步，只需根据当前栈顶状态而不必向前查看输入符号就能确定应采取的分析动作。所能分析的LR（0）文法要求文法的每一个LR（0）的每一个项目集都不包含项目冲突。
1、术语的定义：
句柄：一个句型的最左直接短语称为该句型的句柄，句柄是规范归约的可归约串。
字符串前缀:是指字符串的任意首部。
如 abc 的前缀有 e、a、ab、abc。
活前缀：指规范句型的一个前缀，这种前缀不包含句柄之后的任何号。
若 S′ÞαAωÞαβω 是文法G′中的一个规范推导，G′是 G 的拓广文法，符号串γ是αβ的前缀，则称γ是 G 的，也是 G′的一个活前缀。其中规范推导是最左推导。
最左推导：每次替换是总是选择最左边的非终结符进行替换。
项目：我们把文法 G 中右部添加一个圆点的产生式称为文法 G 的一个 LR(0)项目。 例如：产生式 A→XYZ 有四个 LR(0) 项目：
A→.XYZ
A→X.YZ
A→XY.Z
A→XYZ.
每个项目的含义与圆点的位置有关:
概括地说，圆点的左部表示分析过程的某时刻用该产生式归约时句柄已识别过的部分，圆点右部表示待识别的部分。
只要已扫描过的部分保持可归约成一个规范句型的活前缀，那就意味着所扫描过的部分是正确的。为此，我们把构造识别文法所有活前缀的有限自动机 NFA[1] 的每个状态由 LR(0)项目构成。
项目可以分成归约项目，移进项目，待约项目，和接受项目。
归约项目：形如 A→α. 的项目，其中，aÎ(VTêVN)*。
它表示栈顶已形成句柄 α,下一步动作应该是归约。
移进项目：形如 A→α.aβ的项目。其中，aÎVT，a,βÎ(VTêVN)* 。
它表示期待从输入串中移进一个符号，已待形成句柄。
待约项目：形如 A→α.Bβ的项目。其中，BÎVN，a,βÎ(VTêVN)*。
它表示期待从输入串中进行归约而得到 B，然后进一步得到 A 的全部右部。
接受项目：形如 S’→α. 的项目。S’是文法开始符，以 S’为左部的规则只有一个（通过对一般文法拓广得到的），所以，该归约项目是一个特殊的归约项目，它表示整个句子已分析完毕，可以接受
项目集：是项目根据闭包算法求出的由多个项目组成的集合。
例如文法：S’→S
S→A
S→B
A→aAb
A→c
B→aBb
B→d
假设项目集I初始时是 {S’→.S}，则根据闭包算法时求出的项目集是
CLOSURE(I)={S’→.S, S→.A, S→.B, A→.aAb,A→.c, B→.aBb, B→.d}= I0
其中I0就是I求出的项目集。
2、LR(0)算法的总体原理：
一个LR分析器由 3 个部分组成：
(1) 总控程序：对所有的LR分析器总控程序都是相同的。
(2) 分析表：不同的文法分析表将不同，分析方法将也不同；
(3) 分析栈：文法符号栈和相应的状态栈，存放“历史”和“展望”信息。
图2.1
如图2.1实质上是一个带先进后出存储器（栈）的确定有限状态自动机[1]。它的每一步工作都是由栈顶状态和现行输入符号唯一确定的。其中“状态”综合了历史（已归约和移进的整个符号串）和展望（可能的输入符号）信息。
总控程序根据栈顶状态，和输入的字符串，及已经构造好的分析表来判断输入的当前字符是否是正确的，如果正确就按照分析表中的内容执行下一部的动作。
【LR(0)算法实例笔算结果】
例:文法是
E->TA
A->+TA
A->e
T->FB
B->*FB
B->e
F->(E)
F->i
对上述文法进行拓展分解后，求闭包集，go函数，进而求得项目集规范族
形成如下的图2.2：
图2.2
//每一个方框中代表一个状态，每个状态中包含若干个项目。每个项目圆点后的字符是该状态可以识别的字符。
例如图2.2中的I0状态中的项目S->.S，圆点后的字符是S，说明状态I0可以识别字符S。
带箭头的线为方向线，箭头方向是头，不带箭头的是尾。每条方向线连接两个状态，每条方向线旁边有一个字符。每条方向线表示某一状态遇到一个字符转换到另一个状态。
例如图2.2中在状态I0和I1之间有一个方向线，方向线上有一个字符S，这表示状态I0遇到输入字符S后，转换到I1状态。//
根据上述的状态转换图，又可以生成如下的图2.3
图2.3
如图2.3所示：S表示动作为移进，S后面的数字表示移后进入的状态。
r表示动作归约，R后面的数字表示用哪一个产生式进行归约。
acc表示分析正确。
【算法的设计】
【总体设计】
算法主要包括以下主要模块：
#
#此部分为我所做的整个程序的架构设计。
【数据结构设计】
1、设计数据结构FormulaType，用于存储产生式：
typedef struct
{
char left;//产生式左部
char right[10];//产生式右部
int rightnum;//产生式右部字符数
}FormulaType;
2、设计数据结构GrammerType,用于存储文法
typedef struct
{
FormulaType formula[20];//存储文法中的产生式
int formulanum;//存储文法中的产生式个数
char vt[10];//存储文法中的终结符
char vn[10];//存储文法中的非终结符
int vtnum;//存储文法中的终结符个数
int vnnum;//存储文法中的非终结符个数
char startv;//存储文法的开始符号
}GrammerType;//文法存储结构
3、设计数据结构ItemType,用于项目
typedef struct
{
int fno;//产生式编号
int point;//圆点位置
}ItemType;//项目结构
4、设计数据结构ItemType,用于存储项目集
typedef struct
{
int itemsetno;//项目集编号
int itemnum;//项目集中的项目数
ItemType item[10];//项目集中的项目
}ItemSetType;//项目集存储结构
5、设计数据结构ItemSetsType,用于存储项目集族
typedef struct
{
ItemSetType *set[20];//项目集指针
int itemsetnum;//项目集数
}ItemSetsType;//项目集簇
6、设计数据结构ActionType,用于存储分析表中的动作类型及状态
typedef struct
{
char act;//动作
int state;//状态
}ActionType;//ACTION表结构
7、设计数据结构LRlistType，用于存储分析表
typedef struct
{
ActionType actiontable[20][10];//存储分析表中的actiontable表
int gototable[20][10];//存储分析表中的gototable表
}LRlistType;//分析表
8、设计数据结构stacktype,用于存储分析栈的类型
typedef struct StackType//分析表中，栈的类型
{
int state;//存储状态
char ch;//存储字符
}stacktype;
9、设计数据结构stack,用于定义分析栈
typedef struct Stack//用来定义栈
{
stacktype stackarry[maxsize];
int top;
}stack;
#
【所有代码】
#include
#include
#include
#include
using namespace std;
#pragma warning(disable:4996)
#define maxsize 50
/*****************************************************/
//
// 存储结构
/***************************************************/
struct FormulaType
{
char left;//产生式左部
char right[10];//产生式右部
int rightnum;//产生式右部字符数
};
struct GrammerType
{
FormulaType formula[20];
int formulanum;
char vt[10];
char vn[10];
int vtnum;
int vnnum;
char startv;
};//文法存储结构
struct ItemType
{
int fno;//产生式编号
int point;//圆点位置
};//项目结构
typedef struct
{
int itemsetno;//项目集编号
int itemnum;//项目集中的项目数
ItemType item[10];//项目集中的项目
}ItemSetType;//项目集存储结构
struct ItemSetsType
{
ItemSetType *set[20];//项目集指针
int itemsetnum;//项目集数
};//项目集簇
struct ActionType
{
char act;//动作
int state;//状态
};//ACTION表结构
struct LRlistType
{
ActionType actiontable[20][10];
int gototable[20][10];
};//分析表
struct StackType//分析表中，栈的类型
{
int state;
char ch;
};
typedef struct Stack//用来定义栈
{
StackType stackarry[maxsize];
int top;
}stack;
/*****************************************************/
//
// 函数声明
/***************************************************/
void initgrammer();//初始化文法
void initformula();//产生式初始化
void readvt();//读产生式的终结符
void readvn();//读产生式的非终结符
void readgrammer();//读入产生式
void readformular(char formular[]);//读入产生式
void dispose(char formular[]);//处理输入的产生式
void printgrammer();//输出文法G，检测文法处理格式是否正确
void initsets(ItemSetsType *Cp);//初始化项目集族
ItemSetType *closure(ItemSetType *I);//求项目集I 的闭包
ItemSetType *allotmem(ItemSetType *I);//为项目集I分配内存空间
int index_vt(char ch);//判断ch是否是终结符，如果是则返回终结符在vt[]中的位置，如果不是则返回-1
int index_vn(char ch);//判断ch是否是非终结符，如果是则返回非终结符在vn[]中的位置，如果不是则返回-1
int isbelongitem(ItemSetType *I, int j);//判断第j可产生式，圆点位置为0的项目是否在项目集I中
void printitemset(ItemSetType *I);//打印生成后的项目集
int indexitemset(ItemSetType *Ip);//判断项目集是否属项目集族C,如果IP输入C则返回Ip在C中的编号，否则返回-1
bool isbelong(ItemSetType *I, ItemType p);//判断项目P是否在项目集I中，如果在返回1，否则返回0
int select(char input[], int i);//选出第i个项目集面临的输入符号，放入input[]中，并返回input[]中的字符
bool isbelonginput(char input[], char ch);//判断字符ch是否在字符数组input[]中，如果在则返回1，否则返回0
ItemSetType *go(ItemSetType *I, char ch, ItemSetType *IP);//项目集I面临输入字符ch时，产生式的闭包集放入IP中
void itemsets();//建立分析表
void printitemset(ItemSetType *I);//打印生成后的项目集
void initRlist();//初始化分析
void printRlist();//打印分析表表
void readstring(char str[]);//输入要判断的句子
void initstring(char str[], int num);//初始化要输入的字符串
void initstack(stack &st);//初始化栈
int isEmpty(stack st);//判断栈是否为空,空时返回1，否则返回0
int push(stack &st, int state, char ch);//把状态为state,字符为ch压入栈st中
int pop(stack &st);//出栈操作
int gettop(stack st);//得到栈顶状态元素
void initanlayse();//初始化分析栈
void control(char temp[]);//分析输入的是否正确
void printstack(stack st, char str[], int position);
void defaultinput();//此时用默认的文法
void enterinput();//此时要输入文法才能判
/*****************************************************/
//
// 全局变量
/***************************************************/
GrammerType G;//定义全局变量 文法G
ItemSetsType C;//定义全局变量 项目集族C
LRlistType L;//定义全局变量 分析表L
stack stackexample;//定义全局变量，分析栈
char temp[10] = { '�' };
char sentence[100] = { '�' };
/*****************************************************/
//
// 文法的输入及处理
/***************************************************/
void initgrammer()//初始化文法
{
G.formula[0].left = '$';
G.formulanum = 0;
G.startv = '$';
G.vnnum = 0;
G.vtnum = 0;
for (int i = 0; i<10; i++)
{
G.vn[i] = '�';
G.vt[i] = '�';
}
initformula();//对产生式结构进行初始化
}
void initformula()//产生式初始化
{
int j = 1;
for (int i = 0; i<20; i++)//对产生式进行遍历
{
G.formula[i].rightnum = 0;//对产生式右部个数进行初始化
G.formula[j].left = '�';//对产生式左部进行初始化
j++;
for (int k = 0; k<10; k++)//对产生式右部进行初始化
{
G.formula[i].right[k] = '�';
}
}
}
void readvt()//读产生式的终结符
{
char ch;
int i = 0;
G.vtnum = 0;
printf("please input grammer's vt:");
ch = getchar();
while ('#' != ch)
{
if (ch >= 'a'&&ch <= 'z')
{
G.vt[i] = ch;
i++;
G.vtnum++;
}
ch = getchar();
}
G.vt[i] = '#';//以#号为输入字符串的结束符
G.vtnum++;
setbuf(stdin, NULL);
}
void readvn()//读产生式的非终结符
{
char ch;
int i = 0;
G.vnnum = 0;
printf("please input grammer's vn:");
ch = getchar();
while ('#' != ch)
{
if (ch >= 'A'&&ch <= 'Z')
{
G.vn[i] = ch;
i++;
G.vnnum++;
}
ch = getchar();
}
setbuf(stdin, NULL);
}
void readgrammer()//读入文法
{
char ch = '�';
int formularnumber;
printf("please intput the grammer's number:");
scanf("%d", &formularnumber);//读入要输入的产生式个数，放入文法G.formularnum中
for (int i = 0; i<formularnumber; i++)
{
char formular[20] = { '�' };//缓存清空
printf("please input the %d formular:", i + 1);
readformular(formular);
dispose(formular);
}
}
void readformular(char formular[])//读入产生式
{
char ch;
int i = 0;
ch = getchar();
while ('#' != ch)
{
if ((ch >= 'a'&&ch <= ch="">= 'A'&&ch <= 'Z') || (ch == '-') || (ch == '>') || (ch == '|'))//判断读入的符号是否合法
{
formular[i] = ch;
i++;
}
ch = getchar();
}
}
void dispose(char formular[])//处理读入放入formular[]内的产生式
{
if (G.formulanum == 0)//如果输入的是第一个产生式，则做特殊处理
{
G.formula[0].right[0] = formular[0];
G.formula[0].rightnum = 1;
G.formulanum++;
}
int i = 3;
while ('�' != formular[i])
{
G.formula[G.formulanum].left = formular[0];
int j = 0;
while ('|' != formular[i] && '�' != formular[i])
{
G.formula[G.formulanum].right[j] = formular[i];
i++;
j++;
}
G.formula[G.formulanum].rightnum = j;//产生式右边的个数
printf("n");
G.formulanum++;
if ('�' != formular[i])
i++;
}
/*int m=0;
printf("the grammer's number is:%dn",G.formulanum);
for(m=0;m<G.formulanum;m++)
{
printf("the grammer's %d formular is:",m);
printf("产生式右部符号个数是:%d",G.formula[m].rightnum);
printf("n%c->",G.formula[m].left);//输出产生式的左部符号
int k=0;
for(k=0;k<G.formula[m].rightnum;k++)//输出产生式右部符号
printf("%c",G.formula[m].right[k]);
printf("n");
}*/
}
void printgrammer()//输出文法G，检测文法处理格式是否正确
{
printf("the grammer's startv is:%cn", G.startv);
printf("the grammer's vn is:");
int i = 0;
for (; i<G.vnnum; i++)
printf("%3c", G.vn[i]);
printf("n");
printf("the grammer's vt is:");
for (i = 0; i<G.vtnum; i++)
printf("%3c", G.vt[i]);
printf("n");
int j = 0;
printf("the grammer's number is:%dn", G.formulanum);
for (j = 0; j<G.formulanum; j++)
{
printf("the grammer's %d formular is:", j);
printf("%c->", G.formula[j].left);//输出产生式的左部符号
int k = 0;
for (k = 0; k<G.formula[j].rightnum; k++)//输出产生式右部符号
printf("%c", G.formula[j].right[k]);
printf(" 右部有%d个符号", G.formula[j].rightnum);
printf("n");
}
}
/*****************************************************/
//
// 分析表的生成
/***************************************************/
int index_vn(char ch)//判断ch是否是非终结符，如果是则返回非终结符在vn[]中的位置，如果不是则返回-1
{
int i = 0;
while ('�' != G.vn[i] && G.vn[i] != ch)
{
i++;
}
if (i == G.vnnum)
return -1;
else
return i;
}
int index_vt(char ch)//判断ch是否是终结符，如果是则返回终结符在vt[]中的位置，如果不是则返回-1
{
int i = 0;
while ('�' != G.vt[i] && G.vt[i] != ch)
{
i++;
}
if (i == G.vtnum)
return -1;
else
return i;
}
ItemSetType *allotmen(ItemSetType *I)//为项目集I分配内存空间
{
I = (ItemSetType*)malloc(sizeof(ItemSetType));
I->itemsetno = -1;
I->itemnum = 0;
for (int j = 0; j<10; j++)
{
I->item[j].fno = -1;
I->item[j].point = -1;
}
return I;
}
void initsets()//初始化项目集族
{
C.set[0] = allotmen(C.set[0]);
C.set[0]->itemsetno = 0;
C.set[0]->item[0].fno = 0;
C.set[0]->item[0].point = 0;
C.set[0]->itemnum = 1;
C.set[0] = closure(C.set[0]);
C.itemsetnum = 1;
}
ItemSetType* closure(ItemSetType *I)//求项目集I 的闭包
{
int f;//存放产生式编号
int p;//存放圆点位置
int x;//指向下一个空的项目
// printf("closure 函数内n");
// system("pause");
for (int i = 0; i
{
f = I->item[i].fno;
p = I->item[i].point;
x = I->itemnum - 1;
if (index_vn(G.formula[f].right[p]) != -1)
{
for (int j = 0; j<G.formulanum; j++)
{
if ((G.formula[f].right[p] == G.formula[j].left) && !isbelongitem(I, j))
{
x++;
I->item[x].fno = j;
I->item[x].point = 0;
I->itemnum++;
}//end if
}//end for
}//end if
}//end for
//printitemset(I);
return I;
}//end fuction
int isbelongitem(ItemSetType *I, int j)//判断第j个产生式，圆点位置为0的项目是否在项目集I中
{
int i = 0;
while (i
{
if (I->item[i].fno == j&&I->item[i].point == 0)
break;
else
i++;
}
if (i == I->itemnum)
return 0;//不在项目集I中
else
return 1;//在项目集中I中
}
void printitemset(ItemSetType *I)//打印生成后的项目集
{
cout << "I" << I->itemsetno << ":" << endl;
for (int i = 0; i < I->itemnum; i++)
{
cout << G.formula[I->item[i].fno].left << "->";
for (int j = 0; j <(strlen(g.formula[i->item[i].fno].right) + 1); j++)
{
if (j == I->item[i].point) cout << ".";
cout << G.formula[I->item[i].fno].right[j];
}
cout << endl;
}
}
void printallitemset()
{
for (int i = 0; i<C.itemsetnum; i++)
{
printitemset(C.set[i]);
}
}
int indexitemset(ItemSetType *Ip)//判断项目集是否属项目集族C，如果是则返回IP在项目集族中的编号，否则返回-1
{
bool l;//判断项目集是否属项目集族C的标识
int i;
for (i = 0; i<C.itemsetnum; i++)//循环遍历项目族中的项目集
{
l = 1;
if (C.set[i]->itemnum != Ip->itemnum)//两个项目集中的项目数不相等
l = 0;
if (C.set[i]->itemnum == Ip->itemnum)//如果 第i个项目集的项目数等于项目集Ip中的项目集数
{
for (int j = 0; j
{
if (!isbelong(C.set[i], Ip->item[j]))//函数isbelong()判断项目IP是否在项目集C.set[i]中，如果在返回1，否则返回0
{
l = 0;
}//end if
}//end for
}//end if
if (l == 1)
break;
}//end for
if (1 == l)
return i;
else
return -1;
}//end fuction
bool isbelong(ItemSetType *I, ItemType p)//判断项目P是否在项目集I中，如果在返回1，否则返回0
{
bool l = 0;
for (int i = 0; i
{
if (I->item[i].fno == p.fno&&I->item[i].point == p.point)
l = 1;
}
return l;
}
int select(char input[20], int i)//选出第i个项目集面临的输入符号，放入input[]中，并返回input[]中的字符
{
int j = 0;//记录第i个项目集面临要输入字符的个数
for (int k = 0; k
{
if (!isbelonginput(input, G.formula[C.set[i]->item[k].fno].right[C.set[i]->item[k].point]))
{
input[j] = G.formula[C.set[i]->item[k].fno].right[C.set[i]->item[k].point];
j++;
}//end if
}//end for
return j + 1;
}
bool isbelonginput(char input[20], char ch)//判断字符ch是否在字符数组input[]中，如果在则返回1，否则返回0
{
int i = 0;
while (input[i] != '�'&&input[i] != ch)//遍历数组input
{
i++;
}//end while
if (input[i] == '�')
return 0;
else
return 1;
}
ItemSetType *go(ItemSetType *I, char ch, ItemSetType *IP)//项目集I面临输入字符ch时，产生式的闭包集放入IP中
{
//printf("n现在在go函数里面n");
//printf("面临的输入字符ch是：%cn",ch);
int position = 0;//记录下一个空着的项目的位置
IP = allotmen(IP);//为要生成的项目集分配内存
for (int i = 0; i
{
if (G.formula[I->item[i].fno].right[I->item[i].point] == ch)
{
IP->itemnum++;
IP->item[position].fno = I->item[i].fno;
IP->item[position].point = I->item[i].point + 1;
position++;
}//end if
}//end for
//没有求闭包集前的项目集IP
IP = closure(IP);//求输入ch后的项目集的闭包集
//求过闭包集后的项目集IP
return IP;
}//end fuction
void initRlist()//初始化分析表
{
for (int i = 0; i<20; i++)
{
for (int j = 0; j<10; j++)
{
L.actiontable[i][j].act = ' ';
L.actiontable[i][j].state = -1;
L.gototable[i][j] = -1;
}
}
}
void itemsets()//建立分析表
{
initRlist();
initsets();
int position = C.itemsetnum;//记录下一个要填充的项目集位置
for (int i = 0; i
{
if (C.set[i]->itemnum == 1 && G.formula[C.set[i]->item[0].fno].right[C.set[i]->item[0].point] == '�')//第i个项目集为规约项目，或接受项目
{
if (G.formula[C.set[i]->item[0].fno].left == '$')//用#输入字符串结束
{
L.actiontable[i][G.vtnum - 1].act = 'acc';//用符号@作为输入字符串的接受状态
}
else
{
for (int j = 0; j<G.vtnum; j++)
{
L.actiontable[i][j].act = 'r';
L.actiontable[i][j].state = C.set[i]->item[0].fno;
}//end for
}//end else
}//end if
else//项目集不是规约与接受时，对项目集进行处理
{
char input[20] = { '�' };
int inputnum = select(input, i);
ItemSetType *Ip = 0;
int itemsetno, inputno;//itemsetno是生成临时项目集编号，inputno是要输入字符在vt[]或vn[]中的编号
for (int k = 0; k<inputnum - 1; k++)
{
Ip = go(C.set[i], input[k], Ip);//求项目集C.set[i]面临input[k]时，生成的项目集Ip
//printf("nn刚从go函数出来后，进入itemsets()建立分析表nn");
//printitemset(Ip);
itemsetno = indexitemset(Ip);//indexitemset()函数式为了求IP是否在项目集族中，如果是则返回项目集编号，如果不是则返回-1
//printf("itemsetno等于：%dn",itemsetno);
if (-1 == itemsetno)//Ip不在项目集族中
{
C.set[position] = Ip;
C.set[position]->itemsetno = position;//项目集编号就是在set[]中的下表
C.itemsetnum++;//项目集族中的项目数增加1
//printitemset(C.set[position]);
inputno = index_vt(input[k]);//查找input[k]是否在vt[]中，如果在则返回vt[]中的编号，否则返回-1
if (-1 != inputno)//此时input[k]在vt[]中
{
L.actiontable[i][inputno].act = 's';
L.actiontable[i][inputno].state = position;//项目集的编号用set[]中的下表标识
}
else//此时input[k]在vn[]中
{
inputno = index_vn(input[k]);
L.gototable[i][inputno] = position;//项目集的编号用set[]中的下表标识
}//end else
position++;//项目集位置要加上1
}// end if
else//此时Ip在项目集中
{
free(Ip);
inputno = index_vt(input[k]);//查找input[k]是否在vt[]中，如果在则返回vt[]中的编号，否则返回-1
if (-1 != inputno)//此时input[k]在vt[]中
{
L.actiontable[i][inputno].act = 's';
L.actiontable[i][inputno].state = itemsetno;//项目集的编号用set[]中的下表标识
}
else//此时input[k]在vn[]中
{
inputno = index_vn(input[k]);
L.gototable[i][inputno] = itemsetno;//项目集的编号用set[]中的下表标识
}//end else
}
}//end for
}//end if
}//end for
}//end fuction
void printRlist()//打印分析表
{
int i, j;
printf(" ");//打印四个空格
for (i = 0; i<G.vtnum; i++)
{
printf("%-3c", G.vt[i]);
printf(" ");//打印两个空格
}
for (i = 0; i<G.vnnum; i++)
{
printf("%-3c", G.vn[i]);
printf(" ");//打印两个空格
}
printf("n");//换行
for (i = 0; i<C.itemsetnum; i++)
{
printf("%-2d", i);
printf(" ");//打印两个空格
for (j = 0; j<G.vtnum; j++)
{
if (L.actiontable[i][j].act == 's')
printf("%c%-2d ", L.actiontable[i][j].act, L.actiontable[i][j].state);
if (L.actiontable[i][j].act == ' ')
printf(" ");
if (L.actiontable[i][j].act == 'r')
printf("%c%-2d ", L.actiontable[i][j].act, L.actiontable[i][j].state);
if (L.actiontable[i][j].act == '@')
printf("%c ", L.actiontable[i][j].act);
}
for (j = 0; j<G.vnnum; j++)
{
if (L.gototable[i][j] == -1)
printf(" ");
else
printf("%-2d ", L.gototable[i][j]);
}
printf("n");
}
}//end function
/*****************************************************/
//
// 总控程序
/******************************************************/
/*****************************************************/
//
// 总控选择
/***************************************************/
void enterinput()//此时要输入文法才能判断
{
initgrammer();
readvt();
readvn();
system("cls");
setbuf(stdin, NULL);
readgrammer();
system("cls");
}//end fuction
void main()
{
enterinput();
itemsets();
printallitemset();
setbuf(stdin, NULL);
printRlist();
system("pause");
}
