(代码在最后面)

一、实验目的

熟悉语法分析阶段的要求，掌握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

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;
	}
}

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("}");
	}
}

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;
	}

}

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;
}

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();
}

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;
}

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();
		}
	}
}