SLR1 语法分析器实现：从 LR0 到 SLR1 分析表构造
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 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 Table[][] GET_ANA()
{
SLR0Analy();
return SLRAna;
}
public void SLRAnaly()
{
//构造SLR分析表
//初始化分析表
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 < proitemset.Count; i++)
{
for (int j = 0; j < Echar.Count; j++)
{
char ch = Echar[j];
List<int> Goto = GOTO(proitemset[i].Container, ch);
if (Goto.Count > 0)
{
int k = getitemset(Goto);
if (isFinalsymbol(ch))
SLRAna[i][j] = new Table('S', k);
else
SLRAna[i][j + Echar.Count] = new Table('G', k);
}
}
for (int j = 0; j < proitemset[i].Container.Count; j++)
{
int k = proitemset[i].Container[j];
if (SLRobjNum[k].Right.IndexOf('.') == SLRobjNum[k].Right.Length - 1)
{
if (SLRobjNum[k].Left == 'S'')
SLRAna[i][Echar.Count - 1] = new Table('A', 0);
else
{
HashSet<char> followset = follow[SLRobjNum[k].Left[0]];
foreach (char ch in followset)
{
int index = Echar.IndexOf(ch);
if (index != -1)
SLRAna[i][index] = new Table('R', k);
}
}
}
}
}
}
public void SLR0Analy()
{
//构造LR0项目集
LR0itemset();
//构造DFA
LR0DFA();
//构造SLR分析表
SLRAnaly();
}
//获取非终结符ch的FIRST集
public HashSet<char> first(char ch)
{
HashSet<char> set = new HashSet<char>();
for (int i = 0; i < SLRproNum.Count; i++)
{
if (SLRproNum[i].Left[0] == ch)
{
if (isFinalsymbol(SLRproNum[i].Right[0]))
set.Add(SLRproNum[i].Right[0]);
else
{
HashSet<char> temp = first(SLRproNum[i].Right[0]);
foreach (char c in temp)
{
set.Add(c);
}
}
}
}
return set;
}
//获取非终结符ch的FOLLOW集
public HashSet<char> followset(char ch)
{
HashSet<char> set = new HashSet<char>();
if (ch == 'S')
set.Add('#');
for (int i = 0; i < SLRproNum.Count; i++)
{
for (int j = 0; j < SLRproNum[i].Right.Length; j++)
{
if (SLRproNum[i].Right[j] == ch)
{
if (j == SLRproNum[i].Right.Length - 1)
{
if (SLRproNum[i].Left[0] != ch)
{
HashSet<char> temp = followset(SLRproNum[i].Left[0]);
foreach (char c in temp)
{
set.Add(c);
}
}
}
else
{
if (isFinalsymbol(SLRproNum[i].Right[j + 1]))
set.Add(SLRproNum[i].Right[j + 1]);
else
{
HashSet<char> temp = first(SLRproNum[i].Right[j + 1]);
foreach (char c in temp)
{
set.Add(c);
}
if (temp.Contains('ε'))
{
if (SLRproNum[i].Left[0] != ch)
{
HashSet<char> temp2 = followset(SLRproNum[i].Left[0]);
foreach (char c in temp2)
{
set.Add(c);
}
}
}
}
}
}
}
}
return set;
}
//构造SLR分析表
public void SLRAnaly()
{
//初始化follow集
foreach (char ch in Nchar)
{
follow[ch] = new HashSet<char>();
}
follow['S'] = new HashSet<char>();
follow['S'].Add('#');
for (int i = 0; i < SLRproNum.Count; i++)
{
for (int j = 0; j < SLRproNum[i].Right.Length; j++)
{
if (isNonfinalsymbol(SLRproNum[i].Right[j]))
{
if (j == SLRproNum[i].Right.Length - 1)
{
HashSet<char> temp = followset(SLRproNum[i].Left[0]);
foreach (char ch in temp)
{
follow[SLRproNum[i].Right[j]].Add(ch);
}
}
else
{
HashSet<char> temp = first(SLRproNum[i].Right[j + 1]);
foreach (char ch in temp)
{
if (ch != 'ε')
follow[SLRproNum[i].Right[j]].Add(ch);
}
if (temp.Contains('ε'))
{
HashSet<char> temp2 = followset(SLRproNum[i].Left[0]);
foreach (char ch in temp2)
{
follow[SLRproNum[i].Right[j]].Add(ch);
}
}
}
}
}
}
//构造SLR分析表
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 < proitemset.Count; i++)
{
for (int j = 0; j < Echar.Count; j++)
{
char ch = Echar[j];
List<int> Goto = GOTO(proitemset[i].Container, ch);
if (Goto.Count > 0)
{
int k = getitemset(Goto);
if (isFinalsymbol(ch))
SLRAna[i][j] = new Table('S', k);
else
SLRAna[i][j + Echar.Count] = new Table('G', k);
}
}
for (int j = 0; j < proitemset[i].Container.Count; j++)
{
int k = proitemset[i].Container[j];
if (SLRobjNum[k].Right.IndexOf('.') == SLRobjNum[k].Right.Length - 1)
{
if (SLRobjNum[k].Left == 'S'')
SLRAna[i][Echar.Count - 1] = new Table('A', 0);
else
{
HashSet<char> followset = follow[SLRobjNum[k].Left[0]];
foreach (char ch in followset)
{
int index = Echar.IndexOf(ch);
if (index != -1)
SLRAna[i][index] = new Table('R', k);
}
}
}
}
}
}
上述代码中，SLRAnaly() 函数是核心构造 SLR 分析表的函数，其中 follow 字典用于存储非终结符的 FOLLOW 集，在该函数中，我们会利用 follow 字典来填充分析表中的归约项。
此外，需要补充 LR0itemset()、LR0DFA()、GOTO()、getitemset()、isFinalsymbol()、isNonfinalsymbol() 等辅助函数，这些函数用于构造 LR0 项目集，构建 DFA，以及判断终结符和非终结符等操作。
以下给出 first() 和 followset() 函数的实现代码：
// 获取非终结符ch的FIRST集
public HashSet<char> first(char ch)
{
HashSet<char> set = new HashSet<char>();
for (int i = 0; i < SLRproNum.Count; i++)
{
if (SLRproNum[i].Left[0] == ch)
{
if (isFinalsymbol(SLRproNum[i].Right[0]))
set.Add(SLRproNum[i].Right[0]);
else
{
HashSet<char> temp = first(SLRproNum[i].Right[0]);
foreach (char c in temp)
{
set.Add(c);
}
}
}
}
return set;
}
// 获取非终结符ch的FOLLOW集
public HashSet<char> followset(char ch)
{
HashSet<char> set = new HashSet<char>();
if (ch == 'S')
set.Add('#');
for (int i = 0; i < SLRproNum.Count; i++)
{
for (int j = 0; j < SLRproNum[i].Right.Length; j++)
{
if (SLRproNum[i].Right[j] == ch)
{
if (j == SLRproNum[i].Right.Length - 1)
{
if (SLRproNum[i].Left[0] != ch)
{
HashSet<char> temp = followset(SLRproNum[i].Left[0]);
foreach (char c in temp)
{
set.Add(c);
}
}
}
else
{
if (isFinalsymbol(SLRproNum[i].Right[j + 1]))
set.Add(SLRproNum[i].Right[j + 1]);
else
{
HashSet<char> temp = first(SLRproNum[i].Right[j + 1]);
foreach (char c in temp)
{
set.Add(c);
}
if (temp.Contains('ε'))
{
if (SLRproNum[i].Left[0] != ch)
{
HashSet<char> temp2 = followset(SLRproNum[i].Left[0]);
foreach (char c in temp2)
{
set.Add(c);
}
}
}
}
}
}
}
}
return set;
}
通过这些代码，您可以将 LR0 分析器改造为 SLR1 分析器，并实现 SLR1 分析表的构造。请注意，您需要根据具体的语法规则和产生式列表来完善代码，并确保所有辅助函数的正确实现。
原文地址: https://www.cveoy.top/t/topic/f0NY 著作权归作者所有。请勿转载和采集!