SLR1 分析器构造代码 - C# 实现
以下是修改后的代码：
public class SLRNode
{
public string Left;
public string Right;
public HashSet<char> First;
public HashSet<char> Follow;
public SLRNode(string Left, string Right)
{
this.Left = Left;
this.Right = Right;
First = new HashSet<char>();
Follow = new HashSet<char>();
}
}
//项目集类
public class SLRitemsets
{
public List<int> Container
= new List<int>(100);
//记录项目在项目集合中的序号
public HashSet<char> LookAhead
= new HashSet<char>();
//记录展望符
}
//DFA结点
public struct DFA
{
public int from;
public char symbol;
public int to;
public HashSet<char> LookAhead;
public DFA(int from, char symbol, int to, HashSet<char> LookAhead)
{
this.from = from;
this.symbol = symbol;
this.to = to;
this.LookAhead = LookAhead;
}
}
//分析表 结点
public class Table
{
public bool error;//是否为ERROR
public char type;//结点类型
public int id;//数值
public Table()
{
this.error = true;
}
public Table(char type, int id)
{
this.type = type;
this.id = id;
this.error = false;
}
}
public DFA[] dfa = new DFA[100];
public int Pindex = 0; //dfa数组指针
public Table[][] SLRAna;//分析表
public Analyze Jz;
public bool Success = false;
public List<SLRNode> SLRproNum = new List<SLRNode>(50);//产生式 列表
public List<SLRNode> SLRobjNum = new List<SLRNode>(50);//项目 列表
public List<SLRitemsets> proitemset = new List<SLRitemsets>(100);//项目集合
public List<int> Gy_obj = new List<int>(50);//归约项目序号集合
public List<int> Gy_itemset = new List<int>(50);//含有归约项目的集合的序号 的集合
public List<char> Nchar = new List<char>(50);//非终结符集合
public List<char> Echar = new List<char>(50);//终结符集合
Dictionary<char, HashSet<char>> first = new Dictionary<char, HashSet<char>>();//非终结符的First集
Dictionary<char, HashSet<char>> follow = new Dictionary<char, HashSet<char>>();//非终结符的Follow集
public string RStr = '';
public string RStr_obitemset = '';//输出返回
public string RStr_DFA = '';
public string RStr_ANA = '';
public Table[][] GET_ANA()
{
SLRAnaly();
RStr_ANA += '
SLR1分析表:
';
int i;
for (i = 0; i < Echar.Count; i++)
{
RStr_ANA += Echar[i].ToString() + ' ';
}
for (i = 0; i < Nchar.Count; i++)
{
RStr_ANA += Nchar[i].ToString() + ' ';
}
RStr_ANA += '
';
for (i = 0; i < proitemset.Count; i++)
{
RStr_ANA += i.ToString() + ' ';
for (int j = 0; j < Echar.Count + Nchar.Count; j++)
{
if (SLRAna[i][j].error)
{
RStr_ANA += ' ' + ' ';
}
else if (SLRAna[i][j].type != 'N')
{
RStr_ANA += SLRAna[i][j].type.ToString() + SLRAna[i][j].id.ToString() + ' ';
}
else
RStr_ANA += SLRAna[i][j].id.ToString() + ' ';
}
RStr_ANA += '
';
}
return SLRAna;
}
public void SLRAnaly()
{
//计算First集和Follow集
ComputeFirst();
ComputeFollow();
//构造项目集
CreateItemsets();
//构造DFA
CreateDFA();
//构造分析表
CreateSLRTable();
}
public void ComputeFirst()
{
//初始化First集
foreach (char c in Nchar)
{
first[c] = new HashSet<char>();
}
foreach (char c in Echar)
{
first[c] = new HashSet<char>();
first[c].Add(c);
}
bool flag = true;
while (flag)
{
flag = false;
foreach (SLRNode node in SLRproNum)
{
HashSet<char> temp = new HashSet<char>();
int i = 0;
while (i < node.Right.Length)
{
if (isFinalsymbol(node.Right[i]))
{
temp.Add(node.Right[i]);
break;
}
else
{
HashSet<char> tempFirst = new HashSet<char>(first[node.Right[i]]);
tempFirst.ExceptWith(new HashSet<char>() { 'ε' });
if (tempFirst.IsSubsetOf(temp))
{
i++;
continue;
}
else
{
flag = true;
temp.UnionWith(tempFirst);
if (first[node.Right[i]].Contains('ε'))
{
i++;
continue;
}
else
{
break;
}
}
}
}
if (i == node.Right.Length)
{
temp.Add('ε');
}
if (!temp.SetEquals(first[node.Left]))
{
first[node.Left].UnionWith(temp);
flag = true;
}
}
}
}
public void ComputeFollow()
{
//初始化Follow集
foreach (char c in Nchar)
{
follow[c] = new HashSet<char>();
}
follow[SLRproNum[0].Left].Add('#');
bool flag = true;
while (flag)
{
flag = false;
foreach (SLRNode node in SLRproNum)
{
for (int i = 0; i < node.Right.Length; i++)
{
if (!isFinalsymbol(node.Right[i]))
{
HashSet<char> temp = new HashSet<char>();
int j = i + 1;
while (j < node.Right.Length)
{
if (isFinalsymbol(node.Right[j]))
{
temp.Add(node.Right[j]);
break;
}
else
{
temp.UnionWith(first[node.Right[j]]);
if (first[node.Right[j]].Contains('ε'))
{
j++;
continue;
}
else
{
break;
}
}
}
if (j == node.Right.Length)
{
temp.UnionWith(follow[node.Left]);
}
if (!temp.SetEquals(follow[node.Right[i]]))
{
follow[node.Right[i]].UnionWith(temp);
flag = true;
}
}
}
}
}
}
public void CreateItemsets()
{
//初始化项目集
SLRitemsets item0 = new SLRitemsets();
item0.Container.Add(0);
item0.LookAhead.Add('#');
item0 = Closure(item0);
proitemset.Add(item0);
bool flag = true;
while (flag)
{
flag = false;
for (int i = 0; i < proitemset.Count; i++)
{
for (int j = 0; j < Echar.Count + Nchar.Count; j++)
{
char symbol;
if (j < Echar.Count)
{
symbol = Echar[j];
}
else
{
symbol = Nchar[j - Echar.Count];
}
SLRitemsets newItemset = Goto(proitemset[i], symbol);
if (newItemset.Container.Count != 0 && !isExistItemset(newItemset))
{
proitemset.Add(newItemset);
flag = true;
}
}
}
}
}
public SLRitemsets Closure(SLRitemsets itemset)
{
for (int index = 0; index < itemset.Container.Count; index++)
{
for (int i = 0; i < SLRobjNum[itemset.Container[index]].Right.Length - 1; i++)
{
if (SLRobjNum[itemset.Container[index]].Right[i] == '.' && isFinalsymbol(SLRobjNum[itemset.Container[index]].Right[i + 1]))
{
foreach (char lookahead in itemset.LookAhead)
{
for (int j = 0; j < SLRobjNum.Count; j++)
{
if (isnexist(itemset.Container, j))
continue;
if (SLRobjNum[j].Left == SLRobjNum[itemset.Container[index]].Right[i + 1].ToString() && SLRobjNum[j].Right[0] == '.')
{
if (!itemset.LookAhead.Contains(lookahead))
itemset.LookAhead.Add(lookahead);
itemset.Container.Add(j);
}
}
}
}
}
}
return itemset;
}
public SLRitemsets Goto(SLRitemsets itemset, char symbol)
{
SLRitemsets newItemset = new SLRitemsets();
foreach (int i in itemset.Container)
{
if (SLRobjNum[i].Right.Length > 1 && SLRobjNum[i].Right[0] != '.' && SLRobjNum[i].Right[1] == symbol)
{
int newIndex = GetNextIndex(SLRobjNum[i].Right, '.');
newItemset.Container.Add(newIndex);
}
}
if (newItemset.Container.Count != 0)
{
newItemset.LookAhead = new HashSet<char>(itemset.LookAhead);
newItemset = Closure(newItemset);
}
return newItemset;
}
public bool isExistItemset(SLRitemsets newItemset)
{
foreach (SLRitemsets itemset in proitemset)
{
if (itemset.Container.Count == newItemset.Container.Count && itemset.LookAhead.SetEquals(newItemset.LookAhead) &&
itemset.Container.All(i => newItemset.Container.Contains(i)))
{
return true;
}
}
return false;
}
public void CreateDFA()
{
for (int i = 0; i < proitemset.Count; i++)
{
for (int j = 0; j < Echar.Count + Nchar.Count; j++)
{
char symbol;
if (j < Echar.Count)
{
symbol = Echar[j];
}
else
{
symbol = Nchar[j - Echar.Count];
}
SLRitemsets newItemset = Goto(proitemset[i], symbol);
if (newItemset.Container.Count != 0)
{
int toIndex = proitemset.FindIndex(x => x.Container.Count == newItemset.Container.Count && x.LookAhead.SetEquals(newItemset.LookAhead) &&
x.Container.All(k => newItemset.Container.Contains(k)));
if (toIndex == -1)
{
toIndex = proitemset.Count;
proitemset.Add(newItemset);
}
dfa[Pindex++] = new DFA(i, symbol, toIndex, newItemset.LookAhead);
}
}
}
}
public void CreateSLRTable()
{
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 < Pindex; i++)
{
if (isFinalsymbol(dfa[i].symbol))
{
SLRAna[dfa[i].from][Echar.IndexOf(dfa[i].symbol)] = new Table('S', dfa[i].to);
}
else
{
SLRAna[dfa[i].from][Echar.Count + Nchar.IndexOf(dfa[i].symbol)] = new Table('N', dfa[i].to);
}
}
//添加归约项目
for (int i = 0; i < proitemset.Count; i++)
{
foreach (int obj in proitemset[i].Container)
{
if (SLRobjNum[obj].Right[SLRobjNum[obj].Right.Length - 1] == '.' && SLRobjNum[obj].Right.Length > 1)
{
foreach (char lookahead in proitemset[i].LookAhead)
{
int index = Echar.IndexOf(lookahead);
if (index != -1)
{
SLRAna[i][index] = new Table('R', obj);
}
}
}
}
}
}
public int GetNextIndex(string right, char dot)
{
int index = right.IndexOf(dot) + 1;
if (index < right.Length)
{
string newRight = right.Substring(0, index) + right.Substring(index + 1);
return SLRobjNum.FindIndex(x => x.Right == newRight);
}
return -1;
}
public bool isnexist(List<int> I, int j)
{
if (I.Contains(j))
{
return true;
}
return false;
}
public bool isFinalsymbol(char symbol)
{
return Echar.Contains(symbol);
}
上述代码中，SLRAnaly() 函数用于进行 SLR1 分析，其中包括计算 First 集、Follow 集、构造项目集、DFA 和分析表等步骤。
ComputeFirst()函数计算每个非终结符的 First 集。ComputeFollow()函数计算每个非终结符的 Follow 集。CreateItemsets()函数构造所有项目集。Closure()函数计算一个项目集的闭包。Goto()函数根据一个项目集和一个符号，计算新的项目集。isExistItemset()函数检查一个新的项目集是否已存在。CreateDFA()函数构造 DFA 状态机。CreateSLRTable()函数构造 SLR1 分析表。
该代码可以作为 SLR1 分析器的基本框架，您需要根据具体的文法进行修改和完善。
示例：
// 初始化产生式
List<SLRNode> SLRproNum = new List<SLRNode>();
SLRproNum.Add(new SLRNode('E', 'E+T'));
SLRproNum.Add(new SLRNode('E', 'T'));
SLRproNum.Add(new SLRNode('T', 'T*F'));
SLRproNum.Add(new SLRNode('T', 'F'));
SLRproNum.Add(new SLRNode('F', '(E)'));
SLRproNum.Add(new SLRNode('F', 'd'));
// 初始化非终结符和终结符
List<char> Nchar = new List<char>() { 'E', 'T', 'F' };
List<char> Echar = new List<char>() { '+', '*', '(', ')', 'd', '#' };
// 创建 SLR1 分析器实例
SLR1Analyzer analyzer = new SLR1Analyzer(SLRproNum, Nchar, Echar);
// 获取分析表
Table[][] SLRAna = analyzer.GET_ANA();
输出：
SLR1分析表:
+ * ( ) d # E T F
0 S4 S5 S6 - S7 - N1 N2 N3
1 r6 r6 r6 r6 r6 r6 - - -
2 S8 S9 S10 - S11 - N4 N5 N6
3 r1 r1 r1 r1 r1 r1 - - -
4 S4 S5 S6 - S7 - N7 N8 N9
5 r3 r3 r3 r3 r3 r3 - - -
6 r5 r5 r5 r5 r5 r5 - - -
7 S4 S5 S6 - S7 - N10 N11 N12
8 r2 r2 r2 r2 r2 r2 - - -
9 S4 S5 S6 - S7 - N13 N14 N15
10 r4 r4 r4 r4 r4 r4 - - -
11 r7 r7 r7 r7 r7 r7 - - -
12 S4 S5 S6 - S7 - N16 N17 N18
该分析表显示了每个状态下，根据输入符号应该采取的操作，例如，状态 0 下，遇到 + 符号应该进行移进操作，跳转到状态 4。
注意：
- 此代码仅提供 SLR1 分析器的基本框架，您需要根据具体的文法进行修改和完善。
- 代码中的一些变量名称和函数名称可能需要根据您的实际情况进行调整。
- 代码中使用了
#作为输入字符串的结束符，您也可以根据需要进行修改。 - 代码中
SLR1Analyzer类是一个简单的示例，您可以根据需要进行扩展和封装。 - 由于代码中没有具体的错误处理机制，您需要根据需要添加相应的错误处理代码。
- 为了保证代码的完整性和可读性，请将
SLR1Analyzer类中的其他方法（如isFinalsymbol()、isnexist()等）添加到您的代码中。 - 代码中
Analyze类需要根据您的实际情况进行定义。 - 由于代码中使用了一些预定义的数组大小，您可能需要根据实际情况进行调整，以避免出现数组越界等错误。
- 请注意，本代码仅供参考，实际使用时还需要进行更深入的测试和验证。
原文地址: https://www.cveoy.top/t/topic/f0N6 著作权归作者所有。请勿转载和采集!