SLR1文法分析表实现 - C# 代码示例
{
public partial class Form5 : Form
{
public Form5()
{
InitializeComponent();
}
LR lr = new LR();//全局变量 依次执行
private int step = 0; // 记录当前分析到第几步
// 构造LR分析表
private void button5_Click(object sender, EventArgs e)
{
listView2.Clear();
LR.Table[][] table;
table = lr.GET_ANA();
int xlen = table.GetLength(0);
int ylen = table[1].Length;
listView2.Columns.Clear();
listView2.Items.Clear();
listView2.View = View.Details;
listView2.Columns.Add(" ");
for (int i = 0; i < lr.Echar.Count; i++)//添加表头
{
string text = lr.Echar[i].ToString();
listView2.Columns.Add(text,58);
}
for (int i = 0; i < lr.Nchar.Count; i++)//添加表头
{
string text = lr.Nchar[i].ToString();
listView2.Columns.Add(text,58);
}
for (int i = 0; i < xlen; i++)
{
ListViewItem li = new ListViewItem(i.ToString());
for (int j = 0; j < ylen; j++)
{
string st = "";
if (table[i][j].error)
st = "-";
else if (table[i][j].type == 'A')
st = "AC";
else
st = table[i][j].type.ToString() + table[i][j].id.ToString();
li.SubItems.Add(st);
}
listView2.Items.Add(li);
}
listView2.GridLines = true;
}
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 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;
}
}
}
//构造闭包
public List<int> Closure(List<int> I)
{
for (int index = 0; index < I.Count; index++)//遍历该集合中的所有序号 初始序号就是拓广文法的0 下面的ADD步骤中会扩大他的内容
for (int i = 0; i < LRobjNum[I[index]].Right.Length - 1; i++)//遍历第index序号项目右侧字符串 找到.A结构
{
if (LRobjNum[I[index]].Right[i] == '.' && isFinalsymbol(LRobjNum[I[index]].Right[i + 1]))
{
for (int j = 0; j < LRobjNum.Count; j++)//遍历所有项目，找到以A开头的.a
{
if (isnexist(I, j))
continue;
if (LRobjNum[j].Left == LRobjNum[I[index]].Right[i + 1].ToString() && LRobjNum[j].Right[0] == '.')
I.Add(j);//ADD：在项目集（序号集合）中加入新成员
}
}
}
return I;
}
//构造项目 在right[index]位置插入'.'
public string CreObj(string right, int index)
{
int i = 0;
string Restr = "";
while (i < right.Length)
{
if (i == index)
Restr += '.';
Restr += right[i];
i++;
}
if (i == index)
Restr += '.';
return Restr;
}
//判断ch是否为非终结符
public bool isFinalsymbol(char ch1)
{
//char ch1=ch[0];
if (ch1 >= 'A' && ch1 <= 'Z')
return true;
else
return false;
}
//判断集合是I否存在于proitemset
//如果存在就返回已存在的项目集序号
//如果不存在就返回-1
public int isexist(List<int> I)
{
I.Sort();
for (int i = 0; i < proitemset.Count; i++)
{
proitemset[i].Container.Sort();
if (I.SequenceEqual(proitemset[i].Container))
{
return i;
}
}
return -1;
}
//判断num是否存在于I
//存在返回true 不存在返回False
public bool isnexist(List<int> I, int num)
{
for (int i = 0; i < I.Count; i++)
{
if (I[i] == num)
return true;
}
return false;
}
//判断ch是否存在于I
//存在返回true 不存在返回False
public bool exist(List<char> I, char ch)
{
for (int i = 0; i < I.Count; i++)
{
if (I[i] == ch)
return true;
}
return false;
}
//寻找ch在I中的序号
public int FindID(List<char> I, char ch)
{
for (int i = 0; i < I.Count; i++)
{
if (I[i] == ch)
return i;
}
return -1;
}
//寻找项目最初的产生式序号 E->.ab ====> E->a
public int Find_pro(LRNode LR)
{
string s = "";
for (int i = 0; i < LR.Right.Length; i++)
{
if (LR.Right[i] != '.')
s += LR.Right[i];
}
for (int i = 0; i < LRproNum.Count; i++)
{
if (LRproNum[i].Left == LR.Left && LRproNum[i].Right == s)
return i;
}
return -1;
}
}
}
//构造SLR1分析表
public Table[][] GET_ANA_SLR()
{
SLRAnaly();
RStr_ANA += "\r\nSLR1分析表:\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;
}
//构造SLR1分析表
public void SLRAnaly()
{
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 j = 0; j < Nchar.Count; j++)//SLR1分析表中，归约项目的follow集也可以作为归约动作的依据
{
if (exist(Follow[LRobjNum[proitemset[Gy_itemset[i]].Container[0]].Left], Nchar[j]))
{
int CID = FindID(Nchar, Nchar[j]);
LRAna[Gy_itemset[i]][CID + Echar.Count] = 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;
//SLR1分析表中，移进项目的follow集也可以作为移进动作的依据
for (int j = 0; j < Follow[LRobjNum[dfa[i].to]].Count; j++)
{
if (exist(Follow[LRobjNum[dfa[i].to]].ToList(), Follow[LRobjNum[dfa[i].to]][j]))
{
int CID2 = FindID(Nchar, Follow[LRobjNum[dfa[i].to]][j]);
LRAna[dfa[i].from][CID2 + 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;
}
}
}
//SLR1分析表构造函数调用
private void button3_Click(object sender, EventArgs e)
{
listView2.Clear();
LR.Table[][] table;
table = lr.GET_ANA_SLR(); //调用SLR1分析表构造函数
int xlen = table.GetLength(0);
int ylen = table[1].Length;
listView2.Columns.Clear();
listView2.Items.Clear();
listView2.View = View.Details;
listView2.Columns.Add(" ");
for (int i = 0; i < lr.Echar.Count; i++)//添加表头
{
string text = lr.Echar[i].ToString();
listView2.Columns.Add(text, 58);
}
for (int i = 0; i < lr.Nchar.Count; i++)//添加表头
{
string text = lr.Nchar[i].ToString();
listView2.Columns.Add(text, 58);
}
for (int i = 0; i < xlen; i++)
{
ListViewItem li = new ListViewItem(i.ToString());
for (int j = 0; j < ylen; j++)
{
string st = "";
if (table[i][j].error)
st = "-";
else if (table[i][j].type == 'A')
st = "AC";
else
st =
原文地址: https://www.cveoy.top/t/topic/fZ4E 著作权归作者所有。请勿转载和采集!