cfg化简说明.txt

CFG上下文无关文法的化简程序

CFG文法化简程序
计算机软件与理论 08级研究生  刘浩   学号2080130509
对应某一个文法，譬如：
G=({S,D,C,E},{a,b,ε},P,S)
S→DCE
D→CC|ε
C→EE|b
E→DD|a
我用Vc++编写了一个控制台程序
由于→和ε在控制台下难输入，故规定用->代替→,^代替ε
屏幕上说明了用户输入产生式的必要规则，如#表输入结束
此程序经测试，能化简大部分CFG
程序中定义了一个类：Simplify
定义数据类型：
	private:
	typedef struct{
		string value;//产生式
		int flag;//flag用来标记产生式已经到了化简的哪一步
		int count;//用来计算输出的次数
				} Produce;//产生式集
	Produce P[50];//产生式集
	char N[10];//非终结符集
	char T[10];//终结符集

	char S;//开始符号
	int NO_N;//非终结符的数目
	int NO_T;//终结符的数目
	int NO_P;//产生式的个数
	

	public:
	//Simplify(void);//构造函数
	void InitParam();//初始化,输入要化简的CFG
	void separate();//将产生式中含'|'的通通分解，使最终的产生式不含'|'
	void Step1();//找出有用的非终结符
	void Step2();//找出有用符号
	void Step3();//消除ε产生式

程序基本上是进行字符数组运算
用户按提示输入文法后，系统先将产生式中含'|'的通通分解，使最终的产生式不含'|'，即使D→CC|ε变为
D->CC和D->^等
然后化简

上述文法执行过程如下：（控制台屏幕显示结结果）
请认真阅读完下面的说明后按提示操作
请输入非终结符号集N，每两个非终结符号间空一格，每两个字符都不能相等，全部输入完毕后再输入#回车
注意每个非终结符只能用一个字符表示，最好是大写的英文字母,可以输入最多10个字符
SDCE#   （此为用户输入）
请输入终结符号集T，每两个终结符号间空一格，每两个字符都不能相等，全部输入完毕后再输入#回车
注意每个终结符只能用一个字符表示，最好是小写的英文字母和数字标点，且不能为#
可以输入最多10个字符
ab^#    （此为用户输入,^表示ε）
请输入产生式集P，每输入完一个产生式回车，不要输入两个完全一样的产生式
注意产生式应当写成诸如S->AwB|BaV等合法的形式，→用->代替，若产生式已经输入完，则输入#回车
最多可以输入的产生式为20个
请输入第1个产生式，每输入完一个产生式回车
S->DCE   （此为用户输入）
请输入第2个产生式，每输入完一个产生式回车
D->CC|^    （此为用户输入）
请输入第3个产生式，每输入完一个产生式回车
C->EE|b   （此为用户输入）
请输入第4个产生式，每输入完一个产生式回车
E->DD|a    （此为用户输入）
请输入第5个产生式，每输入完一个产生式回车
#      （此为用户输入）
请输入开始符号集S回车
S    （此为用户输入）
下面为分解产生式，使之不含|的过程
产生式S->DCE
产生式D->CC
产生式D->^
产生式C->EE
产生式C->b
产生式E->DD
产生式E->a
下面为找出有用的非终结符(即所有能直接或间接推出终结符串的非终结符)的过程
产生式D->^ 有用
产生式C->b 有用
产生式 E->a有用
产生式S->DCE 有用
产生式E->DD 有用
产生式D->CC 有用
产生式 C->EE有用
下面为找出有用符号，删除开始符号无法到达的符号与产生式的过程
产生式S->DCE 有用
产生式D->CC 有用
产生式D->^ 有用
产生式 C->EE有用
产生式C->b 有用
产生式E->DD 有用
产生式 E->a有用
下面为消除ε产生式的过程，为便于输入用^代替ε
若出现小写的s，则加入了新的产生式，s为新的开始符号
D能推出ε
应当删除
输出结束，回车将退出
Press any key to continue