SLR1 分析器代码实现：功能函数解析与分析表构建
SLR1 分析器代码实现：功能函数解析与分析表构建
本文将继续补充给出生成构成 SLR1 分析器功能的各函数代码及调用的下面代码中未给的函数。
class SLR
{
//产生式结点类
public class SLRNode
{
public string Left;
public string Right;
public SLRNode(string Left, string Right)
{
this.Left = Left;
this.Right = Right;
}
}
//项目集类
public class SLRitemsets
{
public List<int> Container
= new List<int>(100);
//记录项目在项目集合中的序号
}
//DFA结点
public struct DFA
{
public int from;
public char symbol;
public int to;
public DFA(int from, char symbol, int to)
{
this.from = from;
this.symbol = symbol;
this.to = to;
}
}
//分析表 结点
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>> follow = new Dictionary<char, HashSet<char>>();//非终结符的Follow集
public string RStr = '';
public string RStr_obitemset = '';//输出返回
public string RStr_DFA = '';
public string RStr_ANA = '';
public void Buildprod(string str)
{
SLRNode Lr;
int i = 0;
string left = '';
string right = '';
left += 'S'';
right += str[0];
Lr = new SLRNode(left, right);//拓广文法开始
SLRproNum.Add(Lr);
while (i < str.Length)
{
left = right = '';//还原
int j = i;
while (i < str.Length && str[i] != '\r' && str[i] != '\n')//换行符‘\r\n’
{
if (str[i] == ' ')
{
i++;
continue;
}
if (str[i] == '|') // 遇到'|'可构造一条产生式
{
Lr = new SLRNode(left, right);
SLRproNum.Add(Lr);
right = ''; //产生式左边相同 右边重新积累
i++; //跳过'|'
continue;
}
if ((i - j) == 0)
{
if (!exist(Nchar, str[i]))//如果非终结符集合中不存在str[i],加入Nchar 产生式左边 只有非终结符 不必判断终结符
Nchar.Add(str[i]);
left += str[i++];
}
else if (i - j <= 2)
i++;
else
{
if (isFinalsymbol(str[i]) && !exist(Nchar, str[i]))//如果非终结符集合中不存在str[i],加入Nchar isfinalsymbol 非终结符返回T 终结符返回F
Nchar.Add(str[i]);
else if (!isFinalsymbol(str[i]) && !exist(Echar, str[i]))//产生式右边 需要判断终结符
Echar.Add(str[i]);
right += str[i++];
}
}//while
i++;//跳过换行符
if (left != '' && right != '')
{
Lr = new SLRNode(left, right);//构造每一行最后一个产生式，不存在'|'时就是该行产生式本身
SLRproNum.Add(Lr);
}
}//while
Echar.Add('#');
//构造项目 对产生式集合SLRproNum中的所有产生式都循环插'.'
SLRNode Lobj;
for (i = 0; i < SLRproNum.Count; i++)
{
left = '';
right = '';
for (int j = 0; j <= SLRproNum[i].Right.Length; j++)//j可以等于length 项目共length+1个
{
left = SLRproNum[i].Left;
right = CreObj(SLRproNum[i].Right, j);//在第j个位置插入'.'
if (j == SLRproNum[i].Right.Length && SLRobjNum.Count != 1)
{//在产生式最后的位置插入. 即为归约项目 项目集中1号位置为接受项目
Gy_obj.Add(SLRobjNum.Count);//归约项目在项目集中的序号 不用+1 本身就是从0开始的
}
Lobj = new SLRNode(left, right);
SLRobjNum.Add(Lobj);
left = '';//还原
right = '';
}
}
Creteitemsets();//项目集
RStr_obitemset += '\r\n项目集构建：\r\n';
for (int j = 0; j < proitemset.Count; j++)
{
RStr_obitemset += 'I' + j.ToString() + ':' + '\r\n';
for (i = 0; i < proitemset[j].Container.Count; i++)
{
RStr_obitemset += SLRobjNum[proitemset[j].Container[i]].Left.ToString() + '->' + SLRobjNum[proitemset[j].Container[i]].Right.ToString() + '\r\n';
}
}
//return RStr_obitemset;
}
//构造项目集
public void Creteitemsets()
{
//初始化
SLRitemsets I0 = new SLRitemsets();
I0.Container.Add(0);//将拓广文法的产生式加入项目集
proitemset.Add(I0);//将I0加入项目集合
int i = 0;
while (i < proitemset.Count)
{
SLRitemsets I = proitemset[i];
//寻找I中所有项目的点后面的符号，将其加入集合C中
List<char> C = new List<char>();
for (int j = 0; j < I.Container.Count; j++)
{
int index = SLRobjNum[I.Container[j]].Right.IndexOf('.');
if (index == SLRobjNum[I.Container[j]].Right.Length - 1)//如果点在产生式最后，跳过
continue;
char ch = SLRobjNum[I.Container[j]].Right[index + 1];
if (!exist(C, ch))
C.Add(ch);
}
//对于集合C中的每个符号，构造新的项目集I'
for (int j = 0; j < C.Count; j++)
{
SLRitemsets I_new = new SLRitemsets();
for (int k = 0; k < I.Container.Count; k++)
{
int index = SLRobjNum[I.Container[k]].Right.IndexOf('.');
if (index == SLRobjNum[I.Container[k]].Right.Length - 1)//如果点在产生式最后，跳过
continue;
char ch = SLRobjNum[I.Container[k]].Right[index + 1];
if (ch == C[j])
{
SLRNode Lobj = new SLRNode(SLRobjNum[I.Container[k]].Left, CreObj(SLRobjNum[I.Container[k]].Right, index + 1));
int num = isexist(I_new.Container);
if (num == -1)//如果I'不存在，加入
{
I_new.Container.Add(SLRobjNum.Count);
SLRobjNum.Add(Lobj);
}
else//如果I'已存在，加入
{
I_new.Container.Add(num);
}
}
}
//如果I'不存在于项目集合中，加入
int num1 = isexist(I_new.Container);
if (num1 == -1)
{
proitemset.Add(I_new);
num1 = proitemset.Count - 1;
}
//构造DFA
dfa[Pindex] = new DFA(i, C[j], num1);
Pindex++;
}
i++;
}
}
//获取LR0分析表
public Table[][] GET_ANA()
{
int i, j;
//获取非终结符的Follow集
follow = GetFollow(Nchar, Echar, SLRproNum, SLRobjNum);
//构造分析表
SLRAna = new Table[proitemset.Count][];
for (i = 0; i < proitemset.Count; i++)
{
SLRAna[i] = new Table[Echar.Count + Nchar.Count];
for (j = 0; j < Echar.Count; j++)
{
SLRAna[i][j] = new Table();
}
for (j = 0; j < Nchar.Count; j++)
{
SLRAna[i][j + Echar.Count] = new Table();
}
}
//填充分析表
for (i = 0; i < proitemset.Count; i++)
{
for (j = 0; j < proitemset[i].Container.Count; j++)
{
int index = SLRobjNum[proitemset[i].Container[j]].Right.IndexOf('.');
if (index == SLRobjNum[proitemset[i].Container[j]].Right.Length - 1)//如果点在产生式最后
{
if (SLRobjNum[proitemset[i].Container[j]].Left == 'S'')
{//接受状态
SLRAna[i][Echar.Count - 1] = new Table('A', -1);
}
else
{//归约状态
int pro_index = Find_pro(SLRobjNum[proitemset[i].Container[j]]);
HashSet<char> follow_set = follow[SLRobjNum[proitemset[i].Container[j]].Left[0]];
foreach (char c in follow_set)
{
int col = FindID(Echar, c);
SLRAna[i][col] = new Table('R', pro_index);
}
}
}
else
{
char ch = SLRobjNum[proitemset[i].Container[j]].Right[index + 1];
if (isFinalsymbol(ch))
{//移进状态
int col = FindID(Echar, ch);
int to = dfa[i * (Echar.Count + Nchar.Count) + col].to;
SLRAna[i][col] = new Table('S', to);
}
}
}
}
return SLRAna;
}
//构造分析表
public void SLRAnaly()
{
GET_ANA();
RStr_ANA += '\r\n分析表：\r\n';
RStr_ANA += ' |';
for (int i = 0; i < Echar.Count; i++)
{
RStr_ANA += ' ' + Echar[i] + ' |';
}
for (int i = 0; i < Nchar.Count; i++)
{
RStr_ANA += ' ' + Nchar[i] + ' |';
}
RStr_ANA += '\r\n';
for (int i = 0; i < proitemset.Count; i++)
{
RStr_ANA += i.ToString().PadLeft(2) + '|';
for (int j = 0; j < Echar.Count + Nchar.Count; j++)
{
if (SLRAna[i][j].error)
RStr_ANA += ' |';
else
{
RStr_ANA += ' ';
RStr_ANA += SLRAna[i][j].type.ToString();
RStr_ANA += SLRAna[i][j].id.ToString().PadLeft(2);
RStr_ANA += ' |';
}
}
RStr_ANA += '\r\n';
}
}
}
未给函数代码
//判断符号是否为终结符
public bool isFinalsymbol(char ch)
{
if (ch >= 'a' && ch <= 'z')
return true;
if (ch >= 'A' && ch <= 'Z')
return false;
return false;
}
//判断元素是否存在于集合中
public bool exist(List<char> list, char ch)
{
foreach (char c in list)
{
if (c == ch)
return true;
}
return false;
}
//判断元素是否存在于集合中，返回元素所在集合的序号
public int isexist(List<int> list)
{
for (int i = 0; i < proitemset.Count; i++)
{
bool flag = true;
if (list.Count == proitemset[i].Container.Count)
{
for (int j = 0; j < list.Count; j++)
{
if (list[j] != proitemset[i].Container[j])
{
flag = false;
break;
}
}
if (flag)
return i;
}
}
return -1;
}
//在字符串中插入'.'
public string CreObj(string str, int index)
{
string newstr = '';
for (int i = 0; i < index; i++)
{
newstr += str[i];
}
newstr += '.';
for (int i = index; i < str.Length; i++)
{
newstr += str[i];
}
return newstr;
}
//寻找产生式在产生式集合中的序号
public int Find_pro(SLRNode Lobj)
{
for (int i = 0; i < SLRproNum.Count; i++)
{
if (SLRproNum[i].Left == Lobj.Left && SLRproNum[i].Right == Lobj.Right)
return i;
}
return -1;
}
//获取符号在集合中的序号
public int FindID(List<char> list, char ch)
{
for (int i = 0; i < list.Count; i++)
{
if (list[i] == ch)
return i;
}
return -1;
}
//获取非终结符的Follow集
public Dictionary<char, HashSet<char>> GetFollow(List<char> Nchar, List<char> Echar, List<SLRNode> SLRproNum, List<SLRNode> SLRobjNum)
{
Dictionary<char, HashSet<char>> follow = new Dictionary<char, HashSet<char>>();
// 初始化 Follow 集，每个非终结符的 Follow 集为空集
foreach (char ch in Nchar)
{
follow[ch] = new HashSet<char>();
}
// 1. 将 '#' 加入开始符号 S' 的 Follow 集
follow['S''][0] = '#';
// 2. 遍历所有产生式
for (int i = 0; i < SLRproNum.Count; i++)
{
string right = SLRproNum[i].Right;
for (int j = 0; j < right.Length; j++)
{
if (!isFinalsymbol(right[j])) // 当前符号是非终结符
{
// 如果当前符号不是产生式的最后一个符号
if (j < right.Length - 1)
{
// 获取当前符号之后的符号
char nextSymbol = right[j + 1];
// 如果下一个符号是终结符，则将下一个符号加入当前符号的 Follow 集
if (isFinalsymbol(nextSymbol))
{
follow[right[j]].Add(nextSymbol);
}
// 如果下一个符号是非终结符，则将下一个符号的 Follow 集加入当前符号的 Follow 集
else
{
follow[right[j]].UnionWith(follow[nextSymbol]);
}
}
else // 当前符号是产生式的最后一个符号
{
// 如果当前符号是产生式的最后一个符号，且当前产生式不是拓广产生式，则将产生式左部的 Follow 集加入当前符号的 Follow 集
if (SLRproNum[i].Left != 'S'')
{
follow[right[j]].UnionWith(follow[SLRproNum[i].Left[0]]);
}
}
}
}
}
return follow;
}
代码解析
isFinalsymbol(char ch)：判断一个字符是否是终结符。如果字符是小写字母，则返回 true，否则返回 false。exist(List<char> list, char ch)：判断一个字符是否在一个字符列表中。如果存在，则返回 true，否则返回 false。isexist(List<int> list)：判断一个项目集是否在项目集合列表中存在。如果存在，则返回该项目集在列表中的索引，否则返回 -1。CreObj(string str, int index)：在字符串的指定位置插入一个点号“.”，并返回新的字符串。Find_pro(SLRNode Lobj)：查找一个项目在产生式列表中的序号，如果找到，则返回序号，否则返回 -1。FindID(List<char> list, char ch)：查找一个字符在字符列表中的序号，如果找到，则返回序号，否则返回 -1。GetFollow(List<char> Nchar, List<char> Echar, List<SLRNode> SLRproNum, List<SLRNode> SLRobjNum)：计算所有非终结符的 Follow 集，并返回一个字典，键为非终结符，值为该非终结符的 Follow 集。
总结
本文详细解析了 SLR1 分析器关键功能函数的代码实现，涵盖项目集构造、分析表填充、Follow 集计算等重要环节，并提供了代码示例，帮助读者理解 SLR1 分析器的工作原理和实现过程。
原文地址: https://www.cveoy.top/t/topic/f0NG 著作权归作者所有。请勿转载和采集!