一、实验目的
通过实验，加深数据挖掘中一个重要方法——关联分析的认识，其经典算法为apriori算法，了解影响apriori算法性能的因素，掌握基于apriori算法理论关联分析的原理和方法。
二、实验内容
对一数据集用apriori算法做关联分析，用matlab实现。
三、方法手段
关联规则挖掘的一个典型例子是购物篮分析。市场分析员要从大量的数据中发现顾客放入其购物篮中的不同商品之间的关系。如果顾客买牛奶，他也购买面包的可能性有多大？ 什么商品组或集合顾客多半会在一次购物时同时购买？例如，买牛奶的顾客有80%也同时买面包，或买铁锤的顾客中有70%的人同时也买铁钉，这就是从购物篮数据中提取的关联规则。分析结果可以帮助经理设计不同的商店布局。一种策略是：经常一块购买的商品可以放近一些，以便进一步刺激这些商品一起销售，例如，如果顾客购买计算机又倾向于同时购买财务软件，那么将硬件摆放离软件陈列近一点，可能有助于增加两者的销售。另一种策略是：将硬件和软件放在商店的两端，可能诱发购买这些商品的顾客一路挑选其他商品。

关联规则是描述数据库中数据项之间存在的潜在关系的规则,形式为 ,其中 , 是数据库中的数据项.数据项之间的关联规则即根据一个事务中某些项的出现,可推导出另一些项在同一事务中也出现。
四、Apriori算法
1.算法描述
Apriori算法的第一步是简单统计所有含一个元素的项集出现的频率,来决定最大的一维项目集。在第k步,分两个阶段,首先用一函数sc_candidate(候选),通过第(k-1)步中生成的最大项目集Lk-1来生成侯选项目集Ck。然后搜索数据库计算侯选项目集Ck的支持度. 为了更快速地计算Ck中项目的支持度, 文中使用函数count_support计算支持度。

Apriori算法描述如下：

(1)  C1={candidate1-itemsets};

(2)  L1={c∈C1|c.count≥minsupport};

(3)  for(k=2,Lk-1≠Φ,k++)　　 //直到不能再生成最大项目集为止

(4)  Ck=sc_candidate(Lk-1);　     //生成含k个元素的侯选项目集

(5)  for all transactions  t∈D        //办理处理

(6)  Ct=count_support(Ck,t);　     //包含在事务t中的侯选项目集

(7)  for all candidates c∈Ct

(8)  c.count=c.count+1;

(9)  next

(10) Lk={c∈Ck|c.count≥minsupport};

(11) next

(12) resultset=resultset∪Lk

其中, D表示数据库；minsupport表示给定的最小支持度；resultset表示所有最大项目集。

Sc_candidate函数

该函数的参数为Lk-1,即: 所有最大k-1维项目集,结果返回含有k个项目的侯选项目集Ck。事实上,Ck是k维最大项目集的超集,通过函数count_support计算项目的支持度,然后生成Lk。

该函数是如何完成这些功能的, 详细说明如下:

首先, 通过对Lk-1自连接操作生成Ck,称join(连接)步,该步可表述为:

insert into Ck　

select P.item1,P.item2,…,P.itemk-1,Q.itemk-1 from Lk-1P,Lk-1Q　

where P.item1=Q.item1,…,P.itemk-2=Q.itemk-2,P.itemk-1<Q.itemk-1

若用集合表示:Ck={X∪X’|X,X’∈Lk-1,|X∩X’|=k-2}

然后,是prune(修剪)步,即对任意的c,c∈Ck, 删除Ck中所有那些(k-1)维子集不在Lk-1中的项目集,得到侯选项目集Ck。表述为：

for all itemset　c∈Ck　　

for all (k-1)维子集s of c　

if(s不属于Lk-1) then delete c from Ck;

用集合表示:Ck={X∈Ck|X的所有k-1维子集在Lk-1中}
2.Apriori算法的举例
示例说明Apriori算法运作过程，有一数据库D, 其中有四个事务记录, 分别表示为



在Apriori算法中每一步创建该步的侯选集。统计每个侯选项目集的支持度,并和预定义的最小支持度比较,来确定该步的最大项目集。

首先统计出一维项目集,即C1.这里预定义最小支持度minsupport=2,侯选项目集中满足最小支持度要求的项目集组合成最大的1-itemsets。为生成最大的2-itemsets,使用了sc_candidate函数中join步,即：L1joinL1，并通过prune步删除那些C2的那些子集不在L1中的项目集。生成了侯选项目集C2。搜索D中4个事务,统计C2中每个侯选项目集的支持度。然后和最小支持度比较,生成L2。侯选项目集C3是由L2生成.要求自连接的两个最大2-itemsets中,第一个项目相同,在L2中满足该条件的有{I2,I3},{I2,I5}.这两个集合经过join步后, 产生集合{I2，I3，I5}.在prune步中,测试{I2，I3，I5}的子集{I3，I5},{I2，I3},{I2，I5}是否在L2中,由L2可以知道{I3,I5},{I2,I3},{I2,I5}本身就是最大2-itemsets.即{I2,I3,I5}的子集都是最大项目集.那么{I2,I3,I5}为侯选3-itemset.然后搜索数据库中所有事务记录,生成最大的3-tiemsets L3。此时, 从L3中不能再生成侯选4-itemset 。Apriori算法结束.
算法的图例说明


五、实验结果
test.txt格式及内容如下：



实验结果如下：


六、实验总结
Apriori算法可以很有效地找出数据集中存在的关联规则且能找出最大项的关联规则，但从以上的算法执行过程可以看到Apriori算法的缺点:

