编译原理-语法分析-LL1

编译原理实现LL（1）包括消除左递归，求First集，Follow集，预测分析表，预测分析过程

#include “StdAfx.h“
#include “CSyntaxAnalysis.h“

CSyntaxAnalysis::CSyntaxAnalysis（void）
{
}

CSyntaxAnalysis::~CSyntaxAnalysis（void）
{
}
void CSyntaxAnalysis::ClearAll（）
{
	startLL = ““;                         //  LL（1）开始符号        
	Terminator.clear（）;                   //  保存终结符            
	Non_Terminator.clear（）;               //  保存非终结符           
	Input_Grammar.clear（）;                //  保存当初输入的文法     
	NoLeftRe_Grammar.clear（）;             //  保存消除左递归的文法   
	Left.clear（）;                         //  保存消除左递归后的文法的左部集合      
	HaveVisited.clear（）;                  //  保存非终结符是否访问过              
	NoLeftRe_Grammar_Gather.clear（）;   //  保存左部->右边集合形如 A:{sA‘@}    
	FirstGather.clear（）;               //   First 集合                         
	FollowGather.clear（）;              //   Follow 集合                        
    SelectGather.clear（）;              //   Select 集合                        
	anaStr.clear（）;                    //   要分析的字符串  

	ShowHaveMatch.clear（）;    // 显示的已匹配 
	ShowStaGrammar.clear（）;   // 显示的队列   
	ShowInput.clear（）;        // 显示的输入   
	ShowActions.clear（）;      // 显示的动作   
}
// 总流程控制
void CSyntaxAnalysis::Commander（）
{
	if（JudgeGrammar（））          // 判断输入的文法是否合法
	{
		UniteOR（）;              // 合并能合并的 文法
		RemoveLeft_Recursive（）; // 消除左递归
		SplitOR（）;              // 拆分能拆分的 文法
		GetLEFT_GATHER（）;       // 获得左部->集合
		FindLeft（）;             // 获得左部集合
		GetFirstGather（0）;      // 查找First集合
		for （int i = 0;i < HaveVisited.size（）;i++）  // 重新赋值
		{
             HaveVisited[i] = false;
		}
		GetFollowGather（0）; //  获得FOLLOE集合
		GetSelectGather（）;  //  获得SELECT集
		if（!IsLegalLL（））    //  判断是不是LL（1）
			AfxMessageBox（“NOT THE LL（1）!“）;
		else                //  执行分析过程 
		{
			PredictAnalysis（anaStr）;
		}
	}
	else//  错误信息 
	{
		CString infor = “文法错误，请检查！“;
		infor.Append（“\r\n“）;
		infor.Append（“不合法情况:“）;
		infor.Append（“\r\n“）;
		infor.Append（“（1）形如 A->A“）;
		infor.Append（“\r\n“）;
		infor.Append（ “（2）形如 A->“）;
		AfxMessageBox（infor）;
	}
}
//---------------------------------------------------------------------------------------------------------
// 判断文法是否合法
//    满足条件：
//   （1）左部以非终结符开始，并且只有一个
//   （2）右部必须有非终结符，并且只能用零个或多个终结符和非终结符组成
//    不合法情况
//   （1）  形如 A->A
//   （2）  形如 A->
bool CSyntaxAnalysis::JudgeGrammar（）
{
	for（int i = 0;i < Input_Grammar.size（）;i++）
	{
		int nEnd = 0;
		bool HaveNon_T = false;    // 记录右边是否含有非终结符
		CString startGrammar = ““; // 左部字符
		nEnd = Input_Grammar[i].Find（“->“）;
		startGrammar = Input_Grammar[i].Mid（0 nEnd）;
		if （startGrammar == Input_Grammar[i].Mid（nEnd + 2 Input_Grammar[i].GetLength（） - nEnd - 2））
			return false;//   （1）  形如 A->A
		if （（Input_Grammar[i].GetLength（） - nEnd - 2） < 0）
			return false;//   （2）  形如 A->
		if（find（Non_Terminator.begin（） Non_Terminator.end（） startGrammar） == Non_Terminator.end（））
			return false;//    不是非终结符
		for（int j = nEnd + 2;j < Input_Grammar[i].GetLength（） - nEnd - 2;j++）
		

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      62194  2010-12-08 16:40  Syntax_Analysis\Syntax_Analysis\CSyntaxAnalysis.cpp

     文件       4039  2010-12-07 18:31  Syntax_Analysis\Syntax_Analysis\CSyntaxAnalysis.h

     文件       1000  2010-12-07 14:43  Syntax_Analysis\Syntax_Analysis\ExampleDlg.cpp

     文件        413  2010-12-07 14:37  Syntax_Analysis\Syntax_Analysis\ExampleDlg.h

     文件        491  2010-12-01 21:44  Syntax_Analysis\Syntax_Analysis\InforDlg.cpp

     文件        363  2010-12-01 21:44  Syntax_Analysis\Syntax_Analysis\InforDlg.h

     文件       3035  2010-11-30 22:38  Syntax_Analysis\Syntax_Analysis\ReadMe.txt

     文件      21630  2005-09-23 09:25  Syntax_Analysis\Syntax_Analysis\res\Syntax_Analysis.ico

     文件        371  2010-11-30 22:38  Syntax_Analysis\Syntax_Analysis\res\Syntax_Analysis.rc2

     文件       1469  2010-12-07 14:49  Syntax_Analysis\Syntax_Analysis\resource.h

     文件        146  2010-11-30 22:38  Syntax_Analysis\Syntax_Analysis\stdafx.cpp

     文件       2489  2010-11-30 22:38  Syntax_Analysis\Syntax_Analysis\stdafx.h

     文件      61744  2010-12-07 14:52  Syntax_Analysis\Syntax_Analysis\Syntax_Analysis.aps

     文件       1766  2010-11-30 22:38  Syntax_Analysis\Syntax_Analysis\Syntax_Analysis.cpp

     文件        495  2010-11-30 22:38  Syntax_Analysis\Syntax_Analysis\Syntax_Analysis.h

     文件       8720  2010-12-07 14:52  Syntax_Analysis\Syntax_Analysis\Syntax_Analysis.rc

     文件       5967  2010-12-07 14:37  Syntax_Analysis\Syntax_Analysis\Syntax_Analysis.vcproj

     文件       1427  2010-12-08 16:40  Syntax_Analysis\Syntax_Analysis\Syntax_Analysis.vcproj.LIUCHANGCHUN-PC.Administrator.user

     文件       1405  2010-12-03 17:00  Syntax_Analysis\Syntax_Analysis\Syntax_Analysis.vcproj.PC92.Administrator.user

     文件       9919  2010-12-07 19:55  Syntax_Analysis\Syntax_Analysis\Syntax_AnalysisDlg.cpp

     文件       1014  2010-12-07 14:52  Syntax_Analysis\Syntax_Analysis\Syntax_AnalysisDlg.h

     文件        910  2010-12-02 20:24  Syntax_Analysis\Syntax_Analysis.sln

    ..A..H.     53760  2010-12-08 16:40  Syntax_Analysis\Syntax_Analysis.suo

     目录          0  2010-12-03 23:15  Syntax_Analysis\Syntax_Analysis\res

     目录          0  2010-12-08 16:41  Syntax_Analysis\Syntax_Analysis

     目录          0  2010-12-08 16:45  Syntax_Analysis

----------- ---------  ---------- -----  ----

               244767                    26