【C++】编译原理+预测分析方式构造语法分析器_ll(1)语法分析器

(代码在最后面)

一、实验目的

熟悉语法分析阶段的要求，掌握LL(1)语法分析的原理，利用预测分析方式构造语法分析器。

二、实验设备

硬件：PC 机一台

软件：Windows系统，高级语言集成开发环境

三、实验内容

用LL(1)预测分析法构造语法分析器。

四、实验要求及步骤

文法G(E):

E->TE’

E’->+TE’|$

T->FT’

T’->*FT’|$

G. >(E)|i

项目结构：

首先定义文法类：

exp4.h

编写文法类的方法

wf.cpp

然后求First集与Follow集：

first_and_follow.cpp

定义全局变量：

所求结果：

证明上述文法是LL（1）文法；

is_ll1.cpp

判断是否左递归：

构造预测分析表；

analysis_table.cpp

结果如下：

利用预测分析表实现以上文法的语法分析器；

Grammar_analyzer.cpp

结果如下：

测试

自设10个输入语句（每个语句多加一个#作为结束标记），展示这10个语句经该语法分析器分析后的结果，如果正确输出"Right"，错误输出"ERROR"并输出判错时指针所指符号。

i*(i+i)#

i#

ii#

i+(i*i)#

i+i#

i-i#

–i#

i*(i*i*i)#

i+i+i++#

++i#

分析

从代码量、时间复杂度、空间复杂度三方面，分析对比实验三与实验四两种语法分析器。

（可能有误，不确定正误）

• 实验3：
  • 代码量：
    • 215行
      包含三个文件：
      exp3.h
      exp3.cpp
      exp3_wenfa.cpp
  • 时间复杂度
    • 梯度下降语法分析器的时间复杂度为O(n^3)，其中n为输入句子的长度。
      由于在梯度下降算法中，需要对每个非终结符计算对它的梯度，实际上对于每个非终结符需要计算的梯度次数是O(n)，而对于一个语法规则的加权和，需要计算的梯度次数是O(n^2)。
  • 空间复杂度
    • 梯度下降文法分析器的空间复杂度为O(n+m)，其中n表示输入句子的长度，m表示分析栈大小。
      字符栈最大值为n，然后逐步将字符抛出减少。
      分析栈初始值为2，（即“E”与“#”），随后增加与减少。
• 实验4：
  • 代码量：
    • 715行
      包含8个文件：
      exp4.h
      analysis_table.cpp
      first_and_follow.cpp
      is_ll1.cpp
      Grammar_analyzer.cpp
      main.cpp
      utils.cpp
      wf.cpp
  • 时间复杂度
    • 实现了预测分析表的语法分析器时间复杂度为O(n^2)，其中n为输入句子的长度。
      对于句子中的每个字符，在预测分析表中查询该单元格 ，判断是否能到达。如果不能到达，则直接结束，输出Error。如果能到达，则根据单元格的语句查找下一步骤，直到该字母消除。
      所以是O(n^2)。
  • 空间复杂度
    • 实现了预测分析表的语法分析器空间复杂度为O(n^m)+O(n)+O(m) = O(n^m)，其中n为输入句子的长度，m为文法中的非终结符个数。
      用n*m储存预测分析表。
      用n的空间作为字符栈的储存空间。
      用m作为分析栈的储存空间。

附录：代码

exp4.h

#ifndef WF_H
#define WF_H
#include<bits/stdc++.h>
using namespace std;

//wf.cpp
class WF
{
public:
    string left;
    set<string> right;
    vector<string>rights;
    map<char, string>tables;

    WF(char s[]);
    void print();
    void insert(char s[]);
    void get_rights();
};

//is_ll1
void is_ll1();

//first_and_follow
void make_first();
void make_follow();
void print_first();
void print_follow();

//analysis_table
void make_table();
void print_analyzer();

bool check_first(const string& text, char ch);
bool check_follow(const string& text, char ch);

//utils
stack<string> Stringsplit(string str, char split);
void init();

const int MAX = 507;
extern map<string, set<char> > first;
extern map<string, set<char> > follow;
extern map<string, int> VN_dic;
extern vector<WF> VN_set;
extern  bool used[MAX];
extern vector<map<char, string> > predict_table;
#endif // WF_H

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

analysis_table.cpp