第一,在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素；第二,每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求一种能减少这种系统1/O开销的更为快捷的算法。
七、实验程序
function my_apriori(X,minsup)  
clc;
%%%%主函数，输入X数据集，判断产生大于minsup最小支持度的关联规则
%%%%%%%%%%%%%%%%%%%%%%%%%%打开test.txt文件
file = textread('test.txt','%s','delimiter','\n','whitespace','');
[m,n]=size(file);
for i=1:m
    words=strread(file{i},'%s','delimiter',' ');
    words=words';
    X{i}=words;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
minsup=0.3; %预先定义支持度

[m,N]=size(X); %求X的维数
temp=X{1}; %用已暂存变量存储所有不同项集
for i=2:N
   temp=union(temp,X{i}); %找出所有不同项（种类）
end    

%%%%%%%%%%%%%%%%%%%%找出k-频繁项
L=Sc_candidate(temp);    %找出2-项候选项集
sum=1;     %统计满足条件的最多项集
while(~isempty(L{1})) %循环终止条件为第k次频繁项集为空
    sum=sum+1;
    C=count_support(L,X,minsup);   %挑选出满足最小支持度的k-频繁项
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    sprintf('%s%d%s','满足要求的',sum,'次频繁项集依次为')  %显
    for i=1:size(C,1)                                    %示
        disp(C{i,1});                                   %部
    end                                               %分
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    L=gen_rule(C);    %依次产生k-频繁项(依据apriori算法规则）
End


%%%%%%%%%%%%%%%%%%%%%%%%各个子程序如下
function y=cell_union(X,Y)   %实现两cell元组合并功能,由k-1项集增加到k项集函数
[m,n]=size(X);
if(~iscellstr(X)) %判断X是否元组
    L{1}=X;
    L{1,2}=Y;
else
    L=X;
    L{1,n+1}=Y;
end
y=L;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function y=count_support(L,X,minsup)
%找出符合大于支持度sup的候选集,L为候选集，X为总数据集
X=X';%转置
%%%%%%%%%%%%%%%%%统计频繁项
[m,n]=size(L);
[M,N]=size(X);
count=zeros(m,1);
for i=1:m
    for j=1:M
        if(ismember(L{i},X{j}))
            count(i)=count(i)+1;
        end
    end
end

%%%%%%%%%%%删除数据表中不频繁的项
p=1;
C=cell(1);
for i=1:m
    if(count(i)>minsup*M)         %小于支持度的项为不频繁数，将删除,大于的保留
        C{p}=L{i};
        p=p+1;
    end
end
y=C';

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function y=gen_rule(C) %apriori算法规则判断是否产生k-候选项集
if(~isempty(C{1})) %判断C是否为空
    [M,N]=size(C);
    [m,n]=size(C{1});
    temp1=C;
    L=cell(1);
    for i=1:M
        temp2{i}=temp1{i}{n};
        temp1{i}{n}=[];
    end
    p=1;
    for i=1:M
        for j=i+1:M
            if(isequal(temp1{i},temp1{j}))   %判断前k-1项候选集是否相等
                L{p}=cell_union(C{i},temp2{j});  %若相等，则增加至k-项集
                p=p+1;
            end
        end
    end
    y=L';
else
    y=cell(1);%否则y返回空
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function y=Sc_candidate(C)   %产生2-项候选集函数
C=C'; %转置
[m,n]=size(C);
bcount=zeros(m*(m-1)/2,1);
L=cell(m*(m-1)/2,1);
p=1;
for i=1:m-1   %注意
    for j=i+1:m
        L{p}=cell_union(C{i},C{j}); %产生2-项候选集
        p=p+1;
    end
end
y=L;

function y=count_support(L,X,minsup)
%找出符合大于支持度sup的候选集,L为候选集，X为总数据集
X=X';%转置
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%统计频繁项
[m,n]=size(L);
[M,N]=size(X);
count=zeros(m,1);
for i=1:m
    for j=1:M
        if(ismember(L{i},X{j}))
            count(i)=count(i)+1;
        end
    end
end

%%%%%%%%%%%%%%%%%%%%%%%删除数据表中不频繁的项
p=1;
C=cell(1);
for i=1:m
    if(count(i)>minsup*M)         %小于支持度的项为不频繁数，将删除,大于的保留
        C{p}=L{i};
        p=p+1;
    end
end
y=C'; 

前文：
最近课程实验有点多且难，上一次编译原理做完词法分析器后，这一次终于把语法分析器给撸出来了。通过这一次的实验发现，词法分析器做的有很多不严谨的地方，因为词法分析器不应该是一个独立的，而是需要和语法分析器甚至下面的语义相关联，所以在一开始我们就应该对其有一定的规划，但是刚开始的时候没有这个意识，在网上看了相关代码之后只是觉得符合要求就提交上去了。于是觉得应该对词法分析器加以改进，故重新撸了一篇词法分析器的博文。这一次是语法分析器，先来看看我们老师的要求吧。
题目要求


可以看到这里要求递归下降分析，这个就不多说了。还有一个拓展要求，要求错误恢复和提示，这个依据恐慌模式来做，不懂？可以看一下这个视频。
代码分析：
一下代码是我昨晚一点多撸完的，感觉太臃肿了，应该分成项目来做，至少也得多个头文件，但是由于时间太赶，先原文贴出。
代码有点偏长，九百多行，其中大部分是词法分析器的，所以最好看一下我的上一篇关于词法分析器的代码。
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>

int  wordanalysis();
void Irparser();
void yucu();
void statement();
void expression();
void term();
void factor();
void One();
void Two();
void Three();
void is_equal();
void not_equal();
void is_four_cal();
void not_four_cal();
void is_colon();
void not_right();
void not_biaozhifu();


using namespace std;


//BEGIN
//
//
//a = 10;
//b = a + 10;
//e = a + b
//end#


//保留字的种别码。从1开始到25
//出现过的标识符的种别码设为26
//未出现过的标识符种别码为52，将该标识符保存到标识符表中
//数字种别码设为27
// 等号种别码为28
// <= 种别码为29.
// <> 种别码为30。
// < 种别码为31
// >= 种别码为32
// > 种别码为33.
// + 种别码为34
// - 种别码为35
// * 种别码为36
// / 种别码 53
// ;种别码为38
// = 种别码为28
//1到51为正常的。空格为100， 换行符为101， #号为102，错误为404
//case '(': syn = 39; 
//case ')': syn = 40; 

int i, row = 0, line = 0; //line用来保存标识符的个数。row来保存数字个数。i保存读到哪个字符了
char test[1000];  //这是读取文件的内容的。 
int number[100];	//常数表,有个疑问，数字需要常数来保存吗？
char mark[100][5];   //用来存放标识符的。
int count = 1; //记录出错的行号 
int syn;
int wu;
int final_flag = 0;
//关键字：
char pro[100][100] = { "PROGRAM", "BEGIN", "END", "VAR", "INTEGER", "WHILE",
"IF", "THEN", "ELSE", "DO", "PROCEDURE" ,"char",
"int","if","else","var" ,"return","break",
"do","while","for","double","float","short", "main" };
//关键字：从1开始到25.

void Irparser() {
	printf("语法分析\n");
	i = 0;
	count = 1;
	wu = wordanalysis();
	while (wu == 100 || wu == 101) {
		i++;
		wu = wordanalysis();
	}
	if (syn == 2) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
		yucu();
		//yucu（）函数结束之后，把空格和换行过滤掉
		if (syn == 3) {
			i++;
			wu = wordanalysis();
			while (wu == 100 || wu == 101) {
				i++;
				wu = wordanalysis();
			}
			if (syn == 102 && final_flag == 0) {
				printf("成功");
			}
			else {
				printf("这是一串失败的语句");
			}
		}
		else {
			printf("缺少END");
		}
	}
	else {
		printf("开头缺少BEGIN\n");
		final_flag = 1;
		// 看这个单词，如果是BEGIN的下一个找文件内容下一个单词与他匹配，否则就还是从BEGIN开始，单词从下一个找
		//BEGIN的下一个是END或者标识符
		if (syn == 3 || syn == 26 || syn == 52) {
			if (syn == 3) {
				One();
			}
			else if (syn == 26 || syn == 52) {
				Two();
			}
		}
		else {
			Three();
		}
	}
}

