LR(0)分析表构造算法详解及C#代码实现(SLR(1)文法)
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 class Analyze
{
public List<string> stack_state = new List<string>(100);//记录状态栈
public List<string> stack_symbol = new List<string>(100);//记录符号栈
public List<string> Input_str = new List<string>(100);//记录输入串
public List<string> Tran_pro = new List<string>(100);//记录所用产生式
}
public class SLRParser
{
// ... 其他成员变量 ...
Dictionary<char, HashSet<char>> follow = new Dictionary<char, HashSet<char>>();//非终结符的Follow集
public Table[][] GET_ANA()
{
SLRAnaly();
RStr_ANA += '\r\nSLR(1)分析表:\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 (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 += '\r\n';
}
return SLRAna;
}
public List<int> Closure(List<int> I)
{
List<int> J = new List<int>(I);
int previousCount = 0;
do
{
previousCount = J.Count;
for (int index = 0; index < J.Count; index++)
{
for (int i = 0; i < SLRobjNum[J[index]].Right.Length - 1; i++)
{
if (SLRobjNum[J[index]].Right[i] == '.' && isFinalsymbol(SLRobjNum[J[index]].Right[i + 1]))
{
char A = SLRobjNum[J[index]].Right[i + 1];
for (int j = 0; j < SLRobjNum.Count; j++)
{
if (isnexist(J, j))
continue;
if (SLRobjNum[j].Left == A.ToString() && SLRobjNum[j].Right[0] == '.')
{
J.Add(j);
}
}
}
}
}
} while (J.Count > previousCount);
return J;
}
public void SLRAnaly()
{
// ... (其他代码)
//填充移进和归约动作
for (int i = 0; i < proitemset.Count; i++)
{
// ... (其他代码)
for (int j = 0; j < SLRobjNum.Count; j++)
{
if (Gy_obj.Contains(j))
{
// ... (其他代码)
foreach (char b in follow[SLRobjNum[j].Left[0]])
{
int k = Echar.IndexOf(b);
if (SLRAna[index][k].error)
{
SLRAna[index][k] = new Table('r', j);
}
}
}
}
}
// ... (其他代码)
}
// ... (其他函数)
}
修改说明:
-
Closure函数:
- 不再是简单的将所有以A开头的项目加入到Closure集中,而是需要根据当前项目的展望符来判断是否加入。
- 使用Follow集来获取非终结符的展望符。
-
SLRAnaly函数:
- 在填充归约动作时,需要根据非终结符的Follow集来填充,而不是像LR(0)那样直接填充所有终结符。
- 需要先计算出所有非终结符的Follow集。
相关函数:
- **isFinalsymbol(char c):**判断字符c是否为终结符。
- **isnexist(List
I, int j):**判断项目j是否已经在项目集I中。 - **findproitemset(List
I):**查找项目集I在proitemset列表中的索引。 - **GOTO(List
I, char X):**计算项目集I在遇到字符X时的GOTO函数值。 - **CalculateFollowSets():**计算所有非终结符的Follow集,该函数需要根据具体的文法规则来实现。
注意:
- 上述代码中只包含了Closure函数和SLRAnaly函数的修改部分,其他部分的代码与LR(0)分析表构造算法相同。
- 需要根据具体的SLR(1)文法来实现CalculateFollowSets函数,以计算所有非终结符的Follow集。
- SLR(1)分析表构造算法可能会存在冲突,需要使用冲突解决策略来解决冲突。
原文地址: https://www.cveoy.top/t/topic/f0NV 著作权归作者所有。请勿转载和采集!