SLR1 分析表构建：基于 LR0 文法的扩展
public class LR
{
//产生式结点类
public class LRNode
{
public string Left;
public string Right;
public LRNode(string Left, string Right)
{
this.Left = Left;
this.Right = Right;
}
}
//项目集类
public class LRitemsets
{
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[][] LRAna;//分析表
public Analyze Jz;
public bool Success = false;
public List<LRNode> LRproNum = new List<LRNode>(50);//产生式 列表
public List<LRNode> LRobjNum = new List<LRNode>(50);//项目 列表
public List<LRitemsets> proitemset = new List<LRitemsets>(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);//终结符集合
public string RStr = '';
public string RStr_obitemset = '';//输出返回
public string RStr_DFA = '';
public string RStr_ANA = '';
public void Buildprod(string str)
{
LRNode Lr;
int i = 0;
string left = '';
string right = '';
left += 'S';
right += str[0];
Lr = new LRNode(left, right);//拓广文法开始
LRproNum.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 LRNode(left, right);
LRproNum.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 LRNode(left, right);//构造每一行最后一个产生式，不存在'|'时就是该行产生式本身
LRproNum.Add(Lr);
}
}//while
Echar.Add('#');
//构造项目 对产生式集合LRproNum中的所有产生式都循环插'.'
LRNode Lobj;
for (i = 0; i < LRproNum.Count; i++)
{
left = '';
right = '';
for (int j = 0; j <= LRproNum[i].Right.Length; j++)//j可以等于length 项目共length+1个
{
left = LRproNum[i].Left;
right = CreObj(LRproNum[i].Right, j);//在第j个位置插入'.'
if (j == LRproNum[i].Right.Length && LRobjNum.Count != 1)
{
//在产生式最后的位置插入. 即为归约项目 项目集中1号位置为接受项目
Gy_obj.Add(LRobjNum.Count);//归约项目在项目集中的序号 不用+1 本身就是从0开始的
}
Lobj = new LRNode(left, right);
LRobjNum.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 += LRobjNum[proitemset[j].Container[i]].Left.ToString() + '->' + LRobjNum[proitemset[j].Container[i]].Right.ToString() + '\r\n';
}
}
//return RStr_obitemset;
}
public Table[][] GET_ANA()
{
LRAnaly();
RStr_ANA += '\r\nLR0分析表:\r\n ';
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 += '\r\n';
for (i = 0; i < proitemset.Count; i++)
{
RStr_ANA += i.ToString() + ' ';
for (int j = 0; j < Echar.Count + Nchar.Count; j++)
{
if (LRAna[i][j].error)
{
RStr_ANA += ' ' + ' ';
}
else if (i == 1 && j == Echar.Count - 1)
{
RStr_ANA += 'AC' + ' ';
}
else if (LRAna[i][j].type != 'N')
{
RStr_ANA += LRAna[i][j].type.ToString() + LRAna[i][j].id.ToString() + ' ';
}
else
RStr_ANA += LRAna[i][j].id.ToString() + ' ';
}
RStr_ANA += '\r\n';
}
return LRAna;
}
//分析表
public void LRAnaly()
{
Table tnode = new Table();
LRAna = new Table[proitemset.Count][];
for (int i = 0; i < proitemset.Count; i++)
LRAna[i] = new Table[Echar.Count + Nchar.Count];
for (int i = 0; i < proitemset.Count; i++)//初始化 赋予ERROR属性
for (int j = 0; j < Echar.Count + Nchar.Count; j++)//为终结符加r状态
LRAna[i][j] = tnode;
tnode = new Table('A', 0);
LRAna[1][FindID(Echar, '#')] = tnode;//项目集1必定是接受项目 构建[1][#]:acc的情况 先直接赋值好 dfa里没有
for (int i = 0; i < Gy_itemset.Count; i++)
{
tnode = new Table('r', Find_pro(LRobjNum[proitemset[Gy_itemset[i]].Container[0]]));//归约项目 找到原产生式序号 添加状态r
for (int j = 0; j < Echar.Count; j++)
{
LRAna[Gy_itemset[i]][j] = tnode;
}
}
for (int i = 0; i < Pindex; i++)
{
if (isFinalsymbol(dfa[i].symbol))//symbol为非终结符 添加状态N
{
int CID = FindID(Nchar, dfa[i].symbol);
tnode = new Table('N', dfa[i].to);
LRAna[dfa[i].from][CID + Echar.Count] = tnode;
}
else //不是归约项目 添加状态S
{
int CID = FindID(Echar, dfa[i].symbol);
tnode = new Table('S', dfa[i].to);
LRAna[dfa[i].from][CID] = tnode;
}
}
}
//计算Follow集
public void Follow()
{
Dictionary<char, HashSet<char>> follow = new Dictionary<char, HashSet<char>>();//非终结符的Follow集
foreach (char c in Nchar)
{
follow[c] = new HashSet<char>();
}
follow[Nchar[0]].Add('#');//将开始符号的Follow集加入#
bool flag = true;
while (flag)
{
flag = false;
foreach (LRNode lr in LRproNum)//遍历每个产生式
{
string right = lr.Right;
int len = right.Length;
for (int i = 0; i < len; i++)
{
if (isFinalsymbol(right[i])) continue;//终结符不考虑
HashSet<char> fset = follow[right[i]];
if (i == len - 1)//如果是产生式右边的最后一个符号
{
HashSet<char> fset2 = follow[lr.Left[0]];
if (fset2.IsSupersetOf(fset)) continue;//如果已经包含了就不用再添加了
fset2.UnionWith(fset);
follow[lr.Left[0]] = fset2;
flag = true;
}
else
{
HashSet<char> fset2 = first(right.Substring(i + 1));
if (fset2.Contains('#'))//如果后继符号可以为空
{
fset2.Remove('#');
fset2.UnionWith(follow[lr.Left[0]]);
}
if (fset2.IsSubsetOf(fset)) continue;//如果已经包含了就不用再添加了
fset.UnionWith(fset2);
follow[right[i]] = fset;
flag = true;
}
}
}
}
//输出Follow集
RStr += '\r\nFollow集:\r\n';
foreach (char c in Nchar)
{
RStr += c + ': { ';
foreach (char f in follow[c])
{
RStr += f + ' ';
}
RStr += '}
\n';
}
}
//SLR1分析表
public void SLRAnaly()
{
Follow();//计算Follow集
Table tnode = new Table();
LRAna = new Table[proitemset.Count][];
for (int i = 0; i < proitemset.Count; i++)
LRAna[i] = new Table[Echar.Count + Nchar.Count];
for (int i = 0; i < proitemset.Count; i++)//初始化 赋予ERROR属性
for (int j = 0; j < Echar.Count + Nchar.Count; j++)//为终结符加r状态
LRAna[i][j] = tnode;
tnode = new Table('A', 0);
LRAna[1][FindID(Echar, '#')] = tnode;//项目集1必定是接受项目 构建[1][#]:acc的情况 先直接赋值好 dfa里没有
for (int i = 0; i < Gy_itemset.Count; i++)
{
HashSet<char> fset = follow[LRobjNum[proitemset[Gy_itemset[i]].Container[0]].Left[0]];//获取归约项目对应产生式的Follow集
foreach (char c in fset)//遍历Follow集
{
int CID = FindID(Echar, c);
tnode = new Table('r', Find_pro(LRobjNum[proitemset[Gy_itemset[i]].Container[0]]));//归约项目 找到原产生式序号 添加状态r
LRAna[Gy_itemset[i]][CID] = tnode;
}
}
for (int i = 0; i < Pindex; i++)
{
if (isFinalsymbol(dfa[i].symbol))//symbol为非终结符 添加状态N
{
int CID = FindID(Nchar, dfa[i].symbol);
tnode = new Table('N', dfa[i].to);
LRAna[dfa[i].from][CID + Echar.Count] = tnode;
}
else //不是归约项目 添加状态S
{
int CID = FindID(Echar, dfa[i].symbol);
tnode = new Table('S', dfa[i].to);
LRAna[dfa[i].from][CID] = tnode;
}
}
}
// ... 其他代码 ...
}
解释：
-
计算Follow集：
Follow()函数计算每个非终结符的 Follow 集，并在SLRAnaly()函数开始时被调用。- 算法遍历所有产生式，对于产生式中的每个非终结符
A，如果A在产生式的最后，则其 Follow 集包含A左侧非终结符的 Follow 集；否则，其 Follow 集包含A后继符号的 First 集（排除空符号），如果后继符号的 First 集包含空符号，则还包含A左侧非终结符的 Follow 集。
-
SLR1 分析表构建：
SLRAnaly()函数利用Follow集构建 SLR1 分析表。- 对于每个归约项目，遍历其对应产生式的 Follow 集，并将
r状态（包含产生式编号）添加到分析表中对应的行列。 - 对于其他项目，根据 DFA 状态转移关系添加
S或N状态，分别对应移进和移进并归约操作。
示例：
假设以下产生式集合：
S' -> S
S -> aAb
S -> c
A -> a
经过 SLR1 分析表构建，得到如下分析表：
a b c # S A
-------------------------
I0 S1 E S3 E E E
I1 E r4 E r4 E E
I2 S5 E E E E E
I3 E E E r2 E E
I4 E E E E E E
I5 S1 E E E E E
该分析表中，r2 表示归约到产生式 S -> c，r4 表示归约到产生式 S -> aAb。其他状态表示移进或移进并归约操作。
注意：
first()和exist()函数需要根据具体情况进行实现。- 该代码示例仅供参考，实际实现中可能需要根据具体文法进行调整。
原文地址: https://www.cveoy.top/t/topic/f0Mi 著作权归作者所有。请勿转载和采集!