//当当前这一位是BEGIN的FOLLOW集END时
void One() {
	i++;
	wu = wordanalysis();
	while (wu == 100 || wu == 101) {
		i++;
		wu = wordanalysis();
	}
	if (syn == 102 && final_flag == 0) {
		printf("成功");
	}
	else {
		printf("这是一串失败的语句");
	}
}

// 当当前这一位是BEGIN的follow集标识符时。
void Two() {
	i++;
	wu = wordanalysis();
	while (wu == 100 || wu == 101) {
		i++;
		wu = wordanalysis();
	}
	yucu();
	//yucu（）函数结束之后，把空格和换行过滤掉
	if (syn == 3) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
		if (syn == 102 && final_flag == 0) {
			printf("成功");
		}
		else {
			printf("这是一串失败的语句");
		}
	}
	else {
		printf("缺少END");
	}
}

//这个是当前单词不是BEGIN的FOLLOW集，所以选择下一个单词。
void Three() {
	i++;
	wu = wordanalysis();
	while (wu == 100 || wu == 101) {
		i++;
		wu = wordanalysis();
	}
	if (syn == 2) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
		yucu();
		//yucu（）函数结束之后，把空格和换行过滤掉
		if (syn == 3) {
			i++;
			wu = wordanalysis();
			while (wu == 100 || wu == 101) {
				i++;
				wu = wordanalysis();
			}
			if (syn == 102 && final_flag == 0) {
				printf("成功");
			}
			else {
				printf("这是一串失败的语句");
			}
		}
		else {
			printf("缺少END");
		}
	}
	else {
		printf("第%d行缺少BEGIN\n", count);
		final_flag = 1;
		// 看这个单词，如果是BEGIN的下一个找文件内容下一个单词与他匹配，否则就还是从BEGIN开始，单词从下一个找
		//BEGIN的下一个是END或者标识符
		if (syn == 3 || syn == 26 || syn == 52) {
			if (syn == 3) {
				One();
			}
			else if (syn == 26 || syn == 52) {
				Two();
			}
		}
		else {
			Three();
		}
	}
}




void yucu() {
	statement();
	//如果是；，则不断循环下去
	while (syn == 38) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
		statement();
	}
}

void statement() {
	//如果是标识符
	if (syn == 26 || syn == 52) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
		//如果标识符后面为=
		if (syn == 28) {
			i++;
			wu = wordanalysis();
			while (wu == 100 || wu == 101) {
				i++;
				wu = wordanalysis();
			}
			expression();
		}
		else {
			printf("第%d行等号赋值错误\n", count);
			final_flag = 1;
			//当跟=不匹配时，我们知道=的FOLLOW集为标识符（这里的标识符为26
			//出现过的标识符的种别码设为26
			//未出现过的标识符种别码为52，
			if (syn == 26) {
				expression();
			}
			else {
				not_biaozhifu();
			}
		}
	}
	else {
		printf("第%d行标识符有错误\n", count);
		final_flag = 1;
		//这里出现不是标识符的情况，那么如果这个单词是标识符的FOLLOW集，即
		//=，所以看这个单词是=吗,要是不是的话，那就直接下一个单词匹配是否是标识符
		if (syn == 28) {
			is_equal();
		}
		else {
			not_equal();
		}
	}
}

