SLR 分析表生成算法实现
SLR 分析表生成算法实现
本文将详细介绍 SLR 分析表生成算法的实现，并针对代码中出现的错误提供修改方案。
public void SLRAnaly()
{
SLRAna = new Table[proitemset.Count][];
for (int i = 0; i < proitemset.Count; i++)
{
SLRAna[i] = new Table[Echar.Count + Nchar.Count];
for (int j = 0; j < Echar.Count + Nchar.Count; j++)
{
SLRAna[i][j] = new Table();
}
}
// 遍历每个状态
for (int i = 0; i < proitemset.Count; i++)
{
// 遍历每个终结符
for (int j = 0; j < Echar.Count; j++)
{
bool flag = false;
int index = -1;
// 遍历移进项
for (int k = 0; k < proitemset[i].Container.Count; k++)
{
int itemIndex = proitemset[i].Container[k];
if (SLRobjNum[itemIndex].Right.Contains('.') && SLRobjNum[itemIndex].Right.IndexOf('.') < SLRobjNum[itemIndex].Right.Length - 1 && SLRobjNum[itemIndex].Right[SLRobjNum[itemIndex].Right.IndexOf('.') + 1] == Echar[j])
{
flag = true;
index = k;
break;
}
}
if (flag)
{
SLRAna[i][j] = new Table('S', proitemset[Move(proitemset[i], Echar[j])[0]].Container[index + 1]);
}
else
{
SLRAna[i][j] = new Table();
}
}
// 遍历每个非终结符
for (int j = 0; j < Nchar.Count; j++)
{
int index = -1;
// 遍历移进项
for (int k = 0; k < proitemset[i].Container.Count; k++)
{
int itemIndex = proitemset[i].Container[k];
if (SLRobjNum[itemIndex].Right.Contains('.') && SLRobjNum[itemIndex].Right.IndexOf('.') < SLRobjNum[itemIndex].Right.Length - 1 && SLRobjNum[itemIndex].Right[SLRobjNum[itemIndex].Right.IndexOf('.') + 1] == Nchar[j])
{
index = k;
break;
}
}
if (index != -1)
{
SLRAna[i][Echar.Count + j] = new Table('S', proitemset[Move(proitemset[i], Nchar[j])[0]].Container[index + 1]);
}
else
{
SLRAna[i][Echar.Count + j] = new Table();
}
}
// 遍历归约项
for (int j = 0; j < Gy_obj.Count; j++)
{
int itemIndex = Gy_obj[j];
if (proitemset[i].Container.Contains(itemIndex))
{
foreach (char c in Follow(SLRobjNum[itemIndex].Left))
{
if (SLRAna[i][GetIndex(c)].error)
{
SLRAna[i][GetIndex(c)] = new Table('r', itemIndex);
}
else
{
Console.WriteLine("Conflict: state " + i + " " + c + " " + SLRAna[i][GetIndex(c)].type + SLRAna[i][GetIndex(c)].id + " r" + itemIndex);
}
}
}
}
}
// 处理接受状态
int acceptState = -1;
for (int i = 0; i < proitemset.Count; i++)
{
if (proitemset[i].Container.Contains(0))
{
acceptState = i;
break;
}
}
SLRAna[acceptState][GetIndex('#')] = new Table('A', 0);
}
// 获取符号在分析表中的索引
private int GetIndex(char c)
{
if (isFinalsymbol(c))
{
return Echar.IndexOf(c);
}
else
{
return Echar.Count + Nchar.IndexOf(c);
}
}
// 求 FOLLOW 集
private List<char> Follow(string symbol)
{
List<char> followSet = new List<char>();
if (symbol == "S'")
{
followSet.Add('#');
}
foreach (SLRNode node in SLRproNum)
{
int index = node.Right.IndexOf(symbol);
if (index != -1 && index < node.Right.Length - 1)
{
List<char> firstSet = First(node.Right.Substring(index + 1));
if (firstSet.Contains('#'))
{
followSet.AddRange(Follow(node.Left));
followSet.Remove('#');
}
followSet.AddRange(firstSet);
}
}
return followSet;
}
// 求 FIRST 集
private List<char> First(string str)
{
List<char> firstSet = new List<char>();
if (str == "#" )
{
firstSet.Add('#');
return firstSet;
}
if (isFinalsymbol(str[0]))
{
firstSet.Add(str[0]);
return firstSet;
}
foreach (SLRNode node in SLRproNum)
{
if (node.Left == str[0].ToString())
{
List<char> tempSet = First(node.Right);
firstSet.AddRange(tempSet);
if (tempSet.Contains('#'))
{
firstSet.Remove('#');
firstSet.AddRange(First(str.Substring(1)));
}
return firstSet;
}
}
return firstSet;
}
private List<int> Move(SLRitemsets itemset, char symbol)
{
List<int> moveSet = new List<int>();
foreach (int index in itemset.Container)
{
int dotIndex = SLRobjNum[index].Right.IndexOf('.');
if (dotIndex != -1 && dotIndex < SLRobjNum[index].Right.Length - 1 && SLRobjNum[index].Right[dotIndex + 1] == symbol)
{
moveSet.Add(index + 1);
}
}
return Closure(moveSet);
}
代码解释
代码中使用了以下几个关键数据结构：
- proitemset: 状态集合，每个元素代表一个状态，包含一个 List
类型 Container 属性，存储该状态对应的项目集编号列表。 - SLRobjNum: 项目集集合，每个元素代表一个项目集，包含一个 string 类型 Right 属性，存储该项目集的项目规则的右部。
- Echar: 终结符集合。
- Nchar: 非终结符集合。
- Gy_obj: 归约项目集编号集合。
- SLRproNum: 项目规则集合，每个元素包含一个 string 类型 Left 属性，存储该项目规则的左部，一个 string 类型 Right 属性，存储该项目规则的右部。
- SLRAna: SLR 分析表，是一个二维数组，第一维表示状态，第二维表示终结符和非终结符，每个元素存储一个 Table 类型对象，表示该状态对应该符号的分析动作。
代码实现流程如下：
- 初始化 SLR 分析表 SLRAna，每个元素为空 Table 对象。
- 遍历每个状态 i：
- 遍历每个终结符 j：
- 遍历每个项目集 k：
- 如果项目集 k 的项目规则右部包含一个点，且点后面的符号为当前终结符 j，则说明该项目集为移进项，将 SLRAna[i][j] 设置为一个移进动作，并设置下一状态的编号为 moveSet[0]。
- 遍历每个项目集 k：
- 遍历每个非终结符 j：
- 遍历每个项目集 k：
- 如果项目集 k 的项目规则右部包含一个点，且点后面的符号为当前非终结符 j，则说明该项目集为移进项，将 SLRAna[i][Echar.Count + j] 设置为一个移进动作，并设置下一状态的编号为 moveSet[0]。
- 遍历每个项目集 k：
- 遍历每个归约项目集 j：
- 如果当前状态 i 包含项目集 j：
- 遍历该项目集对应的左部的 Follow 集：
- 如果 SLRAna[i][GetIndex(c)] 为空，则将该元素设置为一个归约动作，并设置归约项目的编号为 j。
- 否则，说明出现了冲突，打印冲突信息。
- 遍历该项目集对应的左部的 Follow 集：
- 如果当前状态 i 包含项目集 j：
- 遍历每个终结符 j：
- 设置接受状态的分析动作。
代码错误分析与修正
代码中出现的问题在于语句 SLRAna[i][Echar.Count + j] = new Table('S', proitemset[Move(proitemset[i], Nchar[j])].Container[index + 1]); 中，Move(proitemset[i], Nchar[j]) 函数返回一个 Listproitemset[Move(proitemset[i], Nchar[j])].Container[index + 1] 试图直接将 List
修正方法：
将 SLRAna[i][Echar.Count + j] = new Table('S', proitemset[Move(proitemset[i], Nchar[j])].Container[index + 1]); 改为 SLRAna[i][Echar.Count + j] = new Table('S', proitemset[Move(proitemset[i], Nchar[j])[0]].Container[index + 1]);，即从 moveSet 中取出第一个元素作为下一状态的编号。
总结
本文介绍了 SLR 分析表生成算法的实现，详细解释了代码中各个步骤，并针对代码中出现的错误提供了修改方案。SLR 分析表是语法分析器的重要组成部分，通过构建 SLR 分析表，可以实现对输入字符串的语法分析，进而判断其是否符合语法规则。
原文地址: https://www.cveoy.top/t/topic/f1Qh 著作权归作者所有。请勿转载和采集!