C++/C#实现文法符号First集计算算法

使用C++/C#计算文法符号First集

本文提供两种语言的代码示例，用于计算文法符号First集，包括C++和C#。

C++代码示例

unordered_map<char, unordered_map<char, int>>p; //存储每个文法符号的first集，嵌套的map即为first集，存在标志为1

//存储每个文法符号的first集，嵌套的map即为first集，存在标志为1
for (auto s : VT) { //若文法符号为终结符
	p[s.first][s.first]=1;
}

for (auto s : toEpsilon) {
	if (s.second == true) { //若能推出epsilon
		p[s.first]['=']=1;
	}
}

int count = 0;

//计算每个文法符号的first集
while (count <= 20) { //迭代20次
	for (auto s : curr) {
		//产生式:A->BC,s1:BC s2:A
		vector<string>s1 = s.second;
		char s2 = s.first;
		for (int i = 0; i < s1.size(); i++) {
			if (VT.count(s1[i][0]) != 0) { //终结符
				p[s2][s1[i][0]]=1;
				continue;
			}
			int judge = 0; //用于判断是否产生式右边都能推到空
			for (int j = 0; j < s1[i].size(); j++) {
				if (VT.count(s1[i][j]) == 0) {
					if (toEpsilon[s1[i][j]] == true) { //若此文法符号能推到epsilon
						for (auto t : p[s1[i][j]]) { //将first集都减去epsilon再加入
							if (p[s2].count(t.first) == 0&&t.first!='=') {
								p[s2][t.first] = 1;
							}
						}
					}
					else {
						for (auto t : p[s1[i][j]]) { //将first集都减去epsilon再加入
							if (p[s2].count(t.first) == 0) {
								p[s2][t.first] = 1;
							}
						}
						judge = 1; //表示不能都推到epsilon
						break;
					}
				}
			}
			if (judge == 0) { //若都能推到epsilon
				p[s2]['='] = 1;
			}
		}
	}
	count++;
}

unordered_map<string, unordered_map<char, int>>bStr; //key:产生式右侧，value:first集

//计算每个产生式右边的first集
for (auto s : curr) {
	vector<string>s1 = s.second; //产生式右侧集合
	for (int i = 0; i < s1.size(); i++) {
		string s2 = s1[i]; //产生式右侧
		int judge = 0; //用于判断是否都能推到出空
		for (int j = 0; j < s2.size(); j++) {
			if (p.count(s2[0]) != 0 &&p[s2[0]].count('=') ==0) { //第一个字符不能推出空
				for (auto t1 : p[s2[j]]) { //将该符号的first集加入产生式的first集
					if (bStr[s2].count(t1.first) == 0) {
						bStr[s2][t1.first] = 1;
					}
				}
				judge = 1; //标志为1，表示不能都推导出epsilon
				break;
			}
			if (VT.count(s2[j]) == 0) { //非终结符
				if (toEpsilon[s2[j]] == true) { //能推出空,first(s2[j])-{=}属于first(s2)
					for (auto t : p[s2[j]]) { //将该符号的first集加入产生式的first集
						if (bStr[s2].count(t.first) == 0 && t.first != '=') {
							bStr[s2][t.first] = 1;
						}
					}
				}
				else {
					for (auto t : p[s2[j]]) {
						if (bStr[s2].count(t.first) == 0) { //first(s2[j])属于first(s2)
							bStr[s2][t.first] = 1;
						}
					}
					judge = 1; //不能全部推到空
					break;
				}
			}
		}//若为终结符可当做不能推导出epsilon的非终结符处理，将其加入后break即可
		if (judge == 0) { //若能全部推到空
			bStr[s2]['='] = 1;
		}
	}
}

C#代码示例

Dictionary<char, Dictionary<char, int>> p = new Dictionary<char, Dictionary<char, int>>();

//存储每个文法符号的first集，嵌套的Dictionary即为first集，存在标志为1
foreach (KeyValuePair<char, bool> s in toEpsilon)
{
    if (s.Value == true)//若能推出epsilon
    {
        if (!p.ContainsKey(s.Key))
            p.Add(s.Key, new Dictionary<char, int>());
        p[s.Key].Add('=', 1);
    }
}