void not_biaozhifu() {
	i++;
	wu = wordanalysis();
	while (wu == 100 || wu == 101) {
		i++;
		wu = wordanalysis();
	}
	if (syn == 28) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
		expression();
	}
	else {
		printf("第%d行等号赋值错误\n", count);
		final_flag = 1;
		//当跟=不匹配时，我们知道=的FOLLOW集为标识符（这里的标识符为26
		//出现过的标识符的种别码设为26
		//未出现过的标识符种别码为52，
		if (syn == 26) {
			expression();
		}
		else {
			not_biaozhifu();
		}
	}
}


void is_equal() {
	i++;
	wu = wordanalysis();
	while (wu == 100 || wu == 101) {
		i++;
		wu = wordanalysis();
	}
	expression();
}

void not_equal() {
	i++;
	wu = wordanalysis();
	while (wu == 100 || wu == 101) {
		i++;
		wu = wordanalysis();
	}
	if (syn == 26 || syn == 52) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
		//如果标识符后面为=
		if (syn == 28) {
			i++;
			wu = wordanalysis();
			while (wu == 100 || wu == 101) {
				i++;
				wu = wordanalysis();
			}
			expression();
		}
		else {
			printf("第%d行等号赋值错误\n", count);
			final_flag = 1;
			//当跟=不匹配时，我们知道=的FOLLOW集为标识符（这里的标识符为26
			//出现过的标识符的种别码设为26
			//未出现过的标识符种别码为52，
			if (syn == 26) {
				expression();
			}
			else {
				not_biaozhifu();
			}
		}
	}
	else {
		printf("第%d行标识符有错误\n", count);
		final_flag = 1;
		//这里出现不是标识符的情况，那么如果这个单词是标识符的FOLLOW集，即
		//=，所以看这个单词是=吗,要是不是的话，那就直接下一个单词匹配是否是标识符
		if (syn == 28) {
			is_equal();
		}
		else {
			not_equal();
		}
	}
}

void expression() {
	term();
	//当时加或者减的时候
	while (syn == 34 || syn == 35) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
		term();
	}
}
void term() {
	factor();
	// 当为/或者*的时候
	while (syn == 53 || syn == 36) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
		factor();
	}
}
void factor() {
	// 后面是数字或者出现过的标识符
	if (syn == 26 || syn == 27) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
	}
	// 如果是（
	else if (syn == 39) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
		expression();
		// 如果是）的话
		if (syn == 40) {
			i++;
			wu = wordanalysis();
			while (wu == 100 || wu == 101) {
				i++;
				wu = wordanalysis();
			}
		}
		else {
			printf("第%d行有错误, 缺少）\n", count);
			final_flag = 1;
			//如果不是的话，那么）的FOLLOW集应该是加减乘除或者；或者END
			if (syn == 34 || syn == 35 || syn == 36 || syn == 53 || syn == 38 || syn == 3) {
				if (syn == 34 || syn == 35 || syn == 36 || syn == 53) {
					is_four_cal();
				}
				// 如果是；38
				if (syn == 38) {
					is_colon();
				}
				// 如果是END
				if (syn == 3) {
					One();
				}
			}
			else {
				// 代表没有）的FOLLOW集
				not_right();
			}
		}
	}
	else {
		printf("第%d行输出表达式有错误\n", count);
		final_flag = 1;
		//这里我们看到标识符或者数字下一个即FOLLOW集应该是加减乘除或者;或者END
		if (syn == 34 || syn == 35 || syn == 36 || syn == 53 || syn == 38 || syn == 3) {
			if (syn == 34 || syn == 35 || syn == 36 || syn == 53) {
				is_four_cal();
			}
			// 如果是；38
			if (syn == 38) {
				is_colon();
			}
			// 如果是END
			if (syn == 3) {
				One();
			}
		}
		else {
			not_four_cal();
		}
		
	}
}

void not_right() {
	i++;
	wu = wordanalysis();
	while (wu == 100 || wu == 101) {
		i++;
		wu = wordanalysis();
	}
	// 如果是）的话
	if (syn == 40) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
	}
	else {
		printf("第%d行有错误, 缺少）\n", count);
		final_flag = 1;
		//如果不是的话，那么）的FOLLOW集应该是加减乘除或者；或者END
		if (syn == 34 || syn == 35 || syn == 36 || syn == 53 || syn == 38 || syn == 3) {
			if (syn == 34 || syn == 35 || syn == 36 || syn == 53) {
				is_four_cal();
			}
			// 如果是；38
			if (syn == 38) {
				is_colon();
			}
			// 如果是END
			if (syn == 3) {
				One();
			}
		}
		else {
			// 代表没有）的FOLLOW集
			not_right();
		}
	}
}


void is_colon() {
	while (syn == 38) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
		statement();
	}
}

