精华内容
下载资源
问答
  • LL1语法分析器(c++).rar

    2019-06-04 23:12:45
    LL1语法分析器,c++实现,first,follow,分析表算法详细注释,
  • 自己实现的编译原理的LL1语法分析器,是自己的实验作业,用Vs2017实现,可以直接运行,代码注释丰富,希望与大家交流学习!欢迎大家下载!
  • 自己实现的编译原理的LL1语法分析器,是自己的实验作业,用Vs2017实现,可以直接运行
  • 编译原理 LL1语法分析器(JAVA写的)

    热门讨论 2009-12-01 19:36:15
    编译原理 LL1语法分析器: 用JAVA写的一个简单语法分析器; 输入一个表达式,输出表达式判断的结果。
  • 编译原理课程设计,开发的一款基于java的语法分析器,用到LL1文法
  • 使用MFC实现编译原理LL1语法分析器(含消除左递归)使用MFC实现编译原理LL1语法分析器(含消除左递归)
  • 根据某一文法编制调试 LL (1 )分析程序, 以便对任意输入的符号串进行分析。 2. 构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 3.分析法的功能是利用 LL(1)控制程序根据显示栈...
  • 自己写的,很简单 ,希望大家不要批评就好
  • 编译原理课程实验,LL1语法分析器根据某一文法编制调试 LL1分析程序, 对任意输入的符号串进行分析。构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分析程序。分析法的功能是利用 LL1控制程序根据...
  • 可实现加分要求,实现所有文法而非课本给定文法的文法分析,并自动构造LL1分析表,仅供学弟学妹们参考思路,请勿直接当作作业提交,严禁发生抄袭等学术不端行为
  • LL1语法分析器

    2008-06-12 00:24:24
    判断是否是LL1文法,提取左公共因子,消除左递归
  • 附测试用例
  • 自定义一个文法集,输入文法产生式,计算文法的FIRST,FOLLOW和SELECT集合, 利用SELECT集合构造预测分析表,接着用预测分析程序,栈 和预测分析表对输入串进行分析,给出分析过程。
  • SyntacticLL1 分析器 用于编译器 TP 的 LL1 语法分析器 由 Sofia Rebeca Legal Bernal 和 Atilio David Gomez Riveros 编写的 TP 06/13/2015
  • 编译原理-LL1语法分析器(消除左递归+消除回溯)

    万次阅读 多人点赞 2018-11-25 20:58:30
    编译原理-LL1语法分析器(消除左递归+消除回溯) 实验要求: 要求一 1、 给出文法如下: G[E]: E->T|E+T; T->F|T*F; F->i|(E); 2、 根据该文法构造相应的LL(1)文法及LL(1)分析表,并为该文法...

    编译原理-LL1语法分析器(消除左递归+消除回溯)

    实验要求:

    要求一

    1、 给出文法如下:
    G[E]:
    E->T|E+T;
    T->F|T*F;
    F->i|(E);

    2、 根据该文法构造相应的LL(1)文法及LL(1)分析表,并为该文法设计预测分析程序,利用C语言或C++语言或Java语言实现;
    3、 利用预测分析程序完成下列功能:
    1) 手工将测试的表达式写入文本文件,每个表达式写一行,用“;”表示结束;
    2) 读入文本文件中的表达式;
    3) 调用实验一中的词法分析程序搜索单词;
    4) 把单词送入预测分析程序,判断表达式是否正确(是否是给出文法的语言),若错误,应给出错误信息;
    5) 完成上述功能,有余力的同学可以进一步完成通过程序实现对非LL(1)文法到LL(1)文法的自动转换

    要求二

    1、 将一个可转换的非LL(1)文法转换为LL(1)文法,要经过两个阶段,1)消除文法左递归,2)提取左因子,消除回溯。
    2、 提取文法左因子算法:
    1)对文法G的所有非终结符进行排序
    2)按上述顺序对每一个非终结符Pi依次执行:
    for( j=1; j< i-1;j++)
    将Pj代入Pi的产生式(若可代入的话);
    消除关于Pi的直接左递归:
    Pi -> Piα|β ,其中β不以Pi开头,则修改产生式为:
    Pi —> βPi′
    Pi′—> αPi′|ε
    3)化简上述所得文法。
    3、 提取左因子的算法:
    A —> δβ1|δβ2|…|δβn|γ1|γ2|…|γm
    (其中,每个γ不以δ开头)
    那么,可以把这些产生式改写成
    A —> δA′|γ1| γ2…|γm
    A′—>β1|β2|…|βn
    4、 利用上述算法,实现构造一个LL(1)文法:
    1) 读入文法,利用实验二附加资料2的实验要求将文法存入设计的数据结构;
    2) 设计函数remove_left_recursion()和remove_left_gene()实现消除左递归和提取左因子算法,分别对文法进行操作,消除文法中的左递归和提出左因子;
    3) 整理得到的新文法;
    4) 在一个新的文本文件输出文法,文法输出按照一个非终结符号一行,开始符号引出的产生式写在第一行,同一个非终结符号的候选式用“|”分隔的方式输出。

    要求三

    1、 了解文法定义的4个部分:
    G(Vn, Vt, S, P)
    Vn 文法的非终结符号集合,在实验中用大写的英文字母表示;
    Vt 文法的终结符号集合,在实验中用小写的英文字母表示;
    S 开始符号,在实验中是Vn集合中的一个元素;
    P 产生式,分左部和右部,左部为非终结符号中的一个,右部为终结符号或非终结符号组成的字符串,如S->ab|c
    2、 根据文法各个部分的性质,设计一个合理的数据结构用来表示文法,
    1) 若使用C语言编写,则文法可以设计成结构体形式,结构体中应包含上述的4部分,
    2) 若使用C++语言编写,则文法可以设计成文法类形式,类中至少含有4个数据成员,分别表示上述4个部分
    文法数据结构的具体设计由学生根据自己想法完成,并使用C或C++语言实现设计的数据结构。
    3、 利用完成的数据结构完成以下功能:
    1) 从文本文件中读入文法(文法事先应写入文本文件);
    2) 根据文法产生式的结构,分析出文法的4个部分,分别写入定义好的文法数据结构的相应部分;
    3) 整理文法的结构;
    4) 在计算机屏幕或者文本框中输出文法,文法输出按照一个非终结符号一行,开始符号引出的产生式写在第一行,同一个非终结符号的候选式用“|”分隔的方式输出。

    代码

    #include <iostream>
    #include <string>
    #include <fstream>
    #include <set>
    #include <map>
    #include <iomanip>
    #include <stack>
    using namespace std;
    const int maxnlen = 1e4;
    class Grammar {
    private:
    	set<char>Vn;
    	set<char>Vt;
    	char S;
    	map<char, set<string> > P;
    	map<char,set<char> >FIRST;
    	map<char,set<char> >FOLLOW;
    	map<string, string>Table;
    public:
    	Grammar(string filename) {
    		Vn.clear();
    		Vt.clear();
    		P.clear();
    		FIRST.clear();
    		FOLLOW.clear();
    		ifstream in(filename);
    		if (!in.is_open()) {
    			cout << "文法  文件打开失败" << endl;
    			exit(1);
    		}
    		char *buffer = new char[maxnlen];
    		in.getline(buffer, maxnlen, '#');
    		string temps = "";
    		bool is_sethead = 0;
    		for (int i = 0; i < strlen(buffer); i++) {
    			if (buffer[i] == '\n' || buffer[i] == ' ')continue;
    			if (buffer[i] == ';') {
    				if (!is_sethead) {
    					this->setHead(temps[0]);
    					is_sethead = 1;
    				}
    				this->add(temps);
    				temps = "";
    			}
    			else
    				temps += buffer[i];
    		}
    		delete buffer;
    		/*
    			输出Vn,Vt,set
    			
    		*/
    		
    	}
    	void setHead(char c) {
    		S = c;
    	}
    	void add(string s) {
    		char s1 = s[0];
    		string s2="";
    		int num = 0;
    		for (int i = 0; i < s.length() ; i++) {
    			if (s[i] == '>')num=i;
    			if (num == 0)continue;
    			if (i > num)
    				s2 += s[i];
    		}
    		s2 += ';';
    		Vn.insert(s1);
    		string temp = "";
    		for (char s : s2) {
    			if (!isupper(s) && s != '|'&&s != ';'&&s!='@')Vt.insert(s);
    			if (s == '|' || s == ';') {
    				P[s1].insert(temp);
    				temp = "";
    			}
    			else {
    				temp += s;
    			}
    		}
    	}
    	void print() {
    		cout << "当前分析文法为:" << endl << endl;
    		for (set<char>::iterator it = Vn.begin(); it != Vn.end(); it++) {
    			char cur_s = *it;
    			for (set<string>::iterator it1 = P[cur_s].begin(); it1 != P[cur_s].end(); it1++) {
    				string cur_string = *it1;
    				cout << cur_s << "->" << cur_string << endl;
    			}
    		}
    	}
    	void getFirst() {
    		FIRST.clear();
    		//判断迭代次数
    		int iter = 4;
    		while (iter--) {
    			for (set<char>::iterator it = Vn.begin(); it != Vn.end(); it++) {
    				char cur_s = *it;
    				/*
    				cur_s->cur_string[0]
    					a加到A的FIRST集
    				cur_s->cur_string[0]
    					B的FITRST集加到A的FIRST集
    				*/
    				for (set<string>::iterator it1 = P[cur_s].begin(); it1 != P[cur_s].end(); it1++) {
    					string cur_string = *it1;
    					if (!isupper(cur_string[0])) {
    						FIRST[cur_s].insert(cur_string[0]);
    					}
    					else {
    						char nxt_s = cur_string[0];
    						for (set<char>::iterator it2 = FIRST[nxt_s].begin(); it2 != FIRST[nxt_s].end(); it2++) {
    							if ((*it2) != '@') {
    								FIRST[cur_s].insert(*it2);
    							}
    						}
    					}
    				}
    			}
    		}
    		//输出FIRST集
    		cout << "FIRST集为:" << endl << endl;
    		for (set<char>::iterator it = Vn.begin(); it != Vn.end();it++) {
    			char cur_s = *it;
    			cout << "FIRST()   " << cur_s ;
    			for (set<char>::iterator it1 = FIRST[cur_s].begin(); it1 != FIRST[cur_s].end(); it1++) {
    				 cout<<"       " << *it1 ;
    			}
    			cout << endl;
    		}
    	}
    	void getFollow() {
    		FOLLOW.clear();
    		FOLLOW[S].insert('#');
    		//判断迭代次数
    		int iter = 4;
    		while (iter--) {
    			for (set<char>::iterator it = Vn.begin(); it != Vn.end(); it++) {
    				char cur_s = *it;
    				/*
    				cur_s->cur_string[0]
    				a加到A的FIRST集
    				cur_s->cur_string[0]
    				B的FITRST集加到A的FIRST集
    				*/
    				for (set<string>::iterator it1 = P[cur_s].begin(); it1 != P[cur_s].end(); it1++) {
    					string cur_string = *it1;
    					for (int i = 0; i < cur_string.length() - 1; i++) {
    						/*
    							B->Ac
    							将c加到A的follow集
    						*/
    						if (isupper(cur_string[i]) && !isupper(cur_string[i + 1])) {
    							FOLLOW[cur_string[i]].insert(cur_string[i + 1]);
    						}
    						/*
    							B->AC
    							将C的first集加到A的follow集
    						*/
    						if (isupper(cur_string[i]) && isupper(cur_string[i + 1])) {
    							//遍历C的first去除@,加到A的follow集
    							for (auto it2 = FIRST[cur_string[i + 1]].begin(); it2 != FIRST[cur_string[i + 1]].end(); it2++) {
    								if((*it2)!='@')
    								FOLLOW[cur_string[i]].insert(*it2);
    							}
    						}
    						
    					}
    					/*
    					AC/ACK为最后两个或者三个
    					B->AC
    					B->ACK(K的first集含有@)
    					将B的follow集加入到C的follow集
    					*/
    					int len = cur_string.length();
    					if ( (len>=1&&isupper(cur_string[len - 1])) ) {
    						for (auto it2 = FOLLOW[cur_s].begin(); it2 != FOLLOW[cur_s].end(); it2++) {
    							if(isupper(cur_string[len - 1]))
    								FOLLOW[cur_string[len - 1]].insert(*it2);
    						}
    					}
    					if ((len >= 2 && isupper(cur_string[len - 2]) && isupper(cur_string[len - 1]) && FIRST[cur_string[len - 1]].count('@') > 0)) {
    						for (auto it2 = FOLLOW[cur_s].begin(); it2 != FOLLOW[cur_s].end(); it2++) {	
    							FOLLOW[cur_string[len - 2]].insert(*it2);
    						}
    					}
    				}
    			}
    		}
    		//输出FOLLOW集
    		cout << "FOLLOW集为:" << endl << endl;
    		for (set<char>::iterator it = Vn.begin(); it != Vn.end(); it++) {
    			char cur_s = *it;
    			cout << "FOLLOW()  " << cur_s;
    			for (set<char>::iterator it1 = FOLLOW[cur_s].begin(); it1 != FOLLOW[cur_s].end(); it1++) {
    				cout << "       " << *it1;
    			}
    			cout << endl;
    		}
    	}
    	void getTable() {
    		set<char>Vt_temp;
    		for (char c : Vt) {
    			Vt_temp.insert(c);
    		}
    		Vt_temp.insert('#');
    		for (auto it = Vn.begin(); it != Vn.end(); it++) {
    			char cur_s = *it;
    			for (auto it1 = P[cur_s].begin(); it1 != P[cur_s].end(); it1++) {
    				/*
    				产生式为
    					cur_s->cur_string
    				*/
    				string cur_string = *it1;
    				if (isupper(cur_string[0])) {
    					char first_s = cur_string[0];
    					for (auto it2 = FIRST[first_s].begin(); it2 != FIRST[first_s].end(); it2++) {
    						string TableLeft = "";
    						TableLeft = TableLeft +cur_s + *it2;
    						Table[TableLeft] = cur_string;
    					}
    					
    				}
    				else {
    					string TableLeft = "";
    					TableLeft = TableLeft+ cur_s + cur_string[0];
    					Table[TableLeft] = cur_string;
    				}	
    			}
    			if (FIRST[cur_s].count('@') > 0) {
    				for (auto it1 = FOLLOW[cur_s].begin(); it1 != FOLLOW[cur_s].end(); it1++) {
    					string TableLeft = "";
    					TableLeft =TableLeft+ cur_s + *it1;
    					Table[TableLeft] = "@";
    				}
    			}
    		}
    		/*
    			检查出错信息:即表格中没有出现过的
    		*/
    		
    		
    		for (auto it = Vn.begin(); it != Vn.end(); it++) {
    			for (auto it1 = Vt_temp.begin(); it1 != Vt_temp.end(); it1++) {
    				string TableLeft = "";
    				TableLeft =TableLeft+ *it + *it1;
    				if (!Table.count(TableLeft)) {
    					Table[TableLeft] = "error";
    				}
    			}
    		}
    		
    		/*
    			显示Table
    		*/
    		cout << "显示table表:" << endl << endl;
    		cout.setf(std::ios::left);
    		for (auto it1 = Vt_temp.begin(); it1 != Vt_temp.end(); it1++) {
    			if (it1 == Vt_temp.begin())cout << setw(10) << " ";
    			cout << setw(10) << *it1;
    		}
    		cout << endl;
    		for (auto it = Vn.begin(); it != Vn.end(); it++) {
    			for (auto it1 = Vt_temp.begin(); it1 != Vt_temp.end(); it1++) {
    				string TableLeft="";
    				if (it1 == Vt_temp.begin())cout << setw(10) << *it;
    				TableLeft =TableLeft+ *it + *it1;
    				cout << *it << "->" << setw(7) << Table[TableLeft];
    			}
    			cout << endl;
    		}
    	}
    	/*
    		每一次分析一个输入串
    		Sign为符号栈,出栈字符为x
    		输入字符串当前字符为a
    	*/
    	bool AnalyzePredict(string inputstring){
    		stack<char>Sign;
    		Sign.push('#');
    		Sign.push(S);
    		int StringPtr = 0;
    		char a = inputstring[StringPtr++];
    		bool flag = true;
    		while (flag) {
    			char x = Sign.top();
    			Sign.pop();
    			//如果是终结符,直接移出符号栈
    			if (Vt.count(x)) {
    				if (x == a)a = inputstring[StringPtr++];
    				else
    					return false;
    			}
    			else {
    				//如果不是终结符,
    				//如果是末尾符号
    				if (x == '#') {
    					if (x == a)flag = false;
    					else
    						return false;
    				}
    				else {
    					//如果是非终结符,需要移进操作
    					string left = "";
    					left += x;
    					left += a;
    					if (Table[left] != "error") {
    						string right = Table[left];
    //						cout << left << "---->" << right << endl;
    						for (int i = right.length() - 1; i >= 0; i--) {
    							Sign.push(right[i]);
    						}
    						
    					}
    					else {
    						return false;
    					}
    				}
    			}		
    		}
    		return true;
    	}
    	/*
    		消除左递归
    	*/
    	void remove_left_recursion(){
    		string tempVn = "";
    		for (auto it = Vn.begin(); it != Vn.end(); it++) {
    			tempVn += *it;
    		}
    		
    		for (int i = 0; i < tempVn.length(); i++) {
    			char pi = tempVn[i];
    			set<string>NewPRight;
    			for (auto it = P[pi].begin(); it != P[pi].end(); it++) {
    				bool isget = 0;
    				string right = *it;
    				for (int j = 0; j < i; j++) {
    					char pj = tempVn[j];
    					if (pj == right[0]) {
    						isget = 1;
    						for (auto it1 = P[pj].begin(); it1 != P[pj].end(); it1++) {
    							string s = *it1 + right.substr(1);
    							NewPRight.insert(s);
    						}
    					}
    				}
    				if (isget == 0) {
    					NewPRight.insert(right);
    				}
    			}
    			/*
    			for (int j = 0; j < i; j++) {
    				char pj=tempVn[j];
    				for (auto it = P[pi].begin(); it != P[pi].end(); it++) {
    					string right = *it;
    					if (right[0] == pj) {
    						for (auto itpj = P[pj].begin(); itpj != P[pj].end(); itpj++) {
    							string s = *itpj + right.substr(1);
    							NewPRight.insert(s);
    						}
    					}
    					else {
    						NewPRight.insert(right);
    					}
    				}
    			}
    			*/
    			if(i!=0)
    				P[pi] = NewPRight;
    
    			remove_left_gene(pi);
    		}
    	}
    	/*
    		提取左因子
    	*/
    	void remove_left_gene(char c) {
    		char NewVn;
    		for (int i = 0; i < 26; i++) {
    			NewVn = i + 'A';
    			if (!Vn.count(NewVn)) {
    				break;
    			}
    		}
    		bool isaddNewVn = 0;
    		for (auto it = P[c].begin(); it != P[c].end(); it++) {
    			string right = *it;
    			
    			if (right[0] == c) {
    				isaddNewVn = 1;
    				
    				break;
    			}
    		}
    		if (isaddNewVn) {
    			set<string>NewPRight;
    			set<string>NewPNewVn;
    			for (auto it = P[c].begin(); it != P[c].end(); it++) {
    				string right = *it;
    				if (right[0] != c) {
    					right += NewVn;
    					NewPRight.insert(right);
    				}
    				else {
    					right = right.substr(1);
    					right += NewVn;
    					NewPNewVn.insert(right);
    				}
    			}
    			Vn.insert(NewVn);
    			NewPNewVn.insert("@");
    			P[NewVn] = NewPNewVn;
    			P[c] = NewPRight;
    		}
    	}
    	void ShowByTogether() {
    		for (auto it = Vn.begin(); it != Vn.end(); it++) {
    			cout << *it << "->";
    			char c = *it;
    			for (auto it1 = P[c].begin(); it1 != P[c].end(); it1++) {
    				if (it1 == P[c].begin())cout << *it1;
    				else
    					cout << "|" << *it1;
    					
    			}
    			cout << endl;
    		}
    	}
    };
    int main() {
    	/*
    	文法测试
    	E->T|E+T;
    	T->F|T*F;
    	F->i|(E);
    
    	A->+TA|@;
    	B->*FB|@;
    	E->TA;
    	F->(E)|i;
    	T->FB;
    	直接将上面两个测试样例放在Gramar_test.txt中
    	*/
    	string filename_gramer = "D:\\c++Project\\fundamentals_of_compiling\\Parsing\\Gramar_test.txt";
    	Grammar *grammar=new Grammar(filename_gramer);
    	cout << "/-------------------------没有消除左递归-----------------------------/" << endl;
    	cout << "规格显示:" << endl;
    	grammar->ShowByTogether();
    	cout << endl;
    	grammar->getFirst();
    	cout << endl;
    	grammar->getFollow();
    	cout << endl;
    	grammar->getTable();
    	
    	cout << "/--------------------------------------------------------------------/" << endl<<endl<<endl;
    
    
    	cout << "/-------------------------已经消除左递归-----------------------------/" << endl;
    	/*
    	消除左递归之后的判断
    	*/
    	grammar->remove_left_recursion();
    	cout << "规格显示:" << endl;
    	cout << endl;
    	grammar->ShowByTogether();
    	grammar->getFirst();
    	cout << endl;
    	grammar->getFollow();
    	cout << endl;
    	grammar->getTable();
    	
    	cout << "/--------------------------------------------------------------------/" << endl << endl << endl;
    	cout << "/-------------------------对词法进行分析----------------------------/" << endl;
    	/*
    		目前的想法是使用第一个实验分离出不同的单词,对单词操作,
    		如果单词为+,*,等于他本身,否则等于i;
    		以下直接使用实验一的输出文本
    	*/
    	string filename= "D:\\c++Project\\fundamentals_of_compiling\\Parsing\\out.txt";
    	ifstream in(filename);
    	char buffer[200];
    	string inf="";
    	int num = 0;
    //	cout << "文法分析结果为:" << endl << endl;
    	if (in.is_open()) {
    		while (!in.eof()) {
    			in.getline(buffer, 100);
    //			cout << buffer << endl;
    			inf += buffer;
    			num++;
    		}
    	}
    	string row = "";
    	for (int i = 0; i < num-1; i++) {
    		int ptr = i * 13;
    		string temp = "";
    		for (int j = 1; j <= 5; j++) {
    			if (inf[j+ptr] == ' ')continue;
    			else
    				temp += inf[ptr+j];
    		}
    		if (temp == "+" || temp == "-" || temp == "*" || temp == "/" || temp == ">" || temp == "<" || temp == "=" || temp == "(" || temp == ")") {
    			row += temp;
    		}
    		else {
    			if (temp == ";") {
    				row += "#";
    				cout << "当前row为:   " << row << endl;
    				if (grammar->AnalyzePredict(row)) {
    					cout << "                                         正确" << endl;
    				}
    				else
    					cout << "                                         错误" << endl;
    				row = "";
    			}
    			else {
    				row += "i";
    			}
    		}
    	}
    	cout << "/--------------------------------------------------------------------/" << endl << endl << endl;
    	system("pause");
    	return 0;
    }
    
    

    实验截图

    实验代码结果显示部分非常详细,其中我实现了自动生成FITST集,FOLLOW集,显示table表,消除左递归。
    另外为了对比,我将未消除左递归的结果和已经消除的结果做对比,我们会发现不同。
    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述


    非常感谢大家对我博客的喜爱,之前确实写得比较粗略,我在补充点运行的细节。
    一、代码中的包含两个测试样例,分别为
    测试样例a:

    E->T|E+T;
    T->F|T*F;
    F->i|(E);
    

    测试样例b:

    A->+TA|@;
    B->*FB|@;
    E->TA;
    F->(E)|i;
    T->FB;
    

    将他们分别放在两个txt文件里头,例如代码中注释的,我将测试样例a放在了D:\\c++Project\\fundamentals_of_compiling\\Parsing\\Gramar_test.txt
    同时,注意windows系统的文件格式。
    测试 测试样例b时,更换文件内容即可。
    二、关于代码中的第二部分(对词法进行分析)
    代码内的文件D:\\c++Project\\fundamentals_of_compiling\\Parsing\\out.txt是将D:\\c++Project\\fundamentals_of_compiling\\Parsing\\Gramar_test.txt作为输入,运行上一篇博客的代码,得到的保存运行结果的文件。

    展开全文
  • 编译原理实验-LL1语法分析器(自动生成First、Follow)java 博主在做实验时,参考众多他人代码,发现bug众多,在[@moni_mm]代码基础上,与伙伴把能看到的BUG都做出修正,同时增添了一个GUI展示。再次我将代码做出...

    编译原理实验-LL1语法分析器(自动生成First、Follow)java

    博主在做实验时,参考众多他人代码,发现bug众多,在@moni_mm代码基础上,与伙伴把能看到的BUG都做出修正,同时增添了一个GUI展示。再次我将代码做出讲解。完整代码最下方贴出。

    一、数据结构

    下文程序运行的文法为:

    static String[] grammarStr = {"E->TG" ,"G->+TG|-TG" ,"G->ε" ,"T->FS" ,"S->*FS|/FS" ,"S->ε" ,"F->(E)" ,"F->i"};//相关文法
    

    处理的输入串为:

    static inStr="i+i*i#";//输入串
    

    -----首先要考虑FOLLOW、FIRST、终结符、非终结符、预测分析表、栈、各个产生式的存储的数据结构设计:

    static HashMap<Character, HashSet<Character>> FirstSet  = new HashMap<>();//构造FIRST集合
    static HashMap<String, HashSet<Character>> FirstSetX  = new HashMap<>();//生成任何符号串的first
    static HashMap<Character, HashSet<Character>> FollowSet = new HashMap<>();//构造FOLLOW集合
    static String[][] table;//预测分析表
    static HashSet<Character> VnSet = new HashSet<>();//非终结符Vn集合
    static HashSet<Character> VtSet = new HashSet<>();//终结符Vt集合
    static Stack<Character>   stack = new Stack<>();  //符号栈
    static HashMap<Character,ArrayList<String>> production = new HashMap<>();//产生式
    

    二、运行效果

    LL(1)预测分析的实现均在类LL1中得到实现,类GUI仅仅将结果在桌面程序得到展示,LL1也可单独运行,结果输出控制台:

    运行GUI(注释掉LL1的main即可,反之亦然):

    在这里插入图片描述

    运行LL1:在这里插入图片描述

    在这里插入图片描述

    三、类的设计

    • class: LL1(打印相关不与介绍)

        - dividechar()     将产生式填充进production,划分终结符(vt)与非终结符(vn)
        - First()          生成FIRST集(非终结符的)
        - getFirstX()      生成FIRST集(任意字符串的),Follow()需要调用
        - Follow()         生成FOLLOW集
        - insert()         将生成式插入表中
        - creatTable()     创建预测分析表
        - find(char X, char a)   寻找预测分析表中对应内容,X非终结符,a终结符
        - processLL1()     执行LL1栈分析
      
    • class:GUI(可专注于LL1即可,本处简略)
      - Gui(String title) 添加组件,创建面板
      - class Listener implements ActionListener 时间监听器(添加具体执行语句,展示LL1.stepList、LL1.FirstSet、LL1.FollowSet的数据)

    三、核心算法(求first\follow)

    • 求First集:
      first集叫做首终结符集下面是博主自己的理解,用的列子讲的。在博主自己学的时候,不会的时候,死磕概念是看不懂的。额,博主菜ji.
      基本就两种情况:(终结符的first即它本身)
      • 1.直接遇到终结符
        A->aBCd | ε
        若a,e为终结符,first(A)= {a,ε}。
      • 2.第一个为非终结符
        A->BC
        此时first(A)=first(B);值得注意的是,若first(B)包含空ε,需要继续求first(C )加入first(A)中。若first(c)仍旧包含空ε,将空字符ε加入first(A)。
    • 程序实现:
       /**
       * 生成非终结符的FIRST集的递归入口
       */
      static void First(){
          //遍历求每一个非终结符vn的first集
          for (Character vn: VnSet
               ) {
              getfisrst(vn);
          }
      }
      /**
       * 生成非终结符FIRST集的递归程序
       */
      static void getfisrst(Character ch){
          ArrayList<String> ch_production = production.get(ch);
          HashSet<Character> set = FirstSet.containsKey(ch) ? FirstSet.get(ch) : new HashSet<>();
          // 当ch为终结符vt
          if(VtSet.contains(ch)){
              set.add(ch);
              FirstSet.put(ch,set);
              return;
          }
          //ch为非终结符vn
          for (String str:ch_production
               ) {
                  int i = 0;
                  while (i < str.length()) {
                      char tn = str.charAt(i);
                      //递归
                      getfisrst(tn);
                      HashSet<Character> tvSet = FirstSet.get(tn);
                      // 将其first集加入左部
                      for (Character tmp : tvSet) {
                          if (tmp != 'ε')
                              set.add(tmp);
                      }
                      // 若包含空串 处理下一个符号
                      if (tvSet.contains('ε'))
                          i++;
                          // 否则退出 处理下一个产生式
                      else
                          break;
                  }
                  //此处处理产生式如A ->BC,B、C的first集都有ε
                  if(i==str.length())
                      set.add('ε');
          }
          FirstSet.put(ch,set);
      }
      
      • 求follow集:
        课本上规则如下:
    1. 将放到follow(S)中,其中S是开始符号,#将放到follow(S)中,其中S是开始符号,而#是输入右端的结束标记。

    2. 如果存在一个产生式A→αBβ,那么first(β)中除ε之外的所有符号都在follow(B)中。

    3. 如果存在一个产生式A→αB,或存在产生式A→αBβ(β可以是单个非终结符,或数个非终结符的组合,β或许是CD)且first(β)包含ε,那么follow(A)中的所有符号都在follow(B)中。

    举例说明:
    ①E→TE’
    ②E’→+TE’ | ε
    ③T→FT’
    ④T’→*FT’ | ε
    ⑤F→(E)| id
    各个规则的展现:
    规则一:E是文法的开始符号,第一步,follow(E).add(’#’)
    规则二:对于产生式①E→TE’,follow(T).add(first(E’))
    规则三:对于产生式①E→TE’,E’后面为空,故follow(E’).add(follow(E));又first(E’)包含空ε,follow(T).add(follow(E))

    对每条产生式套用上述规则,循环至各个follow集都不增加。
    因为:例如对于产生式①E→TE’,first(E’)包含空ε,follow(T).add(follow(E)),而此时follow(E)并未求完整。需要第二遍。

    • 程序实现:
      /**
         * 生成FOLLOW集
         */
        static void Follow(){
            //此处我多循环了几次,合理的方法应该是看每一个非终结符的follow集师傅增加,不增加即可停止循环。
            for (int i = 0; i <3 ; i++) {
                for (Character ch:VnSet
                ) {
                    getFollow(ch);
                }
    
            }
    
        }
      /**
         * 求单个字符的FOLLOW集
         */
        static void getFollow(char c){
            ArrayList<String> list = production.get(c);
                HashSet<Character> setA = FollowSet.containsKey(c) ? FollowSet.get(c) : new HashSet<Character>();
            //如果是开始符 添加 #
            if (c == start) {
                setA.add('#');
            }
            //查找输入的所有产生式,确定c的后跟 终结符
            for (Character ch : VnSet) {
                ArrayList<String> l = production.get(ch);
                for (String s : l)
                    for (int i = 0; i < s.length(); i++)
                        if (s.charAt(i) == c && i + 1 < s.length() && VtSet.contains(s.charAt(i + 1)))
                            setA.add(s.charAt(i + 1));
            }
            FollowSet.put(c, setA);
            //处理c的每一条产生式,从右向左分析,A->aBβ,
            for (String s : list) {
                int i = s.length() - 1;
                while (i >= 0 ) {
                    char tn = s.charAt(i);
                    //只处理非终结符
                    if(VnSet.contains(tn)){
                        // 都按 A->αBβ  形式处理
                        //若β不存在   followA 加入 followB
                        //若β存在,把β的非空first集  加入followB
                        //若β存在  且 first(β)包含空串   followA 加入 followB
    
                        //若β存在
                        if (s.length() - i - 1 > 0) {
                            String right = s.substring(i + 1);
                            //非空first集 加入 followB
                            HashSet<Character> setF = null;
                            if( right.length() == 1){
                                if(!FirstSet.containsKey(right.charAt(0)))
                                    getfisrst(right.charAt(0));
                                setF = FirstSet.get(right.charAt(0));
                            }
                            else{
                                //先找出右部的first集
                                if(!FirstSetX.containsKey(right))
                                    getFirstX(right);
                                setF =FirstSetX.get(right);
                            }
                            HashSet<Character> setX = FollowSet.containsKey(tn) ? FollowSet.get(tn) : new HashSet<Character>();
                            for (Character var : setF)
                                if (var != 'ε')
                                    setX.add(var);
                            FollowSet.put(tn, setX);
    
                            // 若first(β)包含空串   followA 加入 followB
                            if(setF.contains('ε')){
                                if(tn != c){
                                    HashSet<Character> setB =FollowSet.containsKey(tn) ? FollowSet.get(tn) : new HashSet<Character>();
                                    for (Character var : setA)
                                        setB.add(var);
                                    FollowSet.put(tn, setB);
                                }
                            }
                        }
                        //若β不存在   followA 加入 followB
                        else{
                            // A和B相同不添加
                            if(tn != c){
                                HashSet<Character> setB = FollowSet.containsKey(tn) ? FollowSet.get(tn) : new HashSet<Character>();
                                for (Character var : setA)
                                    setB.add(var);
                                FollowSet.put(tn, setB);
                            }
                        }
                        i--;
                    }
                    //如果是终结符往前看  如 A->aaaBCDaaaa  此时β为 CDaaaa
                    else i--;
                }
            }
        }
    

    四、完整代码

    IDEA 工程文件放在github上:https://github.com/mhl222/BiYiYuanLi_2
    大家可直接git clone下来运行

    import javax.swing.*;
    import javax.swing.table.DefaultTableModel;
    import java.awt.*;
    import java.awt.event.ActionEvent;
    import java.awt.event.ActionListener;
    import java.util.*;
    /**
    * class:
    * --LL1:
    *      实现LL(1)分析,构造分析预测程序(FIRST集-->FOLLOW集-->分析预测表-->stack预测分析)
    * --Gui:
    *      读取输入串,桌面程序展示分析预测步骤
    */
    
    public class LL1 {
       static String[] grammarStr = {"E->TG" ,"G->+TG|-TG" ,"G->ε" ,"T->FS" ,"S->*FS|/FS" ,"S->ε" ,"F->(E)" ,"F->i"};//相关文法
       static HashMap<Character,ArrayList<String>> production = new HashMap<>();//产生式
       static HashMap<Character, HashSet<Character>> FirstSet  = new HashMap<>();//构造FIRST集合
       static HashMap<String, HashSet<Character>> FirstSetX  = new HashMap<>();//生成任何符号串的first
       static HashMap<Character, HashSet<Character>> FollowSet = new HashMap<>();//构造FOLLOW集合
       static String[][] table;//预测分析表
       static HashSet<Character> VnSet = new HashSet<>();//非终结符Vn集合
       static HashSet<Character> VtSet = new HashSet<>();//终结符Vt集合
       static Stack<Character>   stack = new Stack<>();  //符号栈
       static String inStr="i+i*i#";//输入串
       static Character start = 'E';
       static int index = 0;//输入字符指针
       static String action ="";
       static ArrayList<Vector>  stepList = new ArrayList<>();//与LL(1)无关,可不关心,为GUI记录了stack每一步的变化
       public static void main(String[] args) {
           dividechar();
           First();
           for (Character c : VnSet) {
               ArrayList<String> l = production.get(c);
               for (String s : l)
                  getFirstX(s);
           }
           Follow();
           creatTable();
           ouput();
           processLL1();
    
       }
    
       /**
        * 生成产生式Map(production),划分终结符(vt)与非终结符(vn)
        */
       static void dividechar(){
           //生成产生式Map(production)
           for (String str:grammarStr
                ) {
               //将“|”相连的产生式分开
               String[] strings = str.split("->")[1].split("\\|");
               //非终结符
               char Vch = str.charAt(0);
               ArrayList<String> list = production.containsKey(Vch) ? production.get(Vch) : new ArrayList<String>();
               for (String S:strings
                    ) {
                   list.add(S);
               }
               production.put(str.charAt(0),list);
               VnSet.add(Vch);
           }
           //寻找终结符
           for (Character ch:VnSet
               ){
               for (String str : production.get(ch)
                    ) {
                   for (Character c: str.toCharArray()
                   ) {
                       if( !VnSet.contains(c) )
                           VtSet.add(c);
                   }
               }
    
           }
    
       }
       /**
        * 生成非终结符的FIRST集的递归入口
        */
       static void First(){
           //遍历求每一个非终结符vn的first集
           for (Character vn: VnSet
                ) {
               getfisrst(vn);
           }
       }
       /**
        * 生成非终结符FIRST集的递归程序
        */
       static void getfisrst(Character ch){
           ArrayList<String> ch_production = production.get(ch);
           HashSet<Character> set = FirstSet.containsKey(ch) ? FirstSet.get(ch) : new HashSet<>();
           // 当ch为终结符
           if(VtSet.contains(ch)){
               set.add(ch);
               FirstSet.put(ch,set);
               return;
           }
           //ch为vn
           for (String str:ch_production
                ) {
                   int i = 0;
                   while (i < str.length()) {
                       char tn = str.charAt(i);
                       //递归
                       getfisrst(tn);
                       HashSet<Character> tvSet = FirstSet.get(tn);
                       // 将其first集加入左部
                       for (Character tmp : tvSet) {
                           if (tmp != 'ε')
                               set.add(tmp);
                       }
                       // 若包含空串 处理下一个符号
                       if (tvSet.contains('ε'))
                           i++;
                           // 否则退出 处理下一个产生式
                       else
                           break;
                   }
                   if(i==str.length())
                       set.add('ε');
           }
           FirstSet.put(ch,set);
       }
       /**
        * 生成任何符号串的first
        */
       static void getFirstX(  String s) {
    
               HashSet<Character> set = (FirstSetX.containsKey(s))? FirstSetX.get(s) : new HashSet<Character>();
               // 从左往右扫描该式
               int i = 0;
               while (i < s.length()) {
                   char tn = s.charAt(i);
                   if(!FirstSet.containsKey(tn))
                       getfisrst(tn);
                   HashSet<Character> tvSet = FirstSet.get(tn);
                   // 将其非空 first集加入左部
                   for (Character tmp : tvSet)
                       if(tmp != 'ε')
                           set.add(tmp);
                   // 若包含空串 处理下一个符号
                   if (tvSet.contains('ε'))
                       i++;
                       // 否则结束
                   else
                       break;
                   // 到了尾部 即所有符号的first集都包含空串 把空串加入
                   if (i == s.length()) {
                       set.add('ε');
                   }
               }
               FirstSetX.put(s, set);
    
    
       }
       /**
        * 生成FOLLOW集
        */
       static void Follow(){
           //此处我多循环了几次,合理的方法应该是看每一个非终结符的follow集师傅增加,不增加即可停止循环。
           for (int i = 0; i <3 ; i++) {
               for (Character ch:VnSet
               ) {
                   getFollow(ch);
               }
    
           }
    
       }
       static void getFollow(char c){
           ArrayList<String> list = production.get(c);
               HashSet<Character> setA = FollowSet.containsKey(c) ? FollowSet.get(c) : new HashSet<Character>();
           //如果是开始符 添加 #
           if (c == start) {
               setA.add('#');
           }
           //查找输入的所有产生式,确定c的后跟 终结符
           for (Character ch : VnSet) {
               ArrayList<String> l = production.get(ch);
               for (String s : l)
                   for (int i = 0; i < s.length(); i++)
                       if (s.charAt(i) == c && i + 1 < s.length() && VtSet.contains(s.charAt(i + 1)))
                           setA.add(s.charAt(i + 1));
           }
           FollowSet.put(c, setA);
           //处理c的每一条产生式
           for (String s : list) {
               int i = s.length() - 1;
               while (i >= 0 ) {
                   char tn = s.charAt(i);
                   //只处理非终结符
                   if(VnSet.contains(tn)){
                       // 都按 A->αBβ  形式处理
                       //若β不存在   followA 加入 followB
                       //若β存在,把β的非空first集  加入followB
                       //若β存在  且 first(β)包含空串   followA 加入 followB
    
                       //若β存在
                       if (s.length() - i - 1 > 0) {
                           String right = s.substring(i + 1);
                           //非空first集 加入 followB
                           HashSet<Character> setF = null;
                           if( right.length() == 1){
                               if(!FirstSet.containsKey(right.charAt(0)))
                                   getfisrst(right.charAt(0));
                               setF = FirstSet.get(right.charAt(0));
                           }
                           else{
                               //先找出右部的first集
                               if(!FirstSetX.containsKey(right))
                                   getFirstX(right);
                               setF =FirstSetX.get(right);
                           }
                           HashSet<Character> setX = FollowSet.containsKey(tn) ? FollowSet.get(tn) : new HashSet<Character>();
                           for (Character var : setF)
                               if (var != 'ε')
                                   setX.add(var);
                           FollowSet.put(tn, setX);
    
                           // 若first(β)包含空串   followA 加入 followB
                           if(setF.contains('ε')){
                               if(tn != c){
                                   HashSet<Character> setB =FollowSet.containsKey(tn) ? FollowSet.get(tn) : new HashSet<Character>();
                                   for (Character var : setA)
                                       setB.add(var);
                                   FollowSet.put(tn, setB);
                               }
                           }
                       }
                       //若β不存在   followA 加入 followB
                       else{
                           // A和B相同不添加
                           if(tn != c){
                               HashSet<Character> setB = FollowSet.containsKey(tn) ? FollowSet.get(tn) : new HashSet<Character>();
                               for (Character var : setA)
                                   setB.add(var);
                               FollowSet.put(tn, setB);
                           }
                       }
                       i--;
                   }
                   //如果是终结符往前看  如 A->aaaBCDaaaa  此时β为 CDaaaa
                   else i--;
               }
           }
       }
       /**
        * 生成预测分析表
        */
       static void creatTable(){
           Object[] VtArray = VtSet.toArray();
           Object[] VnArray = VnSet.toArray();
           // 预测分析表初始化
           table = new String[VnArray.length + 1][VtArray.length + 1];
           table[0][0] = "Vn/Vt";
           //初始化首行首列
           for (int i = 0; i < VtArray.length; i++)
               table[0][i + 1] = (VtArray[i].toString().charAt(0) == 'ε') ? "#" : VtArray[i].toString();
           for (int i = 0; i < VnArray.length; i++)
               table[i + 1][0] = VnArray[i] + "";
           //全部置error
           for (int i = 0; i < VnArray.length; i++)
               for (int j = 0; j < VtArray.length; j++)
                   table[i + 1][j + 1] = "error";
    
           //插入生成式
           for (char A : VnSet) {
               ArrayList<String> l = production.get(A);
               for(String s : l){
                   HashSet<Character> set = FirstSetX.get(s);
                   for (char a : set)
                       insert(A, a, s);
                   if(set.contains('ε'))  {
                       HashSet<Character> setFollow = FollowSet.get(A);
                       if(setFollow.contains('#'))
                           insert(A, '#', s);
                       for (char b : setFollow)
                           insert(A, b, s);
                   }
               }
           }
       }
       /**
        * 将生成式插入表中
        */
       static void insert(char X, char a,String s) {
           if(a == 'ε') a = '#';
           for (int i = 0; i < VnSet.size() + 1; i++) {
               if (table[i][0].charAt(0) == X)
                   for (int j = 0; j < VtSet.size() + 1; j++) {
                       if (table[0][j].charAt(0) == a){
                           table[i][j] = s;
                           return;
                       }
                   }
           }
       }
    
       /**
        * 返回当前栈内容的字符串,与LL(1)无关,为GUI提供字符串
        *
        */
       static String getStack(){
           String str ="";
           for (Character ch : stack
                ) {
               str+=ch;
           }
           return str;
       }
    
       /**
        * 与LL(1)无关,为GUI的表格所需的setpList,提供一行数据
        */
       static void addRowToList(String production,String action){
           Vector v = new Vector();
           v.add(stepList.size()+1);
           v.add(getStack());
           v.add(inStr.substring(index));
           v.add(production);
           v.add(action);
           stepList.add(v);
       }
    
       /**
        * 执行LL1栈分析
        */
       static void processLL1(){
           System.out.println("****************LL分析过程**********");
           System.out.println("               Stack           Input     Action");
           stack.push('#');
           stack.push('E');
           addRowToList("","");//GUI数据,可不关心
           displayLL();
           char X = stack.peek();
           while (X != '#') {
               char a = inStr.charAt(index);
               if (X == a) {
                   action = "match " + stack.peek();
                   stack.pop();
                   index++;
                   addRowToList("","POP,GETNEXT(I)");//GUI数据,可不关心
    
               }
    //            }else if (VtSet.contains(X))
    //                return;
               else if (find(X, a).equals("error")){
                   boolean flag = false;
                   if(FirstSet.get(X).contains('ε')){
    
                       addRowToList(X+"->ε","POP");//GUI数据,可不关心
                       action = X+"->ε";
                       stack.pop();
                       flag = true;
                   }
                   if(!flag){
                       action="error";
                      addRowToList("","ERROR");//GUI数据,可不关心
                       displayLL();
                       return;
                   }
    
               }
               else if (find(X, a).equals("ε")) {
                   stack.pop();
                   action = X + "->ε";
                   addRowToList(action,"POP");//GUI数据,可不关心
               }
               else {
                   String str = find(X, a);
                   if (str != "") {
                       action = X + "->" + str;
                       stack.pop();
                       int len = str.length();
                       String pushStr="";
                       for (int i = len - 1; i >= 0; i--){
                           stack.push(str.charAt(i));
                           pushStr+=str.charAt(i);
                       }
                       addRowToList(action,"POP,PUSH("+pushStr+")");//GUI数据,可不关心
                   }
                   else {
                       System.out.println("error at '" + inStr.charAt(index) + " in " + index);
                       return;
                   }
               }
               X = stack.peek();
               displayLL();
           }
           System.out.println("analyze LL1 successfully");
           System.out.println("****************LL分析过程**********");
       }
    
       /**
        *
        * @param X 非终结符
        * @param a 终结符
        * @return  预测分析表中对应内容
        */
       static String find(char X, char a) {
           for (int i = 0; i < VnSet.size() + 1; i++) {
               if (table[i][0].charAt(0) == X)
                   for (int j = 0; j < VtSet.size() + 1; j++) {
                       if (table[0][j].charAt(0) == a)
                           return table[i][j];
                   }
           }
           return "";
       }
       static void displayLL() {
           // 输出 LL1单步处理
           Stack<Character> s = stack;
           System.out.printf("%23s", s);
           System.out.printf("%13s", inStr.substring(index));
           System.out.printf("%10s", action);
           System.out.println();
       }
       /**
        * 打印first.follow集,预测分析表
        */
       static void ouput() {
           System.out.println("*********first集********");
           for (Character c : VnSet) {
               HashSet<Character> set = FirstSet.get(c);
               System.out.printf("%10s",c + "  ->   ");
               for (Character var : set)
                   System.out.print(var);
               System.out.println();
           }
           System.out.println("**********first集**********");
    
           System.out.println("**********follow集*********");
    
           for (Character c : VnSet) {
               HashSet<Character> set =FollowSet.get(c);
               System.out.print("Follow " + c + ":");
               for (Character var : set)
                   System.out.print(var);
               System.out.println();
           }
           System.out.println("**********follow集**********");
    
           System.out.println("**********LL1预测分析表********");
    
           for (int i = 0; i < VnSet.size() + 1; i++) {
               for (int j = 0; j < VtSet.size() + 1; j++) {
                   System.out.printf("%6s", table[i][j] + " ");
               }
               System.out.println();
           }
           System.out.println("**********LL1预测分析表********");
       }
    }
    class Gui extends JFrame {
       static JButton btnLL1 = new JButton("LL(1)分析");
       static JTextField input = new JTextField("i+i*i#",8);
       static JLabel label = new JLabel("输入串:");
       static JLabel first = new JLabel("FIRST:");
       static JLabel follow = new JLabel("FOLLOW:");
       static JLabel tit = new JLabel("---------------      LL(1)单步     -------------");
       static JPanel contentPanel = new JPanel();
    
       static Vector row= new Vector();;
       static Vector row2= new Vector();
       static Vector row3= new Vector();
       static Vector columnNames2 = new Vector() ;
       static Vector columnNames1 = new Vector() ;
       static JTable table3;
       static JTable table2;
       static JTable table;
    
    //    public static void main(String[] args) {
    //        new Gui("LL1");
    //    }
       public Gui(String title) throws HeadlessException {
    
           super(title);
           setSize(550,500);
           setResizable(false);
    
           contentPanel.setLayout(null);
           columnNames1.add("步骤");
           columnNames1.add("分析栈");
           columnNames1.add( "剩余输入串");
           columnNames1.add("所用产生式");
           columnNames1.add("动作");
           table = new JTable(row,columnNames1);
           JScrollPane scrollPane1 = new JScrollPane(table);
    
    
    
           columnNames2.add("非终结符");
           columnNames2.add("结果");
           table2 = new JTable(row2,columnNames2);
           JScrollPane scrollPane2 = new JScrollPane(table2);
           table3 = new JTable(row3,columnNames2);
           JScrollPane scrollPane3 = new JScrollPane(table3);
           contentPanel.add(btnLL1);
           contentPanel.add(input);
           contentPanel.add(label);
           contentPanel.add(first);
           contentPanel.add(follow);
           contentPanel.add(scrollPane1);
           contentPanel.add(scrollPane2);
           contentPanel.add(scrollPane3);
           contentPanel.add(tit);
    
           label.setBounds(5,5,110,30);
           input.setBounds(70,8,100,25);
           btnLL1.setBounds(180,8,100,25);
           first.setBounds(5,40,110,30);
           follow.setBounds(280,40,110,30);
           tit.setBounds(150,180,300,30);
           scrollPane1.setBounds(5,220,520,200);
           scrollPane2.setBounds(5,70,250,100);
           scrollPane3.setBounds(280,70,250,100);
           btnLL1.addActionListener(new Listener());
    
           this.add(contentPanel);
           this.setVisible(true);
           this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    
       }
    
       class Listener implements ActionListener {
    
           @Override
           public void actionPerformed(ActionEvent actionEvent) {
    
               if(actionEvent.getSource()==btnLL1){
                   String in = input.getText();
                   LL1.inStr = in;
                   LL1.dividechar();
                   LL1.First();
    
                   for (Character ch:LL1.VnSet
                        ) {
                       HashSet<Character> firset = LL1.FirstSet.get(ch);
                       String token = "";
                       for (Character c:firset
                            ) {
                           token+=c;
                       }
                       Vector vc = new Vector();
                       vc.add(ch);
                       vc.add(token);
                       ((DefaultTableModel)Gui.table2.getModel()).addRow(vc);
                   }
                   for (Character c : LL1.VnSet) {
                       ArrayList<String> l = LL1.production.get(c);
                       for (String s : l)
                           LL1.getFirstX(s);
                   }
                   LL1.Follow();
                   for (Character chr:LL1.VnSet
                   ) {
                       HashSet<Character> firset = LL1.FollowSet.get(chr);
                       String token1 = "";
                       for (Character c:firset
                       ) {
                           token1+=c;
                       }
                       Vector vc1 = new Vector();
                       vc1.add(chr);
                       vc1.add(token1);
                       ((DefaultTableModel)Gui.table3.getModel()).addRow(vc1);
                   }
                   LL1.creatTable();
                   LL1.processLL1();
    
                   for (Vector vc2: LL1.stepList
                        ) {
                       ((DefaultTableModel)Gui.table.getModel()).addRow(vc2);
                   }
    
    
    
    
               }
           }
       }
    
    }
    
    展开全文
  • ll1语法分析器

    热门讨论 2008-04-18 17:49:50
    用类c语言实现的ll_文法分析器, 构造first,follow集,预测分析表等
  • LL1语法分析器3(WINDOW).rar LL1语法分析器3(WINDOW).rar
  • 【编译原理】LL1文法语法分析器

    千次阅读 2019-06-19 11:25:35
    【编译原理】LL1文法语法分析器 作者:杨博东的博客 原文:https://blog.csdn.net/yangbodong22011/article/details/53415401 上篇文章 【编译原理】语法分析——自上向下分析 分析了LL1语法,文章最后说给出...

    【编译原理】LL1文法语法分析器

    作者:杨博东的博客 
    原文:https://blog.csdn.net/yangbodong22011/article/details/53415401 

    上篇文章 【编译原理】语法分析——自上向下分析 分析了LL1语法,文章最后说给出栗子,现在补上去。

    说明:

    这个语法分析器是利用LL1分析方法实现的。
    预测分析表和终结符以及非终结符都是针对一个特定文法定义好的。
    输入的分析串必须以 # 开头和结尾。

    原始文法:

    E -> E + T | T
    T -> T * T | F
    F -> (E) | i

    消除左递归之后:

    E -> TE'
    E' -> +TE' | e
    T -> FT'
    T' -> *FT' | e
    F -> (E) | i

    //备注 
    e 表示 一步赛楞
    E' 在实际程序中用Z代替
    T' 在实际程序中用Y代替

    程序如下:

    // LL2.cpp: 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<iostream>
    #include<cstdlib>
    #include<vector>
    #include<string>
    #include<stack>
    
    #define BEGIN_SYB 'E'
    
    class Tab {                   //预测分析表中单个产生式
    public:
    	Tab(char n, char e, std::string p) :noend(n), end(e), prod(p) {};
    
    	char noend;
    	char end;
    	std::string prod;
    };
    
    std::vector<Tab>  pTab;       //预测分析表
    std::stack<char>  pStack;     //栈
    std::string       pStr;       //输入串
    int               index = 0;  //输入串的下标
    int               num = 0;    //下标
    char              X;          //从栈顶取出的符号
    char              a;          //字符串目前分析到的位置
    std::vector<char> VT{ 'i','+','*','(',')','#' };    //终结符号集合
    std::vector<char> VN{ 'E','Z','T','Y','F' };    //非终结符号集合
    
    int
    isPartVT(char ch)
    {
    	for (auto u : VT) {
    		if (u == ch) {
    			return 1;
    		}
    	}
    	return 0;
    }
    
    int
    isPartVN(char ch)
    {
    	for (auto u : VN) {
    		if (u == ch) {
    			return 1;
    		}
    	}
    	return 0;
    }
    
    void
    initpTab()
    {
    	pTab.push_back(Tab('E', 'i', "TZ"));       //Z表示E'
    	pTab.push_back(Tab('E', '(', "TZ"));
    	pTab.push_back(Tab('Z', '+', "+TZ"));
    	pTab.push_back(Tab('Z', ')', "$"));
    	pTab.push_back(Tab('Z', '#', "$"));
    	pTab.push_back(Tab('T', 'i', "FY"));
    	pTab.push_back(Tab('T', '(', "FY"));       //Y表示T'
    	pTab.push_back(Tab('Y', '+', "$"));
    	pTab.push_back(Tab('Y', '*', "*FY"));
    	pTab.push_back(Tab('Y', ')', "$"));
    	pTab.push_back(Tab('Y', '#', "$"));
    	pTab.push_back(Tab('F', 'i', "i"));
    	pTab.push_back(Tab('F', '(', "(E)"));
    }
    
    void
    printStack()
    {
    	std::stack<char> pTemp(pStack);
    	while (pTemp.size() != 0) {
    		std::cout << pTemp.top() << " ";
    		pTemp.pop();
    	}
    	std::cout << "         ";
    }
    
    int
    synaly()
    {
    	pStack.push(pStr[index++]);
    	pStack.push(BEGIN_SYB);
    	a = pStr[index++];
    	bool flag = true;
    	while (flag) {
    		std::cout << num++ << "        ";  //输出行号
    		printStack();
    		if (pStack.size() != 0) {
    			X = pStack.top();              //将符号栈顶给X
    			pStack.pop();
    		}
    
    		if (isPartVT(X)) {                  //如果是终结符
    			if (X == '#' && a == '#') {
    				flag = false;
    			}
    			else if (X == a) {
    				std::cout << std::endl;
    				a = pStr[index++];
    			}
    			else {
    				std::cout << "EROOR!" << std::endl;
    				return 0;
    			}
    
    		}
    		else if (X == '#') {
    			if (X == a) {
    				flag = false;
    			}
    			else {
    				std::cout << "EROOR!" << std::endl;
    				return 0;
    			}
    
    		}
    		else if (isPartVN(X) && isPartVT(a)) {  //如果非终结符
    			int type = 0;
    			for (auto u : pTab) {
    				if (u.noend == X && u.end == a) {
    					std::string tempProd = u.prod;
    					std::cout << X << "->" << tempProd << std::endl;
    					if (tempProd == "$") {
    						type = 1;
    						break;
    					}
    					else {
    						for (int i = tempProd.size() - 1; i >= 0; --i) {
    							pStack.push(tempProd[i]);
    						}
    						type = 1;
    						break;
    					}
    				}
    			}
    			if (type != 1) {
    				std::cout << "EROOR!" << std::endl;
    				return 0;
    
    			}
    
    		}
    		else {
    			std::cout << "EROOR!" << std::endl;
    			return 0;
    		}
    
    	}
    	return 1;
    }
    
    int main(int argc, char *argv[])
    {
    	initpTab();
    	std::cout << "请输入语法串:";
    	std::cin >> pStr;
    	std::cout << "步骤" << "     " << "符号栈" << "      " << "所用产生式" << std::endl;
    	int flag = synaly();
    	std::cout << std::endl;
    	if (flag == 1) {
    		std::cout << "分析成功~~" << std::endl;
    	}
    	else {
    		std::cout << "分析失败~~" << std::endl;
    	}
    	system("pause");
    	return 0;
    }

     


     

    展开全文
  • LL1语法分析,编译原理实验,非常好的程序
  • 编译原理课设 LL1语法分析器,注释掉的一部分代码是可以扩展的部分
  • LL(1)语法分析器

    2018-09-29 21:12:47
    通过Java完成LL(1)语法分析器。 (1)通过文件扫描,识别出终结符与非终结符; (2)求解first集与follow集; (3)根据first集与follow集构建预测分析表; (4)写总控程序; (5)进行字符串匹配。
  • LL1通用语法分析器(java实现完整代码) import java.awt.*; import java.awt.event.*; import javax.swing.*; import javax.swing.table.DefaultTableModel; import java.sql.*; import java.util.Vector; //以LL...

    LL1通用语法分析器(java实现完整代码)

    import java.awt.*;
    import java.awt.event.*;
    import javax.swing.*;
    import javax.swing.table.DefaultTableModel;
    import java.sql.*;
    import java.util.Vector;
    
    //以LL(1)分析法对任意输入的符号串进行分析的语法分析程序
    public class LL1 extends JFrame implements ActionListener{
        private static final long serialVersionUID = 1L;
        JTextField tf1;
        JTextField tf2;
        JLabel l;
        JButton b0;
        JPanel p1,p2,p3;
        JTextArea t1,t2,t3;
        JButton b1,b2,b3;
        JLabel l0,l1,l2,l3,l4;
        JTable table;
        Statement sta;
        Connection conn;
        ResultSet rs;
        DefaultTableModel dtm;
        String Vn[]=null;
        Vector<String> P=null;
    
        int firstComplete[]=null;//存储已判断过first的数据
        char first[][]=null;//存储最后first结果
        int followComplete[]=null;//存储已判断过follow的数据
        char follow[][]=null;//存储最后follow结果
        char select[][]=null;//存储最后select结果
        int LL=0;//标记是否为LL(1)
        String vt_tou[]=null;//储存Vt
        Object shuju[][]=null;//存储表达式数据
        char yn_null[]=null;//存储能否推出空
    
    
        LL1()//基本布局
        {
            setLocation(100,0);
            setSize(700,780);
            tf1=new JTextField(13);
            tf2=new JTextField(13);
            l=new JLabel(">>");
            l0=new JLabel("输入字符串:");
            l1=new JLabel("输入的文法为:                                                                         ");
            l2=new JLabel(" ");
            l3=new JLabel("分析的结果:                                                                              ");
            l4=new JLabel("预测分析表:                                                                                                                                             ");
            //p1=new JPanel();
            p2=new JPanel();
            p3=new JPanel();
            t1=new JTextArea(24,20);
            t2=new JTextArea(1,30);
            t3=new JTextArea(24,40);
            b0=new JButton("确定(S为开始)");
            b1=new JButton("       判断文法                ");
            b2=new JButton("输入");
            b3=new JButton("清空");
            table=new JTable();
            JScrollPane jp1=new JScrollPane(t1);
            JScrollPane jp2=new JScrollPane(t2);
            JScrollPane jp3=new JScrollPane(t3);
            p2.add(tf1);
            p2.add(l);
            p2.add(tf2);
    
            p2.add(b0);
            p2.add(b1);
            p2.add(l0);
            p2.add(l2);
            p2.add(jp2);
            p2.add(b2);
            p2.add(b3);
    
            p2.add(l1);
            p2.add(l3);
            p2.add(jp1);
            p2.add(jp3);
    
            p3.add(l4);
            p3.add(new JScrollPane(table));
            add(p2,"Center");
            add(p3,"South");
    
            b0.addActionListener(this);
            b1.addActionListener(this);
            b2.addActionListener(this);
            b3.addActionListener(this);
            setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
            table.setPreferredScrollableViewportSize(new Dimension(660,200));
            setVisible(true);
    
        }
    
        public void actionPerformed(ActionEvent e)
        {
            if(e.getSource()==b0)
            {
                String a=tf1.getText();
                String b=tf2.getText();
                t1.append(a+'→'+b+'\n');
            }
            if(e.getSource()==b1)
            {
                t3.setText("");
                int Vnnum=0,k;
                Vn=new String[100];
                P=new Vector<String>();
                String s[]=t1.getText().split("\n");
    
                for(int i=0;i<s.length;i++)
                {
                    if(s.length<2){
                        t3.setText("文法输入有误,请重新输入");//判断长度是否符合
                        return;
                    }
                    if(s[i].charAt(0)<='Z'&&s[i].charAt(0)>='A'&&s[i].charAt(1)=='→')
                    {
                        for(k=0;k<Vnnum;k++)
                        {
                            if(Vn[k].equals(s[i].substring(0, 1))){
                                break;
                            }
                        }
                        if(Vnnum==0||k>=Vnnum)
                        {
                            Vn[Vnnum]=s[i].substring(0, 1);//存入Vn数据
                            Vnnum++;
                        }
                        P.add(s[i]);
                    }
                    else
                    {
                        t3.setText("文法输入有误,请重新输入");
                        return;
                    }
                }
                yn_null=new char[100];
                first=new char[Vnnum][100];
                int flag=0;
                String firstVn[]=null;
                firstComplete=new int[Vnnum];
    
                for(int i=0;Vn[i]!=null;i++)   //依次求 FIRST**
                {
                    flag=0;
                    firstVn=new String[20];
                    if((flag=add_First(first[i],Vn[i],firstVn,flag))==-1)return;
                    firstComplete[i]=1;
    
                }
                t3.append("first集:"+"\n");   //显示FIRST**
                for(int i=0;Vn[i]!=null;i++)
                {
                    t3.append("first("+Vn[i]+")={ ");
                    for(int j=0;first[i][j]!='\0';j++)
                    {
                        t3.append(first[i][j]+" , ");
                    }
                    t3.append("}"+"\n");
                }
                follow=new char[Vnnum][100];
                String followVn[]=null;
                followComplete=new int[Vnnum];
    
                for(int i=0;Vn[i]!=null;i++)   //求FOLLOW**
                {
                    flag=0;
                    followVn=new String[20];
                    if((flag=tianjiaFollow(follow[i],Vn[i],followVn,flag))==-1)return;
                    followComplete[i]=1;
                }
                t3.append("follow集:"+"\n");      //显示FOLLOW**
                for(int i=0;Vn[i]!=null;i++)
                {
                    t3.append("follow("+Vn[i]+")={ ");
                    for(int j=0;follow[i][j]!='\0';j++)
                    {
                        t3.append(follow[i][j]+" , ");
                    }
                    t3.append("}"+"\n");
                }
                select=new char[P.size()][100];
    
                for(int i=0;i<P.size();i++)          //求SELECT**
                {
                    flag=0;
                    tianjiaSelect(select[i],(String)P.elementAt(i),flag);
                }
                t3.append("select集:"+"\n");        //显示SELECT**
                for(int i=0;i<P.size();i++)
                {
                    t3.append("select("+(String)P.elementAt(i)+")={ ");
                    for(int j=0;select[i][j]!='\0';j++)
                    {
                        t3.append(select[i][j]+" , ");
                    }
                    t3.append("}"+"\n");
                }
    
                for(int i=0;Vn[i]!=null;i++)//判断select交集是否为空
                {
                    int biaozhi=0;
                    char save[]=new char[100];
                    for(int j=0;j<P.size();j++)
                    {
                        String t=(String)P.elementAt(j);
    
                        if(t.substring(0,1).equals(Vn[i]))
                        {
                            for(k=0;select[j][k]!='\0';k++)
                            {
                                if(puanduanChar(save,select[j][k]))
                                {
                                    save[biaozhi]=select[j][k];
                                    biaozhi++;
                                }
                                else//当有交集时,不为LL(1)文法
                                {
                                    t3.append("不是LL(1)文法!!"+"\n");
                                    return;
                                }
                            }
                        }
                    }
                }
                char Vt[]=new char[100];
                int biaozhi=0;
                for(int i=0;i<P.size();i++)
                {
                    String t=(String)P.elementAt(i);
                    for(int j=2;j<t.length();j++)//提取表达式右侧的终结符存入Vt
                    {
                        if(t.charAt(j)>'Z'||t.charAt(j)<'A')
                        {
                            if(puanduanChar(Vt,t.charAt(j)))
                            {
                                Vt[biaozhi]=t.charAt(j);
                                biaozhi++;
                            }
                        }
                    }
                }
                if(puanduanChar(Vt,'#'))//若可推出空集,则将#加入Vt。
                {
                    Vt[biaozhi]='#';
                    biaozhi++;
                }
                vt_tou=new String[biaozhi+1];//根据select和表达式生成预测分析表
                shuju=new String[Vnnum][biaozhi+1];
                String f="";
                vt_tou[0]=f;
                for(int i=0;i<biaozhi;i++)
                {
                    vt_tou[i+1]=String.valueOf(Vt[i]);
                }
                for(int i=0;i<Vnnum;i++)
                {
                    shuju[i][0]=Vn[i];
                }
                for(int i=0;i<P.size();i++)
                {
                    String t=(String)P.elementAt(i);
                    int j;
                    for(j=0;j<Vn.length;j++)
                    {
                        if(Vn[j].equals(t.substring(0,1)))
                        {
                            break;
                        }
                    }
                    for(k=0;select[i][k]!='\0';k++)
                    {
                        int y=puanduanXulie(Vt,select[i][k]);
                        shuju[j][y+1]=t.substring(1);
                    }
                }
                dtm=new DefaultTableModel(shuju,vt_tou);//显示预测分析表
                table.setModel(dtm);
                LL=1;
            }
            if(e.getSource()==b3)//清空列表
            {
                tf1.setText("");
                tf2.setText("");
                t1.setText("");
                t2.setText("");
                t3.setText("");
                Vn=null;
                P=null;
                firstComplete=null;
                first=null;
                followComplete=null;
                follow=null;
                select=null;
                dtm=new DefaultTableModel();
                table.setModel(dtm);
    
            }
    
            if(e.getSource()==b2)//输入字符串并预测分析
            {
                t3.setText("");
                if(LL==1)
                {
                    String s=t2.getText();
                    for(int i=0;i<s.length();i++)
                    {
                        if(s.charAt(i)=='\0')
                        {
                            t3.setText("字符串中请不要加入空格"+"\n");
    
    
    
                            return;
                        }
                    }
                    char zifu[]=new char[100];//剩余输入串
                    char fenxi[]=new char[100];//分析栈
                    zifu[0]='#';
                    fenxi[1]='S';
                    fenxi[0]='#';
                    int fzifu=1;
                    int ffenxi=2;
                    for(int i=s.length()-1;i>=0;i--)
                    {
                        zifu[fzifu]=s.charAt(i);
                        fzifu++;
                    }
                    int buzhou=2;
                    char n[]=new char[65];//存储要显示的内容
                    t3.append("步骤                   分析栈                      剩余输入串              所用产生式或匹配"+"\n");
                    n[0]='1';
                    n[15]='#';
                    n[14]='S';
                    int u=29;
                    for(int i=fzifu-1;i>=0;i--)
                    {
                        n[u]=zifu[i];
                        u++;
                    }
                    while(!(fenxi[ffenxi-1]=='#'&&zifu[fzifu-1]=='#'))//剩余输入串不为#则分析
                    {
                        int i,j;
                        char t=zifu[fzifu-1];
                        char k=fenxi[ffenxi-1];
                        if(t==k)//产生式匹配
                        {
                            n[49]=k;
                            n[50]='匹';
                            n[51]='配';
                            t3.append(String.copyValueOf(n)+"\n");
                            n=new char[65];
                            fzifu--;
                            ffenxi--;
                            if(buzhou<10)
                                n[0]=(char)('0'+buzhou);//显示步骤数
                            else
                            {
                                n[0]=(char)('0'+buzhou/10);
                                n[1]=(char)('0'+buzhou%10);
                            }
                            u=14;
                            for(int y=ffenxi-1;y>=0;y--)//处理分析栈,出栈
                            {
                                n[u]=fenxi[y];
                                u++;
                            }
                            u=29;
                            for(int y=fzifu-1;y>=0;y--)//处理剩余字符串,消除一个字符
                            {
                                n[u]=zifu[y];
                                u++;
                            }
                            buzhou++;
                            continue;
                        }
    
                        for(i=0;Vn[i]!=null;i++)//搜寻所用产生式的左部
                        {
                            if(Vn[i].equals(String.valueOf(k)))break;
                        }
                        for(j=0;j<vt_tou.length;j++)//判断是否匹配
                        {
                            if(vt_tou[j].equals(String.valueOf(t)))break;
                        }
                        if(j>=vt_tou.length)//全部产生式都不能符合则报错
                        {
                            t3.append(String.copyValueOf(n));
                            t3.append("\n"+"该串不是该文法的句型"+"\n");
                            return;
                        }
    
                        Object result1=shuju[i][j];
                        if(result1==null)
                        {
                            t3.append(String.copyValueOf(n));
                            t3.append("\n"+"该串不是该文法的句型"+"\n");
                            return;
                        }
                        else//找到所用产生式
                        {
                            n[49]=Vn[i].charAt(0);
                            u=50;
                            String result=(String)result1;
                            for(int y=0;y<result.length();y++)
                            {
                                n[u]=result.charAt(y);
                                u++;
                            }
                            t3.append(String.copyValueOf(n)+"\n");
                            n=new char[65];
    
                            ffenxi--;
                            for(i=result.length()-1;i>0;i--)//将分析栈内非终结符换为右边表达式
                            {
                                if(result.charAt(i)!='#')
    
    
                                {
                                    fenxi[ffenxi]=result.charAt(i);
                                    ffenxi++;
                                }
                            }
                        }
                        if(buzhou<10)//显示“步骤”
                            n[0]=(char)('0'+buzhou);
                        else
                        {
                            n[0]=(char)('0'+buzhou/10);
                            n[1]=(char)('0'+buzhou%10);
                        }
                        u=14;
                        for(int y=ffenxi-1;y>=0;y--)
                        {
                            n[u]=fenxi[y];
                            u++;
                        }
                        u=29;
                        for(int y=fzifu-1;y>=0;y--)
                        {
                            n[u]=zifu[y];
                            u++;
                        }
                        buzhou++;
                    }
                    n=new char[65];
                    n[0]='1';
                    n[14]='#';
                    n[29]='#';
                    n[49]='分';
                    n[50]='析';
                    n[51]='成';
                    n[52]='功';
                    t3.append(String.copyValueOf(n));
                    t3.append("\n"+"该串是此文法的句型"+"\n");
                    return;
                }
                else
                {
                    t3.setText("请先依次输入LL(1)文法,并点击 文法判断 按钮"+"\n");
                    return;
                }
    
            }
        }
    
        private int add_First(char a[],String b,String firstVn[],int flag)         //计算FIRST**(递归)
        {
            if(puanduanString(firstVn,b.charAt(0))){addString(firstVn,b);}
            else
            {
                return flag;
            }
            for(int i=0;i<P.size();i++)
            {
    
                String t=(String)P.elementAt(i);
                for(int k=2;k<t.length();k++)
                {
                    if(t.substring(0, 1).equals(b))
                    {
                        if(t.charAt(k)>'Z'||t.charAt(k)<'A')//表达式右端第i个不是非终结符
                        {
                            if(flag==0||puanduanChar(a,t.charAt(k)))
                            {
    
                                if(t.charAt(k)=='#')//#时直接加入first
                                {
                                    if(k+1==t.length())
                                    {
                                        a[flag]=t.charAt(k);
                                        flag++;
                                    }
                                    int flag1=0;
                                    for(int j=0;yn_null[j]!='\0';j++)//所求非终结符进入yn_null**
                                    {
                                        if(yn_null[j]==b.charAt(0))//判断能否推出空
                                        {
                                            flag1=1;break;
                                        }
                                    }
                                    if(flag1==0)
                                    {
                                        int j;
                                        for(j=0;yn_null[j]!='\0';j++)
                                        {
    
                                        }
                                        yn_null[j]=b.charAt(0);
                                    }
                                    continue;
                                }
                                else//终结符直接加入first**
                                {
                                    a[flag]=t.charAt(k);
                                    flag++;
                                    break;
                                }
                            }break;
                        }
                        else//非终结符
                        {
                            if(!puanduanString(Vn,t.charAt(k)))
                            {
                                int p=firstComplete(t.charAt(k));//当该非终结符的first已经求出
                                if(p!=-1)
                                {
                                    flag=addElementFirst(a,p,flag);//直接加入所求first
                                }
                                else if((flag=add_First(a,String.valueOf(t.charAt(k)),firstVn,flag))==-1)
                                    return -1;
                                int flag1=0;
                                for(int j=0;yn_null[j]!='\0';j++)//当非终结符的first有空
                                {
                                    if(yn_null[j]==t.charAt(k))
                                    {
                                        flag1=1;break;
                                    }
                                }
                                if(flag1==1)//当非终结符的first能推出空
                                {
                                    if(k+1==t.length()&&puanduanChar(a,'#'))//之后无符号,且所求first无#
                                    {
                                        a[flag]='#';//first中加入#
                                        flag++;
                                    }
                                    continue;//判断下一个字符
                                }
                                else
                                {
                                    break;
                                }
                            }
                            else//错误
                            {
                                t3.setText("文法输入有误"+"\n");
                                return -1;
                            }
                        }
                    }
                }
            }
            return flag;
        }
    
        private int tianjiaFollow(char a[],String b,String followVn[],int flag)   //计算FOLLOW**(递归)
        {
            if(puanduanString(followVn,b.charAt(0))){addString(followVn,b);}
            else
            {
                return flag;
            }
            if(b.equals("S"))//当为S时#存入follow
            {
                a[flag]='#';
                flag++;
            }
            for(int i=0;i<P.size();i++)
            {
                String t=(String)P.elementAt(i);
                for(int j=2;j<t.length();j++)
                {
                    if(t.charAt(j)==b.charAt(0)&&j+1<t.length())
                    {
                        if(t.charAt(j+1)!='\0')
                        {
                            if((t.charAt(j+1)>'Z'||t.charAt(j+1)<'A'))//所求为终结符
                            {
                                if(flag==0||puanduanChar(a,t.charAt(2)))//自身
                                {
                                    a[flag]=t.charAt(j+1);
                                    flag++;
                                }
                            }
    
                            else//所求为非终结符
                            {
                                int k;
                                for(k=0;Vn[k]!=null;k++)
                                {
                                    if(Vn[k].equals(String.valueOf(t.charAt(j+1))))
                                    {
                                        break;//找寻下一个非终结符的Vn位置
                                    }
    
                                }
                                flag=addElementFirst(a,k,flag);//把下一个非终结符first加入所求follow集
                                for(k=j+1;k<t.length();k++)
                                {
                                    if((t.charAt(j+1)>'Z'||t.charAt(j+1)<'A'))break;
                                    else
                                    {
                                        if(panduan_kong(t.charAt(k)))
                                        {}
                                        else
                                        {
                                            break;
                                        }
                                    }
                                }
                                if(k>=t.length())//下一个非终结符可推出空,把表达式左边非终结符的follow集加入所求follow集
                                {
                                    int p=followComplete(t.charAt(0));
                                    if(p!=-1)
                                    {
                                        flag=addElementFollow(a,p,flag);
                                    }
                                    else if((flag=tianjiaFollow(a,String.valueOf(t.charAt(0)),followVn,flag))==-1)
                                        return -1;
                                }
                            }
                        }
                        else//错误
                        {
                            t3.setText("文法输入有误,请重新输入"+"\n");
                            return -1;
                        }
    
                    }
                    if(t.charAt(j)==b.charAt(0)&&j+1==t.length())//下一个字符为空,把表达式左边非终结符的follow集加入所求follow集
                    {
                        int p=followComplete(t.charAt(0));
                        if(p!=-1)
                        {
                            flag=addElementFollow(a,p,flag);
                        }
                        else if((flag=tianjiaFollow(a,String.valueOf(t.charAt(0)),followVn,flag))==-1)
                            return -1;
                    }
                }
            }
            return flag;
        }
        private void tianjiaSelect(char a[],String b,int flag)          //计算SELECT**
        {
            int i=2;
            int biaozhi=0;
            while(i<b.length())
            {
                if((b.charAt(i)>'Z'||b.charAt(i)<'A')&&b.charAt(i)!='#')//是终结符
                {
                    a[flag]=b.charAt(i);//将这个字符加入到Select**,结束Select**的计算
                    break;
                }
                else if(b.charAt(i)=='#')//是空
                {
                    int j;
                    for(j=0;Vn[i]!=null;j++)//将表达式左侧的非终结符的follow加入select
                    {
                        if(Vn[j].equals(b.substring(0,1)))
                        {
                            break;
                        }
                    }
                    for(int k=0;follow[j][k]!='\0';k++)
                    {
                        if(puanduanChar(a,follow[j][k]))
                        {
                            a[flag]=follow[j][k];
                            flag++;
                        }
                    }
                    break;
                }
                else if(b.charAt(i)>='A'&&b.charAt(i)<='Z'&&i+1<b.length())//是非终结符且有下一个字符
                {
                    int j;
                    for(j=0;Vn[i]!=null;j++)
                    {
                        if(Vn[j].equals(String.valueOf(b.charAt(i))))
                        {
                            break;
                        }
                    }
                    for(int k=0;first[j][k]!='\0';k++)
                    {
                        if(puanduanChar(a,first[j][k]))//把表达式右侧所有非终结符的first集加入。
                        {
                            if(first[j][k]=='#')//first中存在空
                            {
                                biaozhi=1;
                            }
                            else
                            {
                                a[flag]=first[j][k];
                                flag++;
                            }
                        }
                    }
                    if(biaozhi==1)//把右侧所有非终结符的first中的#去除
                    {
                        i++;biaozhi=0;continue;
                    }
                    else
                    {
                        biaozhi=0;break;
                    }
                }
                else if(b.charAt(i)>='A'&&b.charAt(i)<='Z'&&i+1>=b.length())//是非终结符且没有下一个字符
                {
                    int j;
                    for(j=0;Vn[i]!=null;j++)
                    {
                        if(Vn[j].equals(String.valueOf(b.charAt(i))))
                        {
                            break;
                        }
                    }
                    for(int k=0;first[j][k]!='\0';k++)
                    {
                        if(puanduanChar(a,first[j][k]))
                        {
                            if(first[j][k]=='#')
                            {
                                biaozhi=1;//表达式右侧能推出空,标记
                            }
                            else
                            {
                                a[flag]=first[j][k];//不能推出空,直接将first集加入select集
                                flag++;
                            }
    
                        }
                    }
                    if(biaozhi==1)//表达式右侧能推出空
                    {
                        for(j=0;Vn[i]!=null;j++)
                        {
                            if(Vn[j].equals(b.substring(0,1)))
                            {
                                break;
                            }
                        }
                        for(int k=0;follow[j][k]!='\0';k++)
                        {
                            if(puanduanChar(a,follow[j][k]))
                            {
                                a[flag]=follow[j][k];//将将表达式左侧的非终结符的follow加入select
                                flag++;
                            }
                        }
                        break;
                    }
                    else
                    {
                        biaozhi=0;break;
                    }
                }
            }
        }
    
        //返回b在Vt[]的位置
        private int puanduanXulie(char Vt[],char b)
        {
            int i;
            for(i=0;Vt[i]!='\0';i++)
            {
                if(Vt[i]==b)break;
            }
            return i;
        }
        //判断b是否在a中,在返回false,不在返回true
        private boolean puanduanChar(char a[],char b)
        {
    
            for(int i=0;a[i]!='\0';i++)
            {
                if(a[i]==b)return false;
    
            }
            return true;
        }
        //判断b是否在a中,在返回false,不在返回true
        private boolean puanduanString(String a[],char b)
        {
            for(int i=0;a[i]!=null;i++)
            {
                if(a[i].equals(String.valueOf(b)))return false;
    
            }
            return true;
        }
        //把b加入字符串组firstVn[]
        private void addString(String firstVn[],String b)
        {
            int i;
            for(i=0;firstVn[i]!=null;i++)
            {
            }
            firstVn[i]=b;
        }
        //判断b是否已完成first判断
        private int firstComplete(char b)
        {
            int i;
            for(i=0;Vn[i]!=null;i++)
            {
                if(Vn[i].equals(String.valueOf(b)))
                {
                    if(firstComplete[i]==1)return i;
                    else return -1;
                }
    
            }
            return -1;
        }
        //判断b是否已完成follow判断
        private int followComplete(char b)
        {
            for(int i=0;Vn[i]!=null;i++)
            {
                if(Vn[i].equals(String.valueOf(b)))
                {
                    if(followComplete[i]==1)return i;
                    else return -1;
                }
    
            }
            return -1;
        }
        //把相应终结符添加到first**中
        private int addElementFirst(char a[],int p,int flag)
        {
            for(int i=0;first[p][i]!='\0';i++)
            {
                if(puanduanChar(a,first[p][i])&&first[p][i]!='#')
                {
                    a[flag]=first[p][i];
                    flag++;
                }
            }
            return flag;
        }
        //把相应终结符添加到follow**中
        private int addElementFollow(char a[],int p,int flag)
        {
            for(int i=0;follow[p][i]!='\0';i++)
            {
                if(puanduanChar(a,follow[p][i]))
                {
                    a[flag]=follow[p][i];
                    flag++;
                }
            }
            return flag;
        }
        //判断a能是否包含空
        private boolean panduan_kong(char a)
        {
            int i;
            for(i=0;Vn[i]!=null;i++)
            {
                if(Vn[i].equals(String.valueOf(a)))
                {
                    break;
                }
    
            }
            for(int j=0;first[i][j]!='\0';j++)
            {
                if(first[i][j]=='#')return true;
            }
    
            return false;
        }
    
        public static void main(String[] args) {
            new LL1();
        }
    }
    
    展开全文
  • 编译原理LR(o)以及LL1语法分析器
  • C++实现LL(1)法分析器:构造First集、Follow集,分析语法是否符合LL(1),并构造预测分析表。
  • 【编译原理】LL1文法的语法分析器(预测分析表)

    千次阅读 多人点赞 2019-12-04 22:09:45
    输入LL(1)文法 #include<iostream> #include<vector> #include<map> #include<cstring> #include<.../*定义产生式的语法集结构*/ typedef struct { char formula[200];...
  • LL(1)语法分析器

    2012-06-03 20:40:24
    语法分析程序用LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用LL(1)分析),先求出所输入的文法的每个非终结符是否能推出空,再分别计算非终结符号的FIRST集合,每个非终结符号的FOLLOW集合,...
  • Java实现LL1语法分析器

    千次阅读 2020-07-14 20:42:39
    一、实验目的 加深对语法分析器工作过程的理解;加强对预测分析法实现语法分析程序的掌握;能够 采用一种编程语言实现简单的语法分析程序;能够使用自己编写的分析程序对简单的程序段 进行语法翻译。 二、实验内容 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 463
精华内容 185
关键字:

LL1语法分析器