SLR 分析表构建算法实现 - C# 代码示例
{
"title": "SLR 分析表构建算法实现 - C# 代码示例",
"description": "本文提供 C# 代码示例，展示如何使用 SLR 分析表构建算法解析语法，并附带详细的代码注释，帮助您理解算法的实现过程。",
"keywords": "SLR 分析表，语法分析，编译原理，C# 代码示例，SLR 解析",
"content": "
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
//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 Table[][] SLRAna;//分析表
public SLRNode[] SLRNodeList = new SLRNode[100]; // 产生式列表
public List<char> T = new List<char>(); // 终结符列表
public List<char> NT = new List<char>(); // 非终结符列表
public Dictionary<char, List<char>> Follow = new Dictionary<char, List<char>>(); // FOLLOW 集
public int d = 0; // DFA 状态数量
public void SLRAnaly()
{
int n = 0;
//记录每个项目集的编号
Dictionary<SLRitemsets, int> itemsets = new Dictionary<SLRitemsets, int>();
//初始化第一个项目集
SLRitemsets I0 = new SLRitemsets();
I0.Container.Add(0);
itemsets.Add(I0, n++);
//通过循环遍历每个项目集
for (int i = 0; i < n; i++)
{
SLRitemsets I = new SLRitemsets();
I.Container = itemsets.ElementAt(i).Key.Container;
//获取该项目集中的每个项目
for (int j = 0; j < I.Container.Count; j++)
{
int l = 0;
//获取该项目的左部和右部
string left = SLRNodeList[I.Container[j]].Left;
string right = SLRNodeList[I.Container[j]].Right;
//判断该项目是否已经处理过
if (right.Length > l && !Char.IsUpper(right[l]))
continue;
//获取该项目的下一个字符
char X = right[l + 1];
SLRitemsets J = new SLRitemsets();
//对于每个文法符号，计算它的闭包
for (int k = 0; k < I.Container.Count; k++)
{
string left2 = SLRNodeList[I.Container[k]].Left;
string right2 = SLRNodeList[I.Container[k]].Right;
if (right2.Length > l && right2[l] == X)
{
J.Container.Add(k);
}
}
//如果该闭包不为空，则加入到项目集中
if (J.Container.Count > 0)
{
if (!itemsets.ContainsKey(J))
{
itemsets.Add(J, n++);
}
dfa[d++] = new DFA(i, X, itemsets[J]);
}
}
}
//构建分析表
SLRAna = new Table[n][];
for (int i = 0; i < n; i++)
{
SLRAna[i] = new Table[T.Count() + NT.Count() + 1];
for (int j = 0; j < T.Count() + NT.Count() + 1; j++)
{
SLRAna[i][j] = new Table();
}
}
//填充分析表
for (int i = 0; i < n; i++)
{
for (int j = 0; j < T.Count(); j++)
{
char a = T[j];
int p = getAction(i, a);
if (p != -1)
{
if (SLRNodeList[p].Left == "acc")
{
SLRAna[i][j] = new Table('a', 0);
}
else
{
SLRAna[i][j] = new Table('s', p);
}
}
}
for (int j = 0; j < NT.Count(); j++)
{
char a = NT[j];
int p = getGoto(i, a);
if (p != -1)
{
SLRAna[i][j + T.Count()] = new Table('g', p);
}
}
}
//填充归约项
for (int i = 0; i < n; i++)
{
for (int j = 0; j < SLRNodeList.Count; j++)
{
if (SLRNodeList[j].Right == "#")
{
int p = getReduce(i, SLRNodeList[j]);
if (p != -1)
{
SLRAna[i][T.Count() + NT.Count()] = new Table('r', p);
}
}
else
{
for (int k = 0; k < T.Count(); k++)
{
char a = T[k];
int p = getReduce(i, SLRNodeList[j], a);
if (p != -1)
{
SLRAna[i][k] = new Table('r', p);
}
}
}
}
}
}
//获取ACTION表中的值
private int getAction(int i, char a)
{
for (int j = 0; j < d; j++)
{
if (dfa[j].from == i && dfa[j].symbol == a)
{
return dfa[j].to;
}
}
return -1;
}
//获取GOTO表中的值
private int getGoto(int i, char a)
{
for (int j = 0; j < d; j++)
{
if (dfa[j].from == i && dfa[j].symbol == a)
{
return dfa[j].to;
}
}
return -1;
}
//获取归约项
private int getReduce(int i, SLRNode node)
{
for (int j = 0; j < itemsets.ElementAt(i).Key.Container.Count; j++)
{
int p = itemsets.ElementAt(i).Key.Container[j];
if (SLRNodeList[p].Left == node.Left && SLRNodeList[p].Right == node.Right)
{
return p;
}
}
return -1;
}
//获取归约项
private int getReduce(int i, SLRNode node, char a)
{
for (int j = 0; j < itemsets.ElementAt(i).Key.Container.Count; j++)
{
int p = itemsets.ElementAt(i).Key.Container[j];
if (SLRNodeList[p].Left == node.Left && SLRNodeList[p].Right == node.Right)
{
for (int k = 0; k < Follow[node.Left].Count; k++)
{
if (Follow[node.Left][k] == a)
{
return p;
}
}
}
}
return -1;
}
}
原文地址: https://www.cveoy.top/t/topic/f1PA 著作权归作者所有。请勿转载和采集!