SLR1 分析器构造：完整代码示例和解释
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 void ComputeFirst()
{
//初始化 First 集
foreach (char c in Nchar)
{
first.Add(c, new HashSet<char>());
}
foreach (char c in Echar)
{
first.Add(c, new HashSet<char>() { c });
}
//计算 First 集
bool flag = true;
while (flag)
{
flag = false;
foreach (SLRNode node in SLRproNum)
{
HashSet<char> temp = new HashSet<char>();
bool canEpsilon = true;
foreach (char c in node.Right)
{
if (Echar.Contains(c))
{
temp.UnionWith(first[c]);
if (!first[c].Contains('ε'))
{
canEpsilon = false;
break;
}
}
else
{
canEpsilon = false;
temp.UnionWith(first[c]);
break;
}
}
if (canEpsilon)
{
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.Add(c, new HashSet<char>());
}
follow[SLRproNum[0].Left].Add('#');
//计算 Follow 集
bool flag = true;
while (flag)
{
flag = false;
foreach (SLRNode node in SLRproNum)
{
for (int i = 0; i < node.Right.Length; i++)
{
if (Nchar.Contains(node.Right[i]))
{
HashSet<char> temp = new HashSet<char>();
bool canEpsilon = true;
for (int j = i + 1; j < node.Right.Length; j++)
{
if (Echar.Contains(node.Right[j]))
{
temp.UnionWith(first[node.Right[j]]);
if (!first[node.Right[j]].Contains('ε'))
{
canEpsilon = false;
break;
}
}
else
{
canEpsilon = false;
temp.UnionWith(first[node.Right[j]]);
break;
}
}
if (canEpsilon)
{
temp.UnionWith(follow[node.Left]);
}
if (!temp.SetEquals(follow[node.Right[i]]))
{
follow[node.Right[i]].UnionWith(temp);
flag = true;
}
}
}
if (node.Right.EndsWith(Nchar.ToString()))
{
if (!follow[node.Left].SetEquals(follow[node.Right[node.Right.Length - 1]]))
{
follow[node.Right[node.Right.Length - 1]].UnionWith(follow[node.Left]);
flag = true;
}
}
}
}
}
public void CreateItemsets()
{
//初始化第一个项目集
SLRitemsets itemset0 = new SLRitemsets();
itemset0.Container.Add(0);
itemset0.LookAhead.Add('#');
itemset0 = Closure(itemset0);
proitemset.Add(itemset0);
//构造所有项目集
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 = j < Echar.Count ? Echar[j] : Nchar[j - Echar.Count];
HashSet<char> lookAhead = new HashSet<char>();
foreach (int index in proitemset[i].Container)
{
if (SLRobjNum[index].Right.Contains('.') && SLRobjNum[index].Right.IndexOf('.') < SLRobjNum[index].Right.Length - 1 && SLRobjNum[index].Right[SLRobjNum[index].Right.IndexOf('.') + 1] == symbol)
{
if (SLRobjNum[index].Right.Length - 1 == SLRobjNum[index].Right.IndexOf('.') + 1)
{
lookAhead.UnionWith(proitemset[i].LookAhead);
}
else
{
bool canEpsilon = true;
for (int k = SLRobjNum[index].Right.IndexOf('.') + 2; k < SLRobjNum[index].Right.Length; k++)
{
if (Echar.Contains(SLRobjNum[index].Right[k]))
{
lookAhead.UnionWith(first[SLRobjNum[index].Right[k]]);
if (!first[SLRobjNum[index].Right[k]].Contains('ε'))
{
canEpsilon = false;
break;
}
}
else
{
canEpsilon = false;
lookAhead.UnionWith(first[SLRobjNum[index].Right[k]]);
break;
}
}
if (canEpsilon)
{
lookAhead.UnionWith(proitemset[i].LookAhead);
}
}
}
}
if (lookAhead.Count > 0)
{
SLRitemsets newItemset = new SLRitemsets();
foreach (int index in proitemset[i].Container)
{
if (SLRobjNum[index].Right.Contains('.') && SLRobjNum[index].Right.IndexOf('.') < SLRobjNum[index].Right.Length - 1 && SLRobjNum[index].Right[SLRobjNum[index].Right.IndexOf('.') + 1] == symbol)
{
SLRNode newNode = new SLRNode(SLRobjNum[index].Left, SLRobjNum[index].Right.Insert(SLRobjNum[index].Right.IndexOf('.') + 2, '$'));
if (!SLRobjNum.Contains(newNode))
{
SLRobjNum.Add(newNode);
newItemset.Container.Add(SLRobjNum.Count - 1);
newItemset.LookAhead.Add(symbol);
}
else
{
int index2 = SLRobjNum.IndexOf(newNode);
newItemset.Container.Add(index2);
newItemset.LookAhead.Add(symbol);
}
}
}
newItemset = Closure(newItemset);
if (!proitemset.Contains(newItemset))
{
proitemset.Add(newItemset);
flag = true;
}
dfa[Pindex++] = new DFA(i, symbol, proitemset.IndexOf(newItemset), lookAhead);
}
}
}
}
}
public void CreateDFA()
{
RStr_DFA += '
SLR1分析器DFA:
';
RStr_DFA += '状态|';
foreach (char c in Echar)
{
RStr_DFA += c + '|';
}
foreach (char c in Nchar)
{
RStr_DFA += c + '|';
}
RStr_DFA += '
';
for (int i = 0; i < Pindex; i++)
{
RStr_DFA += i + ' |';
for (int j = 0; j < Echar.Count + Nchar.Count; j++)
{
if (dfa[i].to == -1)
{
RStr_DFA += ' |';
}
else
{
if (dfa[i].symbol == (j < Echar.Count ? Echar[j] : Nchar[j - Echar.Count]))
{
RStr_DFA += dfa[i].to + ',' + string.Join('', dfa[i].LookAhead) + '|';
}
else
{
RStr_DFA += ' |';
}
}
}
RStr_DFA += '
';
}
}
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 (dfa[i].symbol == '#' && dfa[i].to != -1)
{
foreach (int index in proitemset[dfa[i].to].Container)
{
if (SLRobjNum[index].Right.EndsWith('.'))
{
SLRAna[dfa[i].from][Echar.Count + Nchar.Count - 1] = new Table('A', index);
break;
}
}
}
for (int j = 0; j < Echar.Count + Nchar.Count; j++)
{
if (dfa[i].symbol == (j < Echar.Count ? Echar[j] : Nchar[j - Echar.Count]) && dfa[i].to != -1)
{
SLRAna[dfa[i].from][j] = new Table('S', dfa[i].to);
}
}
for (int k = 0; k < proitemset.Count; k++)
{
foreach (int index in proitemset[k].Container)
{
if (SLRobjNum[index].Right.EndsWith('.'))
{
foreach (char c in proitemset[k].LookAhead)
{
if (c != '#' && c != 'ε')
{
int index2 = Echar.IndexOf(c);
SLRAna[k][index2] = new Table('R', index);
}
}
}
}
}
}
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 (i == 1 && j == Echar.Count - 1)
{
RStr_ANA += 'AC' + ' ';
}
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 += '
';
}
}
public SLRitemsets Closure(SLRitemsets I)
{
for (int index = 0; index < I.Container.Count; index++)//遍历该集合中的所有序号 初始序号就是拓广文法的0 下面的ADD步骤中会扩大他的内容
for (int i = 0; i < SLRobjNum[I.Container[index]].Right.Length - 1; i++)//遍历第index序号项目右侧字符串 找到.A结构
{
if (SLRobjNum[I.Container[index]].Right[i] == '.' && isFinalsymbol(SLRobjNum[I.Container[index]].Right[i + 1]))
{
for (int j = 0; j < SLRobjNum.Count; j++)//遍历所有项目，找到以A开头的.a
{
if (isnexist(I.Container, j))
continue;
if (SLRobjNum[j].Left == SLRobjNum[I.Container[index]].Right[i + 1].ToString() && SLRobjNum[j].Right[0] == '.')
I.Container.Add(j);//ADD：在项目集（序号集合）中加入新成员
}
}
}
return I;
}
//判断符号是否为终结符
public bool isFinalsymbol(char c)
{
return Echar.Contains(c);
}
//判断项目序号是否在项目集中
public bool isnexist(List<int> I, int index)
{
return I.Contains(index);
}
解释
1. ComputeFirst() 函数
- 功能: 计算每个非终结符的 First 集。
- 步骤:
- 初始化 First 集: 为每个非终结符和终结符创建空的 First 集，终结符的 First 集包含自身。
- 迭代计算: 循环遍历每个产生式，从产生式的右部第一个符号开始，将该符号的 First 集加入到产生式左部的 First 集中。
- 处理 ε: 如果产生式右部的 First 集包含 ε，则将 ε 加入到产生式左部的 First 集中。
- 重复循环: 直到所有 First 集不再发生改变，循环结束。
2. ComputeFollow() 函数
- 功能: 计算每个非终结符的 Follow 集。
- 步骤:
- 初始化 Follow 集: 为每个非终结符创建空的 Follow 集。
- 初始化开始符号的 Follow 集: 将 # 加入到开始符号的 Follow 集中。
- 迭代计算: 循环遍历每个产生式，对于每个非终结符 A，如果 A 出现于产生式右部，且 A 后面还有其他符号，则将该符号的 First 集加入到 A 的 Follow 集中。如果 A 后面没有其他符号，或者 A 后面的符号的 First 集包含 ε，则将产生式左部的 Follow 集加入到 A 的 Follow 集中。
- 重复循环: 直到所有 Follow 集不再发生改变，循环结束。
3. CreateItemsets() 函数
- 功能: 构造 SLR1 项目集族。
- 步骤:
- 初始化第一个项目集: 将拓广文法的第一个产生式的第一个项目加入到第一个项目集中。
- 迭代构造: 循环遍历每个项目集，对于每个项目，如果该项目的点号 '.' 不在最右边，则将该项目移点后产生的项目加入到新的项目集中，并且将新的项目集加入到项目集族中。
- 计算 LookAhead 集: 对于每个项目集中的项目，如果该项目点的右边有符号，则将该符号的 First 集加入到 LookAhead 集中，否则将该项目集的 LookAhead 集加入到 LookAhead 集中。
- 重复循环: 直到所有项目集不再发生改变，循环结束。
4. CreateDFA() 函数
- 功能: 构造 SLR1 分析器的 DFA。
- 步骤:
- 初始化 DFA: 根据项目集族，初始化 DFA 的状态和转移。
- 迭代构造: 循环遍历每个状态，对于每个状态，根据状态的 LookAhead 集，构造状态之间的转移。
- 输出 DFA: 输出 DFA 的状态和转移信息。
5. CreateSLRTable() 函数
- 功能: 构造 SLR1 分析表。
- 步骤:
- 初始化分析表: 为每个状态和每个符号创建一个空的分析表项。
- 填充分析表: 根据 DFA 的转移，填充分析表中的项目，包括移进 (S)、归约 (R) 和接受 (A) 操作。
- 输出分析表: 输出 SLR1 分析表的内容。
代码示例
以下是一个简单的 SLR1 分析器构造的示例代码：
public class SLRAnalyzer
{
// ... (上述代码)
public static void Main(string[] args)
{
// 定义产生式
List<SLRNode> productions = new List<SLRNode>
{
new SLRNode('E', 'E+T'),
new SLRNode('E', 'T'),
new SLRNode('T', 'T*F'),
new SLRNode('T', 'F'),
new SLRNode('F', '(E)'),
new SLRNode('F', 'd')
};
// 初始化非终结符和终结符集合
List<char> nonTerminals = new List<char>() { 'E', 'T', 'F' };
List<char> terminals = new List<char>() { '+', '*', '(', ')', 'd', '#' };
// 创建 SLR 分析器
SLRAnalyzer analyzer = new SLRAnalyzer(productions, nonTerminals, terminals);
// 构造分析表
analyzer.CreateSLRTable();
// 输出分析表
Console.WriteLine(analyzer.RStr_ANA);
}
}
总结
本文提供了完整的 SLR1 分析器构造代码，并对代码中的各个函数进行了详细的解释，希望可以帮助你理解 SLR1 分析器的实现原理。在实际应用中，你可以根据具体的文法和需求，调整代码，构造出合适的 SLR1 分析器。
原文地址: https://www.cveoy.top/t/topic/f0N7 著作权归作者所有。请勿转载和采集!