void not_four_cal() {
	i++;
	wu = wordanalysis();
	while (wu == 100 || wu == 101) {
		i++;
		wu = wordanalysis();
	}
	// 后面是数字或者出现过的标识符
	if (syn == 26 || syn == 27) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
	}
	// 如果是（
	else if (syn == 39) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
		expression();
		// 如果是）的话
		if (syn == 40) {
			i++;
			wu = wordanalysis();
			while (wu == 100 || wu == 101) {
				i++;
				wu = wordanalysis();
			}
		}
		else {
			printf("第%d行有错误, 缺少）\n", count);
			final_flag = 1;
			//如果不是的话，那么）的FOLLOW集应该是加减乘除或者；或者END
			if (syn == 34 || syn == 35 || syn == 36 || syn == 53 || syn == 38 || syn == 3) {
				if (syn == 34 || syn == 35 || syn == 36 || syn == 53) {
					is_four_cal();
				}
				// 如果是；38
				if (syn == 38) {
					is_colon();
				}
				// 如果是END
				if (syn == 3) {
					One();
				}
			}
			else {
				// 代表没有）的FOLLOW集
				not_right();
			}
		}
	}
	else {
		printf("输出表达式有错误\n");
		final_flag = 1;
		//这里我们看到标识符或者数字下一个即FOLLOW集应该是加减乘除或者;或者END
		if (syn == 34 || syn == 35 || syn == 36 || syn == 53 || syn == 38 || syn == 3) {
			if (syn == 34 || syn == 35 || syn == 36 || syn == 53) {
				is_four_cal();
			}
			// 如果是；38
			if (syn == 38) {
				is_colon();
			}
			// 如果是END
			if (syn == 3) {
				One();
			}
		}
		else {
			not_four_cal();
		}

	}
}

void is_four_cal() {
	//当时加或者减的时候
	while (syn == 34 || syn == 35) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
		term();
	}

	// 当为/或者*的时候
	while (syn == 53 || syn == 36) {
		i++;
		wu = wordanalysis();
		while (wu == 100 || wu == 101) {
			i++;
			wu = wordanalysis();
		}
		factor();
	}
}




//过滤
void guolv() {
	char temp[1000];
	int flag = 0;
	int j = 0;
	while (test[flag] != '#') {
		//单行注释// 
		if (test[flag] == '/' && test[flag + 1] == '/') {
			while (test[flag] != '\n') {
				flag++;
			}
		}
		else if (test[flag] == '/' && test[flag + 1] == '*') {
			//多行注释/**/ 
			flag = flag + 2;
			while (test[flag] != '*' && test[flag + 1] != '/') {
				flag++;
			}
			flag = flag + 2;
		}
		temp[j] = test[flag];
		flag++;
		j++;
	}
	temp[j] = '#';
	strcpy(test, temp);
}

