LR 分析表构建算法实现代码详解
LR 分析表构建算法实现代码详解
本文将详细解析 LR 分析表构建算法的实现代码，通过分析两个代码片段，您可以深入理解 LR 分析表构建过程，掌握 LR 分析表的生成原理和实现方法。
代码1：按钮点击事件
private void button4_Click(object sender, EventArgs e)
{
step = 0;//单步计数置零
lr = new LR();
listView1.Columns.Clear();
listView1.Items.Clear();
listView1.View = View.Details;
// 添加第一列
listView1.Columns.Add('状态', 150);
listView1.Columns.Add('项目族信息', 350);
lr.Buildprod(richTextBox1.Text);//调用
for (int i = 0; i < lr.proitemset.Count; i++)//输出
{
ListViewItem li = new ListViewItem();
li.SubItems.Clear();
li.SubItems[0].Text = i.ToString();
string tempstr = '';
for (int j = 0; j < lr.proitemset[i].Container.Count; j++)
{
tempstr += lr.LRobjNum[lr.proitemset[i].Container[j]].Left + '->' + lr.LRobjNum[lr.proitemset[i].Container[j]].Right + ' ';
}
li.SubItems.Add(tempstr);
listView1.Items.Add(li);
}
listView1.GridLines = true;
}
代码1 定义了一个按钮点击事件，用于生成 LR 分析表。主要步骤如下：
- 初始化：将单步计数置零，新建一个 LR 对象。
- 清除 ListView：清除 listView1 中的列和项，设置视图为详细视图。
- 添加列名：添加第一列和第二列的列名。
- 构建 LR 分析表：调用 LR 对象的
Buildprod方法，构建 LR 分析表。 - 输出结果：循环遍历 LR 对象中的产生式集合，将其添加到 listView1 中。
- 显示网格线：设置 listView1 的网格线可见。
代码2：Buildprod 方法
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 void Creteitemsets()
{
List<int> lr_item = new List<int>(100);//记录项目的序号
lr_item.Add(0);
lr_item = Closure(lr_item);//构造初始项目集 求闭包
LRitemsets LR_C = new LRitemsets();
LR_C.Container = lr_item;//集合----项目集序号的集合
proitemset.Add(LR_C);//集合的集合----存放项目集序号集合 的集合
for (int i = 0; i < proitemset.Count; i++)//整体集合中 第i个项目集
{
proitemset[i].Container.Sort();//排序由小到大 后面用于判断是否存在的比较
int[] flag = new int[proitemset[i].Container.Count];
for (int fi = 0; fi < proitemset[i].Container.Count; fi++)//标志位，用来判断该序号是否已经构造
{
flag[fi] = 0;
}
for (int j = 0; j < proitemset[i].Container.Count; j++)//第i个项目集的第j个项目
{
if (flag[j] == 1)//如果已经访问过 就不再构造 找下一个项目
continue;
int index = proitemset[i].Container[j];
for (int pi = 0; pi < LRobjNum[index].Right.Length - 1; pi++)//length-1是避免匹配到.在最后的规约项目
{
if (LRobjNum[index].Right[pi] == '.')
{
List<int> lr2_club = new List<int>(100);//记录项目的序号
char symbol = LRobjNum[index].Right[pi + 1];//记录.a转移状态a.的符号a
lr2_club.Add((index + 1));//如果遇到.a形式的项目序号为index 那么项目a.的序号为index+1
for (int m1 = j + 1; m1 < proitemset[i].Container.Count; m1++)
{//在第i个项目集中找到了可以移动的.：.a 重新遍历第i个项目集j项目之后的 找到同样可以移动a的项目集
int index2 = proitemset[i].Container[m1];
for (int m2 = 0; m2 < LRobjNum[index2].Right.Length - 1; m2++)
{
if (LRobjNum[index2].Right[m2] == '.' && LRobjNum[index2].Right[m2 + 1] == symbol)
{
flag[m1] = 1;//标记位置为1 已经访问 之后不再访问
lr2_club.Add(index2 + 1);
}
}
}
lr2_club = Closure(lr2_club);//求闭包
int value = isexist(lr2_club);
if (value == -1)//-1表示不存在相同的
{
for (int m3 = 0; m3 < Gy_obj.Count; m3++)
{
if (isnexist(lr2_club, Gy_obj[m3]))
{
Gy_itemset.Add(proitemset.Count);
}
}
LRitemsets LR_C2 = new LRitemsets();
dfa[Pindex++] = new DFA(i, symbol, proitemset.Count);//count不用加1 本身从0开始
LR_C2.Container = lr2_club;
proitemset.Add(LR_C2);
}
else
{
dfa[Pindex++] = new DFA(i, symbol, value);
}
break;
}
}
}//end-forj
}//end-fori
}
代码2 定义了 Buildprod 方法，用于构建 LR 分析表。主要步骤如下：
- 初始化：初始化一些变量，包括
left、right等，并构建拓广文法开始的产生式。 - 构建产生式集合：循环遍历输入字符串中的字符，构建产生式集合。
- 如果遇到空格，跳过。
- 如果遇到
|，构建一个新的产生式，将左部设为上一个产生式的左部，将右部设为空。 - 如果遇到非终结符，将其添加到非终结符集合中，并将其添加到当前产生式的左部中。
- 如果遇到终结符，将其添加到终结符集合中，并将其添加到当前产生式的右部中。
- 构建项目：对 LR 对象中的每个产生式都插入
.，并将其添加到 LR 对象的项目集合中。 - 构建项目集：求闭包和移进操作，并将其添加到 LR 对象的项目集合集合中。
- 输出项目集合集合：输出项目集合集合，方便调试和查看。
总结
以上两个代码片段展示了 LR 分析表构建算法的实现，包括生成产生式集合、构建项目集和最终构建 LR 分析表的步骤。通过理解这两个代码片段，您可以更好地理解 LR 分析表构建的原理和实现方法。
原文地址: http://www.cveoy.top/t/topic/fZVO 著作权归作者所有。请勿转载和采集!