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 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 (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 += '
';
}
return SLRAna;
}
public List<int> Closure(List<int> I)
{
for (int index = 0; index < I.Count; index++)//遍历该集合中的所有序号 初始序号就是拓广文法的0 下面的ADD步骤中会扩大他的内容
{
for (int i = 0; i < SLRobjNum[I[index]].Right.Length - 1; i++)//遍历第index序号项目右侧字符串 找到.A结构
{
if (SLRobjNum[I[index]].Right[i] == '.' && isFinalsymbol(SLRobjNum[I[index]].Right[i + 1]))
{
for (int j = 0; j < SLRobjNum.Count; j++)//遍历所有项目，找到以A开头的.a
{
if (isnexist(I, j))
continue;
if (SLRobjNum[j].Left == SLRobjNum[I[index]].Right[i + 1].ToString() && SLRobjNum[j].Right[0] == '.')
{
I.Add(j);//ADD：在项目集（序号集合）中加入新成员
foreach (char c in proitemset[index].LookAhead)//将展望符加入新成员的展望符集合中
{
proitemset[j].LookAhead.Add(c);
}
}
}
}
}
}
return I;
}
public void ComputeFirst()
{
foreach (char c in Nchar)
{
First(c);
}
}
public void First(char c)
{
HashSet<char> set = new HashSet<char>();
foreach (SLRNode node in SLRproNum)
{
if (node.Left == c.ToString())
{
if (isFinalsymbol(node.Right[0]))
{
set.Add(node.Right[0]);
}
else
{
foreach (char ch in node.Right)
{
if (!isFinalsymbol(ch))
{
First(ch);
set.UnionWith(first[ch]);
if (!first[ch].Contains('ε'))
{
break;
}
}
else
{
set.Add(ch);
break;
}
}
}
}
}
first[c] = set;
}
public void ComputeFollow()
{
foreach (char c in Nchar)
{
Follow(c);
}
}
public void Follow(char c)
{
HashSet<char> set = new HashSet<char>();
if (c == SLRproNum[0].Left[0])
{
set.Add('#');
}
foreach (SLRNode node in SLRproNum)
{
for (int i = 0; i < node.Right.Length; i++)
{
if (node.Right[i] == c)
{
if (i == node.Right.Length - 1)
{
if (node.Left != c.ToString())
{
Follow(node.Left[0]);
set.UnionWith(follow[node.Left[0]]);
if (node.Right[i] == c && i != node.Right.Length - 1 && isFinalsymbol(node.Right[i + 1]))
{
set.Add(node.Right[i + 1]);
}
else if (node.Right[i] == c && i != node.Right.Length - 1 && !isFinalsymbol(node.Right[i + 1]))
{
First(node.Right[i + 1]);
set.UnionWith(first[node.Right[i + 1]]);
if (first[node.Right[i + 1]].Contains('ε'))
{
Follow(node.Left[0]);
set.UnionWith(follow[node.Left[0]]);
}
}
}
}
else
{
if (isFinalsymbol(node.Right[i + 1]))
{
set.Add(node.Right[i + 1]);
}
else
{
First(node.Right[i + 1]);
set.UnionWith(first[node.Right[i + 1]]);
if (first[node.Right[i + 1]].Contains('ε'))
{
Follow(node.Left[0]);
set.UnionWith(follow[node.Left[0]]);
}
}
}
}
}
}
follow[c] = set;
}
public void SLRAnaly()
{
proitemset.Add(new SLRitemsets());
proitemset[0].Container.Add(0);//添加第一个项目集
SLRobjNum.Add(new SLRNode('S'', 'E#.'));//添加拓广文法的项目
proitemset[0].LookAhead.Add('#');//添加展望符
for (int i = 0; i < SLRproNum.Count; i++)
{
SLRobjNum.Add(new SLRNode(SLRproNum[i].Left, '.' + SLRproNum[i].Right));//加入所有项目
}
Closure(proitemset[0].Container);//计算第一个项目集的闭包
ComputeFirst();//计算First集
ComputeFollow();//计算Follow集
int index = 1;
//计算各个项目集合，并用dfa[]记录dfa结点
while (index < proitemset.Count)
{
//遍历每个项目集
for (int i = 0; i < proitemset[index].Container.Count; i++)
{
//遍历每个项目集中的项目
for (int j = 0; j < SLRobjNum[proitemset[index].Container[i]].Right.Length; j++)
{
//遍历项目的右侧
if (SLRobjNum[proitemset[index].Container[i]].Right[j] == '.')
{
if (j + 1 < SLRobjNum[proitemset[index].Container[i]].Right.Length && isFinalsymbol(SLRobjNum[proitemset[index].Container[i]].Right[j + 1]))
{
//当前项目为.a形式，a为终结符
char symbol = SLRobjNum[proitemset[index].Container[i]].Right[j + 1];
bool exist = false;
for (int k = 0; k < Pindex; k++)
{
//判断dfa数组中是否已存在该转移
if (dfa[k].from == index && dfa[k].symbol == symbol)
{
exist = true;
break;
}
}
if (exist)
{
continue;
}
//dfa数组中不存在该转移
List<int> newI = new List<int>();
//创建新的项目集
for (int k = 0; k < proitemset[index].Container.Count; k++)
{
//遍历当前项目集的项目
if (SLRobjNum[proitemset[index].Container[k]].Right[j] == '.' && j + 1 < SLRobjNum[proitemset[index].Container[k]].Right.Length && SLRobjNum[proitemset[index].Container[k]].Right[j + 1] == symbol)
{
//将所有.a形式的项目加入新项目集
newI.Add(proitemset[index].Container[k]);
}
}
//构造新项目集
for (int k = 0; k < newI.Count; k++)
{
//构造新项目集的右侧
SLRobjNum[newI[k]].Right = SLRobjNum[newI[k]].Right.Substring(0, j + 1) + SLRobjNum[newI[k]].Right[j + 2] + '.' + SLRobjNum[newI[k]].Right.Substring(j + 3);
}
proitemset.Add(new SLRitemsets());
//将新项目集加入项目集列表
proitemset[proitemset.Count - 1].Container = Closure(newI);
//计算新项目集的闭包
//构造dfa结点
dfa[Pindex] = new DFA(index, symbol, proitemset.Count - 1, new HashSet<char>(proitemset[index].LookAhead));
Pindex++;
}
else
{
//当前项目为.A形式，A为非终结符
char symbol = SLRobjNum[proitemset[index].Container[i]].Right[j + 1];
bool exist = false;
for (int k = 0; k < Pindex; k++)
{
//判断dfa数组中是否已存在该转移
if (dfa[k].from == index && dfa[k].symbol == symbol)
{
exist = true;
break;
}
}
if (exist)
{
continue;
}
//dfa数组中不存在该转移
List<int> newI = new List<int>();
//创建新的项目集
for (int k = 0; k < proitemset[index].Container.Count; k++)
{
//遍历当前项目集的项目
if (SLRobjNum[proitemset[index].Container[k]].Right[j] == '.' && j + 1 < SLRobjNum[proitemset[index].Container[k]].Right.Length && SLRobjNum[proitemset[index].Container[k]].Right[j + 1] == symbol)
{
//将所有.A形式的项目加入新项目集
newI.Add(proitemset[index].Container[k]);
}
}
//构造新项目集
for (int k = 0; k < newI.Count; k++)
{
//构造新项目集的右侧
SLRobjNum[newI[k]].Right = SLRobjNum[newI[k]].Right.Substring(0, j + 1) + SLRobjNum[newI[k]].Right[j + 2] + '.' + SLRobjNum[newI[k]].Right.Substring(j + 3);
}
proitemset.Add(new SLRitemsets());
//将新项目集加入项目集列表
proitemset[proitemset.Count - 1].Container = Closure(newI);
//计算新项目集的闭包
//构造dfa结点
dfa[Pindex] = new DFA(index, symbol, proitemset.Count - 1, new HashSet<char>(proitemset[index].LookAhead));
Pindex++;
}
}
}
}
index++;
}
//构造分析表
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();
}
}
//根据dfa数组填充分析表
for (int i = 0; i < Pindex; i++)
{
for (int j = 0; j < Echar.Count; j++)
{
if (dfa[i].symbol == Echar[j])
{
SLRAna[dfa[i].from][j] = new Table('S', dfa[i].to);
}
}
}
//根据项目集的展望符填充分析表
for (int i = 0; i < proitemset.Count; i++)
{
for (int j = 0; j < proitemset[i].Container.Count; j++)
{
if (SLRobjNum[proitemset[i].Container[j]].Right[SLRobjNum[proitemset[i].Container[j]].Right.Length - 1] == '.')
{
//判断项目是否为归约项目
int index = proitemset[i].Container[j];
for (int k = 0; k < SLRproNum.Count; k++)
{
if (SLRobjNum[index].Left == SLRproNum[k].Left && SLRobjNum[index].Right == '.' + SLRproNum[k].Right)
{
//找到对应的产生式
Gy_obj.Add(index);
Gy_itemset.Add(i);
foreach (char c in proitemset[i].LookAhead)
{
//遍历展望符
for (int m = 0; m < Echar.Count; m++)
{
if (c == Echar[m])
{
SLRAna[i][m] = new Table('R', k + 1);
}
}
}
}
}
}
}
}
//将接受状态加入分析表
SLRAna[1][Echar.Count - 1] = new Table('A', 0);
}
代码解释:
- SLRNode类: 存储产生式信息，包括左部非终结符、右部符号串以及First集和Follow集。
- SLRitemsets类: 存储项目集信息，包括项目序号集合、展望符集合。
- DFA结构体: 存储DFA结点信息，包括起始状态、转移符号、目标状态以及展望符集合。
- Table类: 存储分析表结点信息，包括是否为错误、结点类型（S:移进，R:归约，A:接受）以及对应的产生式或项目集序号。
- Closure()函数: 计算项目集的闭包，添加展望符。
- ComputeFirst()函数: 计算所有非终结符的First集。
- First()函数: 计算单个非终结符的First集。
- ComputeFollow()函数: 计算所有非终结符的Follow集。
- Follow()函数: 计算单个非终结符的Follow集。
- SLRAnaly()函数: 构造SLR1分析表，包括计算项目集、DFA结点、分析表等步骤。
修改后的代码在以下几个方面进行了调整:
- 添加了SLRNode类中First和Follow成员变量，并在构造函数中进行初始化。
- 添加了SLRitemsets类中LookAhead成员变量，并在构造函数中进行初始化。
- 在DFA结构体中添加了LookAhead成员变量。
- 在Closure()函数中添加了对展望符的处理，将当前项目集的展望符添加到新加入的项目的展望符集合中。
- 在GET_ANA()函数中修改了输出的表头和表格内容，以包括展望符。
- 添加了计算First集和Follow集的函数。
代码使用示例:
// 定义文法
List<SLRNode> SLRproNum = 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> Nchar = new List<char>() { 'E', 'T', 'F' };
List<char> Echar = new List<char>() { '+', '*', '(', ')', 'd', '#' };
// 实例化SLR1分析器
SLR1Analyzer analyzer = new SLR1Analyzer(SLRproNum, Nchar, Echar);
// 构造SLR1分析表
analyzer.SLRAnaly();
// 打印分析表
analyzer.GET_ANA();
注意事项:
- 代码中使用的是C#语言，需要使用.NET Framework进行编译和运行。
- 代码中假设文法已经过LR(0)分析，并满足SLR1条件。
- 代码中使用了一些辅助函数，如isFinalsymbol()、isnexist()等，需要根据具体的实现进行定义。
结论:
本文提供的代码实现了SLR1文法分析表的构造，并详细解释了代码中各个函数的功能和实现细节，可以帮助读者理解SLR1分析表的构造过程。在实际应用中，可以使用该代码来构建SLR1分析器，对SLR1文法进行语法分析。
原文地址: https://www.cveoy.top/t/topic/f0N2 著作权归作者所有。请勿转载和采集!