//词法分析
int wordanalysis()
{
	//标识符和保留字
	//当第一个字符是字母的时候
	if ((test[i] >= 'A'&&test[i] <= 'Z') || (test[i] >= 'a'&&test[i] <= 'z'))
	{
		char word[10];
		//保留字的种别码。从1开始到25

		int n = 0;
		word[n++] = test[i++];
		while ((test[i] >= 'A'&&test[i] <= 'Z') || (test[i] >= '0' && test[i] <= '9') || (test[i] >= 'a'&&test[i] <= 'z'))
		{
			word[n++] = test[i++];
		}
		word[n] = '\0';
		i--;

		//判断该标识符是否为保留字
		for (n = 0; n < 100; n++)
		{
			if (strcmp(word, pro[n]) == 0)
			{
				syn = n + 1;
				printf(">> %s\t(%d,-) 保留字\n", pro[n], syn);
				return syn;
			}
		}

		//不是关键字的话，判断该标识符是否在标识符表中
		int m = 0;
		if (line != 0)
		{
			int q = 0;
			while (q<line)
			{
				if (strcmp(word, mark[q++]) == 0)
				{
					syn = 26; //出现过的标识符的种别码设为26
					printf(">> %s\t(%d,%d) 标识符\n", word, syn, q);
					return syn;
				}
			}

		}
		//未出现过的标识符种别码为52，将该标识符保存到标识符表中
		strcpy(mark[line], word);
		syn = 52;
		printf(">> %s\t(%d, %d) 标识符\n", word, syn, line + 1);
		line++;
		return syn;

	}
	//数字 
	else if (test[i] >= '0' && test[i] <= '9')
	{
		char x[100];
		int n = 0;
		x[n++] = test[i++];

		while (test[i] >= '0' && test[i] <= '9')
		{
			x[n++] = test[i++];
		}
		x[n] = '\0';
		i--;
		int num = atoi(x); //将字符串转换成int型

						   //判断该常数是否存在于常数表中
		if (row != 0)
		{

			for (int y = 0; y<row; y++)
			{
				if (number[y] == num)
				{
					syn = 27; //数字种别码设为27
					printf(">> %d\t(%d,%d)\n", num, syn, y + 1);
					return syn;
				}
			}
		}

		//将该常数保存到标识符表中
		number[row] = num;
		int line = row;
		syn = 27;
		printf(">> %d\t(%d,%d)\n", num, syn, line + 1);
		row++;
		return syn;
	}

	//各种符号
	else {
		switch (test[i])
		{
		case '=': syn = 28; // 等号种别码为28
			printf(">> =\t(%d,-)\n", syn); return syn;
		case '<':
			i++;
			if (test[i] == '=')
			{
				syn = 29; // <= 种别码为29.
				printf(">> <= \t(%d,-)\n", syn);
				return syn;
			}
			else if (test[i] == '>')
			{
				syn = 30; // <> 种别码为30。
				printf(">> <>\t(%d,-)\n", syn);
				return syn;
			}
			else
			{
				i--;
				syn = 31; // < 种别码为31
				printf(">> <\t(%d,-)\n", syn);
				return syn;
			}
		case '>':
			i++;
			if (test[i] == '=')
			{
				syn = 32; // >= 种别码为32
				printf(">> >=\t(%d,-)\n", syn);
				return syn;
			}
			else
			{
				i--;
				syn = 33; // > 种别码为33.
				printf(">> >\t(%d,-)\n", syn);
				return syn;
			}
		case '+': syn = 34; printf(">> +\t(%d,-)\n", syn); return syn; // + 种别码为34
		case '-': syn = 35;  printf(">> -\t(%d,-)\n", syn); return syn; // - 种别码为35
		case '*': syn = 36;  printf(">> *\t(%d,-)\n", syn); return syn; // * 种别码为36
		case '/': syn = 53; printf(">> *\t(%d, -)\n", syn); return syn; // /的种别码为53 
																		//case '/':
																		//	i++;
																		//	//if (test[i] == '/') {
																		//	//	//单行注释：
																		//	//	while (1) {
																		//	//		if (test[i++] == '\n')
																		//	//			return -1;
																		//	//	}
																		//	//}
																		//	//else if (test[i] == '*') {
																		//	//	i++;
																		//	//	while (!(test[i] == '*' && test[i + 1] == '/')) {
																		//	//		i++;
																		//	//	}
																		//	//}
																		//	if (test[i] != '/') {
																		//		syn = 37;
																		//		i--;
																		//		printf(">> /\t(%d,-)\n", syn); return 3;
																		//	}

																		//	else {
																		//		//单行注释：
																		//		while (1) {
																		//			if (test[i++] == '\n')
																		//				return -1;
																		//		}
																		//		printf(">> //\t(37,-)\n"); return 3;

																		//	}

		case ':': syn = 37; printf(">> :\t(%d,-)\n", syn); return syn;
		case ';': syn = 38; printf(">> ;\t(%d,-)\n", syn); return syn;
		case '(': syn = 39; printf(">> (\t(%d,-)\n", syn); return syn;
		case ')': syn = 40; printf(">> )\t(%d,-)\n", syn); return syn;
		case '{': syn = 41; printf(">> {\t(%d,-)\n", syn); return syn;
		case '}': syn = 42; printf(">> }\t(%d,-)\n", syn); return syn;
		case '[': syn = 43; printf(">> [\t(%d,-)\n", syn); return syn;
		case ']': syn = 44; printf(">> ]\t(%d,-)\n", syn); return syn;
		case '|': syn = 45; printf(">> |\t(%d,-)\n", syn); return syn;
		case '"': syn = 46; printf(">> \"\t(%d,-)\n", syn); return syn;
		case ',': syn = 47; printf(">> ,\t(%d,-)\n", syn); return syn;
		case '\'': syn = 48; printf(">> '\t(%d,-)\n", syn); return syn;//单引号
		case '&':
			i++;
			if (test[i] != '&') {
				i--;
				// & 种别码为 49；
				syn = 49;
				printf(">> &\t(%d,-)\n", syn); return syn;
			}
			//&&种别码为50
			syn = 50;
			printf(">> &&\t(%d,-)\n", syn); return syn;
			// \ 种别码为51
		case '\\': syn = 51; printf(">> \\\t(%d,-)\n", syn); return syn;

		case ' ':
			syn = 100; // 空格种别码为28
			return syn;
		case '\n':count++;
			syn = 101; // 换行符种别码为29
			return syn;
		case '#': syn = 102; //结束符#种别码为30. 
			return syn;
		default:
			syn = 404; //错误的种别码为404
			printf(">> %c error in %d row\n", test[i], count);
			return syn;
		}
	}

}

int main()
{

	int c = 0;
	int m;
	i = 0;
	//读取文件
	FILE *fp;
	fp = fopen("D:\\yes.txt", "r");
	if (fp == NULL)
	{
		printf("can't open file!\n");
		exit(0);
	}
	//把文件内容读取到test数组中
	while (!feof(fp))
	{
		test[c++] = fgetc(fp);
	}
	test[c] = '#';
	while (test[i] != '#') {
		printf("%c", test[i]);
		i++;
	}
	printf("\n");
	printf("------------过滤后的-------------\n");
	guolv();
	i = 0;
	while (test[i] != '#') {
		printf("%c", test[i]);
		i++;
	}
	printf("\n");
	printf("输出文法分析后的：\n");
	//1到51为正常的。空格为100， 换行符为101， #号为102，错误为404
	/*do
	{
	m = wordanalysis();

	switch (m)
	{
	case -1:i++; break;
	case 0: i++; break;
	case 3: i++; break;
	}
	} while (m != 0);*/
	Irparser();
	return 0;
}

文件内容：
BEGIN
a = 10;
//fad a = b + c;
b = a + 10;
e = a + b;
d = (a + b) + e;
d = (a + b)
END#

输出：
BEGIN
a = 10;
//fad a = b + c;
b = a + 10;
e = a + b;
d = (a + b) + e;
d = (a + b)
END
------------过滤后的-------------
BEGIN
a = 10;

b = a + 10;
e = a + b;
d = (a + b) + e;
d = (a + b)
END
输出文法分析后的：
语法分析
>> BEGIN        (2,-) 保留字
>> a    (52, 1) 标识符
>> =    (28,-)
>> 10   (27,1)
>> ;    (38,-)
>> b    (52, 2) 标识符
>> =    (28,-)
>> a    (26,1) 标识符
>> +    (34,-)
>> 10   (27,1)
>> ;    (38,-)
>> e    (52, 3) 标识符
>> =    (28,-)
>> a    (26,1) 标识符
>> +    (34,-)
>> b    (26,2) 标识符
>> ;    (38,-)
>> d    (52, 4) 标识符
>> =    (28,-)
>> (    (39,-)
>> a    (26,1) 标识符
>> +    (34,-)
>> b    (26,2) 标识符
>> )    (40,-)
>> +    (34,-)
>> e    (26,3) 标识符
>> ;    (38,-)
>> d    (26,4) 标识符
>> =    (28,-)
>> (    (39,-)
>> a    (26,1) 标识符
>> +    (34,-)
>> b    (26,2) 标识符
>> )    (40,-)
>> END  (3,-) 保留字
成功
--------------------------------
Process exited after 0.3427 seconds with return value 0
请按任意键继续. . .