foreach (KeyValuePair<char, string[]> s in curr)
{
    char s2 = s.Key;
    string[] s1 = s.Value;//产生式右侧集合
    if (!p.ContainsKey(s2))
        p.Add(s2, new Dictionary<char, int>());
    foreach (string str in s1)
    {
        if (VT.Contains(str[0]))//终结符
        {
            if (!p[s2].ContainsKey(str[0]))
                p[s2].Add(str[0], 1);
            continue;
        }
        int judge = 0;//用于判断是否产生式右边都能推到空
        foreach (char ch in str)
        {
            if (!VT.Contains(ch))
            {
                if (toEpsilon[ch] == true)//若此文法符号能推到epsilon
                {
                    foreach (KeyValuePair<char, int> t in p[ch])//将first集都减去epsilon再加入
                    {
                        if (!p[s2].ContainsKey(t.Key) && t.Key != '=')
                            p[s2].Add(t.Key, 1);
                    }
                }
                else
                {
                    foreach (KeyValuePair<char, int> t in p[ch])//将first集都减去epsilon再加入
                    {
                        if (!p[s2].ContainsKey(t.Key))
                            p[s2].Add(t.Key, 1);
                    }
                    judge = 1;//表示不能都推到epsilon
                    break;
                }
            }
            else if (!p[s2].ContainsKey(ch))//终结符
                p[s2].Add(ch, 1);
            if (!toEpsilon.ContainsKey(ch) || toEpsilon[ch] == false)
            {
                judge = 1;//表示不能都推到epsilon
                break;
            }
        }
        if (judge == 0)//若都能推到epsilon
            p[s2].Add('=', 1);
    }
}

Dictionary<string, Dictionary<char, int>> bStr = new Dictionary<string, Dictionary<char, int>>(); //key:产生式右侧，value:first集

//计算每个产生式右边的first集
foreach (KeyValuePair<char, string[]> s in curr)
{
    string[] s1 = s.Value;//产生式右侧集合
    foreach (string s2 in s1)
    {
        if (!bStr.ContainsKey(s2))
            bStr.Add(s2, new Dictionary<char, int>());
        int judge = 0;//用于判断是否都能推到出空
        foreach (char ch in s2)
        {
            if (VT.Contains(ch))//终结符
            {
                if (!bStr[s2].ContainsKey(ch))
                    bStr[s2].Add(ch, 1);
                judge = 1;//标志为1，表示不能都推导出epsilon
                break;
            }
            if (!p.ContainsKey(ch))
                break;
            if (p[ch].ContainsKey('=') && p[ch]['='] == 1)//能推出空,first(ch)-{=}属于first(s2)
            {
                foreach (KeyValuePair<char, int> t in p[ch])//将该符号的first集加入产生式的first集
                {
                    if (!bStr[s2].ContainsKey(t.Key) && t.Key != '=')
                        bStr[s2].Add(t.Key, 1);
                }
            }
            else
            {
                foreach (KeyValuePair<char, int> t in p[ch])
                {
                    if (!bStr[s2].ContainsKey(t.Key))//first(ch)属于first(s2)
                        bStr[s2].Add(t.Key, 1);
                }
                judge = 1;//不能全部推到空
                break;
            }
        }
        if (judge == 0)//若能全部推到空
            bStr[s2].Add('=', 1);
    }
}

代码说明

代码中使用 unordered_map (C++) 或 Dictionary (C#) 来存储每个文法符号的First集，以及每个产生式右边的First集。

1. 初始化First集: 初始化所有终结符的First集，并将所有能推导出epsilon的非终结符的First集加入'='。
2. 迭代计算: 循环迭代计算每个非终结符的First集，直到所有First集不再发生变化。
3. 计算产生式右侧First集: 计算每个产生式右侧的First集，使用已计算好的非终结符First集。

代码示例中的数据结构

• VT: 存储所有终结符的集合。
• toEpsilon: 存储所有能推导出epsilon的非终结符，键为非终结符，值为布尔值，表示是否能推导出epsilon。
• curr: 存储所有产生式，键为产生式左侧，值为产生式右侧的集合。

注意: 代码示例中 VT, toEpsilon, curr 等数据结构需要根据具体的文法进行初始化。

总结

本文提供的代码示例可以帮助您快速计算文法符号的First集。如果您有任何问题，欢迎留言讨论。