#include "exp4.h"

set<char>letters;
string line = "\n";
void make_letters()
{
	for (auto wf : VN_set)
	{
		for (auto ch : wf.tables)
		{
			letters.insert(ch.first);
		}
	}
	letters.erase('$');
	for (int i = 0; i <= letters.size() * 10; i++)
	{
		line += "--";
	}
	line += "\n";
}
void make_table()
{
	make_letters();
	cout << endl << endl << "预测分析表";
	cout << line;
	cout << "\t\t";
	//表头
	for (auto x : letters)
	{
		cout << setw(10)<< setiosflags(ios::left) << x << "\t";
	}
	cout << line;
	//内容
	for (auto i : VN_set)
	{
		cout << setw(10)<< setiosflags(ios::left) << i.left << "\t";
		for (auto j : letters)
		{
			if (i.tables.count(j) == 0)
			{
				cout << setw(10)<< setiosflags(ios::left) << ""<<"\t";
			}
			else
			{
				cout << setw(10)<< setiosflags(ios::left) << i.tables[j]<< "\t";
			}
		}
		cout << line;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

first_and_follow.cpp

#include "exp4.h"

map<string, set<char> > first;
map<string, set<char> > follow;
map<string, int> VN_dic;
vector<WF> VN_set;
bool used[MAX];

void dfs(int x)
{
	if (used[x]) return;
	used[x] = 1;
	string left = VN_set[x].left;
	for (auto xx : VN_set[x].rights)
	{
		if (xx == "$")
		{
			first[left].insert('$');
			VN_set[x].tables['#'] = left + "->" + '$';
			continue;
		}
		for (int i = 0; i < xx.length(); i++)
		{
			//遇到小写字母，直接把单个小写字母加入first
			if (!isupper(xx.at(i)) && xx.at(i) != '\'')
			{
				char ch = xx.at(i);
				first[left].insert(ch);
				VN_set[x].tables[ch] = left + "->" + xx;
				break;
			}
			//大写字母则判断有无'后，进入下一个dfs(大写字母)
			if (isupper(xx.at(i)))
			{
				int y;
				if (i != xx.length() - 1 && xx.at(i + 1) == '\'')
					y = VN_dic[xx.substr(i, 2)] - 1;
				else y = VN_dic[xx.substr(i, 1)] - 1;
				string tleft = VN_set[y].left;
				dfs(y);
				bool flag = true;
				for (auto xxx : first[tleft])
				{
					first[left].insert(xxx);
					VN_set[x].tables[xxx] = left + "->" + xx;
					if (xxx == '$')
						flag = true;
				}
				if (flag) break;
			}
			else continue;
		}
	}
}

void make_first()
{
	memset(used, 0, sizeof(used));
	for (int i = 0; i < VN_set.size(); i++)
		dfs(i);
}

void print_first()
{
	cout << endl << endl << "=====================================================" << endl;
	cout << "\t\tFirst集：";
	cout << endl << "=====================================================" << endl;
	map<string, set<char> >::iterator it = first.begin();
	for (; it != first.end(); it++)
	{
		printf("FIRST(%3s)  =  {", it->first.c_str());
		set<char>& temp = it->second;
		set<char>::iterator it1 = temp.begin();
		bool flag = false;
		for (; it1 != temp.end(); it1++)
		{
			if (flag) printf(", ");
			printf("%c", *it1);
			flag = true;
		}
		puts("}");
	}
}

bool is_put_in_table(int index)
{
	for (auto x : VN_set[index].rights)
	{
		if (x == "$")
			return true;
	}
	return false;
}


void make_follow()
{
	//包含关系 a包含于b，把a的follow集包含 v={a,b}
	vector<int>v;
	vector<string>vv;

	for (int i = 0; i < VN_set.size(); i++)
	{
		//求to的FOLLOW集——follow[to];
		string to = VN_set[i].left;

		//对于所有的句子的rights进行探索
		for (int j = 0; j < VN_set.size(); j++)
		{
			string left = VN_set[j].left;
			for (auto right : VN_set[j].rights)
			{
				int index_behind = 0;
				while (1)
				{
					int index = right.find(to, index_behind);
					index_behind = index + 1;
					//防止求E的follow集，找到E'的情况
					if (to.size() == 1 && index + 1 < right.size() && right[index + 1] == '\'')
					{
						continue;
					}
					if (index == -1)
						break;
					//
					int next_index = index + to.size();
					//如果后面有东西
					if (next_index < right.size())
					{
						//后面是 i
						if (!isupper(right[next_index]))
						{
							follow[to].insert(right[next_index]);
							/*VN_set[i].tables[right[next_index]] = left + "->" + right;*/
							break;
						}
						//后面是T或T'
						string next_str = "";
						next_str.append(1, right.at(next_index));
						if (right[next_index + 1] == '\'')
						{
							next_str.append(1, '\'');
						}
						//把T'的first加到to的follow集
						for (auto ch : first[next_str])
						{
							if (ch == '$')
								continue;
							follow[to].insert(ch);
							if(is_put_in_table(i))
								VN_set[i].tables[ch] = left + "->" + right;
						}
						int next_str_index = VN_dic[next_str]-1;
						for (auto q : VN_set[next_str_index].rights)
						{
							if (q == "$")
							{
								if (next_index + next_str.size() >= right.size())
								{
									v.push_back(j);
									v.push_back(i);
									vv.push_back(next_str + "->$");
								}
							}
						}
					}
					//是最后一个，把left的follow加入to的follow集
					else if (next_index == right.size())
					{
						//把left的follow加入to的follow集
						v.push_back(j);
						v.push_back(i);
						vv.push_back(to + "->$");
					}
					break;
				}
			}
		}
	}
	//
	for (int i = 0; i < v.size(); i += 2)
	{
		bool flag = is_put_in_table(v[i + 1]);
		string from = VN_set[v[i]].left, to = VN_set[v[i + 1]].left;
			for (auto x : follow[from])
			{
				follow[to].insert(x);
				if(flag)
					VN_set[v[i + 1]].tables[x] = vv[int(i / 2)];
			}
	}
	for (int i = 0; i < v.size(); i += 2)
	{
		bool flag = is_put_in_table(v[i + 1]);
		string from = VN_set[v[i]].left, to = VN_set[v[i + 1]].left;
		for (auto x : follow[from])
		{
			follow[to].insert(x);
			if (flag)
				VN_set[v[i + 1]].tables[x] = vv[int(i / 2)];
		}
	}
}

void print_follow()
{
	cout << endl <<endl<< "=====================================================" << endl;
	cout << "\t\tFollow集：";
	cout << endl << "=====================================================" << endl;
	map<string, set<char> >::iterator it = follow.begin();
	for (; it != follow.end(); it++)
	{
		printf("FOLLOW(%3s)  =  {", it->first.c_str());
		set<char>& temp = it->second;
		temp.insert('#');
		set<char>::iterator it1 = temp.begin();
		bool flag = false;
		for (; it1 != temp.end(); it1++)
		{
			if (flag) printf(", ");
			printf("%c", *it1);
			flag = true;
		}
		puts("}");
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226

Grammar_analyzer.cpp

#include "exp4.h"

string test = "++i#";
stack<string>s;//分析栈
string get_wenfa_top()
{
	string a = "";
	if (s.top().size() == 1)
	{
		a = s.top();
		s.pop();
	}
	else if (s.top().size() == 2)
	{
		if (s.top()[1] == '\'')
		{
			a = s.top();
			s.pop();
		}
		else
		{
			a += s.top()[0];
			s.top() = s.top().substr(1);
		}
	}
	else
	{
		if (s.top()[1] == '\'')
		{
			a = s.top().substr(0, 2);
			s.top() = s.top().substr(2);
		}
		else
		{
			a = s.top().substr(0, 1);
			s.top() = s.top().substr(1);
		}
	}
	return a;
}
typedef struct st
{
	string a, b, c;
	st(string aa, string bb, string cc)
	{
		a = aa;
		b = bb;
		c = cc;
	}
}st;
queue<st>print_text;
string line2 = "";
int index = 0;
void init2()
{
	line2.assign(70, '-');
	line2 += "\n";
	print_text.push(st("文法", "分析栈", "当前分析字符"));

	//字符栈准备
	index = 0;
	//分析栈准备
	s.push("#");
	s.push("E");
	//第一行
	print_text.push(st("E", "E#", test.substr(index)));
}

string get_wenfastack(stack<string>s)
{
	string a = "";
	while (s.size())
	{
		a += s.top();
		s.pop();
	}
	return a;
}
void make_analyzer()
{
	
	while (index < test.size())
	{
		char zifu_top = test[index];
		string wenfa_top = get_wenfa_top();
		int wenfa_index = VN_dic[wenfa_top] - 1;
		map<char, string>tables = VN_set[wenfa_index].tables;
		if (tables.count(zifu_top) == 0)
		{
			cout << "Error! 判错字符为" << test[index]<<endl;
			cout << line2;
			exit(0);
		}

		//a  E->AB'
		string a = tables[zifu_top];
		//next_status		AB'的下标
		string next_status = a.substr(a.find("->") + 2);
		if(next_status!="$")
			s.push(next_status);
		print_text.push(st(a, get_wenfastack(s), test.substr(index)));
		while (s.size() && index < test.size() && s.top()[0] == test[index])
		{
			//文法栈消去一个字母
			get_wenfa_top();
			//字符栈消去一个字母
			index++;
			//打印
			print_text.push(st("", get_wenfastack(s), test.substr(index)));
		}
	}
}

void print_analyzer()
{
	cout << endl << endl << "语法分析器" << endl<<endl;
	cout << "分析："<<test << endl;
	cout << line2;
	init2();
	cout << line2;
	make_analyzer();
	while (print_text.size()!=1)
	{
		st t = print_text.front();
		print_text.pop();
		cout << t.a << "\t\t" << t.b << "\t\t" << t.c << endl;
		cout << line2;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

is_ll1.cpp

#include "exp4.h"

/*
* ①文法 不包含左递归 ;
* ②对于文法中的每一个非终结符 A的各个产生式的 侯选首字符集两两不相交 。
* ③即 ： 对于产生式A→a| b
	   若b ≠ ε, 则 FIRST( a ) ∩ FIRST( b )= Ф
	   若 b ＝ε , 则 FIRST(A) ∩FOLLOW(A)=Ф
*/

string show_text = "";


//判断1：是否包含左递归
bool is_recursive()
{
	for (int i = 0; i < VN_set.size(); i++)
	{
		string left = VN_set[i].left;
		vector<string>rights = VN_set[i].rights;
		for (int j = 0; j < rights.size(); j++)
		{
			string str = rights[j].substr(0, left.size());
			if (str == left)
			{
				show_text += "\n包含左递归\n";
				return false;
			}
		}
	}
	show_text += "\n不包含左递归\n";
	return true;
}

set<char>all_first;

bool push_all_first(set<char>temp)
{
	for (auto x : temp)
	{
		if (all_first.count(x) > 0)
		{
			show_text += "存在重复字符" + x;
			return false;
		}
		all_first.insert(x);
	}
}

//判断2：b ≠ $, 则 FIRST( a ) ∩ FIRST( b )= Ф
bool is_2()
{
	for (int i = 0; i < VN_set.size(); i++)
	{
		string left = VN_set[i].left;
		show_text += left + "\t的所有候选首符集的first集与follow集集合（若存在ε）";
		vector<string>rights = VN_set[i].rights;
		//如果 E： E'T   +EFG   ABC
		//rights:所有的（E'T   +EFG   ABC）

		for (int j = 0; j < rights.size(); j++)
		{
			//t: E'T
			string t = rights[j];
			/*
			* 如果是$，把follo(left)的放入all_first。
			* 如果是大写字符，进行一些操作，把（E'T）这种的变成（E'），把first(left)放入all_first
			* 其他情况（+ET, et），直接跳过
			*/
			if (t[0] == '$')
			{
				if (!push_all_first(follow[left]))
					return false;
				continue;
			}
			int index = 0;
			for (index = 0; isupper(t[index]) || t[index] == '\''; index++);
			if (index == 0)
				continue;
			string first_ = t.substr(0, index);
			while (VN_dic.count(first_) == 0)
			{
				first_ = first_.substr(0, --index);
			}
			//first_: E'
			if (!push_all_first(first[first_]))
			{
				return false;
			}
		}
		show_text += "：\t";
		for (auto x : all_first)
		{
			show_text += x;
			show_text += " ";
		}
		show_text += "\t不存在重复\n";
		all_first.clear();
	}
	return true;
}

void is_ll1()
{
	cout << endl << "=====================================================" << endl;
	cout << "\t\tLL1文法判断：";
	cout << endl << "=====================================================" << endl;
	if (is_recursive() && is_2())
	{
		cout << "Yes";
	}
	else
	{
		cout << "No";
	}
	cout << endl << show_text << endl;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

main.cpp

#include "exp4.h"

//int main()
//{
//	int n;
//	char s[MAX];
//	cout << "你的文法有几句？" << endl;
//	cin >> n;
//	cout << "请在下面输入文法（ε请用$代替）：" << endl;
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%s", s);
//		int len = strlen(s), j;
//		for (j = 0; j < len; j++)
//			if (s[j] == '-') break;
//		s[j] = 0;
//		if (!VN_dic[s])
//		{
//			VN_set.push_back(s);
//			VN_dic[s] = VN_set.size();
//		}
//		int x = VN_dic[s] - 1;
//		VN_set[x].insert(s + j + 2);
//	}
//	is_ll1();
//	make_first();
//	make_follow();
//	make_table();
//}


int main()
{
	int n = 5;
	char s[MAX];
	vector<string>ss = { "E->TE'","E'->+TE'|$","T->FT'","T'->*FT'|$","F->(E)|i" };
	cout << "请在下面输入文法（ε请用$代替）：" << endl;
	for (int i = 0; i < n; i++)
	{
		strcpy(s, ss[i].c_str());
		int len = strlen(s), j;
		for (j = 0; j < len; j++)
			if (s[j] == '-') break;
		s[j] = 0;
		if (!VN_dic[s])
		{
			VN_set.push_back(s);
			VN_dic[s] = VN_set.size();
		}
		int x = VN_dic[s] - 1;
		VN_set[x].insert(s + j + 2);
	}
	init();
	make_first();
	make_follow();
	is_ll1();
	print_first();
	print_follow();
	make_table();
	print_analyzer();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

utils.cpp

#include "exp4.h"

stack<string> Stringsplit(string str, char split)
{
	stack<string>res;
	if (str == "")
		return res;
	string strs = str + split;
	size_t pos = strs.find(split);

	while (pos != strs.npos)
	{
		string temp = strs.substr(0, pos);
		res.push(temp);
		//去掉已分割的字符串,在剩下的字符串中进行分割
		strs = strs.substr(pos + 1, strs.size());
		pos = strs.find(split);
	}
	return res;
}

//获取rightss
void init()
{
	for (int i = 0; i < VN_set.size(); i++)
	{
		VN_set[i].get_rights();
	}
}


//检查一个字符是否属于一个字符串的FIRST集合
bool check_first(const string& text, char ch)
{
    for (int i = 0; i < text.length(); i++)
    {
        bool hasEmpty = false;
        if (!isupper(text[i]) && text[i] != '\'')
        {
            if (text[i] != ch) return false;
            else return true;
        }
        else if (isupper(text[i]))
        {
            string temp;
            if (i != text.length() - 1 && text[i + 1] == '\'')
                temp = text.substr(i, 2);
            else
                temp = text.substr(i, 1);
            set<char>& dic = first[temp];
            set<char>::iterator it = dic.begin();
            for (; it != dic.end(); it++)
            {
                if (*it == '$') hasEmpty = true;
                if (*it == ch) return true;
            }
            if (!hasEmpty) break;
        }
        else continue;
    }
    return false;
}


//检查一个字符是否属于一个字符串的FOLLOW集合
bool check_follow(const string& text, char ch)
{
    set<char>& dic = follow[text];
    set<char>::iterator it = dic.begin();
    for (; it != dic.end(); it++)
        if (*it == ch) return true;
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

wf.cpp

#include "exp4.h"

WF::WF(char s[])
{
	left = s;
}


void WF::print()
{
	printf("%s->", left.c_str());
	set<string>::iterator it = right.begin();
	if (right.begin() != right.end())
	{
		printf("%s", it->c_str());
		it++;
	}
	for (; it != right.end(); it++)
		printf("|%s", it->c_str());
	puts("");
}

void WF::insert(char s[])
{
	right.insert(s);
}


void WF::get_rights()
{
	for (auto x : right)
	{
		stack<string>s = Stringsplit(x, '|');
		while (s.size())
		{
			rights.push_back(s.top());
			s.pop();
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40