-冒泡排序法：
冒泡排序的基本逻辑是相邻两数逐个比较，大数（小数）向前，小数（大数）不动，让最大（最小的数）冒顶，再去进行下一轮的比较，由于第一轮的比较已经确定了顶位，后面的比较在剩下的数字里面决出顶位就可以了，所以比较的次数少1;

由此，冒泡由两轮循环控制：外层循环次数决定要进行几轮的登顶赛，等于比较的总数字量减一（因为最后一个数字不需要比较）；内层循环进行大赛内部的一一对挑，遍历次数等于剩余数字数减一（因为顶位确定不用再比，相当于拿奖出局了）;

两层循环存在关联，即剩余数字数=总数字数-登顶数字数；此关联决定内外循环次数（m,n)的关联关系.


//冒泡排序法
for (m=0;m<19;m++)
{
		for (n=0;n<19-m;n++)
				if(rArray[n+1]>rArray[n])
				{	
					temp=rArray[n+1];
					rArray[n+1]=rArray[n];
					rArray[n]=temp;
				}
}

- 选择排序法（从小到大为例）
选择排序先任意指定第一个值为最值min，然后拿这个数去跟后面的数比较，遇到比它小的数值则min被这个数所取代，遍历一遍，找到最值所在位置（即下标），然后把最值调到最前面；

由于最小值确定，剩下数以此类推进行排序即可；


//选择排序法
	for (i=0;i<20;i++)
	{
		min=i;
		for (j=i+1;j<20;j++)
		{
			if (rArray[min]>rArray[j])
			min=j;
		}
		if (i!=min)
		{
			temp=rArray[min];
			rArray[min]=rArray[i];
			rArray[i]=temp;
		}
	}

所使用的开发工具及环境： PC机一套
实验目的：

(1)了解多态性的概念。

(2)了解虚函数的作用及使用方法。

(3)了解静态关联和动态关联的概念和川法。

(4)了解纯虚函数和抽象类的概念和用法。
实验内容：

1、分析程序运行结果，掌握虚函数的使用。

程序一：
#include <iostream>
using namespace std;
class ONE
{  public:
      virtual void f(){cout<<"ONE"<<endl;}
};
class TWO:public ONE
{  public:
      TWO(){cout<<"TWO"<<endl;}
};
class THREE:public TWO
{  public:
      virtual void f(){TWO::f(); cout<<"THREE";}
};
void main()
{  ONE aa, *p;
   TWO bb;  //TWO
   THREE cc;  //TWO
   p = &cc;
   p->f();//ONE THREE
   cout<<endl;
}

程序二：
#include <iostream>
using namespace std;
class Base
{ public:
   virtual void fn() { cout <<"In Base Class\n";}
};
class SubClass :public Base
{  public:
    virtual void fn(){  cout <<"In Sub Class\n";  }//覆盖
};
void main()
{   Base bc,*p;
    SubClass sc;
    p=&bc;   p->fn();//In Base Class
    p=&sc;   p->fn();//In Sub Class
}

2、实现一个类A，在A中有两个私有的整型变量a和b，定义构造函数对a和b进行初始化，并实现成员函数geta（）取得a的值和getb（）取b的值。实现类B从A继承，覆盖geta（），使其返回a的2倍。主函数中声明类B对象，调用类B中的geta（）并将结果输出。
#include<iostream>
using namespace std;
class A
{
	public:
		A(int a,int b):a(a),b(b){}
		virtual int geta(){return a;}
		friend class B;
private:
	int a;
	int b;
};
class B:public A
{
public:
	B(int a,int b):A(a,b){}
	int geta(){return 2*a;}
};
int main()
{
	A *p=new B(2,3);
	cout<<p->geta()<<endl;
system("pause");
return 0;
}


3、设计一个计算图形面积的类库。它的顶层是一个抽象类，并且提供相应的接口函数。抽象基类Shape，派生出Point类、矩形Rectangle、正方形Square，Point类派生出圆形Circle。 要求：

（1）每个类有构造函数、析构函数，并有相应的输出语句，如：“正在构造圆形”

（2）能显示每个类的信息，如：输出“我是圆形”

（3）能计算面积、周长

（4）定义一个基类Shape类型的指针，实现动态多态

（5）动态创建一个圆形对象，赋值给基类Shape类型的指针变量，程序最后delete该指针，保证析构函数的正确调用（提示：虚析构函数）

（6）在主函数测试。
#include<iostream>
using namespace std;
const double PI=3.1415926;
class Shape
{
public:
	Shape(){cout<<"Constructing Shape..."<<endl;}
	virtual ~Shape(){cout<<"Destructing Shape..."<<endl;}
	virtual void Name(){cout<<"Share"<<endl;}
	virtual double Area()=0;
	virtual double C()=0;
};
class Point: public Shape
{
public:
	Point(){cout<<"Constructing Point..."<<endl;}
	~Point(){cout<<"Destructing Point..."<<endl;}
	virtual void Name(){cout<<"Point"<<endl;}
	double Area(){return 0;}
	double C(){return 0;}
};
class Rectangle:public Shape
{
public:
	Rectangle(int l,int w):length(l),width(w){cout<<"Constructing Rectangle..."<<endl;}
	~Rectangle(){cout<<"Destructing Rectangle..."<<endl;}
	double Area(){return length*width;}
	double C(){return (length+width)*2;}
	void Name(){cout<<"Rectangle"<<endl;}
private:
	double length;
	double width;
};
class Squre:public Shape
{
public:Squre(int l):L(l){cout<<"Constructing Squre..."<<endl;}
	   ~Squre(){cout<<"Destructing Squre..."<<endl;}
	   void Name(){cout<<"Squre"<<endl;}
	   double Area(){return L*L;}
	   double C(){return 4*L;}
private:
	double L;
};
class Circle: public virtual Point
{
public:
	Circle(double r):radious(r){cout<<"Constructing Circle..."<<endl;}
	~Circle(){cout<<"Destructing Circle..."<<endl;}
	void Name(){cout<<"Circle"<<endl;}
	double Area(){return PI*radious*radious;}
	double C(){return 2*PI*radious;}
private:
	double radious;
};
int main()
{
	Shape *p;
	p=new Point;
	p->Name();
	cout<<"C:"<<p->C()<<endl;
	cout<<"Area:"<<p->Area()<<endl;
	delete p;
	cout<<endl;
	 p=new Rectangle(2,3);
	p->Name();
	cout<<"C:"<<p->C()<<endl;
	cout<<"Area:"<<p->Area()<<endl;
	delete p;
	cout<<endl;
	p=new Squre(4);
	p->Name();
	cout<<"C:"<<p->C()<<endl;
	cout<<"Area:"<<p->Area()<<endl;
	delete p;
	cout<<endl;
	p=new Circle(5);
	p->Name();
	cout<<"C:"<<p->C()<<endl;
	cout<<"Area:"<<p->Area()<<endl;
	delete p;
	system("pause");
}


4、设计一个基类Base，其作用是计算一个图形的面积，它只有一个公有的函数成员虚函数area。再从Base 类公有派生一个三角形类Triangle 和一个圆类Circle，在类Triangle 和类Circle 中分别定义自己的area 函数，用于计算各自的面积。在主函数中设计一个Base 类的对象指针，分别指向类Triangle 和类Circle 的对象，调用各自的area 函数显示相应 对象的面积。

分析：用虚函数实现多态。
#include<iostream>
#include<iostream>
using namespace std;
const double PI=3.1415926;
class Base
{
public:
	Base(){cout<<"Constructing Base..."<<endl;}
	virtual ~Base(){cout<<"Destructed Base."<<endl;}
	virtual double Area()=0;
};
class Triangle:public Base
{
public:
	Triangle(double a,double b,double c):a(a),b(b),c(c){cout<<"Constructing Triangle..."<<endl;}
	~Triangle(){cout<<"Destructed Triangle."<<endl;}
	double Area(){return sqrt(0.5*(a+b+c)*(0.5*(a+b+c)-a)*(0.5*(a+b+c)-b)*(0.5*(a+b+c)-c));}
private:
	double a,b,c;
};
class Circle:public Base
{
public:
	Circle(double r):radious(r){cout<<"Constructing Circle..."<<endl;}
	~Circle(){cout<<"Destructed Circle."<<endl;}
	double Area(){return PI*radious*radious;}
private:
	double radious;
};
int main()
{
	Base *p;
	p=new Triangle(3,4,5);
	cout<<"Area:"<<p->Area()<<endl;
	delete p;
	cout<<endl;
	p=new Circle(4);
	cout<<"Area:"<<p->Area()<<endl;
	delete p;
	cout<<endl;
	system("pause");
	return 0;
}


5．将上题中的Base 类改为抽象类，应用抽象类，求矩形、圆形的周长和面积。

分析：将Base 类的其成员函数area 和perimeter 声明为纯虚函数，Base 就成为一个抽 象类。然后再从Base 派生矩形类和圆形类，分别实现Base 中纯虚函数的功能.
#include<iostream>
using namespace std;
const double PI=3.1415926;
class Base
{
public:
	Base(){cout<<"Constructing Base..."<<endl;}
	virtual ~Base(){cout<<"Destructed Base."<<endl;}
	virtual double Area()=0;
	virtual double Perimeter()=0;  //周长
};
class Triangle:public Base
{
public:
	Triangle(double a,double b,double c):a(a),b(b),c(c){cout<<"Constructing Triangle..."<<endl;}
	~Triangle(){cout<<"Destructed Triangle."<<endl;}
	double Area(){return sqrt(0.5*(a+b+c)*(0.5*(a+b+c)-a)*(0.5*(a+b+c)-b)*(0.5*(a+b+c)-c));}
	double Perimeter(){return a+b+c;}
private:
	double a,b,c;
};
class Circle:public Base
{
public:
	Circle(double r):radious(r){cout<<"Constructing Circle..."<<endl;}
	~Circle(){cout<<"Destructed Circle."<<endl;}
	double Area(){return PI*radious*radious;}
	double Perimeter(){return 2*PI*radious;}
private:
	double radious;
};
int main()
{
	Base *p;
	p=new Triangle(3,4,5);
	cout<<"Area:"<<p->Area()<<endl;
	cout<<"Perimeter:"<<p->Perimeter()<<endl;
	delete p;
	cout<<endl;
	p=new Circle(4);
	cout<<"Area:"<<p->Area()<<endl;
	cout<<"Perimeter:"<<p->Perimeter()<<endl;
	delete p;
	cout<<endl;
	system("pause");
	return 0;
}